Презентація на тему - Дерева (trees) - з англійської мови для 7 класу

Завантажити презентацію (0.46 Мб) 8 завантажень 4.0 оцінка

Анотація до презентації

Презентація для школярів на тему "Дерева" з іноземних мов. pptCloud.ru – зручний каталог з можливістю скачати powerpoint презентацію безкоштовно.

Зміст

Дерева (trees)

«…велике Дерево Життя заповнює земну кору своїми мертвими і зламаними гілками і покриває поверхню вічно гілкуються і прекрасними пагонами» Ч. Дарвін

Завдання побудови філогенетичного дерева

Time will come, I believe, though I shall no live to see it, when we shall have fairly true genealogical trees of each great kingdom of Nature. Charles Darwin Математична задача – завдання кластеризації, використання теорії графів та комбінаторної оптимізації для того, щоб на основі «брудних» біологічних даних отримати розумне з погляду експерта-біолога дерево. Біологічні завдання - порівняння 3-х і більше об'єктів (хто на кого більш схожий.) реконструкція еволюції (хто від кого, як і коли стався…)

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

еволюція в природі або, наприклад, деревоподібний граф, лабораторії, а.к. після- обчислений на основі комп'ютерна симуляція або даних, може кількість відображати або не вусиків відображати реальні події Seq4 GCGCTGFKI . . . . . >Seq1 ASGCTAFKL . . .>Seq3 GCGCTLFKI ACGCTAFKI GCGCTAFKI ACGCTAFKL A -> G I -> L

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

Рутинна процедура

Складання вибірки послідовностей Множинне вирівнювання Побудова дерева фрагмент запису у вигляді правильної скобкової структури: Візуалізація та редактура дерева ((((((con101:38.51018,(f53969:28.26973,((f67220:8.39897)) :30.19677) :13.62315):9.53075):25.83145,

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

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

Бінарне дозволене (одночасно може статися одна подія) Бінарне недозволене (чи може в один момент часу відбутися дві події?) Час

Вкорінене орієнтоване дерево відображає напрямок еволюції Неукорінене (нескореневе) неорієнтоване дерево показує лише зв'язки між вузлами Час Якщо число листя дорівнює n, існує (2n-3)!! різних бінарних докорених дерев. (2n-3)!! – це щось на зразок факторіалу, але враховуються лише парні числа. Існує (2n-5)!! різних безкореневих дерев з n вершинами

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 OTUs UNROOTED ROOTED

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

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

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

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

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

Філограма: Довжина ребер пропорційна еволюційній відстані між вузлами. Кладограма: представлена лише топологія, довжина ребер ігнорується. Arabidopsis Caenorhabditis Drosophila Anopheles Tenebrio Trout Mus 0.1 substitutions per site Arabidopsis Caenorhabditis Drosophila Anopheles Tenebrio Trout Mus

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

Методи, що ґрунтуються на оцінці відстаней (матричні методи): Обчислюються еволюційні відстані між усіма вершинами (OTUs) і будується дерево, у якому відстані між вершинами найкраще відповідають матриці попарних відстаней. UPGMA (Unweighted Pair Group with Arithmetic Mean) Найближчих сусідів (Neighbor-joining,NJ) Символьно-орієнтовані методи: Найбільшої правдоподібності, Maximum likelihood,ML Використовується модель еволюції і будується дерево, яке найбільш правдоподібне при даній моделі Максимальної економії parsimony, MP Вибирається дерево з мінімальною кількістю мутацій, необхідних для пояснення даних

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

Дано: М - матриця n x n, де Mij = 0, Mij - еволюційна відстань між листям (OTU). Завдання: Побудувати реберно зважене (an edge-weighted) дерево, де кожна вершина (лист) відповідає об'єкту з M, а відстань, виміряна по дереву між вершинами (листям) i and j відповідає Mij.

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 Повторюємо процедуру…. Зрештою отримуємо єдине ультраметричне вкорінене дерево = 11.5

Не користуйтесь UPGMA!

Алгоритм будує ультраметричне дерево, що означає, що швидкість еволюції однакова всім гілок дерева. Використовувати цей алгоритм має сенс лише у разі ультраметричних даних (об'єктів, що еволюціонують з однаковою швидкістю). реальне з точки зору UPGMA експерта дерево

Метод найближчих сусідів (Neighbor-joining, NJ)

1. Малюємо «зоряне» дерево і будемо "відщипувати" від нього по парі вершин, розглянемо всі можливі пари вершини. нехай – «середня» відстань до інших вершин. 2. Виберемо 2 вершини i та j з мінімальним значенням Mij – ui –uj тобто. вибираємо 2 вузли, які близькі один до одного, але далекі від решти.

3. Кластер (i, j) – новий вузол дерева. 0.5 (Mij + uj-ui) тобто. Довжина гілки залежить від середньої відстані до інших вершин. 4. Обчислюємо відстань від нового кластера до всіх інших M(ij)k = Mik+Mjk – Mij 2 5. У матриці М прибираємо i та j і додаємо (i, j). Повторюємо, доки не залишаться 2 вузли.

Будує безкореневе адитивне дерево Може працювати з великою кількістю даних Досить швидкий алгоритм Добре зарекомендував себе на практиці: якщо є недвозначне з погляду експерта дерево, товоно буде збудовано. Використовується при множинні вирівнювання за допомогою програми ClustalW Можуть з'явитися гілки з довжиною Слайд 20

Достовірність топології. Bootstraps.

Створимо псевдодані: N множинних вирівнювань тієї ж довжини, що і вихідне, кожне з псевдовирівнювань - випадковий набір стовпців з вихідного. Побудуємо N дерев: кожному внутрішньому вузлі відзначимо частку випадків з N, у яких з'являвся цей вузол. Зазвичай вірять у топологію, якщо мітки вузлів на бутстрепному дереві більше 70-80%. Якщо менше 30%, то не віримо. В інших випадках - думаємо ... Є множинне вирівнювання і побудоване по ньому дерево. Чи віримо ми у топологію дерева?

Human Chimp Gorilla Orangutan Gibbon Traditional Human Chimp Gorilla Orangutan Gibbon Molecular

plagiarized by Chuck Staben, 1998 Sergeant Joyce Kilmer, 1914