Філогенетичні дерева

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

Що таке філогенетичне дерево?

Що таке філогенетичне дерево?

Філогенетичне дерево є графом, що складається з вершин і ребер (гілок) у якому будь-які дві вершини з'єднує єдине ребро і між будь-якими двома точками існує єдиний маршрут

Відстань по дереву не те саме, що еволюційна відстань між даними

Ультраметричні дерева

​

Кореневе дерево, в якому для будь-якого

листя i та j відстань D(i,j) – мітка

найменшого загального предка i та j.

​

​

У такому дереві все листя знаходиться на однаковій

від кореня відстані, що відповідає однаковій швидкості

еволюції всіх гілок

​

Адитивні дерева

​

Дерево, у якому будь-яких вершин i і j відстань D(i,j) – це еволюційний шлях від i до j . При цьому відстані від і від j до їх найменшого загального предка можуть сильно відрізнятися.

Які бувають збудовані дерева?

ультраметричні

Які бувають збудовані дерева ?

Ультраметричне дерево

Адитивне дерево

Задача построения филогенетического дерева

• Математична задача – задача кластеризації, використання

теорії графів та комбінаторної оптимізації для того, щоб

на основі «брудних» біологічних даних отримати розумне

з погляду експерта-біолога дерево.

Біологічні завдання –

порівняння 3-х та більше об'єктів

(хто на кого схожий .... )

реконструкція еволюці

(хто від кого, як і коли стався…)

​

​

Основные термины

Вузол (node) - точка поділу предкової послідовності (виду, популяції) на дві незалежно еволюціонують. Відповідає внутрішній вершині графа, що зображує еволюцію..

Лист (leaf, OTU) – оперативна таксономічна одиниця) – реальний (сучасний) об'єкт; зовнішня вершина графіка.

Гілка (branch) - зв'язок між вузлами або між вузлом та листом; ребро графа.

Корінь (root) - гіпотетичний загальний предок.

Клада (clade) - група двох або більше

таксонів або послідовностей ДНК,

яка включає як свого спільного

предка, так і всіх його нащадків.

Кластер

або клада

Як зобразити дерево? �Топологія дерева

Топологія дерева - тільки листя, вузли, (корінь) і гілки, що їх пов'язують (топологія не залежить від способу зображення дерева)

A

B

C

D

E

Два зображення однієї і тієї ж топології

Які бувають збудовані дерева?

1

2

3

4

Які бувають дерева?

Бінарне (дозволене)

(одночасно може

відбутися тільки одна подія)

Небінарне (недозволене)

(чи може в один момент часу

відбутися дві події?)

Время

Які бувають дерева?

Дерево з коренем (rooted tree)

відображає напрямок

Дерево без кореня (unrooted tree) показує

тільки зв'язки між вузлами

Час

Число дихотомічних дерев з коренем для n висячих вершин можна визначити за формулою:

Число дихотомічних дерев без кореня для n висячих вершин можна визначити за формулою:

Штучний спосіб укорінення дерев

• Дерево без кореня можна «укорінити», якщо запровадити зовнішню групу OTU (outgroup).
• Зовнішня група має бути "старіше", тобто, вона відокремилася раніше, ніж відбулася дивергенція решти OTU.

Початкове дерево

Дерево з введеним коренем

Які бувають збудовані дерева?

Філогенетичне дерево генів гемаглютиніну Н3 вірусу грипу типу А.

Ортологи та паралоги

​

​

​

​

​

​

​

�

​

​

​

​

​

​

​

​

​

​

​

​

​

�

Дуплікація

Видоутворення

• Ортологічні гени:

результат видоутворення зберегли клітинну роль

• Паралогічні гени:

результат дуплікації генів зберегли загальну біохімічну функцію

Пример:

gluconate and

idonate kinases

Геном А

Геном В

A1 А2

В1 B2

Генні та видові дерева

Схема реконструкції філогенії за послідовностями

Послідовності

Вирівнювання

Матрично-дистанційні методи

Філогенетичне дерево

Символьно орієнтовані методи

Реальні події: Дані: Побудоване дерево�

​

еволюція у природі чи

лабораторії комп'ютерна

симуляція

>Seq4 GCGCTGFKI

. . . . .

>Seq1 ASGCTAFKL

. . .

>Seq3 GCGCTLFKI

A -> G

I -> L

наприклад, амінокислотна послідовність

або кількість

