35
Détection des transferts horizontaux de gènes : modèles et algorithmes appliqués à l’évolution des espèces et des langues Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique BIF7002 – Séminaire de Bioinformatique Alix Boc

Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

  • Upload
    heller

  • View
    26

  • Download
    0

Embed Size (px)

DESCRIPTION

Détection des transferts horizontaux de gènes : modèles et algorithmes appliqués à l’évolution des espèces et des langues. Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique. - PowerPoint PPT Presentation

Citation preview

Page 1: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Détection des transferts horizontaux de gènes : modèles et algorithmes appliqués à l’évolution des

espèces et des langues

Alix Boc

Université du Québec à Montréal

Bif7002 – Séminaire de Bioinformatique

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 2: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

BIF7002 – Séminaire de Bioinformatique 2 Alix Boc

Sommaire

Reconstruction des arbres phylogénétiques

Transferts horizontaux de gènes

Détection des transferts de gènes complets

Détection des transferts de gènes partiels

Application en biolinguistique

Travaux futurs

Page 3: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Inf7212 - Introduction aux systèmes informatiques

Bif7002 - Séminaire Bioinformatique Alix Boc

Reconstruction des arbres phylogénétiques

Page 4: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Bif7002 - Séminaire Bioinformatique 4 Alix Boc

L’arbre phylogénétique

Inf7212 - Introduction aux systèmes informatiques

racine

ancêtres virtuels

espèces

branches

Page 5: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Reconstruction d’un arbre phylogénétique

AAATGATCTGCGTCAATATTATAA

GCCTGATCCTCACTACTGTCATCTTAA

ATAGGGCCCGTATTTACCCTATAG

AACTGGTCCACCCTTATACTAAAAGACGCCTCACTAGGAAGCTAA

AACTGATCTGCTTCAATAATTTAA

AAATGATCTGCGTCAATATTA---------------------TAA

GCCTGATCCTCACTA------------------CTGTCATCTTAA

ATA---------------------GGGCCCGTATTTACCCTATAG

AACTGGTCCACCCTTATACTAAAAGACGCCTCACTAGGAAGCTAA

AACTGATCTGCTTCAATAATT---------------------TAA

Alignement de séquences

• ClustalW (Higgins et al., 1994)• DiAlign (Morgenstern, 1999)• ….

• Distances • Maximum de parcimonie• Maximum de vraisemblance• Approche Bayesienne

Bif7002 - Séminaire Bioinformatique 5 Alix Boc

Page 6: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Définitions : reconstruction d’un arbre phylogénétique

Application d’une méthode de reconstruction (méthodes de distances)

0 4 2 4 4

4 0 4 4 2

2 4 0 4 4

4 4 4 0 4

4 2 4 4 0

• Neighbor Joining• ADDTREE• Unweighted Neighbor Joining• Circular order reconstruction• Weighted least-squares• BioNJ• ….

Application d’un modèle d’évolution (méthodes de distances)

• Uncorrected Distances• Jukes Cantor• Tajima-Nei• Kimura 2 parameters• Tamura• Jin-Nei Gamma• ….

Bif7002 - Séminaire Bioinformatique 6 Alix Boc

Page 7: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Bif7002 - Séminaire de Bioinformatique 7 Alix Boc

Problématique

Page 8: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Les modèles en réseau

BIF7002 – Séminaire de Bioinformatique 8 Alix Boc

Le transfert horizontal de gènes (Hallett et Lagergren, 2001, Boc et Makarenkov, 2003)

L’hybridation (Huson, 1998, Bryant et Moulton, 2004)

L’homoplasie et la convergence de gènes (Legendre et Makarenkov, 2002)

La duplication ancestrale et la perte partielle de gènes (Delwiche et Palmer, 1996)

1 2 3

4 5

Certains mécanismes d’évolution ne peuvent être représentés que par des modèles en réseau.

Sp1 Sp2 Sp3Sp4

Root

Page 9: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Le transfert horizontal de gène

BIF7002 – Séminaire de Bioinformatique 9 Alix Boc

Page 10: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Quelques méthodes pour la detection de transferts horizontaux de gènes

Hein (1993); Hein et al. (1995, 1996)

Haseler et Churchill (1993)

