Le but principal de ce travail est d'apporter une synthèse des travaux effectués sur les algorithmes capables d'identifier des groupes de gènes, ou des segments de génomes, communs à différentes espèces. Nous nous limitons à une approche basée sur la modélisation des génomes à l'aide de permutations, où les groupes d'éléments conservés entre différents génomes sont définis par la notion d'intervalles communs. L'étude approfondie de cette problématique nous a aussi permis d'innover et de présenter un nouvel algorithme plus général. Ce travail comporte donc deux aspects principaux, bien que le second soit intercalé dans le premier : une partie synthèse et une partie innovatrice. Après un survol des notions de bases, la partie synthèse présente les premiers algorithmes qui permettent de calculer les intervalles communs, puis l'approche de Bergeron et al. (2005) qui a grandement simplifié les premières solutions. Cette partie comprend aussi les algorithmes des mêmes auteurs qui calculent les intervalles communs dits forts, et une discussion sur les avantages de leur utilisation par rapport aux intervalles communs classiques. La partie innovatrice présente un nouvel algorithme qui généralise deux algorithmes de Bergeron et al. (2005). Nous concluons cette étude en constatant l'extrême simplicité et la grande efficacité, autant théorique que pratique, des plus récents algorithmes et nous croyons peu vraisemblable qu'il soit possible d'en améliorer la performance de façon significative. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithmique, Génomique comparée, Intervalles communs, Permutations.
Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.3228 |
Date | January 2006 |
Creators | Levasseur, André |
Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
Detected Language | French |
Type | Mémoire accepté, NonPeerReviewed |
Format | application/pdf |
Relation | http://www.archipel.uqam.ca/3228/ |
Page generated in 0.0023 seconds