Note ABES Algorithmique pour la recherche de motifs approchée et application à la recherche de cibles de microARN Algorithmic for approximate string matching and application for the search of microRNA targets Algorithmique du texte Recherche de motifs approchée 005.741 Bioinformatique Exploration de données MicroARN Régulation génétique Arabidopsis Génétique La recherche de motifs approchée consiste à identifier les occurrences d’un motif modulo une certaine distance au sein d’un texte. Ce problème trouve de nombreuses applications en bio-informatique pour l’analyse de séquences biologiques. Par exemple, les microARN sont des petits ARN qui régulent l’expression des gènes par reconnaissance d’un motif similaire. Comprendre le mode d’action des microARN demande de pouvoir localiser de courts motifs, environ 21 nucléotides, comprenant jusqu’à 3 ou 4 erreurs dans un texte de l’ordre de 108 à 109 nucléotides, représentant un génome. Dans cette thèse, nous proposons un algorithme efficace pour la recherche de motifs approchée, qui se base sur la définition d’un nouveau type de graines avec erreurs, les graines 01*0, et qui exploite une structure d’index compressée, le FM-index. Cet algorithme a été mis en œuvre dans un logiciel librement disponible, appelé Bwolo. Nous démontrons expérimentalement l’avantage de cette approche en nous comparant à l’état de l’art des outils existants. Nous montrons également comment utiliser Bwolo pour mettre en place une analyse originale sur l’étude de la distribution des cibles potentielles de miARN dans deux génomes de plantes, Arabidopsis thaliana et Arabidopsis lyrata. Approximate string matching consists in identifying the occurrences of a motif within a text, modulo a given distance. This problem has many applications in bioinformatics for the analysis of biological sequences. For instance, microRNAs are short RNA molecules regulating the expression of genes by specific recognition of their sequence motif on the target gene. Understanding the mode of action of microRNAs requires the ability to identify short motifs, around 21 nucleotides in size, comprising up to 3-4 errors in a text whose size is in the order of 108-109 , representing a genome. In this thesis, I have proposed an efficient algorithm for the approximate search of short motifs. This algorithm is based on a new type of seeds containing errors, the 01*0 seeds, and uses a compressed index structure, the FM-index. I have implemented this algorithm in a freely available software, Bwolo. I demonstrate experimentally the advantage of this approach and compare it to the state of the art of existing tools. I also show how Bwolo can be used and have set up an original study on the distribution of potential miRNA target sites in two plant genomes, Arabidopsis thaliana and Arabidopsis lyrata. Electronic Thesis or Dissertation Text fr PDF 2232348 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2016/50376-2016-Vroland.pdf https://theses.fr/2016LIL10110/abes Vroland Christophe Vroland 1987-06-02 FR 158771427 https://theses.fr/2016LIL10110 2016LIL10110 https://doi.org/10.70675/d1ccbd61zdf7dz41e9z84d5z8907880f37c1 2016-05-18 Informatique Lille 1 026404184 Doctorat Docteur es non oui Touzet Hélène MADS_DIRECTEUR_DE_THESE_1 10394074X Castric Vincent MADS_DIRECTEUR_DE_THESE_2 142296473 Salson Mikaël MADS_DIRECTEUR_DE_THESE_3 157564363 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X Evolution, Ecologie et Paléontologie (Evo-Eco-Paléo) MADS_PARTENAIRE_DE_RECHERCHE_2 190718293 Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_3 185432247 ddc:000 Touzet Hélène Castric Vincent Salson Mikaël École doctorale Sciences pour l'Ingénieur (Lille) Centre de recherche en informatique, signal et automatique de Lille (CRIStAL) Evolution, Ecologie, Paléontologie (EVO-ECO-PALEO) Institut national de recherche en informatique et en automatique (France). Centre de recherche Lille - Nord Europe PDF 2232348