Sagot
Le Jeudi 17 Février 2000 à 14h30
au LRI, Salle 101
(Institut Pasteur et IGM, Marne-la-Vallé)
Une rencontre de l'algorithmique combinatoire et de la
biologie moléculaire
Introduction aux divers problèmes posés et
développement d'un exemple particulier : extraction de motifs
structurés approchés impliqués dans la régulation
des gènes chez les procaryotes
Résumé/Abstract :
L'exposé comportera deux parties. La première effectuera un rapide
survol d'un certain nombre de thèmes de recherche en biologique
moléculaire, notamment en génomique, qui posent des problèmes
intéressants en algorithmique combinatoire.
Un de ces problèmes, celui de l'extraction de motifs structurés
approchés d'un ensemble de chaînes représentant des séquences
biologiques sera ensuite traité en plus de détail. Un motif structuré
est défini comme étant un motif composé d'une suite ordonnée B de p
boîtes chacune d'une certaine longueur, p taux maximum d'erreur (un
par boîte) et p-1 intervalles de distances (entre deux boîtes
consécutives dans la suite). Le contenu de la boîte est inconnu au
départ (on connaît seulement l'alphabet utilisé), le but de
l'algorithme étant de trouver toutes les suites ordonnées B telles que
B possède des occurrences dans un pourcentage minimum des chaînes en
entrée. L'algorithme exploite pour cela une représentation sous forme
d'arbre des suffixes des chaînes [1] [2]. Les motifs structurés sont
des objets simples mais relativement puissants pour la modélisation de
séquences promotrices et/ou de régulation chez les organismes
eucaryotes ou procaryotes. L'exposé se terminera donc par un exemple
d'application de l'algorithme à la prédiction de séquences promotrices
consensus à partir de l'ensemble des séquences non codantes d'une
bactérie [3]. Trois organismes dont les génomes complets ont été
séquencés sont considérés, E. coli, B. subtilis et H. pylori [4] (le
cas de ce dernier est développé en plus de détail). Une discussion
des divers problèmes, algorithmiques, statistiques, biologiques,
demeurés ouverts conclura l'exposé.
Références
[1] M.-F. Sagot (1998) Spelling approximate repeated or common motifs
using a suffix tree. dans C. L. Lucchesi et A. V. Moura, éditeurs,
LATIN'98, Theoretical Informatics, Campinas, Brésil, volume
1380 de Lecture Notes in Computer Science, pages 111-127, Springer
Verlag.
[2] L. Marsan et M.-F. Sagot (2000) Extracting structured motifs using
a suffix tree - Algorithms and application to promoter consensus
identification. Accepté pour être présenté à RECOMB'2000,
Tokyo, Japon. sous presse.
[3] A. Vanet, L. Marsan et M.-F. Sagot (1999) Promoter sequences and
algorithmical methods for identifying them. Research in
Microbiology, 150:779-799.
[4] A. Vanet, L. Marsan, A. Labigne et M.-F. Sagot (2000) Inferring
regulatory elements from a complete genome. An application to the
analysis of Helicobacter pylori sigma80 family of promoter signals.
soumis à Journal of Molecular Biology.