Doctorat
Equipe : Bioinformatique
Aspects Algorithmiques des Réarrangements Génomiques : Duplications et ordres partiels
Début le 01/10/2006
Direction : DENISE, Alain
[VIALETTE, M. Stéphane]
Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI
Soutenue le 06/11/2009 devant le jury composé de :
Philippe DAGUE
Alain DENISE
Sylvie HAMEL
Bernard MORET
Marie-France SAGOT
Stéphane VIALETTE
Activités de recherche :
- Algorithmique
- Bioinformatique
- Combinatoire
- Complexité
Résumé :
La génomique comparative est une discipline importante pour la compréhension de l'évolution du vivant. Différentes méthodes de comparaison de génomes existent, nous nous intéressons ici en particulier au calcul de 3 mesures de (dis)similarités : les nombres d'adjacences, de points de cassure et d'intervalles communs. En présence de gènes dupliqués ou lorsque l'ordre des gènes n'est que partiellement connu, calculer ces mesures est un problème connu pour être NP-difficile.
D'une part, nous désirons calculer les nombres d'adjacences et de points de cassures pour trois modèles (exemplaire, maximum et le modèle intermédiaire introduit dans cette étude) entre deux génomes possédant des duplications. Dans le but d'obtenir des résultats exacts, nous utilisons dans cette thèse une approche par programmation pseudo-booléenne. Après expérimentation sur 12 génomes de ?-protéobactéries, nous obtenons assez de résultats pour évaluer les différentes combinaisons mesure/modèle. De plus, nous proposons et évaluons (à l'aide des précédents résultats) une famille d'heuristiques basée sur une recherche de plus longue sous-séquence commune qui donne de très bons résultats sur ces données.
Parallèlement à cela, nous prouvons que pour différents problèmes de calcul de mesures entre deux génomes avec duplication, aucune approximation en temps polynomial n'est possible.
D'autre part, nous mettons en place une approche pseudo-booléenne pour calculer les nombres d'adjacences et d'intervalles communs entre deux génomes partiellement ordonnées. À l'aide de près de 800 génomes simulés, nous étudions l'influence de paramètres inhérents aux ordres partiels et nous comparons les deux mesures étudiées.
Pour en savoir plus: http://www.lri.fr/~thevenin/
