Гомология, деревья, эволюция БиБи-4 (набор 2003) осень 2006. - презентация

1 Гомология, деревья, эволюция БиБи-4 (набор 2003) осень 2006

2 Начало Дивергенция похожих белков из общего предка (сходство => гомология) Дупликации Точечные мутации Поэтому можно измерять время до общего предка

3 Ошибка Цукеркандля

4 Теория Кимуры Большинство мутаций нейтральны Следствие: молекулярные часы Доля идентичных позиций в выравнивании за время T при скорости замен R Q = 1/4 + 3/4 (1 – 8R/3) T Мера расстояния D = 3/4 ln (3/(4Q-1)) 2RT Поправки: –На структуру популяций (аллельные различия) – Джукс и Кантор –На структуру матрицы замен – Кимура

5 Теоретические матрицы аминокислотных замен По расстоянию в таблице генетического кода По сходству физико-химических свойств аминокислот Работают не очень хорошо: –плохой поиск по банку –получаемые оптимальные выравнивания далеки от «настоящих» (структурных) –несообразные деревья

6 Эмпирические матрицы аминокислотных замен Интуитивная формула: w(a,b) ~ ln (N(a,b) / (N(a) N(b)) При случайном сопоставлении w(a,b) = 0

7 PAM = percent accepted mutations (Margaret Dayhoff) Сравниваем близкие последовательности –можно пренебречь повторными (и обратными) заменами Посчитаем количество выравненных пар N(a,b) Нормируем на расстояние 1 замена на 100 оснований Посчитаем p(a,b) = (вероятность перехода a в за время, когда происходит 1 замена в 100 позициях). Ясно, что Σ b p(a,b) = 1. Вектор частот f – это стационарный вектор матрицы p, т.е. f = fp Возводя p в степень, получаем серию матриц PAMх Перенормируем для использования при выравниваниях (чтобы можно было складывать): w(a,b) = ln (p(a,b) / f(b)) Упражнение: Это с точностью до нормировки наша «интуитивная» формула

8 BLOSUM = BLOcks Substitution Matrix (Steven and Jorja Henikoff) Недостатки РАМ: –возведение в степень – плохая процедура (чувствительна к ошибкам), –неясно, насколько адекватна эволюционная модель, позволяющая возводить в степень. Следствие: матрицы PAM не очень хорошо работают на больших расстояниях BLOSUM: Далекие выравнивания (для BLOSUMx исключаем все пары последовательностей, которые имеют более x% идентичных позиций) Учитываем только уверенно выравненные сегменты (без вставок/делеций) (BLOCKS)

9 Определения (деревья и пр.) Цикл: замкнутый путь без самопересечений (начало=конец, каждая вершина посещена один раз) Дерево: связный граф без циклов. Для простоты полагаем, что нет вершин степени 2 (хотя потом может быть одна такая - корень). Вершины степени 1 – терминальные (листы). Если на листьях стоят пометки, то это помеченное дерево. Мы рассматриваем только такие. Вершины степени 3 и более – внутренние (узлы) Если все внутренние вершины имеют степень 3, то дерево бинарное Ребра дерева будем называть ветвями

10 Лемма Пусть Т – помеченное бинарное дерево с n3 листьями. Тогда у него n–2 внутренних вершин, n–3 внутренних ветвей и 2n–3 ветвей. Существуют g(n)=135…(2n–5) разных помеченных деревьев с n вершинами.

11 Доказательство При n=3 существует единственное дерево c 1 узлом и 0 внутренними ветвями. По индукции: добавление листа добавляет один узел, одну внутреннюю ветвь и одну внешнюю ветвь (то есть всего две ветви). При (n–1) листах имеем (2n–5) ветвей. Новую вершину можно присоединить к любой ветви, стало быть g(n)=g(n–1)(2n–5).

12 Метрика Определение. Пусть i, j – вершины. D(i,j) – метрика (расстояние), если D(i,j)=D(j,i)0 для любых i, j D(i,j)D(i,k)+D(k,j) для любых i, j, k Для простоты D(i,j)=0 i=j Лемма: в дереве между каждыми двумя вершинами есть только один путь Определение: аддитивная метрика D(i,j) = сумма длин ветвей пути между i и j.

13 Условие четырех точек Определение. Метрика D удовлетворяет условию четырех точек, если для любой четверки листьев i, j, k, l из трех сумм D(i,j) + D(k,l), D(i,k) + D(j,l), D(i,l) + D(j,k) две равны и больше третьей. Например, пусть D(i,j)+D(k,l) D(i,k)+D(j,l) = D(i,l)+D(j,k) Упражнение: нарисовать дерево c вершинами i,j,k,l. Теорема. D – аддитивная метрика некоторого дерева D удовлетворяет условию четырех точек. Замечание. (Неаддитивных) метрик намного больше, чем деревьев. Упражнение. Почему?

14 Ультраметрика Определение. D – ультраметрика, если для любой тройки i, j, k из трех расстояний D(i,j), D(i,k), D(j,k) два равны и не меньше третьего. Например, пусть D(i,j) D(i,k) = D(j,k) Упражнение: нарисовать дерево с вершинами i,j,k, найти в нем длины ветвей. Теорема. Ультраметрика удовлетворяет условию четырех точек. Упражнение: Найти положение корня в нарисованном дереве. Убедиться, что не получится нарисовать корень при D(i,j) D(i,k) = D(j,k). Теорема. Ультраметрика определяет корневое дерево с постоянной скоростью эволюции.

15 Набросок доказательства Обозначим D* = max {D(k,l) | k,l}. Пусть D(i, j) = D*, то есть (i,j) = argmax D. Все вершины делятся на два cвязных непересекающихся множества: I = {k | D(i,k)

16 Упражнение. Задает ли матрица расстояний метрику? Ультраметрику? Удовлетворяет ли она условию четырех точек? ABCDE A B C0813 D01414 E0

17 Кластерные деревья Вход: L={1,…, n} – множество листьев. D – метрика на L. Алгоритм: while |L|>2 Find closest a,b, so that D(a,b) = min D. Cluster c={a,b}: L (L – {a,b}) U c. Calculate D(c,d) для всех d из L.

18 Пересчет расстояний UPGMA (невзвешенные средние) D(c,d) = Σ iεc,jεd D(i,j) / (|c||d|) Ближнего соседа D(c,d) = min {D(i,j) : iεc, jεd} Дальнего соседа D(c,d) = max {D(i,j) : iεc, jεd} Длины ветвей (r – длина ветви или расстояние по дереву): –если c={i,j}, то r(c,i) = r(c,j) = D(i,j)/2 –если c=aUb, то r(c,a) = D(a,b)/2 – r(a,i), где iεa Лемма (упражнение). Не важно, какой лист iεa выбрать.

19 Neighbor-Joining (Saitou-Nei, 1987) Вначале имеем звезду: вершину о (корень), соединенный со всеми листьями. Пусть A(i) = суммарное расстояние от i до всех остальных вершин = Σ ki D(i,k). Найдем пару листьев (i,j), такую, что D(i,j) – (A(i)+A(j)) / (|L|–2) минимально («самое отрицательное») и поставим ей в соответствие узел c. Определим длины ветвей: r(i,c) = ( D(i,j) + (A(i)–A(j)) / (|L|–2) ) / 2 r(j,c) = ( D(i,j) – (A(i)–A(j)) / (|L|–2) ) / 2 а также расстояния от c до остальных листьев k D(c,k) = (D(i,k) + D(j,k) – D(i,j)) / 2 Теорема. Если D удовлетворяет условию четырех точек, то мы построим соответствующее дерево.

20 Метод наибольшей экономии

21 Примеры (рассматривается происходящее в одной позиции выравнвиания) ((АТ)Т)А ([AT]T)A [T]A [TA] Две замены Но А во всех внутренних узлах – тоже две замены ((CT)((GT)A)A ([CT][GTA])A) [T]A [TA] Четыре замены Но A во всех внутренних узлах – тоже четыре замены

22 Проблемы Можно эффективно подсчитать минимальное число замен, но нельзя построить все минимальные сценарии для данного дерева Нельзя построить (кроме как перебором) дерево наибольшей экономии Неявно полагаем, что не бывает повторных, параллельных, обратных замен. Это не работает для больших расстояний

23 Метод наибольшего правдоподобия Вероятность тривиального дерева (эволюции из a в b) P(a b) = f(a)p(a,b) Аналогично, P(a b c) = f(a)p(a,b)p(b,c) Аналогично же, P(b a c) = f(a)p(a,b)p(a,c) Буквы могут быть и одинаковые: P(a a) = f(a)p(a,a) Упражнение. P((b a а) a (b b c))

24 … на самом деле Надо учитывать длины веток. Поэтому теперь матрица замен зависит от времени: p(a,b,t) = exp (qt), где t – время, q – матрица скоростей замен.

25 Таким образом, для любого дерева с помеченными узлами можно вычислить его правдопобие. Берем самое правдоподобное дерево и объявляем его правильным. Отдельные этапы (пометку узлов, определение длин ветвей) можно сделать вычислительно эффективными; топологии надо перебирать, используя эмпирические приемы.

26 Качество деревьев Притяжение длинных ветвей Бутстреп (выборка с возвращением) Консенсусное дерево (только ветки с большими бутстрепами)

27 Ортологи и паралоги (Фитч, 1970) duplication Дупликация Видообразование Ортологичные гены: –результат видообразования –сохранили клеточную роль Паралогичные гены : –результат дупликации генов –сохранили общую биохими- ческую функцию Пример: gluconate and idonate kinases Геном АГеном В A1 А2В1 B2

28 глобины

29 Упражнение: кто кому ортологи и паралоги A1A1A2A2B1B1B2B2 AAB ABB C AABBC AB A1A1A2A2B1B1B2B2 Кластер ортологов Дерево ортологов

30 Как отличать Промежуточные (далекие) геномы Вообще, (под)дерево ортологичных генов должно совпадать с деревом видов Дупликации Слишком длинные ветви ABХ ABB AB

31 Search for orthologs (fast and dirty) … but the best way is to construct a phylogeentic tree (time-consuming) bidirectional best hit (BBH)

32 COGs (старые)

33 Clusters of Orthologous Genes

34 Построение COGов 1. Perform the all-against-all protein sequence comparison. 2. Detect and collapse obvious paralogs, i.e., proteins from the same genome that are more similar to each other than to any proteins from other species. 3. Detect triangles of mutually consistent, genome-specific best hits (BeTs), taking into account the paralogous groups detected at step Merge triangles with a common side to form COGs. 5. Perform a case-by-case analysis of each COG. This analysis serves to eliminate false-positives and to identify groups that contain multidomain proteins by examining the pictorial representation of the BLAST search outputs. The sequences of detected multidomain proteins are split into single-domain segments, and steps 1 4 are repeated with the resulting shorter sequences, which assigns individual domains to COGs in accordance with their distinct evolutionary affinities. 6. Examine large COGs that include multiple members from all or several of the genomes using phylogenetic trees, cluster analysis, and visual inspection of alignments. As a result, some of these groups are split into two or more smaller ones that are included in the final set of COGs.

35 COG: monoamine oxidase Deinococcus radiodurans (DRA0274) Mycobacterium tuberculosis (Rv3170) Bacillus subtilis (BS_yobN) Synechocystis (slr0782) Pseudomonas aeruginosa (PA0421) Mesorhizobium loti (mll3668) Caulobacter crescentus (CC2793 and CC1091) In humans, monoamine oxidase is an enzyme of the mitochondrial outer membrane that seems to be involved in the metabolism of antibiotics and neurologically active agents and is a target for one class of antidepressant drugs.

36 A universal COG: some duplications, good resolution of taxonomy

37 A conserved COG (BirA): single representative, not in all species

38 A garden variety COG (aroG). Enzymes: some duplications, not ubiquitous

39 A huge COG (LacI). Regulators and transporters: many duplications

40 Sugar kinases: impossible to predict specificity by similarity

41 От генов к геномам Согласование деревьев –Дупликации и потери –Горизонтальный перенос –Ненадежные выравания, малое количество информативных позиций => ненадежность глубоких реконструкций Построение деревьев по конкатенатам –Неравномерность скоростей эволюции по позициям (so what?) –Отсутствующие (в каких-то геномах) гены (рассматриваются как делеции специального вида) Эволюция геномов –Генный состав –Полногеномные дупликации –Инверсии и т.п. –Повторы Эволюция геномов и таксономия LUCA (last universal common ancestor) потом