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

Начинаем с выбора ближайшей пары таксонов для присоединения, как это делали в 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.