Филогенетические деревья «…великое Дерево Жизни заполняет земную кору своими мертвыми и сломанными ветвями и покрывает поверхность вечно ветвящимися и прекрасными побегами» Ч. Дарвин ФББ, IV семестр, весна 2008, занятие подготовили А.Б.Рахманинова, С.А.Спирин

The time will come, I believe, though I shall not live to see it, when we shall have fairly true genealogical trees of each great kingdom of Nature. Charles Darwin

Задача построения филогенетического дерева Биологические задачи сравнение 3-х и более объектов (кто на кого более похож.... ) реконструкция эволюции (кто от кого, как и когда произошел…) Математическая задача – задача комбинаторной оптимизации, на основе «грязных» биологических данных нужно получить дерево, наилучшим образом согласованное с этими данными. Программистcкая задача – создание эффективной программы.

I. Как понимать дерево?

Описание структуры дерева (терминология) Узел (node) точка разделения предковой последовательности (вида, популяции) на две независимо эволюционирующие. Соответствует внутренней вершине графа, изображающего эволюцию. Лист реальный (современный) объект; внешняя вершина графа. OTU : Operational Taxonomic Unit. Ветвь (branch) связь между узлами или между узлом и листом; ребро графа. Корень (root) гипотетический общий предок. Кла́да группа организмов, которые являются потомками единственного общего предка и всех потомков этого предка.

Неукоренённое дерево следует понимать как множество возможных укоренений A B C D E C D B A E A C D B D A B C = Есть еще варианты? E E

Небинарное дерево следует понимать как множество возможных «разрешений» = Есть еще варианты? C D E F A B A E D B C F F D B A C E

Топология дерева ?

=

Расстояния по дереву между листьями D( MOUSE, CAEEL ) = = 129 Дерево с заданными длинами ветвей порождает метрическое пространство, элементами которого являются листья. Длины ветвей отражают эволюционные расстояния между листьями в данной модели дерева. Эти расстояния могут численно заметно отличаться от эволюционных расстояний между последовательностями, определенными по Джуксу – Кантору или Кимура.

Скобочная формула То же дерево, что и на предыдущем слайде, но укоренено в среднюю точку, и часть ветвей обрезана. Newick Standard: ((HUMAN:39, CAEEL:92):3.5, (VICFA:36, PROWI:47):49.5); «The reason for the name is that the second and final session of the committee met at Newick's restaurant in Dover, and we enjoyed the meal of lobsters.» Joseph Felsenstein,

Если на дереве можно найти точку такую, что расстояния от нее до всех листьев одинаковы, до дерево называется ультраметрическим. Ультраметрическое дерево можно однозначно укоренить (в эту самую точку). Ультраметрическое пространство особый случай метрического пространства, в котором метрика удовлетворяет усиленному неравенству треугольника: d(x, z) max( d(x, y), d(y, z) ). Содержательно ультраметрические деревья соответствуют случаю, когда длины ветвей суть время эволюции, и все последовательности современны (гипотеза молекулярных часов). Ультраметрические деревья А B C D E

Сколько существует разных деревьев для m листьев? Для укорененных деревьев: N = (2m - 3)! / [2 m-2 (m - 2)!], для m=10 N> Для неукорененных: N = (2m - 5)! / [2 m-3 (m - 3)!], для m=10 N> MEGA manual, Только одно из этих деревьев соответствует реальному ходу событий! Задача реконструкции - найти его. А еще определить длины ветвей хорошо бы.

II. Первое представление об основных алгоритмах ЭвристическиеПереборные Использующие матрицу попарных эволюционных расстояний UPGMA, NJFitch – Margoliash Символьно- ориентированные, т.е. использующие множественное выравнивание MP (maximum parsimony), ML (maximum likelihood)

Seq1 Seq2 Seq3 Seq4 Seq5 Seq1 Seq2 Seq3 Seq4 Seq5 5×5 Cкобочная формула, например: (((Seq1:5,Seq2:5):10, (Seq3:7, Seq4:7):8):2, Seq4:17); Вспоминаем практикумы... Эвристические алгоритмы, использующие матрицу расстояний: UPGMA, NJ Переборные, символьно-ориентированные алгоритмы: ML, MP программы визуализации