Page (1994); Page et Charleston (1998)

Charleston (1998)

Hallett et Lagergren (2001)

Mirkin, Fenner, Galperin et Koonin (2003)

V’yugin, Gelfand et Lyubetsky (2003)

Boc et Makarenkov (2003); Makarenkov et al. (2006)

C. Than, D. Ruths et L. Nakhleh (2008)

BIF7002 – Séminaire de Bioinformatique 10 Alix Boc

Page 11: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Détection des transferts complets

(Boc et al., 2010)

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 12: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Détection des transferts complets

Rhodobacter

Hydrogenovibrio L2

Chromatium L

Thiobacillus fe1

Nitrobacter

Xanthobacter

Rhodobacter

Xanthobacter

Nitrobacter

Chromatium L

Thiobacillus fe1

Hydrogenovibrio L2

Arbre d’espèces Arbre de gène (e.g., rbcL)

Données : arbres phylogénétiques d’espèces et de gène sur le même ensemble d’espèces.

Trouver : nombre minimal de déplacements de sous-arbres dans l’arbre d’espèces permettant de le transformer en l’arbre de gène (=> scénario de réconciliation).

Contraintes : incorporer les règles d’évolution et maintenir la complexité algorithmique polynomiale (le problème SPR, subtree pruning and regrafting, a été montré NP-complet par Hein et al., 1996).

BIF7002 – Séminaire de Bioinformatique 12 Alix Boc

Page 13: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Exemples de règles d’évolution

Root

Root

Lineage 2Lineage 1

LGT1

LGT2

Les transferts sur la même lignée sont interdits.

Les transferts croisés sont interdits.

BIF7002 – Séminaire de Bioinformatique 13 Alix Boc

Le transfert entre les branches (z,w) et (x,y) de l’arbre

d’espèces T sera permis si et seulement si le sous-arbre

regroupant les deux sous-arbres affectés, et enraciné par la

branche (z,b) dans T1, est présent dans l’arbre de gène.

La contrainte de sous-arbres permet de prendre en

compte automatiquement toutes les règles d’évolution.

Règles d’évolution : 2 exemples Contrainte de sous-arbres

Page 14: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Cette dissimilarité mesure la différence topologique entre deux tables de

bipartitions décrivant deux arbres. Elle est définie comme suit  :

où d(a,b) est la distance de Hamming entre les vecteurs de bipartitions a et b

ex: bd(T,T’)= ((2 + 1 + 2) + (2 + 1 + 1))/2 = 4.5.

d(i,j) - distance entre i et j dans l’arbre d’espèces. (i,j) - distance entre i et j dans l’arbre de gène.

Critères d’optimisation

