Filtrage de séquences d'ADN pour la recherche de longues répétitions multiples

(IRISA)

L'un des travaux clef de la génomique moléculaire est la recherche de longues répétitions approchées multiples. Or, les algorithmes permettant leur détection sont trop lents pour être appliqués aux génomes entiers.

Nous proposons dans cette thèse des filtres supprimant rapidement et efficacement, parmi des textes représentant des séquences d'ADN, de longues portions ne pouvant faire partie de répétitions. Les données filtrées sont alors limitées en majorité aux portions pertinentes, c'est-à-dire celles contenant des répétitions.

Les filtres proposés appliquent une condition nécessaire aux séquences pour n'en conserver que les portions la respectant. Nous avons travaillé sur la création de conditions de filtrage efficaces.

L'application de ces conditions de filtrage conduit à de très bons résultats en pratique. Le temps utilisé par des algorithmiques de recherche de répétitions peut être réduit de plusieurs ordres de grandeur en utilisant les filtres proposés.

Durant cet exposé je présenterai l'un des filtres créés, appelé Ed'Nimbus,ainsi que certaines structures de données motivées par ces travaux.