Чтение онлайн

на главную - закладки

Жанры

Математические модели в естественнонаучном образовании. Том II
Шрифт:
empty-line/>

.37

Снова ищем ближайшую пару (теперь это

 и
) и соединяем их аналогичным образом. Объединяем все, кроме
 и
, в одну временную группу
 и вычисляем расстояния
 и
. Полученными значениями заполняем таблицу 5.7. Применение трехточечной формулы
к таблице 5.7 дает рисунок 5.11.

Таблица 5.7. Расстояния между группами; FM-алгоритм, шаг 2a

.683 .783

.37

 

Рисунок 5.11. FM-алгоритм; шаг 2.

Оставляем ребра инцидентные с

 и
 на рисунке 5.11, отбрасывая ребро, ведущие к временной группе
. Таким образом, теперь есть две объединенные группы,
 и
. Чтобы вычислить новую таблицу, содержащую эти две найденные группы, усредняем расстояния
 и
. Выше уже вычислили
, поэтому получаем таблицу 5.8.

Таблица 5.8. Расстояния между группами; FM-алгоритм, шаг 2b

1.005 .8425

.515

На этом этапе можем получить итоговое дерево по таблице путем окончательного применения 3-точечных формул, что дает рисунок 5.12.

Рисунок 5.12. FM-алгоритм; шаг 3.

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

Последним шагом является заполнение оставшихся длин

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

 

Рисунок 5.13. FM-алгоритм; завершение.

Обратите внимание, что одно ребро оказалось отрицательной длины. Поскольку этого не может быть, многие на практике предпочли бы просто переопределить длину в 0. Однако, если это произойдет, то должны будем по крайней мере проверить, что отрицательная длина была близка к 0, иначе придётся беспокоиться о качестве используемых данных.

Хотя на первый взгляд это может показаться странным, но как алгоритм Фитча-Марголиаша, так и UPGMA будут создавать точно такое же топологическое дерево при применении к набору данных. Причина этого заключается в следующем: при принятии решения о том, к каким таксонам или группам присоединиться на каждом шаге, оба метода учитывают точно такую же свернутую таблицу данных и оба выбирают пару, соответствующую наименьшей записи в таблице. Отличаться будут только метрические характеристики результирующих деревьев. Это немного подрывает надежду на то, что FM-алгоритм лучше, чем UPGMA. Хотя это может привести к лучшему метрическому дереву, но топологически оно никогда не отличается.

Фитч и Марголиаш в 1967 году фактически предложили свой алгоритм не как самоцель, а скорее, как эвристический метод получения дерева, которое, вероятно, будет иметь определенное свойство оптимальности, о чем еще поговорим в ходе решения связанных с этим задач. Рассматриваем его здесь, как и UPGMA, в качестве шага на пути к изложению алгоритма из следующего раздела. Знакомство с UPGMA и FM-алгоритмом поможет понять более сложный метод.

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

Хотя алгоритм Фитча-Марголиаша позволил получить неравные длины ветвей в деревьях, за это заплатили высокую цену – построенные деревья оказываются некорневыми. Однако, поскольку поиск корня часто желателен, возникает необходимость обойти этот недостаток.

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

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

5.2.1. Для дерева на рисунке 5.8, построенного методом UPGMA, вычислите таблицу расстояний между таксонами вдоль дерева. Как это соотносится с исходной таблицей данных расстояний?

5.2.2. Предположим, что четыре последовательности

,
,
 и
 ДНК разделены филогенетическими расстояниями, как показано в таблице 5.9. Создайте корневое дерево, показывающее отношения между
,
,
 и
 с помощью UPGMA.

Таблица 5.9. Данные о расстоянии для задач 5.2.2 и 5.2.5

1.2 .9 1.7

1.1 1.9

1.6

5.2.3. Выполните UPGMA для данных расстояния в таблице 5.4, которые были использованы в примере FM-алгоритма. Производит ли UPGMA топологически то же дерево, что и алгоритм FM? А метрически?

5.2.4. FM-алгоритм использует тот факт, что данные о расстоянии, относящиеся к трем терминальным таксонам, могут быть точно подогнаны по одному некорневому дереву, относящемуся к ним.

а. Выведите 3-точечных формулы, приведенные в разделе.

Поделиться:
Популярные книги

Удиви меня

Юнина Наталья
Любовные романы:
современные любовные романы
эро литература
5.00
рейтинг книги
Удиви меня

Live-rpg. эволюция-5

Кронос Александр
5. Эволюция. Live-RPG
Фантастика:
боевая фантастика
5.69
рейтинг книги
Live-rpg. эволюция-5

Матабар III

Клеванский Кирилл Сергеевич
3. Матабар
Фантастика:
фэнтези
5.00
рейтинг книги
Матабар III

Сиротка

Первухин Андрей Евгеньевич
1. Сиротка
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Сиротка

Черный Маг Императора 8

Герда Александр
8. Черный маг императора
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Черный Маг Императора 8

Последний Паладин. Том 5

Саваровский Роман
5. Путь Паладина
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Последний Паладин. Том 5

Аристократ из прошлого тысячелетия

Еслер Андрей
3. Соприкосновение миров
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Аристократ из прошлого тысячелетия

Изгой. Трилогия

Михайлов Дем Алексеевич
Изгой
Фантастика:
фэнтези
8.45
рейтинг книги
Изгой. Трилогия

Великий род

Сай Ярослав
3. Медорфенов
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Великий род

Лорд Системы 12

Токсик Саша
12. Лорд Системы
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Лорд Системы 12

Наемный корпус

Вайс Александр
5. Фронтир
Фантастика:
боевая фантастика
космическая фантастика
космоопера
5.00
рейтинг книги
Наемный корпус

Чехов. Книга 3

Гоблин (MeXXanik)
3. Адвокат Чехов
Фантастика:
альтернативная история
5.00
рейтинг книги
Чехов. Книга 3

Дурная жена неверного дракона

Ганова Алиса
Любовные романы:
любовно-фантастические романы
5.00
рейтинг книги
Дурная жена неверного дракона

Измена. Верну тебя, жена

Дали Мила
2. Измены
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Верну тебя, жена