Extraction de Motifs Communs dans un Ensemble de Séquences

L’ARN

   Les molécules d’ARN diffèrent des molécules d’ADN en quelques points seulement. Principalement, l’ARN est constitué d’une seule chaîne de nucléotides, plutôt que d’une chaîne double. En outre, la Thymine est remplacée par l’Uracile, qui est également une pyrimidine. La structure bio-chimique de l’Uracile est très proche de celle de la Thymine, ce qui lui permet de s’apparier à l’Adénine. Il existe plusieurs type d’ADN ; la distinction est faite selon le rôle de la molécule. Il est question d’ARN messager (ARNm), d’ARN de transfert (ARNt), . . . De même que l’ADN correspond au support du code génétique, l’ARN peut être décrit comme étant une copie locale de ce code. En effet, l’ARN est une réplication de l’ADN. Rappelons que l’ADN possède une structure en double hélice, dans laquelle les brins sont complémentaires. Par conséquent, la connaissance de l’un des deux brins, apporte la connaissance du second. Ce même principe de complémentarité est présent dans l’ARN. En effet, l’ARN est synthétisé à partir du complémentaire d’un brin d’ADN, en substituant juste l’uracile à la thymine. Ce phénomène est appelé la transcription. Cette copie est ensuite épissée (i.e., certaines portions du brin d’ARN sont enlevées). Si le rôle de ce brin d’ARN porte l’information sur la synthèse d’une protéine, il est appelé ARNm et est traduit sous forme de protéine (cf. Section 1.1.3 – page suivante).

Les origines de l’évolution

   Chaque espèce possède son propre code génétique, ses propres structures moléculaires. Mais au sein même d’une même espèce, il existe aussi beaucoup de différences. Celles-ci sont dues à plusieurs facteurs. Sans être exhaustif, citons la reproduction, qui permet un brassage du matériel génétique, ainsi que les étapes de transcription et de traduction (cf. Section 1.1.2 – page 13). En effet, lors de ces étapes, il peut se produire des erreurs, et il arrive que celles-ci n’engendrent pas (ou peu) de conséquences sur les molécules produites. Ces erreurs, lorsqu’elles sont bénignes peuvent être transmises, et contribuent à la diversité des espèces, et à l’évolution. Dans le cas contraire, les molécules produites sont généralement détruites par la cellule. Ces phénomènes sont également à l’origine de diverses pathologies. Dans le cas de l’ADN, de l’ARN et des protéines, ces erreurs sont appelées mutations. Il est possible de distinguer trois types de mutations : les substitutions, les suppressions, et les insertions de bases. En général, les substitutions sont moins dommageables que les insertions ou les suppressions [56]. Elles sont aussi les plus nombreuses ; et parmi les substitutions, il est assez fréquent que celles-ci conservent les propriétés physico-chimiques de la macromolécule. Il arrive néanmoins que de petites mutations aient des conséquences importantes. Citons pour exemple le cas de la mucoviscidose [56] ; la mutation la plus fréquente est une suppression de trois nucléotides aboutissant à l’élimination de la Phénylalanine en position 508 de la protéine CFTR (de l’anglais « Cystic Fibrosis Transmembrane Conductance Regulator »). Les mutations se produisent principalement lors de la fabrication d’un organisme (protéine, cellules, . . .). Quand cela se produit, le plus souvent, la mutation induit alors la destruction de cet organisme, par des mécanismes de retro-contrôle (ce phénomène est extrêmement fréquent). Ces mutations sont alors qualifiées comme étant non-viable. Cependant, les mutations qui portent sur les 85% de gênes « inutiles », généralement désignées comme des régions non codantes, sont souvent viables. Ce qui induit que dans l’ADN, les régions codantes3 pour des fonctions importantes (voire vitales) pour l’organisme sont souvent beaucoup mieux conservées d’un individu à l’autre que des régions non codantes. . .

E. coli et autres organismes

   L’étude du génome et du protéome des organismes permet d’appréhender le fonctionnement de certaines maladies. De plus en plus d’organismes sont séquencés, notamment dans le règne des procaryotes (organismes unicellulaires sans noyau individualisé). En effet, leur génome est plus petit que celui des eucaryotes (organismes unicellulaires ou multicellulaires à noyau individualisé). En particulier, citons la bactérie Escherichia coli (cf. Figure 1.6). Il s’agit de parasites du tube digestif présents chez l’homme et chez l’animal. Ces bactéries sont le plus souvent inoffensives, mais ont la faculté de muter et d’acquérir naturellement des gènes les rendant virulentes pour les différentes espèces qui leur servent d’hôtes. Ces phénomènes permettent l’émergence régulière de nouvelles variétés de bacilles pathogènes adaptés à leurs hôtes et responsables de pathologies spécifiques [116] (diarrhées, infections urinaires, septicémies, méningites, . . .). Cette bactérie est l’une des plus étudiées, et est souvent utilisée comme modèle afin de vérifier la pertinence de tel ou tel algorithme. D’autres organismes sont également étudiés et utilisés comme références, tels que la levure Saccharomyces cerevisiæ (cf. Figure 1.6), le nématode transparent Cænorhabditis elegans, la mauvaise herbe Arabidopsis thaliana, le diptère Drosophila melanogaster ou encore la souris Mus musculus. Tous ces organismes offrent l’avantage d’être faciles à reproduire et en grand nombre. En outre, leur cycle de vie est bref et leur génome est de petite taille (à l’exception de la souris).

