Algorithme de recherche incrémentale d'un motif dans un ensemble de séquences d'ADN issues de séquençages à haut débit / Nadia Ben Nsira ; sous la direction de Thierry Lecroq et de Mourad Elloumi

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Algorithmes

Séquençage à haut débit -- Design patterns

Complexité de calcul (informatique)

Classification Dewey : 005.4

Lecroq, Thierry (1965-.... ; enseignant-chercheur en informatique) (Directeur de thèse / thesis advisor)

Elloumi, Mourad (Directeur de thèse / thesis advisor)

Slimani, Yahya (1951-....) (Président du jury de soutenance / praeses)

Chateau, Annie (1977-....) (Rapporteur de la thèse / thesis reporter)

Normandie Université (Organisme de soutenance / degree-grantor)

Université de Tunis El Manar (Organisme de cotutelle / degree co-grantor)

École doctorale sciences physiques mathématiques et de l'information pour l'ingénieur (Saint-Etienne-du-Rouvray, Seine-Maritime ; ....-2016) (Ecole doctorale associée à la thèse / doctoral school)

Université de Rouen Normandie (Autre partenaire associé à la thèse / thesis associated third party)

Laboratoire d'informatique, de traitement de l'information et des systèmes (Saint-Etienne du Rouvray, Seine-Maritime ; 2006-...) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Dans cette thèse, nous nous intéressons au problème de recherche incrémentale de motifs dans des séquences fortement similaires (On-line Pattern Matching on Highly Similar Sequences), issues de technologies de séquençage à haut débit (SHD). Ces séquences ne diffèrent que par de très petites quantités de variations et présentent un niveau de similarité très élevé. Il y a donc un fort besoin d'algorithmes efficaces pour effectuer la recherche rapide de motifs dans de tels ensembles de séquences spécifiques. 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 algorithmes les plus connus du problème de recherche de motifs et les index associés. Puis, dans les trois parties suivantes, nous développons trois algorithmes directement dédiés à la recherche incrémentale de motifs dans un ensemble de séquences fortement similaires. 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 terme de temps de calcul

Résumé / Abstract : In this thesis, we are interested in the problem of on-line pattern matching in highly similar sequences, On-line Pattern Matching on Highly Similar Sequences, outcoming from Next Generation Sequencing technologies (NGS). These sequences only differ by a very small amount. There is thus a strong need for efficient algorithms for performing fast pattern matching in such specific sets of sequences. 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 popular algorithms of finding problem and the related indexes. Then, in the three following parts, we develop three algorithms directly dedicated to the on-line search for patterns in a set of highly similar sequences. 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 computation time.