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

La détection des transferts latéraux de gènes : les méthodes et leur application en biolinguistique

Alix Boc

Université du Québec à Montréal

Bif7002 – Séminaire de Bioinformatique

BIF7002 – Séminaire de Bioinformatique Alix Boc

BIF7002 – Séminaire de Bioinformatique 2 Alix Boc

Sommaire

Détection des transferts latéraux de gènes

Description Méthode Exemple

Application à la Biolinguistique

Références

Inf7212 - Introduction aux systèmes informatiques

Bif7002 - Séminaire Bioinformatique 3 Alix Boc

Les arbres phylogénétiques

Inf7212 - Introduction aux systèmes informatiques

Bif7002 - Séminaire Bioinformatique 4 Alix Boc

L’arbre phylogénétique

racine

ancêtres virtuels

espèces

branches

Projet de thèse 5 Alix Boc

Définitions : 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 ali., 1994))• DiAlign (Morgenstern, 1999)• ….

• Distance • Maximum de parcimonie• Maximum de vraisemblance• Approche Bayesienne

Projet de thèse 6 Alix Boc

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 de Bioinformatique 7 Alix Boc

Les modèles en réseau

Définition : 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 et la perte 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

Définition : Le transfert horizontal de gène

BIF7002 – Séminaire de Bioinformatique 9 Alix Boc

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

Hein (1990) and Hein et al. (1995, 1996)

Haseler and Churchill (1993)

Page (1994); Page and Charleston (1998)

Charleston (1998)

Hallet and Lagergren (2001)

Mirkin, Fenner, Galperin and Koonin (2003)

V’yugin, Gelfand and Lyubetsky (2003)

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

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

BIF7002 – Séminaire de Bioinformatique 10 Alix Boc

Notre modèle

Makarenkov et al. (2006)

BIF7002 – Séminaire de Bioinformatique 11 Alix Boc

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 (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 des règles biologiques et maintenir la complexité algorithmique polynomiale (le problème STP a été montré NP-complet par Hein et al., 1996).

BIF7002 – Séminaire de Bioinformatique 12 Alix Boc

Exemples de règles biologiques

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

Règles biologiques : contrainte temporelle

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.

BIF7002 – Séminaire de Bioinformatique 14 Alix Boc

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

A

B

DC

E

A

B

DE

CT1T

La distance topologique de Robinson et Foulds (1981) entre deux arbres

phylogénétiques est égale au nombre d’opérations élémentaires de fusion

et de séparation de noeuds pour transformer un arbre en un autre. Ex : la

distance de Robinson et Foulds entre les arbres T et T1 est égale à 2.

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

jijidQ

Moindres carrés (Least-squares)

Robinson et Foulds

BIF7002 – Séminaire de Bioinformatique 15 Alix Boc

Cette distance mesure la différence topologique entre deux tables de bipartition décrivant deux arbres et elle peut être définit comme suit  :

où d(a,b) est la distance de Hamming entre les vecteurs de bipartition a et b ex: bd(T,T’)= ((2 + 1 + 2) + (2 + 1 + 1))/2 = 4.5.

Distance de bipartition

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

BTb BTaBTa BTb

abdabdMinMinbadbadMinMinbd1

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’

Transfert partiel versus transfert complet

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 16 Alix Boc

Algorithme

BIF7002 – Séminaire de Bioinformatique 17 Alix Boc

Algorithme

Begin

Reconstruction of the species tree T and the gene tree T1

Reestimate the length of each branch in T

While Optimization criterion > 0 loop

Test all possible HGTsCompute the value of the optimization criterionAdd the best HGTReestimate the length of each branch in TCompute the value of the optimization criterion

End Loop

End

BIF7002 – Séminaire de Bioinformatique 18 Alix Boc

Algorithme : exemple

BIF7002 – Séminaire de Bioinformatique 19 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 valeurdes moindres carrés, nouvelle distance de Robinson et Foulds et la nouvelle distance de bipartition.

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

Résultat de HGT-Detection dans la version Web de T-Rex

BIF7002 – Séminaire de Bioinformatique 20 Alix Boc

Validation

BIF7002 – Séminaire de Bioinformatique 21 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%

… …

1. 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

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

n scénarios de réconciliation.

Chaque transfert est pondéré

par le nombre d’apparitions.

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

RÉFÉRENCES

Boc, A. and Makarenkov, V. (2003), New Efficient Algorithm for Detection of Horizontal Gene Transfer Events, Algorithms in Bioinformatics, G.

Benson and R. Page (Eds.), 3rd Workshop on Algorithms in Bioinformatics, Springer-Verlag, pp. 190-201.

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

Evol. 13:873-882.

I. Dyen, I., Kruskal, J.B. and Black, P. (1997) Comparative IE Database Collected by Isidore Dyen,

http://www.ntu.edu.au/education/langs/ielex/IE-RATE1.

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

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. and Philippe, H. (2006). New efficient algorithm for modeling partial and complete gene transfer

scenarios. In V. Batagelj, H.-H. Bock, A. Ferligoj, and A. Ziberna, editors, IFCS 2006, Series: Studies in Classification, Data Analysis, and

Knowledge Organization, Springer Verlag, pages 341--349.

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

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

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

Relationships. BMC Bioinformatics, 9:322.

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

Biol. Rev. 64:202-236.

BIF7002 – Séminaire de Bioinformatique 22 Alix Boc