min)),(),(( 2 i j

jijidQ

Moindres carrés

BIF7002 – Séminaire de Bioinformatique 14 Alix Boc

Dissimilarité de bipartitions

2/)))),();,(( ( ))),();,(( (( ''

BTb BTaBTa BTb

abdabdMinMinbadbadMinMinbd

1

3

64

25

4

5

23

16

a d

a 0

1

1

1

0

1

2

b 0

0

1

1

0

1

1

c 0

0

1

0

0

1

2

2

0

1

1

0

1

0 e

1

0

1

0

0

1

0

f

1

0

0

0

1

0

1 d

b c fe

T T’

La distance topologique de Robinson et Foulds (1981)

entre deux arbres phylogénétiques est égale au

nombre minimal d’opérations élémentaires de fusion et

de séparation de noeuds nécessaires pour transformer

un arbre en un autre.

Ex : la distance de Robinson et Foulds entre les arbres

T et T1 est égale à 2.

Robinson et Foulds

A

B

DC

E

A

B

DE

CT1T

Page 15: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Algorithme

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 16: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Algorithme

BIF7002 – Séminaire de Bioinformatique 16 Alix Boc

Inférer les arbres d’espèces et de gène T et T’ sur le même ensemble d’espèces;

Enraciner T et T’ selon des évidences biologiques ou en utilisant un outgroup ou un midpoint;

Si (il existe des sous-arbres identiques avec au moins deux feuilles dans T et T’) alors Réduire la taille du problème en les réduisant à une seule espèce dans T et T’;

Sélectionner le critère d’optimisation : OC = LS (moindres-carrés), RF (distance de Robinson et Foulds), QD (distance des quartets) ou BD (dissimilarité de bipartitions);

Calculer la valeur initiale de OC entre T et T’;T0 = T;k = 1;

Tant que (OC ≠ 0){

Trouver l’ensemble de tous les THG éligibles à l’étape k (noté E_THGk); L’ensemble E_THGk contient seulement les transferts satisfaisant la contrainte de sous-arbre;

Tant que (les THG satisfaisants les conditions des Théorèmes 2 et 1 existent) { Si (il existe des THG appartenant à E_THGk et satisfaisant les conditions du Théorème 2) alors

Effectuer les opérations SPR correspondant à ces THG;

Si (il existe des THG appartenant à E_THGk et satisfaisant les conditions du Théorème 1) alors Effectuer les opérations SPR correspondant à ces THG;

}Effectuer toutes les opérations SPR correspondant aux THG satisfaisant la contrainte de sous-arbres;Calculer la valeur de OC pour identifier la direction de chaque THG;

k = k + 1;Décrémenter la taille du problème en réduisant en une arête tous les sous-arbres identiques dans Tk et T’;Calculer la valeur de OC entre Tk et T’;

}

Éliminer tous les transferts inutiles;

Page 17: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Algorithme : exemple

BIF7002 – Séminaire de Bioinformatique 17 Alix Boc

Scénario trouvé :

1 - transfert de A vers D2 - transfert de E vers B3 - transfert de C vers F

À chaque transfert est associé :• la nouvelle valeur des moindres carrés• la nouvelle distance de Robinson et Foulds• la nouvelle dissimilarité de bipartitions

L’exemple ci-dessous montre comment l’arbre d’espèces T et transformé en l’arbre de gène T1.

A

F

E

D

C

B

A

C

F

E

B

D

A

F

B

E

C

D

A

B

F

C

E

D

1

2 3

Page 18: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Validation

BIF7002 – Séminaire de Bioinformatique 18 Alix Boc

A

F

E

D

C

B

A

E

F

C

D

B

E

F

A

D

C

B

A

B

E

D

C

F

A

F

E

D

C

B

A

F

E

D

C

B

A

F

E

D

C

B

A

F

E

D

C

B80%

60%

HGT-

Detection

Déterminer le pourcentage d’apparition de chaque THG pour plusieurs réplicats de

l’arbre de gène. Les réplicats sont générés à partir des séquences.

arbre d’espèces T

n-1 réplicats de l’arbre de gène.

n scénarios de réconciliation.

La robustesse de chaque transfert est estimée par le nombre d’apparitions

dans la liste de scénarios.

Le premier arbre de gène estla référence T’.

NJ or PhyML

Page 19: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Validation des transferts horizontaux

BIF7002 – Séminaire de Bioinformatique 19 Alix Boc

))/( 100%))(

(( )(_11 1 '

T'Tij

k,ij

NkNjNi

NNN

tσtBSHGT

ijTT

Trois stratégies possibles :

1. Les séquences utilisées pour construire les arbres d’espèces et de gène sont répliquées.

2. Seules les données de séquences utilisées pour construire l’arbre de gène sont répliquées.

3. Le bootstrap des transferts peut être calculé entre deux topologies d’arbres seulement.

sinon. 0,

gène deet espècesd' arbres lespour minimalcoût de scénario le dansest si 1, , )(

'j

Ti

Tktt

k,ijσ

où NT et NT’ sont, respectivement, le nombre d’arbres d’espèces et de gène générés à partir des réplicats et Nij est le nombre de scénarios de coût minimal obtenus quand l’algorithme est appliqué à l’arbre d’espèces Ti et l’arbre de gène Tj’.

Page 20: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Simulations Monte-Carlo

BIF7002 – Séminaire de Bioinformatique 20 Alix Boc

10

15

20

25

30

35

40

45

50

1 2 3 4 5 6 7 8 9 10

Number of transfers

Det

ecti

on r

ate

(%)

RF

QD

LS

BD

LatTrans

a) 60-70% confidence

10

15

20

25

30

35

40

45

50

55

1 2 3 4 5 6 7 8 9 10

Number of transfers

Det

ecti

on r

ate

(%)

RF

QD

LS

BD

LatTrans

b)70-80% confidence

30

35

40

45

50

55

60

65

70

1 2 3 4 5 6 7 8 9 10

Number of transfers

Det

ecti

on r

ate

(%)

RFQD

LSBD

LatTrans

c)80-90% confidence

55

60

65

70

75

80

85

90

1 2 3 4 5 6 7 8 9 10

Number of transfers

Det

ecti

on r

ate

(%)

RF

QD

LS

BD

LatTrans

d) 90-100% confidence

