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

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

Шаг 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

.83 .28 .41

.72 .97

.48

5.3.2. Рассмотрим данные о расстояниях, приведенные в таблице 5.11. Используйте алгоритм присоединения соседей для построения дерева следующим образом:

а. Вычислите

,

,

 и

, а затем заполните таблицу значений

 для таксонов

,

,

 и

. Для начала посчитаем

 и

, получим

.

б. Если правильно справились с частью (а), то должно получиться несколько пар, имеющих одинаковое наименьшее значение

. Одним из таких наименьших значений является

, поэтому попробуем сначала присоединиться к

 и

.

Для новой вершины

, с соединяются

 и

 , вычислите

 и

 по формулам из части (a) предыдущей задачи.

в. Вычислите

 и

 по формулам из части (б) предыдущей задачи.

Поместите свои ответы в новую версию таблицы расстояний 5.12.

г. Поскольку осталось только 3 таксона, используйте 3-точечные формулы, чтобы поместить

,

 и

 в дерево.

д. Нарисуйте последнее дерево, присоединив

 и

 к

 с расстояниями, найденными в части (б).

Таблица 5.12. Групповые расстояния для задачи 5.3.2

? ?

.72

Таблица 5.13. Расстояния таксонов для задачи 5.3.3

.3 .4 .5

.5 .4