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
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
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
Inf7212 - Introduction aux systèmes informatiques
Bif7002 - Séminaire Bioinformatique Alix Boc
Reconstruction des arbres phylogénétiques
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
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
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
Bif7002 - Séminaire de Bioinformatique 7 Alix Boc
Problématique
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
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è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
Détection des transferts complets
(Boc et al., 2010)
BIF7002 – Séminaire de Bioinformatique 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 (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
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
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
Algorithme
BIF7002 – Séminaire de Bioinformatique Alix Boc
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;
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
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
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’.
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)
Exemple : évolution du gène rpl12e (Matte-Tailliez et al., 2002 )
BIF7002 – Séminaire de Bioinformatique 21 Alix Boc
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
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
Détection des transferts partiels
BIF7002 – Séminaire de Bioinformatique Alix Boc
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.
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
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
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.
Exemple : Étude de l’évolution du gène rbcL (Delwiche et Palmer, 1996)
BIF7002 – Séminaire de Bioinformatique Alix Boc
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).
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
Conclusions
BIF7002 – Séminaire de Bioinformatique Alix Boc
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.
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.
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