Рисунок 5.15. 4-таксонное метрическое дерево с дальними соседями,
.
Предположим, что метрическое дерево на рисунке 5.15 описывает истинную филогению таксонов. Тогда идеальные данные дадут нам расстояния в таблице 5.10.
Таблица 5.10. Расстояния между таксонами на рисунке 5.15
3х x+y 2х + y
2x+y x+y
x+2y
Но,
если
намного больше
(на самом деле,
уже достаточно хорошо), то ближайшими таксонами по расстоянию являются
и
, которые не являются соседями. Таким образом, UPGMA или FM-алгоритм, выбирая ближайшие таксоны, выбирает для присоединения не соседей. Самый первый шаг соединения будет неправильным, и как только присоединимся к не соседям, то не восстановим истинное дерево. Суть проблемы заключается в том, что если молекулярные часы не работают, как в случае с деревом на рисунке 5.15, то ближайшие таксоны по расстоянию не обязательно должны быть соседями по дереву.
Вопросы для самопроверки:
– Если
намного меньше
, то откуда уверенность в том, что молекулярные часы не работают в эволюции, описанной деревом на рисунке 5.15?
Рисунок 5.16. Дерево с соседями
и
.
Таким образом, выбор ближайших таксонов для присоединения ввел заблуждение; нужен более сложный критерий выбора таксонов для присоединения. Чтобы изобрести его, представьте себе дерево, в котором таксоны
и
являются соседями, соединенными в вершине
, а
каким-то образом соединена с оставшимися таксонами
, как показано на рисунке 5.16.
Если данные точно соответствуют этому метрическому дереву, то для каждого
, дерево будет включать поддерево, подобное изображенному на рисунке 5.17.
Рисунок 5.17. Поддерево дерева на рисунке 5.16.
Но на этом рисунке видим, что
, так как в сумму слева входят только длины четырех ребер, отходящих от листьев дерева, а в сумму справа – все они и, кроме того, удвоенная длина центрального ребра. Это неравенство называется 4-точечным условием для соседей. Если
и
являются соседями, то неравенство верно для любых значений
из диапазона от 3 до
.
Условие 4-точек лежит в основе метода присоединения соседей, но предстоит еще много работы, чтобы перевести его в простую для применения форму. Для фиксированного
существует
возможных значения
удовлетворяющих условию
при
. Если просуммировать 4-точечные неравенства по этим
, то получим следующее неравенство, содержащее сумму расстояний
.
Чтобы упростить это неравенство, определим общее расстояние от таксона
до всех других таксонов как
, где расстояние
в сумме интерпретируется как 0, естественным образом. Затем, добавление
к каждой стороне исходного неравенства позволяет записать его в более простой форме следующим незамысловатым образом
.
Вычитание
из частей неравенство придает ему ещё более симметричную форму
.
Наконец, если рассмотреть эту последовательность действий для произвольных
и
, а не только для
и
, то можно ввести обозначение
.
Тогда, если
и
являются соседями, то имеет место
для всех
.
Это дает критерий, используемый в методе присоединения соседей: из данных расстояний
, заполоняется новая таблица значений
. Затем для соединения выбирается пара таксонов с наименьшим значением
. Приведенный выше вывод формулы для вычисления
показывает, что если
и
являются соседями, то соответствующее им значение
будет наименьшим из значений в
– й строке,
– м столбце таблицы. Более глубокий анализ, который провели Штудер и Кеплер в 1988 году, показывает, что если данные идеально подходят к дереву, то наименьшая запись во всей таблице значений
будет указывать на пару таксонов, которые являются соседями.
Поскольку полный алгоритм присоединения соседей довольно сложен, приведём лишь краткое описание этого метода:
Шаг 1: Учитывая данные о расстоянии для
таксонов, вычислите новую таблицу значений
. Выберите наименьшее значение, чтобы определить, к каким таксонам присоединиться. Это значение как правило оказывается отрицательным; в этом случае «наименьшее» означает отрицательное число с наибольшим значением по абсолютной величине.
Шаг 2: Если
и
должны быть соединены на новой вершине
, временно сверните все остальные таксоны в одну группу
и определите длины рёбер от
и
до
, используя 3-точечные формулы из предыдущего раздела для
,
и
, как в FM-алгоритме.
Шаг 3: Определите расстояния от каждого из таксонов
в
до
, применив 3-точечные формулы к данным расстояния для 3 таксонов
,
и
. Теперь включите
в таблицу данных о расстоянии и отбросьте
и
.
Шаг 4: Таблица расстояний теперь включает
таксонов. Если есть только 3 таксона, используйте 3-точечные формулы для завершения работы алгоритма. В противном случае вернитесь к шагу 1.