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

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

                                        .7

5.3.3. Рассмотрим данные о расстояниях в таблице 5.13, которые точно соответствуют дереву с рисунка 5.15, при

 и .

а. Используйте UPGMA для восстановления дерева на основе этих данных. Применим ли этот метод?

б. Используйте метод присоединения соседей, чтобы восстановить дерево из этих данных. Применим ли этот метод?

5.3.4. Выполните алгоритм присоединения соседей на данных о расстояниях, используемых в примерах из раздела 5.2. Чтобы использовать MATLAB для этого в первом примере, введите массив расстояний D=[0 .45 .27 .53; 0 0 .40 .50; 0 0 0 .62; 0 0 0 0] и названия таксонов Taxa={'S1','S2','S3','S4'}, затем запрограммируйте функцию nj, реализующую построение дерева методом присоединения соседей, чтобы можно было её использовать nj(D,Taxa{:}).

а. Построит ли метод присоединения соседей на примере с 4 таксонами то же самое дерево, что и метод UPGMA?

б. Производит ли метод присоединения соседей на примере с 5 таксонами то же самое дерево, что и FM-алгоритм?

5.3.5. Используйте расстояние Джукса-Кантора и программу построения деревьев методом присоединения соседей из предыдущей задачи для смоделированных данных последовательности ранее сохранённых в seqdata.mat. Сравните полученные результаты с результатами, полученными другими методами в задачах 5.2.9-5.2.12 предыдущего раздела. Как повлияли на результаты молекулярные часы, работающие в симуляции?

а. Данные a1, a2, a3 и a4 смоделируйте в предположении с молекулярными часами

б. Данные b1, b2, b3, b4 и b5 смоделируйте без молекулярных часов.

5.3.6. Сгенерируйте с использованием 2-параметической модели Кимуры последовательности c1, c2, c3, c4, c5 и сохраните их в seqdata.mat.