Unweighted Pair Group Method with Arithmetic Mean (невзвешенная попарная кластеризация) Кластерный метод, в котором расстояние между кластерами вычисляется как среднее арифметическое расстояний между их элементами. Шаг Находим самые близкие объекты. 2. Строим первый узел n1: d (M,n1) = d(N,n1) = d(M,N) / 2 3. Объединяем объекты и пересчитываем матрицу расстояний: d(MN-K) = [d(M-K) + d(N-K)] / 2 = 16 d(MN-L) = [d(M-L) + d(N-L)] / 2 = 8 Шаг 2. cм. шаг n1 UPGMA получаем единственное укорененное ультраметрическое дерево

За равное время во всех ветвях накапливается равное число мутаций. Если гипотеза молекулярных часов принимается, число различий между выровненными последовательностями можно считать примерно пропорциональным времени. Отклонения от ультраметричности можно считать случайными. Эволюция реконструируется в виде ультраметрического дерева. Если данные таковы, что гипотеза молекулярных часов не проходит, то реконструкция укорененного дерева намного менее надёжна, чем реконструкция неукоренённого Гипотеза «молекулярных часов» (E.Zuckerkandl, L.Pauling, 1962)

Недостатки UPGMA Если данные таковы, что гипотеза молекулярных часов не проходит, то реконструкция укорененного дерева намного менее надёжна, чем реконструкция неукоренённого «Реальное» деревоUPGMA An example from the graduate course compiled by Fred R. OpperdoesFred R. Opperdoes UPGMA

Neighbour joining, NJ (метод ближайших соседей) 1.Рисуем «звездное» дерево с ветвями условной длины, например, равными среднему расстоянию листа до всех остальных. 2.Рассмотрим все m(m-1)/2 пар листьев и соединим ту пару, в которой листья близки друг к другу, но далеки ото всех остальных. A и B такая пара последовательностей, для которых минимальна величина (A, B) – M(A) – M(B), где расстояние из матрицы, а M среднее расстояние от A или B до всех m–2 остальных последовательностей. 3.Объединим А и В в кластер АВ и строим первый узел, расстояние до которого зависит от среднего расстояния до других вершин : d (n1, A)=0.5*( (A, B) + M(A) – M(B)), d (n1, В)=0.5*( (A, B) + M(В) – M(А)), 4.Оставляем кластер АВ и удаляем узлы А и В дерево стало меньше на 1 узел. 5.Повторяем процедуру с п. 2 до тех пор, пока не останется 3 вершины получаем единственное неукорененное дерево A B n1

Neighbour joining, NJ Строит неукоренённое дерево Может работать с очень большим количеством данных Достаточно быстрый Дерево NJ аппроксимация минимальной эволюции (дерева с минимальной общей длиной ветвей) Хорошо зарекомендовал себя на практике: если матрица расстояний разумна, то будет построено дерево, недвусмысленное с точки зрения эксперта Используется при множественном выравнивании с помощью программы ClustalW (хотя именно для этого правильно было бы использовать UPGMA!) Могут появиться ветви с длиной

Основные критерии качества Максимальная экономия (maximum parsimony) Максимальное правдоподобие (maximum likelihood) Соответствие расстояний по дереву заданной матрице расстояний (Fitch – Margoliash или minimal evolution)... Внимание ! Лучшее дерево не обязательно «истинное» дерево Переборные алгоритмы: выбор лучшего дерева из всех возможных

Метод максимального правдоподобия Рассмотрим все варианты деревьев, первый, например, Seq1 Seq2 Seq3 Seq4 Seq j N Seq1 Seq2 Seq3 Seq4 Seq5 Какова вероятность L(j) того, что в рамках принятой эволюционной модели (например, матрицы замен) и при данной эволюционной истории (т.е. при данной топологии дерева) получится исходное выравнивание в колонке j ? Для полного выравнивания : L= L(1) x L(2)..... x L(N) Выбираем дерево, соответствующее максимальной вероятности или наиболее правдоподобное. Числа очень маленькие, поэтому L = max { Pr(D| t)}, t T где D – данные, T –множество всех возможных деревьев, модель эволюции задана и фиксирована

