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

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

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

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

Шаг 2: Если  и  должны быть соединены на новой вершине , временно сверните все остальные таксоны в одну группу  и определите длины рёбер от  и  до , используя 3-точечные формулы из предыдущего раздела для ,   и , как в FM-алгоритме.

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

 до , применив 3-точечные формулы к данным расстояния для 3 таксонов ,  и . Теперь включите  в таблицу данных о расстоянии и отбросьте  и .

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

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

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

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

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

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

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

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

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

.

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

 до , для , могут быть вычислены с помощью формулы .

Таблица 5.11.  Расстояния между таксонами для задачи 5.3.2