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

а. Нарисуйте дерево UPGMA для 4 таксонов, пометив каждое его ребро длиной.

б. По длинам ребер вычислите расстояния между таксонами при обходе вдоль дерева. Близки ли они к исходным расстояниям?

5.2.10. Повторите решение предыдущей задачи, но используя алгоритм FM вместо UPGMA. Является ли дерево, которое получится в результате, «лучше», чем то, которое получалось раньше? Объясните почему.

5.2.11. Смоделируйте данные b1, b2, b3, b4 и b5 в соответствии с моделью Джукса-Кантора, но без молекулярных часов. Сохраните их в файле seqdata.mat. Исследуйте возможность применения UPGMA с расстоянием Джукса-Кантора для построения дерева для последовательностей b1, b2, b3, b4 и b5 в файле данных seqdata.mat. Полезные команды MATLAB см. в задаче 5.2.9.

а. Нарисуйте дерево UPGMA для 5 таксонов, пометив каждое ребро его длиной.

б. По длинам ребер вычислите расстояния между таксонами вдоль дерева. Близки ли они к исходным данным?

5.2.12. Повторите решение предыдущей задачи, но используя алгоритм FM вместо UPGMA. Является ли дерево, которое получилось в результате, «лучше», чем то, которое было получено ранее? Объясните почему.

5.2.13. Построение дерева с помощью UPGMA предполагает молекулярные часы. Предположим, что некорневое метрическое дерево на рисунке 5.14 правильно описывает эволюцию таксонов A, B, C и D.

Рисунок 5.14. Дерево для задачи 5.2.13.

а. Объясните, почему, независимо от местоположения корня, молекулярные часы не могли здесь работать.

б. Задайте массив расстояний между каждой парой из четырех таксонов. Выполните UPGMA для этих данных.

в. UPGMA не реконструировала правильное дерево. Что получилось в результате? Что такого было в этом метрическом дереве, что ввело алгоритм в заблуждение?

г. Объясните, почему алгоритм FM также не построит правильное дерево.

5.3. Построение дерева дистанционным методом присоединения соседей

На практике метод UPGMA и FM-алгоритм редко используются для построения дерева, потому что существует дистанционный метод, который как правило работает лучше, чем любой из них. Тем не менее идеи, лежащие в их основе, помогают понять популярный алгоритм присоединения соседей, на котором сосредоточимся в дальнейшем. Чтобы понять, почему UPGMA или FM-алгоритм могут быть ошибочными, рассмотрим метрическое дерево с 4 таксонами на рисунке 5.15. Здесь

 и

 представляют определенные длины, причем

 намного меньше, чем

. Говорим, что вершины

 и

 в этом дереве являются соседями, потому что ребра, ведущие от них, соединяются в общей вершине. Точно так же

 и

 являются соседями, но

 и

 – нет.

Рисунок 5.15. 4-таксонное метрическое дерево с дальними соседями,

.

Предположим, что метрическое дерево на рисунке 5.15 описывает истинную филогению таксонов. Тогда идеальные данные дадут нам расстояния в таблице 5.10.

Таблица 5.10. Расстояния между таксонами на рисунке 5.15

3х x+y 2х + y

2x+y x+y

x+2y

Но, если

 намного больше

 (на самом деле,

 уже достаточно хорошо), то ближайшими таксонами по расстоянию являются

 и

, которые не являются соседями. Таким образом, UPGMA или FM-алгоритм, выбирая ближайшие таксоны, выбирает для присоединения не соседей. Самый первый шаг соединения будет неправильным, и как только присоединимся к не соседям, то не восстановим истинное дерево. Суть проблемы заключается в том, что если молекулярные часы не работают, как в случае с деревом на рисунке 5.15, то ближайшие таксоны по расстоянию не обязательно должны быть соседями по дереву.

Вопросы для самопроверки:

– Если

 намного меньше

, то откуда уверенность в том, что молекулярные часы не работают в эволюции, описанной деревом на рисунке 5.15?

Рисунок 5.16. Дерево с соседями

 и

.

Таким образом, выбор ближайших таксонов для присоединения ввел заблуждение; нужен более сложный критерий выбора таксонов для присоединения. Чтобы изобрести его, представьте себе дерево, в котором таксоны

 и

 являются соседями, соединенными в вершине

, а

 каким-то образом соединена с оставшимися таксонами

, как показано на рисунке 5.16.

Если данные точно соответствуют этому метрическому дереву, то для каждого

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

Рисунок 5.17. Поддерево дерева на рисунке 5.16.

Но на этом рисунке видим, что

, так как в сумму слева входят только длины четырех ребер, отходящих от листьев дерева, а в сумму справа – все они и, кроме того, удвоенная длина центрального ребра. Это неравенство называется 4-точечным условием для соседей. Если

 и

 являются соседями, то неравенство верно для любых значений

 из диапазона от 3 до

.

Условие 4-точек лежит в основе метода присоединения соседей, но предстоит еще много работы, чтобы перевести его в простую для применения форму. Для фиксированного

 существует

 возможных значения

 удовлетворяющих условию

 при

. Если просуммировать 4-точечные неравенства по этим

, то получим следующее неравенство, содержащее сумму расстояний

.

Чтобы упростить это неравенство, определим общее расстояние от таксона

 до всех других таксонов как

, где расстояние

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

 к каждой стороне исходного неравенства позволяет записать его в более простой форме следующим незамысловатым образом

.

Вычитание

 из частей неравенство придает ему ещё более симметричную форму

.

Наконец, если рассмотреть эту последовательность действий для произвольных

 и

, а не только для

 и

, то можно ввести обозначение

.

Тогда, если

 и

 являются соседями, то имеет место

 для всех

.

Это дает критерий, используемый в методе присоединения соседей: из данных расстояний

, заполоняется новая таблица значений

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

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

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

 и

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

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

– й строке,

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

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