Les algorithmes Probabilistes à base de fouille 

   GIBBS [81] utilise un principe d’échantillonnage afin d’évaluer la pertinence et de raffiner des motifs sélectionnés au hasard. Cette méthode traite le problème EMq. Bien que la longueur des motifs doit être fixée a priori, sa bonne vitesse d’exécution permet d’exécuter l’algorithme plusieurs fois en faisant varier la longueur. Les résultats obtenus par cette méthode sont généralement très bons, surtout lorsque les séquences sont globalement éloignées. Toutefois si les séquences sont globalement toutes très proches les unes des autres, alors la qualité et la pertinence des résultats risquent fort d’en souffrir. Les motifs renvoyés classent cette méthode dans la catégorie C. PROJECTION [21] a été créé en vue de résoudre à un problème (énoncé dans [108]) et de concurrencer WINNOWER. Ce problème consiste à extraire tous les motifs de même longueur fixée a priori et à distance de HAMMING également fixée a priori dans un ensemble de séquences (EM). L’algorithme se classe donc dans la catégorie A/C. Il s’appuie sur l’élaboration d’une fonction de hachage associée à chaque motif à extraire. La fonction de hachage est établie en choisissant aléatoirement un certain nombre (paramètre en entrée, dont les bornes conseillées sont fonction de la distance maximale, du nombre et de la taille des séquences) de positions dans les motifs présents dans les séquences. Lorsque pour une même clé de hachage, le nombre de motifs associé est suffisamment important, la collection de motifs est analysée en vue d’en extraire les résultats. Le processus est réitéré plusieurs fois (sur la base d’une estimation statistique de ce nombre). Cet algorithme offre des performances théoriques quasi optimales selon les auteurs. Pourtant, il semble qu’il soit inadapté à l’extraction de motifs dans les séquences biologiques (toujours selon les auteurs). Meta-MEME [57] utilise les résultats de MEME pour construire un modèle de MARKOV caché (cf. [79, chapitre ] pour un complément d’information au sujet de cette structure). Cet outil répond donc au problème EMq. Il est ensuite utilisé pour chercher des motifs consensuels dans des banques de séquences. Les résultats obtenus par cette méthode sont fortement dépendants de la qualité des bases de données utilisées, et demeurent assez difficiles à interpréter.

Étude statistique des fonctions de scores Block-Based

   Les propriétés, remarques et formules énoncées ci-avant sont ici appliquées à l’étude des fonctions Block-Based présentées au chapitre précédent (cf. Section 3.2.2 – page 49) et rappelées dans cette section. Comme mentionné à la section précédente, il est nécessaire de définir la source aléatoire de mots utilisée. Ceci fait, le cas simple des fonctions linéaires est analysé. Cette première étude se conclut par la preuve du caractère gaussien de la distribution des fonctions de score linéaires. Le cas plus général est ensuite abordé, et une expression de la moyenne et de la variance sont alors proposées. Une méthode permettant de calculer des formes closes de ces expressions est décrite, avec une application à quelques une des fonctions utilisées dans STARS. Enfin, une expérimentation sur des sources sans mémoires, ainsi que sur des séquences biologiques est proposée, afin d’illustrer le  caractère gaussien de la distribution de ces fonctions. Les fonctions Block-Based sont basées sur le découpage en blocs consécutifs de « correspondances » et de « non correspondances » des symboles dans un alignement sans trous de deux mots de même longueur. Les fonctions de score appliquées à un alignement sans trou de deux mots de longueur n sont définies sur la notion de mot alignement (cf. Définition 3.5 – page 50), qui est un mot de longueur n de {0, 1}∗ . L’étude des propriétés statistiques des fonctions Block-Based nécessite donc de définir une source aléatoire de mots alignements.

Les Arbres des Suffixes

   Ces arbres sont des Trie, construits à partir de l’ensemble des suffixes d’un mot. Les arbres des suffixes compacts sont alors les PATRICIA Trie obtenus à partir de l’ensemble des suffixes d’un mot (cf. Figure 5.2). Il est possible de construire un tel arbre en temps linéaire. En effet, les suffixes ne sont pas indépendants les uns des autres, et cette information est exploitée pour construire l’arbre en temps linéaire par rapport à la taille du mot représenté. Le premier algorithme à avoir atteint cette complexité pour la construction d’un tel arbre a été proposé par WEINER en  [136]. Dans cet algorithme, la construction s’effectue en lisant le mot à représenter de la droite vers la gauche. Il faut attendre  pour voir apparaître le premier algorithme linéaire permettant de construire cette structure en lisant le mot de la gauche vers la droite [127]. C’est en effet à cette date qu’UKKONEN a présenté son célèbre algorithme de construction on-line de l’arbre des suffixes (i.e., la structure construite à la i eme `étape de l’algorithme appliqué à un mot de longueur n est l’arbre des suffixes du préfixe de longueur i du mot représenté).

Table des matières

—Corps du document—
Introduction et cadre de la thèse
1 Des molécules et des lettres 
2 Exploration des séquences biologiques
3 Extraction de motifs et STARS 
4 Distribution limite des fonctions Block-Based et StatiSTARS
5 Étude des Oracles des Facteurs et des Suffixes
Conclusions et perspectives
—Annexes —
A Le code IUPAC 
B Représentation des ensembles de séquences biologiques et classification des algorithmes d’extraction de motif
C Matrices de similarité
D Théorie des Graphes et des Automates 
E Lois de probabilités 
F Illustration de STARS 
—Pages annexées —
Bibliographie
Liste des tableaux
Liste des figures
Liste des algorithmes
Liste des exemples
Nomenclature & Biographies
Index alphabétique

Télécharger le rapport complet