Реконструкция филогении по биологическим последовательностям С.А.Спирин 6.III.2007, ФББ МГУ

Что такое дерево (напоминание) Корень Ветвь Узел Лист «Клада»

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

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

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

Расстояния по дереву между листьями D( MOUSE, CAEEL ) = = 129

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

Ультраметрические деревья Если на дереве можно найти точку такую, что расстояния от нее до всех листьев одинаковы, до дерево называется ультраметрическим. Ультраметрическое дерево можно однозначно укоренить (в эту самую точку). Содержательно ультраметрические деревья соответствуют случаю, когда длины ветвей суть время эволюции (а все последовательности современны) Время эволюции можно восстанавливать в предположении «молекулярных часов»

Мы рассматриваем алгоритмы реконструкции филогении по данному множественному выравниванию (хотя бывают и другие!). CAEEL ASWRQLRDVKRREQIQEVGADRMRLKAIKFNTILPQAIRDEAAEKMQKAR HUMAN VDWRMWRDVKRRKMAYEYADERLRINSLRKNTILPKILQDVADEEIAALP MOUSE VDWRMLRDLKRRKMAYEYADERLRINSLRKNTILPKDLQEMAGDEIAALP PROWI MFNSIKRDLKRRKLYKKYESKRLLYKALISDCNLNQDLRFILTQKLNKLP MARPO MSNQIIRDHKRRLLVAKYELKRMHYKAICQDRNLPNKIRYEYFFKLSKLP BRANA SEKQNSRDHKRRLLAAKFELRRKLYKAFCKDPDLPSDMRDKHRYKLSKLP VICFA SEKRNIRDHKRRLLAAKYELRRKLYKAFCKDSDLPSDMRDKLRYKLSKLP

Алгоритмов много! Прежде всего, алгоритм либо предполагает "молекулярные часы", и тогда реконструированное им дерево укорененное и ультраметрическое, либо не предполагает, и тогда дерево всегда не ультраметрическое и как правило не укоренённое.

А что значит «реконструировать»? §Выбрать топологию из множества вариантов §Ещё приписать длины всем ветвям (но не все алгоритмы это делают)

Два типа алгоритмов §a. Использующие вычисление расстояний между последовательностями §b. "Символьно-ориентированные" ВыравниваниеДерево Матрица расстояний a b

Другая классификация алгоритмов §a. Переборные алгоритмы §b. Эвристические алгоритмы ( UPGMA & Neighbor-Joining)

Некоторые алгоритмы

Напоминание §UPGMA предполагает молекулярные часы ( реконструирует укоренённое ультраметрическое дерево) §Neighbor-joining не предполагает МЧ и не укореняет деревья Оба алгоритма работают только с матрицей расстояний

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

UPGMA Unweighted Pair Group Method with Arithmetic Mean Кластерный метод, в котором расстояние между кластерами вычисляется как среднее арифметическое расстояний между их элементами. Ещё к этому прилагается способ вычисления длин ветвей

Идея алгоритма neighbor-joining Находим пару листьев A, B, для которых сумма длин веток такого дерева минимальна. Длины получаются из матрицы расстояний. A B

Идея алгоритма neighbor-joining В наиболее распространённом варианте A и B такая пара последовательностей, для которых минимальна величина (A, B) – M(A,B), где расстояние из матрицы, а M среднее расстояние от A и B до всех остальных последовательностей. A B

Идея алгоритма neighbor-joining Такие «соседи» дальше рассматриваются как один лист. «Объединение соседей» продолжается, пока не останутся только три «листа». A B В отличие от кластерных алгоритмов, NJ не находит корня!

Другая классификация алгоритмов §a. Переборные алгоритмы §b. Эвристические алгоритмы ( UPGMA & Neighbor-Joining)

Переборные алгоритмы §a. Критерий качества дерева §b. Принцип (алгоритм) поиска самого качественного дерева (на практике сводится к поиску "достаточно качественного" дерева) Любой переборный алгоритм включает:

Поиск лучшего дерева Все деревья перебрать (как правило) нельзя! Число различных деревьев с N листьями равно: Это число очень быстро растёт! (2N – 5)!! = (2N – 5) Полный перебор возможен, если число последовательностей не превышает 10–12

Поиск лучшего дерева: «выращивание» Найдем лучшее дерево для части последовательностей Будем добавлять листья по одному, находя для них наилучшее место ? + E+ E A D C B A A A D B E C C C D D B B E E Всего 5 вариантов

Поиск лучшего дерева: «выращивание» Найдем лучшее дерево для части последовательностей Будем добавлять листья по одному, находя для них наилучшее место ! + E+ E A D C B A A A D B E C C C D D B B E E

