Bio-informatica Boom constructie. Peter De Rijk

Bio-informatica Boom constructie Peter De Rijk

8

Waarom boomconstructie ●

Evolutionaire analyse: verwantschap tussen genen en/of species ●

Studie oorsprong en divergentietijden –

● ●

Evolutiegeschiedenis Testen van evolutionaire hypothesen –

● ● ● ●

–

bv. divergentie mens-mensapen, oorspong van het HIV,...

convergentie, co-evoluties, geografische verspreiding, ...

Documentatie van de evolutie van genfamilies (door bv. genduplicaties) achterhalen recombinatie en/of horizontale gentransfer Similariteitsgroepen Verspreiding van ziekten ( epidemiologie)

Maar ook ● ● ●

Alignatie van sequenties (clustering methoden) Micro-array: clustering van genen met gelijkaardige expressie .....

Moleculaire fylogenie Achterhalen evolutionaire geschiedenis op basis van moleculen

Sequentie Sequentiedatabases databases Zoeken op annotatie: Entrez, SRS

Zoeken op sequentie: FASTA, (PSI) BLAST

Homologe Homologesequenties sequenties Automatische alignatie: ClustalW, Dialign, ...

Sequentie Sequentiealignement alignement Controle en finetuning alignment: Bioedit, DCSE, ...

Gecontroleerd Gecontroleerdsequentie sequentiealignement alignement Boomconstructie: Phylip, ...

Phylogenetische Phylogenetischebomen bomen

Fylogenetische bomen ●

Wat? –

●

– – ●

Operational Taxonomic Units Uiteinden (leaves) van de boom bv. Sequenties, taxa, species

Soorten –

F

Ongewortelde boom A

Oorsprong (root) is ongeweten, kan op verschillende plaatsen liggen

B

Gewortelde bomen ●

●

C

De oorsprong wordt aangeduid (“stam” helemaal links)

D E

Boom constructie –

E

B

Ongewortelde bomen ●

–

D

Grafische voorstelling (topologie) van evolutionaire verwantschappen tussen Otu

Otu –

C

A

Vinden van de boom die het best in overeenstemming is met de gegevens van de eindpunten

F

Gewortelde boom

Boomconstructie methoden Karakter gebaseerd

Niet karakter gebaseerd

Expliciet evolutiemodel

“Maximum likelihood”

Afstandsmethoden

Geen expliciet evolutiemodel

Maximale spaarzaamheid

Maximale spaarzaamheid ●

Basis –

●

Beste boom = degene die het minste aantal mutaties vereist

Methode 1.Onderzoek (in theorie) alle mogelijke topologieën (bomen) 2.Reconstrueer voor elke mogelijke topologie de ancestrale sequenties (op de knooppunten) 3.Tel het minimum aantal substituties nodig voor elke topologie 4.Kies de topologie met minste mutaties

Methode

1

2

3

4

Aantal topologieën



Probleem   

Voor 4 sequenties slechts 3 (ongewortelde) topologieën Aantal stijgt spectaculair bij meer sequenties 'exhaustive search' (alle topologieën bestuderen) is praktisch slechts mogelijk bij zeer klein aantal sequenties (~10)

Aantal topologieën OTU's Gewortelde Ongewortelde bomen bomen 3 3 1 4 15 3 5 105 15 6 954 105 7 10395 954 8 135135 10395 9 2027025 135135

Heuristiek

Heuristiek 

Stepwise addition   



Telkens toevoegen nieuwe taak aan “beste” boom tot dan Heuristiek beperkt aantal te onderzoeken topologieën Meest spaarzame boom wordt niet altijd gevonden

Branch swapping 



Testen van een aantal alternatieve topologieën door boom in stukken te breken en in een andere configuratie terug in elkaar te zetten Vind soms betere boom die gemist werd door stepwise addition

Branch swapping

Informativiteit Enkel posities waarin verschillende basen 2 keer voorkomen zijn fylogenetisch informatief

Consensus bomen A B C D E F

of

A C B D E F

?

A B C D E F Consensus boom

Vaak verschillende bomen met eenzelfde aantal substituties → Consensus boom –

●

Voor groepen waar de vertakkingsvolgorde verschilt in verschillende “optimale” bomen, wordt een multifurcatie gebruikt

Taklengte

–

Bomen vaak zonder taklengten ● ● ●

Dikwijls niet mogelijk te beslissen in welke tak mutatie zit Aantal mutaties per tak vaak niet te bepalen Taklengten niet relevant

Maximale spaarzaamheid Conclusies ● ●

Klassieke methode Voordelen – –

●

Alternatieve topologieën Geen reductie van sequentie informatie; volledige info wordt gebruikt.

Nadelen – – –