щетинок

деревоподібний граф, обчислений на основі даних, може відображати чи не відображати реальні події

Будні біоінформатика – дерева, дерева …

Як можна намалювати побудоване дерево?

Філограма:

довжина ребер пропорційна еволюційній відстані між вузлами.

Кладограма:

представлена лише топологія, довжина ребер ігнорується.

Arabidopsis

Caenorhabditis

Drosophila

Anopheles

Tenebrio

Trout

Mus

0.1 substitutions per site

Arabidopsis

Caenorhabditis

Drosophila

Anopheles

Tenebrio

Trout

Mus

Глобальне філогенетичне дерево надродини 16S-18S рибосомальних RNA

• Принциповим становищем мутаційної теорії є твердження, що мутації випадкові і направлені.
• Під цим мається на увазі, що мутації спочатку не адаптивні.

Мутаційна теорія та молекулярна

еволюція

Зазвичай лауреатом Нобелівської премії стають один раз. Лайнус Полінг отримав дві Нобелівські премії. Це двічі знесмертіло його ім'я.

Гіпотеза «молекулярного годинника»�(E.Zuckerkandl, L.Pauling, 1962)

За рівний час у всіх гілках еволюції накопичується рівну кількість мутацій

Якщо гіпотеза молекулярного годинника приймається, число відмінностей між вирівняними послідовностями можна вважати приблизно пропорційним часу. Відхилення від ультраметричності вважатимуться випадковими. Еволюція реконструюється як ультраметричне дерево.

​

Дерево з коренем називається ультраметричним, якщо відстань від кореня до будь-якого з листя однакова.

Мотоо Кимура

Японський біолог, який здобув широку популярність після публікації в 1968 році своєї теорії нейтральної еволюції, яка зробила його одним із найвпливовіших популяційних генетиків. Він також відомий у генетиці завдяки запровадженню прогресивного використання дифузних рівнянь для розрахунку ймовірностей закріплення корисних, шкідливих та нейтральних алелів. Поєднавши теоретичну популяційну генетику з даними молекулярної еволюції, він розвинув нейтральну теорію молекулярної еволюції, у якій генетичний дрейф виступає найважливішим чинником зміни частоти алелей у популяції.

Теорія нейтральної молекулярної еволюції

​

• 1. Швидкість еволюції будь-якого білка, виражена через число амінокислотних замін на сайт на рік, приблизно постійна і однакова в різних філогенетичних лініях, якщо функція та третинна структура цього білка залишаються переважно незмінними.
• 2. Функціонально менш важливі молекули чи його частини еволюціонують (накопичуючи мутаційні заміни) швидше, ніж найважливіші.
• 3. Мутаційні заміни, що призводять до менших порушень структури та функції молекули (консервативні заміни) в ході еволюції відбуваються частіше за тих, які спричиняють більш суттєве порушення структури та функції цієї молекули.
• 4. Появі нового у функціональному відношенні білка завжди має передувати дуплікація гена.
• 5. Селективна елімінація шкідливих мутацій та випадкова фіксація селективно нейтральних або дуже слабко шкідливих мутацій відбувається в ході еволюції набагато частіше, ніж позитивний

Розділи молекулярної еволюції:

• Еволюція генетичних макромолекул:

Мета: встановлення причин та наслідків еволюційних змін у молекулах.

• Молекулярна філогенія

Мета: використання цих молекул як засіб для відновлення біологічної історії організмів та їх генетичних складових

​

Однак на практиці еволюція макромолекул та молекулярна філогенія взаємопов'язані і прогрес в одному з цих розділів сприяє дослідженням в іншому.

Як вибирати послідовності для дерева?

• Крім випадків дуже близьких послідовностей, простіше працювати з білками (а не ДНК)
• Дотримуйтесь невеликої вибірки (< 50 послідовностей)
• Уникайте:
• фрагментів;
• ксенологів;
• рекомбінантних послідовностей;
• багатодоменних білків та повторів
• Використовуйте outgroup (послідовність, що відокремилася від загального предка раніше поділу груп-клад, що цікавлять)

Основні алгоритми побудови філогенетичних дерев

Методи, що ґрунтуються на оцінці

відстаней (матричні методи):

​

Обчислюються еволюційні

відстані між усіма вершинами

(OTUs) і будується дерево, в якому

відстані між вершинами

найкраще відповідають

матриці попарних відстаней.

​

