Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Деревья (trees)

Содержание

Задача построения филогенетического дереваThe time will come, I believe, though I shall not live tosee it, when we shall have fairly true genealogical treesof each great kingdom of Nature.Charles DarwinМатематическая задача – задача кластеризации,
Деревья  (trees)«…великое Дерево Жизни заполняет земную кору своими мертвыми и сломанными Задача построения филогенетического дереваThe time will come, I believe, though I shall Реальные события :    Данные:   Построенное дерево Будни биоинформатика – деревья, деревья… Рутинная процедура  Составление выборки последовательностей  Множественное выравнивание  Построение дерева Основные термины Какие бывают построенные деревья?Бинарное разрешенное(в один момент времени может произойти одно событие Какие бывают построенные деревья?Укорененное ориентированное дерево отражает направление эволюцииНеукорененное (бескорневое)неориентированное дерево показывает ABCABCABCABCABCDABCDABCDABCDABCDABCDABCD… 15 rooted trees of 4 OTUs3 OTUs4 OTUsUNROOTEDROOTED Искусственный способ укоренения деревьев Бескорневое дерево можно «укоренить», если ввести внешнюю группу Какие бывают построенные деревья ? Филограмма:Длина ребер пропорциональна эволюционному расстоянию между узлами.Кладограмма: представлена только топология, длина ребер Основные алгоритмы построения филогенетических деревьевМетоды, основанные на оценке расстояний (матричные методы):Вычисляются эволюционные Методы, основанные на оценке  расстоянийДано:      М UPGMA  (алгоритм последовательной кластеризации)Выбираем 2 наиболее похожие    вершины Не пользуйтесь UPGMA! Алгоритм строит ультраметрическое дерево, а это означает, что скорость Метод ближайших соседей (Neighbor-joining, NJ)1. Рисуем «звездное» дерево и будем Метод ближайших соседей (Neighbor-joining, NJ)3.  Кластер (i, j) – новый узел Метод ближайших соседей (Neighbor-joining, NJ)Строит бескорневое аддитивное деревоМожет работать с большим количеством Достоверность топологии. Bootstraps.Создадим псевдоданные:    N множественных выравниваний той же HumanChimpGorillaOrangutanGibbonTraditionalHumanChimpGorillaOrangutanGibbonMolecular Treesplagiarized by Chuck Staben, 1998Sergeant Joyce Kilmer, 1914
Слайды презентации

Слайд 2 Задача построения филогенетического дерева
The time will come, I

Задача построения филогенетического дереваThe time will come, I believe, though 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

Математическая задача – задача кластеризации,
использование теории графов и комбинаторной оптимизации
для того, чтобы на основе «грязных» биологических данных
получить разумное с точки зрения эксперта-биолога дерево.

Биологические задачи –

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



Слайд 3 Реальные события : Данные:

Реальные события :  Данные:  Построенное дерево  эволюция

Построенное дерево
эволюция в природе или

в например, древовидный граф,
лаборатории, а.к. последо- вычисленный на основе
компьютерная симуляция вательности или данных, может
количество отражать или не
усиков отражать реальные
события

>Seq4 GCGCTGFKI
. . . . .

>Seq1 ASGCTAFKL
. . .

>Seq3 GCGCTLFKI

A -> G

I -> L


Слайд 4 Будни биоинформатика – деревья, деревья…

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

Слайд 5 Рутинная процедура
Составление выборки последовательностей

Множественное

Рутинная процедура Составление выборки последовательностей Множественное выравнивание Построение дерева фрагмент записи

выравнивание




Построение дерева
фрагмент записи в виде правильной

скобочной структуры:



Визуализация и редактура дерева

(((((con101:38.51018,(f53969:28.26973,((f67220:8.39851,
max4:27.50591):4.92893,con92:30.19677):13.62315):9.53075):25.83145,


Слайд 6 Основные термины

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

Слайд 7 Какие бывают построенные деревья?
Бинарное разрешенное
(в один момент времени

Какие бывают построенные деревья?Бинарное разрешенное(в один момент времени может произойти одно

может
произойти одно событие )
Бинарное неразрешенное
(может ли в

один момент времени
произойти два события? )

Время


Слайд 8 Какие бывают построенные деревья?
Укорененное ориентированное
дерево отражает направление

Какие бывают построенные деревья?Укорененное ориентированное дерево отражает направление эволюцииНеукорененное (бескорневое)неориентированное дерево


эволюции
Неукорененное (бескорневое)
неориентированное дерево показывает
только связи между узлами
Время
Если число

листьев равно n, существует (2n-3)!!
разных бинарных укоренных деревьев.
(2n-3)!! – это нечто вроде факториала, но
учитываются только четные числа.

Существует (2n-5)!! разных бескорневых
деревьев с n вершинами


Слайд 9 A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
… 15 rooted trees of 4 OTUs
3 OTUs
4

ABCABCABCABCABCDABCDABCDABCDABCDABCDABCD… 15 rooted trees of 4 OTUs3 OTUs4 OTUsUNROOTEDROOTED

OTUs
UNROOTED
ROOTED


Слайд 10 Искусственный способ укоренения деревьев
Бескорневое дерево можно «укоренить»,

Искусственный способ укоренения деревьев Бескорневое дерево можно «укоренить», если ввести внешнюю

если ввести внешнюю группу OTU (outgroup).
Внешния

группа должна быть "старше", т.е. заведомо отделиться раньше, чем произошла дивергенция остальных OTU.

Слайд 11 Какие бывают построенные деревья ?

Какие бывают построенные деревья ?     Расстояние по

Расстояние по дереву не

то же самое, что
эволюционное расстояние между данными

Ультраметрические деревья
Корневое дерево, в котором для любых
листьев i и j расстояние D(i,j) – метка наименьшего
общего предка i и j .
В таком дереве все листья находятся на
одинаковом от корня, что соответствует
одинаковой скорости эволюции всех ветвей
Аддитивные деревья
Дерево, в котором для любых вершин i и j расстояние D(i,j) – это эволюционный путь от i к j . При этом расстояния от i и от j до их наименьшего общего предка могут сильно различаться.

Другие …

аддитивные

ультраметрические

Вообще говоря, строгое решение задачи
построения аддитивного дерева невозможно
(следует из свойства задачи)


Слайд 12 Филограмма:
Длина ребер пропорциональна эволюционному расстоянию между узлами.
Кладограмма:
представлена

Филограмма:Длина ребер пропорциональна эволюционному расстоянию между узлами.Кладограмма: представлена только топология, длина

только топология, длина ребер игнорируется.
0.1 substitutions per site
Arabidopsis
Caenorhabditis
Drosophila
Anopheles
Tenebrio
Trout
Mus
Как можно

нарисовать построенное дерево?

Слайд 13 Основные алгоритмы построения филогенетических деревьев
Методы, основанные на оценке

Основные алгоритмы построения филогенетических деревьевМетоды, основанные на оценке расстояний (матричные методы):Вычисляются


расстояний (матричные методы):

Вычисляются эволюционные
расстояния между всеми вершинами
(OTUs) и

строится дерево, в котором
расстояния между вершинами
наилучшим образом соответствуют
матрице попарных расстояний.

UPGMA (Unweighted Pair Group with Arithmetic Mean)
Ближайших соседей
(Neighbor-joining, NJ)

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

Наибольшего правдоподобия, Maximum likelihood, ML
Используется модель эволюции и строится дерево, которое наиболее правдоподобно при данной модели

Максимальной экономии (бережливости), maximum parsimony, MP
Выбирается дерево с минимальным количеством мутаций, необходимых для объяснения данных


Слайд 14 Методы, основанные на оценке расстояний
Дано:

Методы, основанные на оценке расстоянийДано:   М – матрица n

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

где Mij>=0 , Mij – эволюционное расстояние
между листьями (OTU).
Задача:
Построить реберно взвешенное (an edge-weighted) дерево, где каждая вершина (лист) соответствует объекту из M , а расстояние, измеренное по дереву между вершинами (листьями) i and j соответствует Mij.


Слайд 15 UPGMA (алгоритм последовательной кластеризации)
Выбираем 2 наиболее похожие

UPGMA (алгоритм последовательной кластеризации)Выбираем 2 наиболее похожие  вершины a, c.Строим

вершины 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

Повторяем процедуру….

В конце концов получаем единственное ультраметрическое
укорененное дерево
=11.5


Слайд 16 Не пользуйтесь UPGMA!
Алгоритм строит ультраметрическое дерево, а

Не пользуйтесь UPGMA! Алгоритм строит ультраметрическое дерево, а это означает, что

это означает, что
скорость эволюции одинакова для всех ветвей

дерева.
Использовать этот алгоритм имеет смысл только в случае
ультраметрических данных (объектов эволюционирующих с
одинаковой скоростью).





реальное
c точки зрения UPGMA
эксперта
дерево










Слайд 17 Метод ближайших соседей (Neighbor-joining, NJ)
1. Рисуем «звездное» дерево

Метод ближайших соседей (Neighbor-joining, NJ)1. Рисуем «звездное» дерево и будем

и будем "отщипывать" от него по паре
вершин,

рассмотрим все возможные пары вершины.

пусть - «среднее» расстояние до других вершин.

2. Выберем 2 вершины i и j с минимальным значением

Mij – ui –uj

т.е. выбираем 2 узла, которые близки друг к другу, но далеки ото всех остальных.

Слайд 18 Метод ближайших соседей (Neighbor-joining, NJ)
3. Кластер (i,

Метод ближайших соседей (Neighbor-joining, NJ)3. Кластер (i, j) – новый узел

j) – новый узел дерева

Расстояние от

i или от j до узла (i,j):
di, (i,j) = 0.5(Mij + ui-uj)
dj, (i,j) = 0.5(Mij + uj-ui)
т.е. длина ветви зависит от
среднего расстояния до других вершин.

4. Вычисляем расстояние от нового кластера до всех других

M(ij)k = Mik+Mjk – Mij
2

5. В матрице М убираем i и j и добавляем (i, j).

Повторяем, пока не останутся 2 узла......



Слайд 19 Метод ближайших соседей (Neighbor-joining, NJ)
Строит бескорневое аддитивное дерево




Может

Метод ближайших соседей (Neighbor-joining, NJ)Строит бескорневое аддитивное деревоМожет работать с большим

работать с большим количеством данных
Достаточно быстрый алгоритм
Хорошо зарекомендовал себя

на практике: если есть недвусмысленное с точки зрения эксперта дерево, то оно будет построено.
Используется при множественном выравнивании с помощью
программы ClustalW
Могут появиться ветви с длиной <0

Слайд 20 Достоверность топологии. Bootstraps.


Создадим псевдоданные:
N

Достоверность топологии. Bootstraps.Создадим псевдоданные:  N множественных выравниваний той же длины,

множественных выравниваний той же длины, что и исходное, каждое

из псевдовыравниваний - случайный набор столбцов из исходного.
Построим N деревьев:
на каждом внутреннем узле отметим долю
случаев из N, в которых появлялся
этот узел.

Обычно верят в топологию, если метки узлов на бутстрепном дереве больше 70-80% . Если меньше 30%, то не верим. В иных случаях – думаем…

Есть множественное выравнивание и
построенное по нему дерево.
Верим ли мы в топологию дерева?


Слайд 21 Human
Chimp
Gorilla
Orangutan
Gibbon
Traditional
Human
Chimp
Gorilla
Orangutan
Gibbon
Molecular

HumanChimpGorillaOrangutanGibbonTraditionalHumanChimpGorillaOrangutanGibbonMolecular

  • Имя файла: derevya-trees.pptx
  • Количество просмотров: 101
  • Количество скачиваний: 0
- Предыдущая А.П. Чехов
Следующая - Переливание крови