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

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