Немного комбинаторики Дерево с N листьями всегда имеет 2N–3 ветви. Поэтому, чтобы вырастить дерево с N листьями, надо проанализировать (2N – 5) = (N – 3)(N – 1) деревьев. Уже для N=10 это число меньше числа всех возможных деревьев в раз! Выращивание не гарантирует нахождение «лучшего» дерева, но при хороших данных не должно приводить к большим ошибкам.

Поиск лучшего дерева Еще один приём: построим сначала «черновое» дерево, а затем попробуем его улучшить. Черновое дерево можно построить одним из эвристических методов или «вырастить». Улучшать будем, просматривая «соседние» деревья.

Что такое «соседние» деревья §Оторвём один лист и «привьём» его на другую ветвь A D B E C C A D E B

Что такое «соседние» деревья §Можно проделать аналогичную операцию с целой кладой A D B E C C D E A B D C B E A В пакете PHYLIP это называется Global rearrangement

Что такое «соседние» деревья §Можно «схлопнуть» одну ветвь и заменить её другой D B E C A В пакете PHYLIP это называется Local rearrangement D B E C A D B E C A

Алгоритм поиска § Строим черновое дерево (два варианта: эвристический метод или «выращивание» с использованием критерия качества). § Анализируем соседние деревья; если находим среди соседей лучшее, берём за основу его. § Повторяем предыдущий пункт, пока текущее дерево не окажется лучше всех своих соседей.

Переборные алгоритмы §a. Критерий качества дерева §b. Принцип (алгоритм) поиска самого качественного дерева (на практике сводится к поиску "достаточно качественного" дерева) Любой переборный алгоритм включает:

Основные критерии качества § Максимальная экономия (maximum parsimony) § Максимальное правдоподобие (maximal likelihood) § Соответствие расстояний по дереву заданной матрице расстояний (Fitch – Margoliash или minimal evolution) Первые два критерия символьно-ориентированные

Укоренение HUMAN MOUSE PROWI MARPO BRANA VICFA CAEEL в среднюю точку +

Укоренение в среднюю точку используя «аутгруппу» (outgroup)

Сравнение деревьев §Консенсусное (небинарное) дерево §Максимальное общее поддерево §Дерево из ветвей, поддержанных большинством (majority-rule tree) §Меры сходства деревьев ("расстояние") i. Доля общих ветвей ii. Расстояние в "пространстве ветвей" iii. Доля общих четверок iv. Длина пути в пространстве деревьев

PHYLIP §Символьно-ориентированная реконструкция: dnapars, protpars, dnaml, dnamlk, protml, protmlk §Вычисление расстояний: dnadist, protdist §Реконструкция по матрице расстояний: neighbor, fitch, kitsch

PHYLIP §Сравнение: consense, treedist, treedistpair §Визуализация: drawgram, drawtree §Редактура: retree

PHYLIP: где взять? §На сайте разработчика: (для установки на своём компьютере) §Web-интерфейс: §В составе EMBOSS/EMBASSY

Реконструкция предковой последовательности (dnaml) +-YERPE | | +BACAN | | | | +BACCR | | | | +BACC | | | BACSU | | | +---BACHD | ECOLI node Reconstructed sequence (caps if > 0.95) 1 latMSqsPIE LKGSSFTLSV VHLHdsrPeV IrQALqeKvd QAPAFLKnAP VViNVatLpn YERPE ---MSQSPIE LKGSSFTLSV VHLHDSRPEV IRQALQEKVD QAPAFLKNAP VVINVATLPN 2 MttqKqQaVT IKGTKdGLTl HLDDrCSFDs ivgeLaeKLS skHYymedgp rlIqVkVlpn 3 MktKKQQnVT IKGTKdGlTL HLDDcCSFdE LLdeLqeKLS tehYyDGdGq klIeVHVlpd 4 MEEKKQQNVT IKGTKDGITL HLDDCCSFSE LLKELDEKLS TeHYYDGDGR SLIEVHVlpd BACAN MEEKKQQNVT IKGTKDGITL HLDDCCSFSE LLKELDEKLS T-HYYDGDGR SLIEVHV--- 5 MEEKKQQNVT IKGTKDGITL HLDDCCSFSE LLKELDEKLS TeHYYDGDGR SLIEVHVlpd BACCR MEEKKQQNVT IKGTKDGITL HLDDCCSFSE LLMELDEKLS T-HYYDGDGR SLIEVHV--- BACC1 MEEKKQQNVT IKGTKDGITL HLDDCCSFSE LLKELDEKLS T-HYYDGDGR SLIEVHV--- BACSU MKTKKQQYVT IKGTKNGLTL HLDDACSFDE LLDGLQNMLS IEQYTDGKGQ K-ISVHV--- BACHD MTTQKKQAVT IKGTKDGLTF HLDDRCSFDS IVGELAEKLS SKHYQMEDQP R-IQVKV--- ECOLI ---MSNTPIE LKGSSFTLSV VHLHEAEPKV IHQALEDKIA QAPAFLKHAP VVLNVSALED