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

. Затем для соединения выбирается пара таксонов с наименьшим значением

. Приведенный выше вывод формулы для вычисления

 показывает, что если

 и

 являются соседями, то соответствующее им значение

 будет наименьшим из значений в

-й строке,

-м столбце таблицы. Более глубокий анализ, который провели Штудер и Кеплер в 1988 году, показывает, что если данные идеально подходят к дереву, то наименьшая запись во всей таблице значений

 будет указывать на пару таксонов, которые являются соседями.

Поскольку полный алгоритм присоединения соседей довольно сложен, приведём лишь краткое описание этого метода:

Шаг 1: Учитывая данные о расстоянии для

 таксонов, вычислите новую таблицу значений

. Выберите наименьшее значение, чтобы определить, к каким таксонам присоединиться. Это значение как правило оказывается отрицательным; в этом случае «наименьшее» означает отрицательное число с наибольшим значением по абсолютной величине.

Шаг 2: Если

 и

 должны быть соединены на новой вершине

, временно сверните все остальные таксоны в одну группу

 и определите длины рёбер от

 и

 до

, используя 3-точечные формулы из предыдущего раздела для

,

  и

, как в FM-алгоритме.

Шаг 3: Определите расстояния от каждого из таксонов

 в

 до

, применив 3-точечные формулы к данным расстояния для 3 таксонов

,

 и

. Теперь включите

 в таблицу данных о расстоянии и отбросьте

 и

.

Шаг 4: Таблица расстояний теперь включает

 таксонов. Если есть только 3 таксона, используйте 3-точечные формулы для завершения работы алгоритма. В противном случае вернитесь к шагу 1.

Как уже можете видеть, метод присоединения соседей утомительно реализовывать вручную. Несмотря на то, что шаги относительно просты, легко потеряться в процессе с таким количеством арифметики. В упражнениях найдете пример частично отработанных данных, с которыми нужно завершить алгоритм, для лучшего понимания шагов. После этого предлагается написать и использовать компьютерную программу, чтобы избежать ошибок.

Точность различных методов построения деревьев – трех, описанных до выше в этой главе, и многих других – проверялась в первую очередь путем моделирования мутаций ДНК в соответствии с определенными филогенетическими деревьями, а затем применяя разные методы, сравнивали, как часто они восстанавливают правильное дерево. Некоторые исследования также были проведены с реальными таксонами, связанными известным филогенетическим деревом; деревья, построенные из последовательностей ДНК с использованием различных методов, можно было затем сравнить с заведомо правильным деревом. Эти тесты привели исследователей к большей уверенности в результативности описанного метода присоединения соседей, чем других методах, которые обсуждали ранее. Хотя UPGMA или FM-алгоритм могут быть надежными при некоторых обстоятельствах, метод присоединения соседей хорошо работает с более широким диапазоном данных. Например, если молекулярные часы не существуют, то лучше использовать метод присоединения соседей, поскольку он не предполагает неявных допущений о молекулярных часах. Поскольку в настоящее время накоплено много данных, указывающих на то, что гипотеза молекулярных часов часто нарушается, таким образом метод присоединения соседей становится предпочтительным дистанционным методом для построения дерева.

Задачи для самостоятельного решения:

5.3.1. Перед проработкой примера, в целях более глубокого понимания метода присоединения соседей, полезно вывести формулы используемые на шаге 2 и 3 изложенного алгоритма. Предположим, что решили объединить

 и

 на шаге 1.

а. Покажите, что на шаге 2 расстояния от

 и

 до внутренней вершины

 могут быть найдены по следующим формулам:

,

.

Затем покажите, что вторая из этих формул может быть заменена на

.