Traag, zeker voor grote datasets Geen correctie voor meervoudige mutaties Gevoelig voor ongelijke evolutiesnelheden in verschillende takken

Afstandsmethoden ●

Basis – – –

Informatie reduceren vóór het maken van boom Dissimilariteiten tussen alle mogelijke paren sequenties: fractie geobserveerde verschillen Omzetting naar evolutionaire afstanden via alignement ● ●

– ●

Schatting aantal werkelijk gebeurde mutaties Correctie voor meervoudige- en terugmutaties

Zoeken naar topologie die in overeenstemming is met deze afstanden

“Distance matrix” methoden –

Afstanden meestal in de vorm van een matrix

Evolutionaire afstanden: RNA/DNA ●

Ribosomaal RNA – –

Niet proteine coderend Wordt erg veel voor evolutionaire studies gebruikt ● ●

●

Komt in alles voor (behalve virussen) Sterk geconserveerde en ook meer divergente delen Geen laterale gen transfer

Evolutionaire afstanden: RNA/DNA 1 UCAAGUCAGGUUCGA 2 UCCAGUUAGACUCGA 3 UUCAAUCAGGCCCGA d = -3/4 ln(1-4/3 f)



1 2 2 4/15=0.267 3 5/15=0.333 5/15=0.333

2 3

1 0.328 0.440

2

3

3

0.440

Correcties volgens substitutiemodel ➔

b.v. Jukes & Cantor voor meervoudige mutaties in DNA sequenties (zie verder)

Substitutie modellen 

Substitutiemodel 

 

Beschrijft de kans dat een nucleotide (of aminozuur) wordt vervangen (substitutie) door een ander nucleotide (of aminozuur) Kan voorgesteld worden in een matrix (zie bv. onder) Voor proteïne sequenties, zie score matrices

● ●

●

πA,πG,πC,πT = frequentie (hoeveelheid) van A, G, C en T a,b,c,...,l = snelheid waarmee elk nucleotide kan vervangen worden door elk andere nucleotide Time reversible: als g=a, h=b, j=d, k=e en l=f

Jukes & Cantor substitutiemodel –

Premissen – – – –

–

Alle substituties zijn onafhankelijk van elkaar Alle posities hebben dezelfde kans om substitutie te ondergaan Elk nucleotide heeft evenveel kans om te muteren naar eender welk ander nucleotide Inserties of deleties worden niet in rekening gebracht

Matrix – –

πA = πG = πC = πT a=b=c=d=e=f=g=h=i=j=k=l

Jukes & Cantor substitutiemodel 3 4 d JC =− ln (1− f ) 4 3 Jukes&Cantor

1.4

evolutionaire afstand d Fractie verwachte verschillen

1.2 Geen correctie

1

Gecorrigeerd voor meervoudige mutaties op dezelfde positie → evolutionaire afstand > fractie verschillen Niet gecorrigeerd → evolutionaire afstand = fractie verschillen

0.8

0.6

0.4

0.2

0.25

0.5

0.75

Dissimilariteit f Fractie geobserveerde verschillen

1

2 Willekeurige nucleotide sequenties → ~ 25% identiteit verwacht → fractie verschillen ~ 75% Zijn niet verwant → evolutionaire afstand oneindig

Andere substitutie modellen –

Kimura's 2 parameter model ●

–

Transitie & transversie/verschillende mutatie rates

Complexere modellen, b.v. 12 parameter model ● ●

●

Zeer complex mathematisch geven niet echt betere resultaten (veel meer assumpties nodig) Niet courant gebruikt

Ongelijke substitutie snelheden ●

Problemen bij Jukes & Cantor: – –

Afwijkingen naar hogere GC gehaltes Ongelijke substitutiesnelheden van verschillende posities in een sequentie-alignement ●

● ●

Geconserveerde stukken (functionele of structurele constraints) vs. neutrale evolutie Onderschatting van grote evolutionaire afstanden Neiging om artificeel lange takken te clusteren –

●

ver uit elkaar gelegen sequenties lijken dichter

Correcties hiervoor leveren vaak betrouwbaardere bomen op

Ongelijke substitutiesnelheden 20 substituties bij identieke substitutie rate op alle posities

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Groen = terugmutatie Rood = mutatie

19

20

19

20

Substituties: gebeurd = 20 afstand = 20/20 = 1 Geobserveerd = 14-3 = 11 afstand = 11/20 = 0.55

20 substituties bij verschillende substitutie rates

1

2

3

4

5

6

7

8

9

10

11

Substituties: gebeurd = 20 Geobserveerd = 9-1 = 8

12

13

14

15

16

17

18

afstand = 20/20 = 1 afstand = 8/20 = 0.4

Gamma distributie –

– – –

