Математические модели в естественнонаучном образовании. Том II

На практике метод UPGMA и FM-алгоритм редко используются для построения дерева, потому что существует дистанционный метод, который как правило работает лучше, чем любой из них. Тем не менее идеи, лежащие в их основе, помогают понять популярный алгоритм присоединения соседей, на котором сосредоточимся в дальнейшем. Чтобы понять, почему UPGMA или FM-алгоритм могут быть ошибочными, рассмотрим метрическое дерево с 4 таксонами на рисунке 5.15. Здесь  и  представляют определенные длины, причем  намного меньше, чем . Говорим, что вершины  и  в этом дереве являются соседями, потому что ребра, ведущие от них, соединяются в общей вершине. Точно так же  и  являются соседями, но  и  – нет.

Рисунок 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 таксонов ,  и . Теперь включите  в таблицу данных о расстоянии и отбросьте  и .