Comparaison de la stratégie basée sur BD avec LatTrans (Hallett et Lagergren, 2001).

Taux de détection en fonction du nombre de transferts.

0

5

10

15

20

25

30

35

40

45

50

1 2 3 4 5 6 7 8 9 10

Number of transfers

Ru

nn

ing

tim

e (s

ec)

a)

0

5

10

15

20

25

30

10 20 30 40 50 60 70 80 90 100

Number of leaves

b)

Ru

nn

ing

tim

e (s

ec)

Page 21: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Exemple : évolution du gène rpl12e (Matte-Tailliez et al., 2002 )

BIF7002 – Séminaire de Bioinformatique 21 Alix Boc

Page 22: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Transferts horizontaux du gène rpl12e

Pyrobaculum aerophilum

Aeropyrum pernix

Sulfolobus solfataricus

Pyrococcus furiosus

Pyrococcus abyssi

Pyrococcus horikoshii

Methanococcus jannaschii

Methanobacterium thermoautotrophicum

Archaeoglobus fulgidus

Methanosarcina barkeri

Haloarcula marismortui

Halobacterium sp.

Thermoplasma acidophilum

Ferroplasma acidarinanus

Pyrobaculum aerophilum

Aeropyrum pernix

Sulfolobus solfataricus

Pyrococcus furiosus

Pyrococcus abyssi

Pyrococcus horikoshii

Methanococcus jannaschii

Methanobacterium thermoautotrophicum

Archaeoglobus fulgidus

Methanosarcina barkeri

Haloarcula marismortui

Halobacterium sp.

Thermoplasma acidophilum

Ferroplasma acidarinanus

Arbre d’espèces Arbre du gène rpl12e

Hypothèse : des transferts du gène rpl12e seraient survenus entre les groupes des Crenarchaeota et des Thermoplasmatales (Matte-Tailliez et al., 2004).

BIF7002 – Séminaire de Bioinformatique 22 Alix Boc

Page 23: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Scénario de réconciliation retrouvé pour le gène rpl12e

Pyrobaculum aerophilum

Aeropyrum pernix

Sulfolobus solfataricus

Pyrococcus furiosus

Pyrococcus abyssi

Pyrococcus horikoshii

Methanococcus jannaschii

Methanobacterium thermoautotrophicum

Archaeoglobus fulgidus

Methanosarcina barkeri

Haloarcula marismortui

Halobacterium sp.

Thermoplasma acidophilum

Ferroplasma acidarinanus

10

100

100

100

30

5594

100

100

100

72

1

3

2

4

5

74%

69%

60%

60%

55%

BIF7002 – Séminaire de Bioinformatique 23 Alix Boc

Page 24: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Détection des transferts partiels

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 25: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Détection des transferts partiels

A B C D E F

Root

A B C D E F

Root

A B C D E F

Root

Partial Transfer Complete Transfer

4

3

2

1

5

4

3

2

1

5

6

7

BIF7002 – Séminaire de Bioinformatique 25 Alix Boc

Transfert partiel versus transfert completContexte d’évolution

Les bactéries et les archées peuvent évoluer dans différentes conditions en s’échangeant des parties gènes, ce qui mène à la création des gènes mosaïques.

Un gène mosaïque est un allèle composé de sous-séquences provenant des espèces ou des souches différentes.

Généralisation : appliqué à l’échelle d’un génome, on peut estimer le taux de transferts horizontaux (complets et partiels) entre les espèces.

Page 26: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Transfert partiel : première approche

BIF7002 – Séminaire de Bioinformatique 26 Alix Boc

Nouvelle fonction d’optimisation qui tient compte de l’existence de plusieurs chemins et du taux de gène transféré.

Formule originale :

