Algorithmes de recherche de motifs dans un ensemble de chaînes codant des macromolécules biologiques : cas des motifs simples
Institution:
RouenDisciplines:
Directors:
Abstract EN:
In this thesis, we are interested in the problem of finding motifs in strings coding biological macromolecules. We are particularly interested in the Simple Motif Search Problem (SMP). We develop new algorithms to process this problem. This thesis is partitioned into five parts. In the first part, we present a state of the art on the most studied versions of the motif finding problem and the related algorithms. Then, in the three following parts, we develop three algorithms to process SMP. Finally, in the fifth part, we conduct an experimental study on these algorithms. This study shows that our algorithms are efficient in practice in terms of time and memory space consumption.
Abstract FR:
Dans cette thèse, nous nous intéressons au problème de recherche de motifs dans un ensemble de chaînes codant des macromolécules biologiques. Nous nous intéressons, particulièrement, au problème de recherche de motifs simples (Simple Motif Search Problem (SMP)). Nous développons de nouveaux algorithmes pour traiter ce problème. Cette thèse est répartie en cinq parties. Dans la première partie, nous présentons un état de l'art sur les versions les plus étudiées du problème de recherche de motifs et les algorithmes associés. Puis, dans les trois parties suivantes, nous développons respectivement trois algorithmes pour traiter le SMP. Enfin, dans la cinquième partie, nous effectuons une étude expérimentale sur ces algorithmes. Cette étude a montré que nos algorithmes sont efficaces en pratique en termes de consommation en temps de calcul et occupation de l'espace mémoire.