• UPGMA (Unweighted Pair Group with Arithmetic Mean)
• Найближчих сусідів (Neighbor-joining, NJ)

Символьно-орієнтовані методи:

​

• Найбільшої правдоподібності, Maximum likelihood, ML

Використовується модель еволюції та будується дерево, яке найбільш правдоподібне при даній моделі

​

• Максимальної економії maximum parsimony, MP

Вибирається дерево з мінімальною кількістю мутацій, необхідних для пояснення даних

Схема реконструкції філогенії по

послідовностям

Послідовності

Вирівнювання

Матриця відстані

Дерево

Програми множинного вирівнювання

(Muscle, MAFFT, PROBCONS, ...)

Оцінка еволюційних відстаней

Реконструкція філогенії

(UPGMA, Neighbor-Joining, Minimal Evolution, Fitch – Margoliash, Quartets, ...)

«Символьно-орієнтовані» методи

Ітераційні методи

​

1.Максимальної економії (maximum parsimony, MP) критерій - найменша кількість мутацій, що дозволяє по цьому дереву отримати дані послідовності

2.Найбільшої правдоподібності (maximum likelihood, ML)

критерій - можливість отримати дані послідовності по даному дереву

​

Дистанційні

i. ordinary least squares (OLS)

критерій - середнє квадратичне відхилення відстаней

ii.Fitch – Margoliash

те ж, що OLS, але використовуються відносні відхилення

iii. Minimum evolution

критерій - сумарна довжина гілок (самі довжини оцінюються по-різному)

Перебірні методи

​

Алгоритм, що реалізує перебірний метод, повинен містити:

а) критерій порівняння дерев (яка з двох топологій краще відповідає вихідним даним?)

б) алгоритм пошуку найкращого за критерієм дерева.

Назва методу збігається з назвою критерію.

Критерії бувають символьно-орієнтовані: найбільша

правдоподібність і максимальна економія, і дистанційні: різні варіанти критерію мінімальної еволюції, найменші квадрати (звичайні та "покращені"), квартетний критерій тощо.

Всі критерії, крім максимальної економії, мають на увазі "по ходу справи" обчислення довжин гілок, тому і у відповіді виходить не тільки топологія, а й довжини гілок.

Евристичні методи

​

1.UPGMA = Unweighted Pair Group Method with Arithmetic mean

будує ультраметричне дерево з коренем.

Мабуть, реально найкращий з методів, що передбачають молекулярний годинник.

​

2.Neighbor-joining (NJ)

будує дерево без кореня. Якщо і поступається деяким перебірним алгоритмам, то не сильно.

Методи, що ґрунтуються на оцінці відстаней

Дано:

М – матриця n x n,

де Mij>=0 , Mij – еволюційна відстань

між листям (OTU).

Завдання:

Побудувати реберно зважене (an edge-weighted) дерево, де кожна вершина (OTU) відповідає об'єкту з M , а відстань, виміряна по дереву між вершинами (OTU) i and j відповідає Mij.

�UPGMA��Unweighted Pair Group Method with Arithmetic Mean

​

різновид кластерного методу

​

​

Відстань між кластерами обчислюється як середня арифметична різноманітних відстаней між послідовностями з кластерів

UPGMA �(алгоритм послідовної кластеризації)

• Вибираємо 2 найбільш схожі

вершини a, c.

​

• Будуємо новий вузол k такої, що D(a,k)=D(b,k)=D(a,c)/2.

​

• Перераховуємо матрицю

попарних відстаней :

D(b, a or c) = [ D(b,a) + D(b,c) ] /2 = (8+9)/2=8.5

D(d, a or c) = [ D(d,a) + D(d,c) ] /2=(12+11)/2=11.5

​

• Повторюємо процедуру….

​

Зрештою отримуємо єдине ультраметричне дерево з коренем

Приклади послідовностей:

А ATTCGTGAGAATGCTATCCGCGAGAATGCC

B A– – – – – – – – – – – – – – – – – – – – – – – – – T

C – –CA–A– – – – – – – – – – – – – – – – – – – – – T

D – –CA–G– – – – – – – A– – – – – – – –A – – – – A

E – – C– –G– –A– – – – G– – T– – – – – – – C – – A

UPGMA �(алгоритм послідовної кластеризації)

Етап 1

UPGMA �(алгоритм послідовної кластеризації)

Етап 2

Етап 3

UPGMA �(алгоритм послідовної кластеризації)

