Un nouvel algorithme pour le calcul des générateurs des intervalles communs de K permutations

Levasseur, André (2006). « Un nouvel algorithme pour le calcul des générateurs des intervalles communs de K permutations » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (2MB)

Résumé

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.

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Bergeron, Anne
Mots-clés ou Sujets:	Algorithmique, Permutation (Mathématiques), Génomique, Intervalle commun
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	RB Service des bibliothèques
Date de dépôt:	12 août 2010 18:42
Dernière modification:	26 sept. 2018 10:11
Adresse URL :	http://archipel.uqam.ca/id/eprint/3228

Modifier les métadonnées (propriétaire du document)

Statistiques