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

Таблица 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. Хотя это может привести к лучшему метрическому дереву, но топологически оно никогда не отличается.