|
|
|
Jeudi 15 Septembre 2011 - Raluca Uricaru (INRA/INRIA Rennes) |
|
|
Written by Pierre PETERLONGO
|
Algorithmes de comparaison de génomes appliqués aux génomes bactériens10h30 Salle Aurigny
Avec plus de 1000 génomes complets disponibles (la grande majorité
venant de bactéries), les analyses comparatives de génomes deviennent
indispensables pour leur annotation fonctionnelle, ainsi que pour la
compréhension de leur structure et leur évolution, et s'appliquent par
exemple en phylogénomique ou au design des vaccins.
L'une des approches les plus utilisées pour comparer des génomes est
l’alignement de leurs séquences d'ADN, i.e. alignement de génomes
complets, c'est-à-dire identifier les régions de similarité en
s'affranchissant de toute annotation. Malgré des améliorations
significatives durant les dernières années, des outils performants pour
cette approche ainsi que des méthodes pour l'estimation de la qualité
des résultats qu'elle produit, en particulier sur les génomes
bactériens, restent encore à développer. Outre leurs grandes tailles
qui rendent les solutions classiques basées sur la programmation
dynamique inutilisables, l'alignement de génomes complets pose des
difficultés supplémentaires dues à des mécanismes d’évolution
particuliers: la divergence, le réordonnancent des portions génomiques,
ou l'acquisition de matériel génétique extérieur, qui produit des
régions
non alignables entres les séquences, e.g. transfert horizontal des
gènes, phages. En conséquence, les solutions pour l’alignement de
génomes sont des heuristiques, dont la plus commune est la stratégie
basée sur des ancres.
Cette stratégie commence par identifier un ensemble initial de régions
de similarité (phase 1). Ensuite une phase de chaînage sélectionne un
sous-ensemble (non-chevauchantes et généralement colinéaires) de ces
similarités de poids maximal, nommées ancres (phase 2). Les phases 1 et
2 sont appliquées de manière récursive sur les régions encore
non-alignées (phase 3). La dernière phase consiste en l’application
systématique des outils d’alignement classiques sur toutes les régions
courtes qui n’ont pas encore été alignées.
Ce travail traite plusieurs problèmes liés à l’alignement de génomes
complets dont: l’évaluation de la qualité des résultats produits par
les outils d’alignement et l’amélioration de la stratégie basée sur des
ancres. Premièrement, nous avons créé un protocole pour
évaluer la qualité des résultats d'alignement, comprenant des
mesures de calcul quantitatives et qualitatives, dont certaines basées
sur des connaissances biologiques. Une analyse de la qualité des
alignements produits par deux des principaux outils existants sur des
paires de génomes bactériens intra-espèces révèle leurs limitations:
des similarités non détectées et des portions d’alignement incorrectes.
À partir de ces résultats, qui suggèrent un manque de sensibilité et
spécificité, nous proposons un nouvel outil pour l’alignement deux à
deux de génomes complets, YOC, qui implémente une version
simplifiée de la stratégie basée sur des ancres, contenant seulement
deux phases. Dans la phase 1, YOC améliore la sensibilité en utilisant
comme ancres, pour la première fois dans cette stratégie, des
similarités locales basées sur des graines espacées, capables de
détecter des similarités plus longues dans des régions plus
divergentes. Cette phase est suivie par une méthode de chainage adaptée
aux similarités locales, un nouveau type de chaînage colinéaire,
permettant des chevauchements proportionnels. Nous avons donné une
formulation de ce nouveau problème et réalisé un premier algorithme qui
donne une solution optimale, i.e. est exacte, et s’exécute en temps
quadratique. Nous avons montré que cet algorithme, comparé au chainage
colinéaire classique, améliore les résultats sur des génomes
bactériens, tout en restant efficace en pratique.
Notre nouvel outil, YOC, a été évalué ensemble avec quatre autres
outils d’alignement sur un ensemble de données composé de 694
couples de génomes bactériens intra-espèces. Les résultats montrent
que YOC améliore les cas divergents en détectant des similarités plus
distantes et en évitant les régions mal alignées. En conclusion, YOC
semble être plus facile à appliquer de manière automatique et
systématique, parce qu’il nécessite pas un post-traitement des régions
mal alignées, ni un paramétrage complexe.
Mots-clés
génomique comparative, alignement des génomes complets, stratégie basée
sur des ancres, graines espacées, chaînage des fragments, programmation
dynamique, graphe trapézoïdal
|
|