Етап 4

Недоліки UPGMA

Алгоритм будує ультраметричне дерево, а це означає, що

швидкість еволюції передбачається однаковою всім гілок дерева.

Використовувати цей алгоритм має сенс у разі ультраметричних

даних (теорія «молекулярного годинника»).

Реальне дерево

UPGMA

Гіпотеза молекулярного годинника не завжди справедлива

A

B

C

D

E

(довжина гілок пропорційна числу мутацій)

Методи зв'язків між сусідами

D_ac + D_bd = D_ad + D_bc = a + b + c + d + 2x = D_ab + D_Cd + 2x, і будуть справедливі такі нерівності:

Dab + D_Cd < D_AC + D_bd,

Dab + D_cd < D_Ad + D_BC.

B

C

A

D

b

a

c

d

x

Сусідами у філогенетичному аналізі називають дві послідовності, з'єднані через один вузол.

Метод об'єднання сусідів�(Neighbor-joining, NJ)

• Будує дерево без кореня

​

• Може працювати з великою кількістю даних

​

• Досить швидкий

​

• Добре зарекомендував себе практично: якщо є недвозначне з погляду експерта дерево, воно буде побудовано.

​

• Можуть з'явитися гілки із довжиною <0

Обмін найближчих сусідів (nearest-neighbour interchange, NNI)

Метод максимальної економії

maximum parsimony

Нехай нам відома матриця відстаней між видами з деякої множини. Тоді деревом максимальної економії називається дерево, що відповідає наступним умовам.

1. Безліч кінцевих вершин дерева збігаються з безліччю аналізованих видів.

2. Довжини всіх ребер дерева не є негативними.

3. Відстань між двома будь-якими вершинами в дереві не менше відстані між відповідними видами за вихідними даними.

4. Сума довжин ребер дерева не більша за суму довжин ребер будь-якого дерева, що задовольняє умовам 1-3.

Метод максимальної правдоподібності

maximum likelihood

Передбачається, що результати спостереженьX₁, ..., X_n є взаємно незалежними випадковими величинами з тим самим розподілом ймовірностей, що залежать від одного невідомого параметра q Î Q, де Q — безліч допустимих значень q. Для надання точного сенсу принципу «найбільшої ймовірності» надходять у такий спосіб. Вводять функцію

де p(t; q) у разі безперервного розподілу інтерпретується як щільність імовірності випадкової величини X, а в дискретному випадку - як ймовірність того, що випадкова величина Х набуде значення t.

Метод максимальної правдоподібності

maximum likelihood

Р = Р_х1(t₁+t₂+t₃)Р_ху(t₁)Р_уk(t₂+t₃)Р_уz(t₂)Р_zi (t₃)Р_zj(tз),

Метод максимальної правдоподібності

maximum likelihood

Побудова філогенетичного дерева методом максимальної правдоподібності, де ймовірності всіх замін розраховуються відповідно до моделі Джукса—Кантора, що використовується в даному випадку.

*

1 TCAAAAATGGCTTTATTCGCTTAATGCCGTTAACCCTTGCGGGGGCCATG

2 TCCGTGATGGATTTATTTCTGCAATGCCTGTCATCTTATTCTCAAGTATC

3 TTCGTGATGGATTTATTGCTGGTATGCCAGTCATCCTTTTCTCATCTATC

4 TTCGTGACGGGTTTATCTCGGCAATGCCGGTCATCCTATTTTCGAGTATT

Метод максимальної правдоподібності

maximum likelihood

P_tree3= P_A×P_AG×P_AC×P_AT× P_TT× P_TT

P_tree2= P_tree3+ P_tree4+…+ P_scenario16

Достоверность топологии. Bootstraps

​

​

• Створимо псевдодані:

N множинних вирівнювань тієї ж довжини, що й вихідне, кожне з псевдовирівнення - випадковий набір стовпців з вихідного (вибірка з поверненням!)

• Побудуємо N дерев:

на кожній внутрішній гілці відзначимо частку

випадків з N, у яких з'являвся

цей вузол.

Зазвичай вірять у топологію, якщо мітки гілок на бутстрепному дереві більше 70-80%. Якщо менше 50%, то не віримо. В інших випадках – думаємо…

Є множинне вирівнювання та

побудоване ним дерево.

Чи віримо ми у топологію дерева?

Bootstraps

Bootstraps

Bootstraps