UNIVERSITATEAPOLITEHNICA TIMIŞOARA

UNIVERSITATEAPOLITEHNICA TIMIŞOARA

MASTER SIIS MASTER SIIS

Sisteme Informatice în Îngrijirea Sisteme Informatice în Îngrijirea Sănătății Sănătății

1

www.medinfo.umft.ro/www.medinfo.umft.ro/dim/bioinformatica.htmdim/bioinformatica.htm

2

BIOINFORMATICABIOINFORMATICA

Prof Dr George I MihalaProf Dr George I Mihalaşş

UMF Victor BabeşUMF Victor Babeş

3

CURSUL 12CURSUL 12

4

ANALIZA FILOGENETICAANALIZA FILOGENETICA

5

Planul cursuluiPlanul cursului

1. Introducere: terminologie, tipuri, aplicaţii

2. Număr de arbori

3. Metode de construcţie:– Metode bazate pe distanţe

• Algoritmul UPGMA

• Ceasul molecular, date ultrametrice

• Metoda Neighbor Joining

– Metode bazate pe parsimonie• Algoritmul lui Fitch

• Parsimonie ponderată

6

Noţiuni generale (i)Noţiuni generale (i)

1.1. DefiniDefiniţieţie: un arbore (tree) este un graf aciclic, nedirecţionat

2.2. Structura unui arboreStructura unui arbore:– Frunze (leaves) – obiecte (ex secvenţe de proteine, gene) =

noduri exterioare, de grad “1”; sunt notate: 1, …, n

– Noduri (nodes) – intersecţie de ramuri; se numerotează de la n+1 în sus

– Ramuri – legături între noduri; au deseori o “lungime” calculată după diverse criterii

– OBS: taxon (pl: taxa) – frunze care reprezintă specii

7

Noţiuni generale (ii)Noţiuni generale (ii)

3. Istoric: 3. Istoric: Zuckerkandl şi Pauling (1960)

4. Tipuri:4. Tipuri:– Fără rădăcină (unrooted trees) – specifică relaţii

– Cu rădăcină (rooted trees) – “rădăcina” este ultima ramură de la ultimul nod; se stabileşte o ierarhie (dendrogramă); (dendrogramă); calea de la rădăcină la un nod reprezintă o cale de evoluţie

– Topologia arborelui – dacă ramurilor nu le sunt asociate “lungimi”

5. Inferenţă filogenetică 5. Inferenţă filogenetică – stabilirea unui arbore filogenetic care caracterizează linia evolutivă între specii sau gene

8

Noţiuni generale (iii)Noţiuni generale (iii)

6. Utilitate / motivaţie 6. Utilitate / motivaţie

• a înţelege relaţiile evolutive a speciilor

• a înţelege cum au evoluat diverse funcţii

• informaţii pentru alinierea multiplă

• a identifica ce este mai important / conservat in unele clase de secvenţe

9

Ex: Arbore al genelor: GlobineEx: Arbore al genelor: Globine

10

Ex: Arbore al speciilor: BabuiniiEx: Arbore al speciilor: Babuinii

11

Arbori cu şi fără rădăcinăArbori cu şi fără rădăcină

12

Numărul de arbori posibiliNumărul de arbori posibili

• Nr. Arbori Fără Rădăcină• Pornim de la arbore cu 3 frunze și

incrementăm

Nr. frunze

3 4 5 … n

Nr. noduri

4 6 8 … 2n 2

Nr. ramuri

3 5 7 … 2n 3

Nr. arbori

1 3×53×5×7

… (2n 5)!!

13

Numărul de arbori posibiliNumărul de arbori posibili• Nr. Arbori cu Rădăcină• Pornim de la arbore cu 3 frunze și incrementăm

14

Numărul de arbori posibiliNumărul de arbori posibili

15

Date pentru construcţia arborilorDate pentru construcţia arborilor

1. Distanţe – măsuri / estimări ale distanţelor între specii sau între gene

2. Caractere – aspecte morfologice (ex nr de picioare), secvenţe de ADN sau proteine

3. Ordinea genelor – după ordinea lineară a genelor ortoloage in genomurile date

16

Metode de construcţie a Metode de construcţie a arborilor filogearborilor filogenneticietici

1. Metoda grupării – bazată pe distanţe – arborele explică distanţele evolutive estimate

2. Parsimonie – arborele care necesită numărul minim de “schimbări” pentru a explica datele

3. Asemănarea maximă – arborele care maximizează asemănarea datelor (neighbour joining)

17

Comparație metodeComparație metode

18

Abordări bazate pe distanţeAbordări bazate pe distanţe

Punerea problemeiPunerea problemei: fiind dată o matrice M a distanţelor Mij între taxonii i şi j, de dimensiune n × n (n = nr de taxoni / frunze), să se construiască un arbore cu ramuri ponderate (“edge-weighted tree”) Mij.

19

• Proprietăţile Proprietăţile distanţelordistanţelor

• Date Ultrametrice:Date Ultrametrice:– Ipoteza Ceas ului MolecularIpoteza Ceas ului Molecular: se presupune că : se presupune că

divergenţa secvenţelor apare cu aceeaşi rată în divergenţa secvenţelor apare cu aceeaşi rată în orice punct din arbore – orice punct din arbore – date ultrametricedate ultrametrice

– Ipoteza nu este în general valabilă – procesul de selecţie variază în diverse perioade de timp, variază cu organismul, genele unui organism sau regiunile unei gene

20

Metoda UPGMAMetoda UPGMAUnweighted Pair Group Method using Unweighted Pair Group Method using

Arithmetic AveragesArithmetic Averages

Ideea de bazăIdeea de bază:

- se compun doi taxoni / clustere, formând un (nou) cluster

- se creează un nou nod pentru noul cluster

- distanţa între două clustere (distanţa între perechi de taxoni din fiecare cluster):

21

Algoritmul UPGMAAlgoritmul UPGMA- Se consideră fiecare taxon ca un cluster

- Se defineşte o frunză pentru fiecare taxon; se plasează la înălţimea “0” pe scara distanţelor

- Când sunt mai mult de două clustere:- Se aleg două clustere, i şi j, pentru care distanţa dij este minimă

- Se defineşte un nou cluster Ck = Ci U Cj

- Se defineşe un nod k părinte al i şi j; se plasează la înălţimea dij / 2

- Se înlocuiesc clusterele i şi j cu k

- Se calculează distanţa între k şi celelalte clustere

- Ultimele două clustere i şi j se unesc cu o rădăcină la înălţimea dij / 2

22

Metoda UPMGAMetoda UPMGAUnweighted Pair Group Method with

Arithmetic mean

23

Ex.2Ex.2

24

Metoda Metoda Neighbor JoiningNeighbor Joining

Deosebiri faţă de UPGMADeosebiri faţă de UPGMA:

- nu aplică ipoteza ceasului molecular

- se creează un arbore fără rădăcină

- presupune “aditivitate”: distanţa între perechi de frunze este suma lungimilor ramurilor care le conectează

Algoritmul Algoritmul – iterativ, asemănător cu UPGMA, cu unele diferenţe (nu trebuie început cu distanţa minimă, sunt alte formule de calcul).

25

PAUZAPAUZA

26