inria-00001036, version 1
Recherches de motifs et de similarités en bioinformatique : modélisations, solutions logicielles et matérielles
Mathieu Giraud 1Laurent Noé
2Gregory Kucherov 2Dominique Lavenier
a, 1
MajecSTIC 2005 : Manifestation des Jeunes Chercheurs francophones dans les domaines des STIC (2005) 18--37
Résumé : Ce tutoriel expose certains problèmes fondamentaux en algorithmique du texte pour la bioinformatique, leurs solutions actuelles ainsi que quelques perspectives de recherche. Après une introduction expliquant pourquoi la bioinformatique s'intéresse aux séquences de caractères et d'où provient le problème de recherche de motifs, nous présentons de façon progressive différentes modélisations des motifs (partie 2). Un motif peut être un simple mot ou un ensemble de mots que l'on recherche de manière exacte ou approchée, par similarités. Plus généralement, on définit un motif comme un langage pouvant se situer à différents niveaux de la hiérarchie de Chomsky et formalisable par des structures telles que des grammaires ou des automates. Le tutoriel se poursuit par la présentation des méthodes logicielles ou matérielles qui résolvent les recherches de motifs selon la modélisation choisie (partie 3). Ces algorithmes s'effectuent avec ou sans pré-traitements du motif ou de la banque de séquences. Quand les motifs deviennent complexes, la recherche par balayage devient la seule solution possible, que cela soit par heuristique ou de manière exacte. Nous évoquerons aussi les architectures spécialisées destinées à traiter de grandes quantités de données : ces machines doivent équilibrer puissance de calcul et accès aux données.
- a – CNRS
- 1 : SYMBIOSE (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
- 2 : ADAGE (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Domaine : Sciences du Vivant/Biochimie, Biologie Moléculaire/Génomique, Transcriptomique et Protéomique
- Mots-clés : recherche de motifs – bioinformatique – distance d'édition – langages – automates – programmation dynamique – heuristiques à base de graines – architectures – FPGA
- inria-00001036, version 1
- http://hal.inria.fr/inria-00001036
- oai:hal.inria.fr:inria-00001036
- Contributeur : Elodie Foret
- Soumis le : Mardi 17 Janvier 2006, 09:53:14
- Dernière modification le : Mardi 23 Janvier 2007, 09:41:50