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

Эти уравнения могут быть решены либо путем записи системы в виде матричного уравнения и нахождения обратной матрицы, либо путем подстановки формулы для одной переменной, полученной из одного уравнения, в другие. Любой способ гарантированно приведёт к следующему решению

,

,

.

Рисунок 5.9. Некорневое 3-таксонное дерево.

Будем называть эти формулы 3-точечными формулами для подгонки таксонов к дереву. К сожалению, с более чем 3 таксонами точная подгонка данных к дереву обычно невозможна. Однако алгоритм Фитча-Марголиаша (кратко называемый в таблицах как FM) использует случай 3 таксонов для обработки большего количества таксонов. Теперь объясним работу алгоритма на примере. Будем использовать данные о расстоянии, приведенные в таблице 5.4.

Таблица 5.4. Расстояния между таксонами

.31 1.01 .75 1.03

1.00 .69 .90

.61 .42

.37

Начинаем с выбора ближайшей пары таксонов для присоединения, как это делали в UPGMA. Глядя на таблицу расстояний,

 и

 являются первой парой, которая соединится. Чтобы соединить их, не помещая их на равное расстояние от общего предка, временно сводим задачу к случаю 3-таксонов, объединяя все остальные таксоны в группу. Таким образом, для имеющихся данных вводим группу

. Находим расстояние от каждого из

 и

 до группы, усредняя их расстояния до каждого члена группы. Таким образом, расстояние от

 до

 равно

, в то время как от

 до

 оно равно

. Это дает таблицу 5.5.

Таблица 5.5. Расстояния между группами; FM-алгоритм, шаг 1a

.31 .93

.863

Имея только три таксона в этой таблице, можем точно подогнать данные к дереву, используя 3-точечные формулы, чтобы получить рисунок 5.10. Ключевым моментом здесь является то, что 3-точечные формулы, в отличие от UPGMA, могут давать неравные расстояния таксонов от общего предка.

Рисунок 5.10. FM-алгоритм; шаг 1.

Теперь оставляем только ребра, заканчивающиеся в

 и

 на рисунке 5.10, и возвращаемся к исходным данным. Помните, что группа

 была нужна только временно, чтобы могли использовать 3-точечные формулы; пока не собирались объединять эти таксоны. Однако, поскольку объединили

 и

, объединяем их в группу для остальной части алгоритма, как сделали бы с UPGMA. Это формирует таблицу 5.6.

Таблица 5.6. Расстояния между группами; FM-алгоритм, шаг 1b

1.005 .72 .965

.61 .42

.37

Снова ищем ближайшую пару (теперь это

 и

) и соединяем их аналогичным образом. Объединяем все, кроме

 и

, в одну временную группу

 и вычисляем расстояния

 и

. Полученными значениями заполняем таблицу 5.7. Применение трехточечной формулы к таблице 5.7 дает рисунок 5.11.

Таблица 5.7. Расстояния между группами; FM-алгоритм, шаг 2a

.683 .783

.37

Рисунок 5.11. FM-алгоритм; шаг 2.

Оставляем ребра инцидентные с

 и

 на рисунке 5.11, отбрасывая ребро, ведущие к временной группе

. Таким образом, теперь есть две объединенные группы,

 и

. Чтобы вычислить новую таблицу, содержащую эти две найденные группы, усредняем расстояния

 и

. Выше уже вычислили

, поэтому получаем таблицу 5.8.

Таблица 5.8. Расстояния между группами; FM-алгоритм, шаг 2b

1.005 .8425

.515

На этом этапе можем получить итоговое дерево по таблице путем окончательного применения 3-точечных формул, что дает рисунок 5.12.

Рисунок 5.12. FM-алгоритм; шаг 3.

Теперь заменяем группы на этой последней диаграмме шаблонами ветвления, которые уже нашли ранее. Это дает рисунок 5.13.

Последним шагом является заполнение оставшихся длин

 и

, используя длины, показанные на рисунке 5.12. Так как

 и

 в среднем дают расстояние

 от соединяющей их вершины, а

 и

 находятся в среднем на

 от соединяющей их вершины, то

 и

 получаем для присвоения длин оставшимся ребрам.

Рисунок 5.13. FM-алгоритм; завершение.

Обратите внимание, что одно ребро оказалось отрицательной длины. Поскольку этого не может быть, многие на практике предпочли бы просто переопределить длину в 0. Однако, если это произойдет, то должны будем по крайней мере проверить, что отрицательная длина была близка к 0, иначе придётся беспокоиться о качестве используемых данных.

Хотя на первый взгляд это может показаться странным, но как алгоритм Фитча-Марголиаша, так и UPGMA будут создавать точно такое же топологическое дерево при применении к набору данных. Причина этого заключается в следующем: при принятии решения о том, к каким таксонам или группам присоединиться на каждом шаге, оба метода учитывают точно такую же свернутую таблицу данных и оба выбирают пару, соответствующую наименьшей записи в таблице. Отличаться будут только метрические характеристики результирующих деревьев. Это немного подрывает надежду на то, что FM-алгоритм лучше, чем UPGMA. Хотя это может привести к лучшему метрическому дереву, но топологически оно никогда не отличается.