Построение филогенетических деревьев биоинформатика

Биоинформатика. Дендрограммы. Молекулярная филогения. (Тема 6)

Граф — это простая диаграмма (абстрактная структура), применяемая
для представления отношений между элементами например чисел,
объектов или мест. Сами элементы изображают в виде узлов, а
отношения между ними показывают в виде связей, или ребер
(соединительных линий).
В теории графов деревом называют граф особого вида. Граф
представляет собой структуру, состоящую из узлов (абстрактных
точек) и соединяющих их ребер (линий между точками). Путь от
одного узла к другому складывается из множества последовательных
ребер, первое из которых выходит из начальной точки (узла), а
последнее входит в конечную точку (узел). Граф называют связным,
если в нем между любыми двумя узлами можно провести по крайней
мере один путь.
Деревом называют связный ациклический граф, между каждыми
двумя точками которого имеется строго один путь.

4. Терминология

Узел (node) — точка разделения предковой последовательности
(вида, популяции) на две независимо эволюционирующие.
Соответствует внутренней вершине графа, изображающего
эволюцию.
Лист (leaf, OTU – оперативная таксономическая единица) —
реальный (современный) объект; внешняя вершина графа.
Ветвь (branch) — связь между узлами или между узлом и
листом; ребро графа.
Корень (root) — общий предок.
Клада (clade) — группа двух или
более таксонов или последовательностей ДНК, которая включает как
своего общего предка, так и всех его
потомков.

5. Зачем нужны деревья?

Биологические задачи:
сравнение 3-х и более объектов
(кто на кого более похож . )
реконструкция эволюции
(кто от кого, как и когда произошел…)

6. Филогенетическое дерево (древо)

Филогения — раздел биологии, изучающий
родственные взаимоотношения разных
групп живых организмов.
Молекулярная филогения Древо сходства и филогенетическое древо –
не одно и то же.

7.

8. Какие бывают деревья?

Бинарное (разрешённое)
Небинарное (неразрешённое)
(в один момент времени может
произойти только одно событие )
(может ли в один момент времени
произойти два события? )
Время

9. Какие бывают деревья?

Укорененное дерево (rooted tree)
отражает направление эволюции
Неукорененное (бескорневое) дерево
(unrooted tree) показывает
только связи между узлами
Время
Если число листьев равно n, существует (2n-3)!!
разных бинарных укоренных деревьев.
По определению, (2n-3)!! = 1·3 ·. ·(2n-3)
Существует (2n-5)!! разных бескорневых
деревьев с n листьями

10.

11.

12. 4 OTUs  3 неукорененных филогенетических деревьев

13.

14.

15.

16.

Количество возможных деревьев
Количество Количество
OTU
укорененных
2
3
4
5
6
7
8
9
10
11
12
1
3
15
105
954
10,395
135,135
2,027,025
34,459,425
654,729,075
13,749,310,575
Количество
неукорененных
1
1
3
15
105
954
10,395
135,135
2,027,025
34,459,425
654,729,075

17. Рутинная процедура, или как строят деревья?