Gamma distributie kan gebruikt worden als model voor de heterogeneiteit in substitutie snelheid Welke distributie (parameter α) hangt af van de dataset In principe kan/moet je α berekenen op basis van het alignement wel vaak bv. α=1 als default genomen

bv. α=20 → meeste posities substitutie rate ~ 1 → weinig posities met veel grotere of kleinere r bv. α=1 → meeste posities substitutie rate bijna 0 → andere r komen ook veel voor

Ongelijke substitutiesnelheden 3 4 −1α d JN = α((1− f ) −1) 4 3 1.4

Jin&Nei

3 4 d JC =− ln (1− f ) 4 3 Jukes&Cantor

●

Methode van Jin &Nei –

evolutionaire afstand d Fractie verwachte verschillen

1.2 Geen correctie

1

0.8

–

0.6

–

0.4

0.2

0.25

0.5

0.75

Dissimilariteit f Fractie geobserveerde verschillen

1

~ Jukes&Cantor, maar houdt rekening met ongelijke substitutie snelheden Welke gamma distributie → Parameter α Aanpassing evolutionaire afstand nog groter (J&C is nog altijd onderschatting)

Boom reconstructie ●

Clustering –

Oudste methode ●

●

– –

Sequentiele clustering van meest verwante groepen in de afstands matrix Herberekening matrix

Eenvoudig te implementeren snel

Clustering   

Groepeer OTU's met kleinste onderlinge afstand in matrix A,B,C,D,E : verschillende taxa A & B liggen het dichtste bij elkaar

B C D E F

A 2 4 6 6 8

B

C

D

E

4 6 6 8

6 6 8

4 8

8

1 A 1 B

Clustering 

Bereken nieuwe afstanden tussen groep AB en andere OTU's

1 A 1 B

d(AB)C = (dAC+dBC)/2 = 4 ... 

Groepeer OTU's met kleinste afstand

C D E F

(AB) 4 6 6 8

C

D

E

6 6 8

4 8

8

2

D

2

E

Clustering 

Bereken nieuwe afstanden tussen groep AB en andere OTU's

d(DE)(AB) = (dD(AB)+dE(AB))/2 = 6 ... 

Groepeer OTU's met kleinste afstand (AB) C 4 (DE) 6 F 8

C

(DE)

6 8

8

1 A 1 B

1 2

C

2

D

2

E

Clustering 

Bereken nieuwe afstanden tussen groep AB en andere OTU's

d(ABC)(DE) = (d(AB)(DE)+dC(DE))/2 = 6 ... 

1 1

Groepeer OTU's met kleinste afstand

1 (ABC) (DE) (DE) 6 F 8 8

1 A 1 B 2

C

2

D

2

E

Clustering 

Bereken nieuwe afstanden tussen groep AB en andere OTU's

1

d(ABC)(DE) = (d(AB)(DE)+dC(DE))/2 = 6 ... 

Groepeer OTU's met kleinste afstand

1 1 1



(ABC),(DE) F 8 Resultaat ➔ ➔

Gewortelde boom Afstand van wortel tot alle eindnodes is dezelfde

1 A 1 B

4

2

C

2

D

2

E F

Boom reconstructie ●

Clustering verschillende methoden –

WPGMA (in voorbeeld) ● ●

–

Weighted Pair Group Method with Arithmetic mean Bij samengestelde groepen → gemiddelde van gemiddelden

UPGMA ●

●

Unweighted Pair Group Method with Arithmetic mean Bij samengestelde groepen → gemiddelde genomen van de afstanden tot alle taxa in de groep

Boom reconstructie ●

Clustering ●

Veronderstelt (zou correct zijn voor) ultrametrische data –

●

Ultrametrische data = data met devolgende eigenschappen ● Additief → distance tussen twee taxa = som van de lengtes van alle takken tussen twee taxa ● Gelijke evolutie snelheid in alle takken → er kan een wortel gevonden worden zodanig dat alle taxa even ver van deze wortel verwijderd zijn →

Komt in de praktijk (matrix van afstanden berekend op basis van bv. moleculaire data) niet echt voor – – – –

(Meervoudige) mutaties op dezelfde posities Fouten in model/correcties Stochastische verschillen in bv. evolutiesnelheid Verschillen in evolutiesnelheid

Additieve methoden –

Additieve data ●

●

Distance tussen twee taxa = som van de lengtes van alle takken tussen twee taxa In realiteit zijn matrices zelden additief – –

–

Stochastische fouten Fouten in het model

Methoden ●

Transformed distance –

●

omzetting naar ultrametrische data, clustering

Fitch-Margoliash –

–

Boom met minimale error bij het fitten van experimenteel bepaalde afstanden met deze berekend op basis van de boom tijdsintensief