Formule modifiée :

min)),(()),()()1((),()(

2

)(

2

)( )(

Sij ijpathk

kij

jbpathk

kjb

Sij ijpathk iapathk

kia

kij jiljilllLQ

où (i,j) est la distance originale entre i et j; est la taille de l’arête k du chemin (ij); est la fraction

de gène transférée (0 ≤ ≤ 1);

kijl

Q (d(i, j )j

(i, j ))2

i

min

Page 27: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Transfert partiel : deuxième approche

BIF7002 – Séminaire de Bioinformatique 27 Alix Boc

A GGTAAAAGACTACCGTCTTACTTACTACACTCCAGATTATGTTGTAAAGGATACTGATATCCTA

B TTCCGTATGACTCCACAACCAGGTGTTCCACCTGAAGAGTGTGCTGCTGCTGTAGCTGCAGAAT

C CAGGTACATGGACAACTGTATGGACTGATGGACTAACAAGTCTTGACCGTTACAAAGGACGTTG

D TATCGAGCCAGTTCCAGGTGAAGATAACCAATACGTTTGTTACGTAGCTTACCCAATCGATCTC

E GAAGGATCAGTTACTAACCTATTCACTTCAATTGTAGGTAACGTATTTGGATTCAAGGCTCTAC

F TACGTCTTGAGGATCTACGTATTCCTCCTGCTTACTGTAAGACTTTCGTAGGACCTCCTCACGG

i Window size w j

Multiple sequence alignment (MSA) of size l

A

FE

DC

B

A

F

EDCB

Tree inference (e.g., using PhyML)

A

FEDCB

Partial gene tree

Species tree

HGT scenario

Set of species X

HGT inference (e.g., using HGT-Detection)

50%

90%

Algorithme

Étape 1. Inférons un arbre phylogénétique T pour un esemble d’espèces X.

Étape 2. Pour i variant de 1 à |l-w|, inférons l’arbre de gène T’ en utilisant les sous-séquences situées dans la fenêtre coulissante entre i et |i+w|. Appliquons HGT-Detection sur T et T’.

Étape 3. Établissons une liste de transferts

prédits. Les transferts entrelacés (Si,j+w .. Sj,j+w) seront considérés comme un unique transfert affectant les sites de i à |j+w|.

Complexité

)))4)_(()(

(( nInfPhyloCs

wlrO

Page 28: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Transfert partiel : simulations Monte-Carlo

BIF7002 – Séminaire de Bioinformatique 28 Alix Boc

0102030405060708090

100

1 2 3 4 5

Number of transfers

HG

T d

etec

tio

n r

ate

(a)

0

10

20

30

40

50

60

1 2 3 4 5

Number of transfers

Fal

se p

osi

tive

(F

P)

rate

(b)

0102030405060708090

100

8 16 32 64

Number of species

Fal

se p

osi

tive

(F

P)

rate

1 2 3 4 5

(d)

0102030405060708090

100

8 16 32 64

Number of species

HG

T d

etec

tio

n r

ate

1 2 3 4 5

(c)

8 16 32 64 8 16 32 64

Taux de détection et taux de faux positifs en fonction du nombre de feuilles et du nombre de transferts horizontaux partiels.

Page 29: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Exemple : Étude de l’évolution du gène rbcL (Delwiche et Palmer, 1996)

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 30: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Exemple : Étude de l’évolution du gène rbcL (Delwiche et Palmer 1996)

BIF7002 – Séminaire de Bioinformatique 30 Alix Boc

Mn oxidizing bacterium (S|85-9a1)

Rhodobacter Sphaeroides IXanthobacter

Alcaligenes 17707 chromosomalAlcaligenes H16 plasmidAlcaligenes H16 chromosomal

Cyanidium

PorphyridiumAntithamnion

Ahnfeltia

Cryptomonas

EctocarpusOlistodiscus

Cylindrotheca

ProchlorococcusHydrogenovibrio L2

Chromatium L

Pseudomonas

Thiobacillus ferrooxidans fe1Nitrobacter

Thiobacillus ferr. 19859Thiobacillus denitrificans I

endosymbiont

AnabaenaSynechococcus

Anacystis

ProchlorothrixSynechocystis

ProchloronCyanophora

ChlorellaBryopsis

ChlamydomonasEuglena

Pyramimonas

ColeochaeteMarchantiaPseudotsuga

NicotianaOryza

-Proteobacteria

b-Proteobacteria

-Proteobacteria

Red and Brown Plastids

Cyanobacteria

g-Proteobacteria

g-Proteobacteria

b-Proteobacteria

-Proteobacteriag-Proteobacteria

Cyanobacteria

Green Plastids

Glaucophyte Plastid

b-Proteobacteria

b-Proteobacteria

Green Type(FORM I)

Red Type (FORM I)

79

83100

100

100

83

94

68

6484

52

100

57

99

66

67

60

99

100

91

99

9750 steps

Hydrogenovibrio L1

Chromatium A46 g-Proteobacteria

64

56100

74

10081

76

98

7342

49

64

65

5132

88

60

22

Les nouveaux algorithmes ont été appliqués à l’étude de l’évolution du gène rbcL initialement décrite dans Delwiche et Palmer (1996).

Page 31: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Résultats : étude de l’évolution du gène rbcL (Delwiche et Palmer 1996)

BIF7002 – Séminaire de Bioinformatique 31 Alix Boc

ProchloronCyanophora

Cyanidium

PorphyridiumAhnfeltiaAnthithamnion

CryptomonasEctocarpusOlistodiscusCylindrotheca

CholrellaBryopsis

ChlamydomonasEuglenaPyramimonas

ColeochaeteMarchantiaPseudotsugaNicotianaOryza

SynechocystisProchlorothrix

Anacystis

SynechococcusAnabaena

Prochlorococus

NitrobacterMn oxidizing bacteriumXanthobacterRhodobacter Sphaeroïde I

Hydrogenovibrio L1

Chromatium A

Thiobacillus ferr. 19859Thiobacillus fe1

PseudomonasendosymbiontThiobacillus denitificans IAlcaligenes 17707 ChromosomalAlcaligenes H16 ChromosomalAlcaligenes H16 plasmid

Green Plastids

Glaucophyte plastid

Cyanobacteria

g-Proteobacteria

b-Proteobacteria

-Proteobacteria

Red & Brown algae

Hydrogenovibrio L2

Chromatium L

1 76.2%

2 81.2%

4

3

5

6

8

61.4%

82.2%

48.5%

42.6%

763.4%

51.5%

9 97%

ProchloronCyanophora

Cyanidium

PorphyridiumAhnfeltiaAnthithamnion

CryptomonasEctocarpusOlistodiscusCylindrotheca

CholrellaBryopsis

ChlamydomonasEuglenaPyramimonas

ColeochaeteMarchantiaPseudotsugaNicotianaOryza

SynechocystisProchlorothrix

Anacystis

SynechococcusAnabaena

Prochlorococus

NitrobacterMn oxidizing bacteriumXanthobacterRhodobacter Sphaeroïde I

Hydrogenovibrio L1

Chromatium A

Thiobacillus ferr. 19859Thiobacillus fe1

PseudomonasendosymbiontThiobacillus denitificans IAlcaligenes 17707 ChromosomalAlcaligenes H16 ChromosomalAlcaligenes H16 plasmid

Green Plastids

Glaucophyte plastid

Cyanobacteria

g-Proteobacteria

b-Proteobacteria

-Proteobacteria

Red & Brown algae

Hydrogenovibrio L2

Chromatium L

52% (31-424)

62%(161-414)

72%(151-532)

72% (21-524)

69% (1-524)

51% (1-484)

61% (231-474) 65%(281-532)

52% (1-214)

58%(101-404)

62% (231-474)

9

1

2

7

5

12

6

11

13

4

10

Détection des THG complets Détection des THG partiels

Page 32: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Conclusions

BIF7002 – Séminaire de Bioinformatique Alix Boc

Page 33: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Conclusions

BIF7002 – Séminaire de Bioinformatique 33 Alix Boc

Dans le cadre de cette recherche doctorale nous avons apporté plusieurs contributions importantes dont :

• un algorithme efficace de détection des transferts horizontaux complets (HGT-Detection).

• une nouvelle mesure de comparaison d’arbres : la dissimilarité de bipartitions.

• un processus de validation des transferts horizontaux.

• deux algorithmes de détection des transferts partiels et d’indentification des gènes mosaïques.

L’étude de l’évolution des langues IE a montré que notre méthode peut être utile dans plusieurs domaines scientifiques.

Les méthodes relatives à la détection des transferts horizontaux de gènes sont librement accessibles à l’adresse URL suivante : www.trex.uqam.ca.

Page 34: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Travaux futurs

BIF7002 – Séminaire de Bioinformatique 34 Alix Boc

Détection des transferts complets

• Mesure de l’impacte des artéfacts de reconstruction et d’autres évènements d’évolution sur la détection des THG.

Détection des transferts partiels

• Développement d’un modèle prenant en compte la duplication ancestrale et la perte partielle de gènes.

• Validation du modèle, par des simulations statistiques, de détection des transferts partiels basé sur l’optimisation par les moindres carrés.

Évolution des langues Indo-Européennes

• Validation manuelle des 1484 arbres de mots.

• Analyse de l’origine des langues Indo-Européennes.

Page 35: Alix Boc Université du Québec à Montréal Bif7002 – Séminaire de Bioinformatique

Références

Boc, A. et Makarenkov, V. (2003) New Efficient Algorithm for Detection of Horizontal Gene Transfer Events. In Benson G. et Page R. (Eds.). WABI 2003,

Algorithms in Bioinformatics, Springer-Verlag, pp. 190-201.

Boc, A., Philippe, H. et Makarenkov, V. (2010a) Inferring and validating horizontal gene transfer events using bipartition dissimilarity. Systematic Biology, 59,

195-211.

Boc, A., A-M. Di Sciullo et V. Makarenkov. (2010b). Classification of the Indo-European languages using a phylogenetic network approach. In  H. Locarek-Junge

et C. Weihs (Eds.). IFCS 2009. Studies in Classification, Data Analysis, and Knowledge Organization, Springer Berlin-Heidelberg-New York, pp. 647-655.

Delwiche, C.F. et Palmer, J. D. (1996) Rampant Horizontal Transfer and Duplication of Rubisco Genes in Eubacteria and Plastids. Mol. Biol. Evol., 13, 873-882.

Dyen, I., Kruskal, J.B. et Black, P. (1997) Comparative IE Database Collected by Isidore Dyen, http://www.ntu.edu.au/education/langs/ielex/IE-RATE1.

Gray, R.D. et Atkinson, Q.D. (2003) Language-tree divergence times support the Anatolian theory of Indo-European origin. Nature, 426, 435-439.

Hallett, M., et Lagergren, J. (2001) Efficient algorithms for lateral gene transfer problems. In El-Mabrouk, N., Lengauer, T. et Sankoff, D. (Eds.), Proceedings of

the fifth annual international conference on research in computational biology, ACM Press, New-York, pp. 149-156.

Levenshtein, V. I. (1966) Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady , 10, 707–710.

Makarenkov,V. (2001),T-Rex: reconstructing and visualizing phylogenetic trees and reticulation networks. Bioinformatics, 17, 664-668.

Makarenkov, V., Boc, A., Delwiche, C.F. et Philippe, H. (2006) New efficient algorithm for modeling partial and complete gene transfer scenarios. In Batagelj, V.,

Bock, H.-H., Ferligoj, A. et Ziberna, A. (Eds.). IFCS 2006, Series: Studies in Classification, Data Analysis, and Knowledge Organization, Springer Verlag, pp.

341-349.

Matte-Tailliez, O., Brochier,C., Forterre, P. et Philippe,H. (2002) Archaeal phylogeny based on ribosomal proteins. Mol. Biol. Evol., 19, 631-639.

Robinson, D.R. et Foulds, L.R. (1981) Comparison of phylogenetic trees. Mathematical Biosciences, 53, 131-147.

Than, C. Ruths, D. et Nakhleh, L. (2008) PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships. BMC

Bioinformatics, 9, 322.

Woese, C.R., Olsen, G., Ibba, M. et Söll,D. (2000) Aminoacyl-tRNA synthetases, the genetic code, and the evolutionary process. Microbiol. Mol. Biol. Rev., 64,

202-236.

BIF7002 – Séminaire de Bioinformatique 35 Alix Boc