Составление выборки последовательностей
Множественное выравнивание
Построение дерева
фрагмент записи в виде скобочной формулы:
(((((con101:38.51018,(f53969:28.26973,((f67220:8.39851,
max4:27.50591):4.92893,con92:30.19677):13.62315):9.53075):25.83145,
Визуализация и редактура дерева

18. Рутинная процедура, или как строят деревья?

Составление выборки последовательностей
Множественное выравнивание (или всё-таки попарное)
Построение дерева
фрагмент записи в виде скобочной формулы:
(((((con101:38.51018,(f53969:28.26973,((f67220:8.39851,
max4:27.50591):4.92893,con92:30.19677):13.62315):9.53075):25.83145,
Визуализация и редактура дерева

19.

Множественное выравнивание
GCGGCTCA
GCGGCCCA
GCGTTCCA
GCGTCCCA
GCGGCGCA
***
**
Matches
TCAGGTAGTT
TCAGGTAGTT
TC—CTGGTT
TCAGCTAGTT
TTAGCTAGTT
*
* ***
GGTG-G
GGTG-G
GGTGTG
GTTG-G
GGTG-A
* **
Spinach
Rice
Mosquito
Monkey
Human

20.

Multiple Alignment
GCGGCTCA
GCGGCCCA
GCGTTCCA
GCGTCCCA
GCGGCGCA
***
**
TCAGGTAGTT
TCAGGTAGTT
TC—CTGGTT
TCAGCTAGTT
TTAGCTAGTT
*
* ***
Matches
Mismatches
GGTG-G
GGTG-G
GGTGTG
GTTG-G
GGTG-A
* **
Spinach
Rice
Mosquito
Monkey
Human

21.

Multiple Alignment
GCGGCTCA
GCGGCCCA
GCGTTCCA
GCGTCCCA
GCGGCGCA
***
**
TCAGGTAGTT
TCAGGTAGTT
TC—CTGGTT
TCAGCTAGTT
TTAGCTAGTT
*
* ***
Matches
Mismatches
Gaps
GGTG-G
GGTG-G
GGTGTG
GTTG-G
GGTG-A
* **
Spinach
Rice
Mosquito
Monkey
Human

22.

23.

Distance Matrix*
Spinach
Rice
Mosquito
Spinach
0.0
Rice
9
0.0
Mosquito Monkey Human
106
91
86
118
122
122
0.0
55
51
0.0
3
Monkey
Human
* Units: количество замен нуклеотидов на 1000
0.0

24.

25. Как выбирать последовательности для дерева?

Кроме случаев очень близких последовательностей,
проще работать с белками (а не с ДНК)
Придерживайтесь небольшой выборки ( < 50
последовательностей)
Избегайте:
◦ фрагментов;
◦ Ксенологов (горизонтальный перенос генов);
◦ рекомбинантных последовательностей;
◦ многодоменных белков и повторов
Используйте outgroup (последовательность,
ответвившаяся от общего предка заведомо (но
минимально!) раньше разделения интересующих группклад)

26. Самое главное – хорошее выравнивание!

Максимальный
вклад в финальное дерево:
нельзя построить хорошее дерево по
плохому выравниванию
Блоки, содержащие много гэпов, плохо
выровненные N- и C- концы можно просто
вырезать.

27. Основные алгоритмы построения филогенетических деревьев

Методы, основанные на
оценке
расстояний (матричные
методы):
UPGMA (кластеризация)
Neighbor-joining
Наибольшего
правдоподобия,
Maximal likelihood, ML
Используется модель эволюции
и строится дерево, которое наиболее
правдоподобно при данной модели
Максимальной экономии (бережливости),
maximal parsimony, MP
Выбирается дерево с минимальным количеством
мутаций, необходимых для объяснения данных

28. Пример матрицы расстояний

1
0.00
2
10.53
0.00
3
9.77
9.02
0.00
4
5
12.78 12.03
12.03
9.77
9.77
9.02
0.00
2.26
0.00
6
16.54
15.79
16.54
17.29
15.79
0.00
7
13.53
9.02
12.03
10.53
8.27
10.53
0.00
Расстояние (уровень дивергенции) между
соответствующими последовательностями из
геномов мыши и свиньи
8
25.00
27.27
24.24
25.76
25.76
29.55
25.00
0.00
HUMAN
HORSE
RABIT
MOUSE
RAT 5
BOVIN
PIG 7
CHICK
1
2
3
4
6
8

29.

Как понимать расстояние между объектами?
• Как время, в течение которого они эволюционировали
• Как число «эволюционных событий» (мутаций)
В первом случае объекты образуют
ультраметрическое пространство
(если все объекты наблюдаются в одно время, что, как правило, верно)
Но время непосредственно измерить невозможно

30.

31. Гипотеза «молекулярных часов» (E.Zuckerkandl, L.Pauling, 1962)

Если гипотеза молекулярных часов
принимается, число различий между
выровненными
последовательностями
можно
считать
примерно
пропорциональным
времени.
Отклонения
от
ультраметричности можно считать
случайными.
Эволюция
реконструируется
в
виде
ультраметрического дерева.
Укоренённое
дерево называется
ультраметрическим,
если
расстояние от корня до любого из
листьев одинаково.
За равное время во всех ветвях эволюции
данного гена\белка накапливается равное
число мутаций

32. UPGMA Unweighted Pair Group Method with Arithmetic Mean

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

33.

Spinach
Rice
Mosquito
Monkey
Human
Spinach
0.0
Rice
9
0.0
Mosquito Monkey Human
106
91
86
118
122
122
0.0
55
51
0.0
3
0.0

34.

Дистанция между человеком и обезьяной минимальна. Эти
группы объединяются в Monkey-Human, а все остальные
дистанции пересчитываются
Dist[Spinach, MonHum] = (Dist[Spinach, Monkey] +
Dist[Spinach, Human])/2 = (91 + 86)/2 = 88.5
Mon-Hum
Mosquito Spinach
Rice
Human
Monkey

35.

Редуцированная матрица дистанций
Spinach
Rice
Mosquito
Mon-Hum
Spinach
0.0
Rice
9
Mosquito
106
Mon-Hum
88.5
0.0
118
122
0.0
53
0.0

36.

37.

38.

39. Недостатки UPGMA

Алгоритм строит ультраметрическое дерево – скорость эволюции
предполагается одинаковой для всех ветвей дерева. Использовать
этот алгоритм имеет смысл только в случае ультраметрических
данных (справедливости «молекулярных часов»).
Реальное дерево
UPGMA

40. Метод ближайших соседей (Neighbor-joining, NJ)

Строит неукоренённое дерево
Может работать с большим количеством данных
Достаточно быстрый
Если есть недвусмысленное с точки зрения
эксперта дерево, то оно будет построено.
. Только древо сходства – не филогенетическое

41. Метод Neighbor-joining

Рисуем «звездное» дерево и будем «отщипывать» от него по паре
листьев
Пусть ui = Σk Mik/(n-2) — среднее расстояние от листа i до других
листьев
1. Рассмотрим все возможные пары листьев. Выберем 2 листа i и j с
минимальным значением величины
Mij – ui –uj
т.е. выбираем 2 узла, которые близки друг к другу, но далеки ото всех
остальных.

42. Метод ближайших соседей (Neighbor-joining, NJ)

2. Кластер (i, j) – новый узел дерева
Расстояние от i или от j до узла (i,j):
D(i, (i,j)) = 0,5·(Mij + ui – uj)
D(j, (i,j)) = 0,5· (Mij + uj – ui)
т.е. длина ветви зависит от среднего расстояния
до других вершин
3. Вычисляем расстояние от нового кластера до всех других
M(ij)k = Mik+Mjk – Mij
2
5. В матрице М убираем i и j и добавляем (i, j).
Повторяем, пока не останутся 3 узла .

43.

44.

Методы, основанные на последовательностях:
Maximum Likelihood (ML), Maximum Parsimony (MP)
Input:
MSA для n последовательностей,
одна последовательность для каждого
вида.
AAAAATC
CCCCCCG
AAAAAAG
Длинная ветвь Похоже на правду
CCCCCCG
AAAAAAG
AAAAATC
Длинная ветвь –
непохоже на правду

45. Как изобразить дерево? Топология дерева

Топология дерева — только листья, узлы, (корень)
и связывающие их ветви
(топология не зависит от способа изображения дерева)
A
B
C
D
E
C
D E
A
Два изображения одной и той же топологии
B

46.

Как можно нарисовать построенное дерево?
Кладограммы и филограммы
Bacterium 1
Bacterium 2
Bacterium 3
Eukaryote 1
Eukaryote 2
Кладограммы – только
топологя. Длины ветвей не
учитываются
Eukaryote 3
Eukaryote 4
3
Bacterium 1
1
Bacterium 2
2
Bacterium 3
4
Eukaryote 1
3
6
6
5
2
4
Филограммы – длины ветвей
пропорциональны
эволюционному расстоянию.
Eukaryote 2
Eukaryote 3
Eukaryote 4

47. Какие on-line программы строят деревья?

ClustalW. “Tree
type” – nj, phylip: строит только
методом NJ, но результат – в разных форматах,
no bootstraps
Phylip (Felsenstein, 1993) – пакет программ для
построения филогенетических деревьев (standalone)
PAUP (Phylogenetic Analysis Using Parsimony)

48. MEGA: филогенетический анализ последовательностей

49.

Эволюция – исторический процесс.
Из 8,200,794,532,637,891,559,375 деревьев для 20 OTUs, 1
является верным и 8,200,794,532,637,891,559,374
неверны.
Truth is one, falsehoods are many.

Источник