Neigbor-joining ●

Methode ● ●

Vergelijkbaar met cluster analyse Minimum in Q-matrix (gebaseerd op distance matrix) –

●

Meest nabije nodes (in Q-matrix) worden gelinkt – –

●

Afstand tussen elk paar nodes wordt aangepast op basis van de afstand ten opzichte van alle andere nodes Vervangen door een ancestrale node Afstanden van alle nodes to nieuwe node berekend

Herhalen → Ongewortelde boom –

Gebruik van een “outgroup” om de wortel te bepalen

...

Neigbor-joining ●

Voordelen – – –

●

Zeer snel, grote datasets – goede resultaten Minder gevoelig voor ongelijke evolutiesnelheden in verschillende takken van de boom Kan ongelijke taklengtes hebben

Nadelen – –

Slechts 1 resultaat → kan geen suboptimale/alternatieve resultaten terug geven Ongewortelde bomen

Afstandsmethoden ●

Voordelen – – – –

●

Snel Laten verwerking grote datasets toe Correctie voor meervoudige - en terugmutaties Gemakkelijker stabiliteit te testen bij veranderende datasets

Nadelen – –

–

sterke reductie fylogenetische informatie sommige methoden (zoals bv. neighbor-joining) geven slechts 1 topologie en laten niet toe om alternatieve topologieën te onderzoeken Soms sterke afhankelijkheid van het gevolgde substitutiemodel

Maximum likelihood ●

Basis –

– – – –

De kans dat het door een boomtopologie gesuggereerde evolutieschema heeft geleid tot de sequenties waarover men beschikt Gebaseerd op een bepaald substitutiemodel Voor elke mogelijke boomtopologie Elke positie in het alignement wordt afzonderlijk geevalueerd Gesofistikeerde statistische methoden

Maximum likelihood ●

Voordelen – – – – – –

●

Statistisch zeer goed onderbouwd Mogelijk om te corrigeren voor meervoudige - en terugmutaties Gebruikt volledige sequentie informatie Mogelijk om alternatieve boomtopologieën te onderzoeken Robuust tegen foute assumpties in evolutie model Dikwijls een lagere variantie dan de andere methoden

Nadelen – –

Zeer traag Ook afhankelijk van het gevolgde substitutiemodel

Betrouwbaarheid van evolutiebomen ●

Factoren die boomconstructie beinvloeden – –

Stochastische (toevallige) fouten Systematische fouten ●

– – – –

versnelde evolutie in verschillende takken van de boom (ongelijke evolutiesnelheden) ongelijke substitutiesnelheden afwijkingen in de sequentie-inhoud 'gene tree' is niet gelijk aan 'species tree' ● ● ●

–

verkeerde veronderstellingen maakt. b.v. door het Jukes en Cantor model toe te passen om sequenties met zeer verschillende GC inhoud.

horizontale gen-transfer convergente evolutie Afhankelijk van gebruikte molecule om boom op te bouwen

Enz ...

Bootstrap analyse – ●

Geeft een idee van de betrouwbaarheid v.d. boom

Methode –

Een (groot) aantal datasets wordt geconstrueerd op basis van de originele dataset ●

●

Random selectie van posities in originele alignement tot een even groot aantal posities bereikt wordt 1 positie kan dus meerdere keren voor komen in elke nieuwe dataset, sommige posities komen niet voor

2 3 4 5

1 5 3 4 5

4

2 4

2 2 5 1 3

A G G C T A C G G T A G G C -

A T G C T A T G G T A - G C -

C G A G C G C A C G C G A G C

G G T A G C C T A G G G - A G

1

2 1

...

Bootstrap analyse – –

Op basis van elke nieuwe dataset wordt een boom geconstrueerd Op elke tak van de originele boom wordt aangeduid hoe dikwijls deze groep werd teruggevonden in alle aangemaakte bomen → groepen die in vrijwel alle bomen teruggevonden zijn veel betrouwbaarder

Bootstrap analyse ●

Resultaten – – – –

Idee van de betrouwbaarheid van verschillende takken in de boom Geeft enkel informatie over stochastische fouten “Sample size” moet groot zijn Zijn niet altijd betekenisvol o.w.v. ● ●

Systematische fouten worden er niet uitgehaald Sommige afwijkingen in de dataset –

bv. twee sequenties samen clusteren omwille van een gemeenschappelijke afwijking in GC gehalte

Conclusies ●

Vergelijking van resultaten op basis van – – –

●

Verschillende methoden Verschillende molecules Verschillende datasets

Boomconstructie Programma's –

Phylip ●

–

Klassieker, vele methoden

Grote lijst (193 programma's, 18 servers) ●

http://evolution.genetics.washington.edu/phylip/soft ware.html