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

Если бы было больше таксонов, то пришлось бы сделать больше шагов для завершения процесса UPGMA, но не было бы никаких принципиально новых действий. На каждом шаге объединяем два ближайших таксона или группы вместе, всегда размещая их на равных расстояниях от общего предка. Затем сворачиваем объединенные таксоны в группу, используя усреднение для вычисления расстояния от этой группы до таксонов и групп, которые еще предстоит объединить. Один момент, с которым следует быть особенно осторожным, заключается в том, что при вычислении расстояний между двумя группами нужно усреднить все расстояния от членов одной группы до членов другой – если одна группа имеет  членов, а другая имеет  членов, придется усреднить  расстояний. Каждый шаг алгоритма уменьшает размер таблицы расстояний на единицу, так что после достаточного количества шагов все таксоны объединяются в единое дерево.

Обратите внимание, что предположение о молекулярных часах неявно присутствовала в UPGMA. В примере, когда поместили  и  на концы ветвей одинаковой длины, предположили, что количество мутаций, которые каждый из них претерпел от своего общего предка, было одинаковым. Метод UPGMA всегда размещает все таксоны на одинаковом расстоянии от корня, так что количество мутаций от корня до любого таксона одинаково.

Вторым рассмотрим алгоритм Фитча-Марголиаша. Этот метод немного сложнее, чем UPGMA, но основан на том же подходе. Тем не менее, попытаемся отказаться от предположения UPGMA о молекулярных часах.

Прежде чем изложить алгоритм, сделаем несколько математических наблюдений. Во-первых, если попытаемся поместить 3 таксона на некорневое дерево, то будет только одна топология, которую необходимо учитывать. Кроме того, для 3 таксонов можем назначить желаемые длины ребер, чтобы точно соответствовать данным. Чтобы убедиться в этом, рассмотрим дерево на рисунке 5.9. Если есть некоторые данные о расстоянии ,  и , то можно составить систему уравнений , , .

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

Рисунок 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