Метод максимального правдоподобия Строит неукоренённое дерево Наиболее теоретически обоснованный Порождает корректную с точки зрения экспертов топологию в трудных случаях Очень вычислительно тяжелый: очень медленный требует значительных компьютерных ресурсов если данных много, то полный перебор всех возможных деревьев все равно не реален Имеет смысл использовать для небольшого количества последовательностей ( ). Имеет смысл использовать для проверки сомнительной топологии в черновом варианте дерева (например, в дереве NJ), разумным образом уменьшив число последовательностей

1.Найдем все информативные сайты. Информативный сайт колонка выравнивания, символы в которой позволяют выбрать одну из возможных топологий, в данном примере сайт 3 информативный, а сайт 2 нет. 2.Для каждого из возможных деревьев определим минимальное число замен в каждом информативном сайте и сложим эти числа. 3.Выберем дерево с наименьшим числом замен; возможно, что окажется несколько деревьев с одинаковым числом замен. MP, метод максимальной экономии Лучшее дерево дерево, в котором различия в данных объясняются минимальным числом элементарных эволюционных событий. 4 листа 3 возможных топологии: Сайты:12345 Seq1 aagag Seq2 acggc Seq3 ataga Seq4 agaga G1 A3 G2A4 G1 G2 A3A4 G1 G2 A4A3 Cайт 3: GAAAAA A1A1 T3T3 C2C2G4G4 A1 C2C2 T3G4G4 A1A1 C2C2 G4T3 Cайт 2 : CTTCTA

MP, алгоритм максимальной экономии Строит одно или несколько неукорененных деревьев Рассматривает лишь часть колонок выравнивания Повторные замены не учитываются Трудно оценить длину ветвей Медленно работает при большом количестве данных При большом количестве данных полный перебор все равно не возможен, используются эвристические допущения Имеет смысл использовать при реконструкции сценария эволюции небольшого числа близкородственных последовательностей

Резюме UPGMANJ, алгоритм ближайших соседей MP, алгоритм максимальной бережливости ML, aлгоритм максимального правдоподобия Использует «гипотезу молекулярных часов»? + дерево по построению получается ультраметрическим ––– Использует матрицу попарных эволюционных расстояний? ++–– Тип алгоритмаЭвристический Переборный Время работыБыстрый Долго Очень долго Рекомендуемая область применения Много данных, есть соображения в пользу «молекулярных часов» Много данныхНебольшое число очень близких последова- тельностей Небольшое число любых последователь- ностей Программы пакета Phylip в EMBOSS fneighbor fdnapars, fprotpars fdnaml, fproml Выбирайте в соответствии с данными и задачей

III. Работа с деревьями 1.Укоренение дерева 2.Построение консенсусного дерева 3.Оценка достоверности топологии

D C A B HBA HBВ Добавить к выравниванию внешнюю группу (outgroup) Укоренить в среднюю точку, средняя точка – середина самого длинного пути по дереву между двумя листьями. Поместить корень исходя из биологического смысла: например, между двумя группами паралогов. Что это меняет ? I. Как укореняют дерево? A D B C O ABOCD BACD HBAHBА HBA HBB «Истинное» эволюционное дерево, наверно, все-таки, укорененное

Построение консенсусного дерева Strict consensus 50% majority-rule consensus 70% majority-rule consensus MEGA manual,

Как оценивают достоверность реконструкции? 1.Бутстреп-анализ (bootstrap) 2. Джекнайф? (jackknife)

Seq1 Seq2 Seq3 Seq4 Seq Seq1 Seq2 Seq3 Seq4 Seq Как оценивают достоверность реконструкции? Х jackknife Х bootstrap деревьев бутстрепзначения для всех ветвей jackknife-значения для всех ветвей

Наиболее популярные пакеты программ PHYLIP Paup*