L'alignement multiple est une opération permettant de mettre en évidence la similarité entre plusieurs séquences. Il est notamment utilisé pour la reconstruction de phylogénies, la recherche de motifs et la prédiction de structures. Cette thèse s'intéresse au développement de nouveaux algorithmes pour ce problème particulièrement difficile, et introduit deux algorithmes progressifs ayant pour point commun de réaliser un alignement multiple par alignements successifs de groupes de séquences.<br />Le premier algorithme, Plasma utilise une méthode de descente, dont chaque itération consiste à réaliser des insertions de colonnes de brèches dans deux alignements multiples à aligner. Le second algorithme, Plasma II , est basé sur le principe de la programmation dynamique. Nous généralisons ici l'algorithme utilisé pour l'alignement de deux séquences, et étendons le cadre de la programmation dynamique `a l'alignement de deux alignements multiples. Cet algorithme ainsi que plusieurs variantes sont intensivement évalués sur les jeux d'essais de Balibase, montrant des résultats encourageants, voire compétitifs, par rapport à certains algorithmes de référence comme Clustal W, tant sur la qualité de l'alignement que sur le temps de calcul.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00352784 |
| Date | 07 March 2008 |
| Creators | Derrien, Vincent |
| Publisher | Université d'Angers |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds