Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse s'intéresse au problème de la recherche de motif dans les permutations, qui a pour objectif de savoir si un motif apparaît dans un texte, en prenant en compte que le motif et le texte sont des permutations. C'est-à-dire s'il existe des éléments du texte tel que ces éléments sont triés de la même manière et apparaissent dans le même ordre que les éléments du motif. Ce problème est NP complet. Cette thèse expose des cas particuliers de ce problème qui sont solvable en temps polynomial.Pour cela nous étudions le problème en donnant des contraintes sur le texte et/ou le motif. En particulier, le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 2413 et 3142 (appelé permutation séparable) et le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 213 et 231 sont considérés. Des problèmes dérivés de la recherche de motif et le problème de la recherche de motif bivinculaire sont aussi étudiés. / This thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied.

L'arrivée des technologies de séquençage d’ADN à haut-débit a représenté une révolution dans le domaine de la génomique personnalisée, en raison de leur résolution et leur faible coût. Toutefois, ces nouvelles technologies présentent un taux d’erreur élevé, qui varie entre 0,1% et 1% pour les séquenceurs de seconde génération. Cette valeur est problématique dans le cadre de la recherche de variants de faible ratio allélique, comme ce qui est observé dans le cas des tumeurs hétérogènes. En effet, un tel taux d’erreur peut mener à des milliers de faux positifs. Chaque région de l’ADN étudié doit donc être séquencée plusieurs fois, et les variants sont alors filtrés en fonction de critères basés sur leur profondeur. Malgré ces filtres, le nombre d’artefacts reste important, montrant la limite des approches conventionnelles et indiquant que certains artefacts de séquençage ne sont pas aléatoires.Dans le cadre de cette thèse, nous avons développé un algorithme exact de recherche des motifs d’ADN dégénérés sur-représentés en amont des erreurs de séquençage non aléatoires et donc potentiellement liés à leur apparition. Cet algorithme a été mis en oeuvre dans un logiciel appelé DiNAMO, qui a été testé sur des données de séquençage issues des technologies IonTorrent et Illumina.Les résultats expérimentaux ont mis en évidence plusieurs motifs, spécifiques à chacune de ces deux technologies. Nous avons ensuite montré que la prise en compte de ces motifs dans l’analyse, réduisait considérablement le taux de faux positifs. DiNAMO peut donc être utilisé en aval de chaque analyse, comme un filtre supplémentaire permettant d’améliorer l’identification des variants, en particulier des variants à faible ratio allélique. / The advent of Next Generation DNA Sequencing technologies has revolutionized the field of personalized genomics through their resolution and low cost. However, these new technologies are associated with a relatively high error rate, which varies between 0.1% and 1% for second-generation sequencers. This value is problematic when searching for low allelic ratio variants, as observed in the case of heterogeneous tumors. Indeed, such error rate can lead to thousands of false positives. Each region of the studied DNA must therefore be sequenced several times, and the variants are then filtered according to criteria based on their depth. Despite these filters, the number of errors remains significant, showing the limit of conventional approaches and indicating that some sequencing errors are not random.In the context of this thesis, we have developed an exact algorithm for over-represented degenerate DNA motifs discovery on the upstream of non-random sequencing errors and thus potentially linked to their appearance. This algorithm was implemented in a software called DiNAMO, which was tested on sequencing data from IonTorrent and Illumina technologies.The experimental results revealed several motifs, specific to each of these two technologies. We then showed that taking these motifs into account in the analysis reduced significantly the false-positive rate. DiNAMO can therefore be used downstream of each analysis, as an additional filter to improve the identification of variants, especially, variants with low allelic ratio.