Филогенетические деревья. 1) Алфавит без пробелов5 2) Кол-во выравниваний10 3) Глобальное выравнивание10 4) Локальное выравнивание7 5) Афинные гэпы8 6) - презентация

1 Филогенетические деревья

2 1) Алфавит без пробелов5 2) Кол-во выравниваний10 3) Глобальное выравнивание10 4) Локальное выравнивание7 5) Афинные гэпы8 6) Нечестная монетка10 7) Backward-Forward для выравниваний25 8) Коэффициент Jukes-Kantor10 9) Усиленное неравенство треугольника5 10) Кол-во деревьев10 60 :)

3 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

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

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

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

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

8 =

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

10 Скобочная формула То же дерево, что и на предыдущем слайде, но укоренено в среднюю точку, и часть ветвей обрезана. 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,

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

12 Сколько существует разных деревьев для m листьев? Только одно из этих деревьев соответствует реальному ходу событий! Задача реконструкции - найти его. А еще определить длины ветвей хорошо бы.

13 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 получаем единственное укорененное ультраметрическое дерево

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

15 Недостатки UPGMA Если данные таковы, что гипотеза молекулярных часов не проходит, то реконструкция укорененного дерева намного менее надёжна, чем реконструкция неукоренённого «Реальное» деревоUPGMA

16 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

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

18 Метод максимального правдоподобия Рассмотрим все варианты деревьев, первый, например, 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 –множество всех возможных деревьев, модель эволюции задана и фиксирована

19 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