Home
Scientific Axes
Members
Publications
Software
Collaborations
Activity Report
Seminars
Positions





Jeudi 15 Septembre 2011 - Raluca Uricaru (INRA/INRIA Rennes) Print
Written by Pierre PETERLONGO   

Algorithmes de comparaison de génomes appliqués aux génomes bactériens

10h30 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

 
< Prev   Next >

Symbiose Project Team - INRIA/Irisa © 2007 - 2008