Université de Rennes 1 Moteur de recherche pour données de séquençage génomique Search engine for genomic sequencing data structure de donnéesindexationk-merfiltresséquençagebioinformatique data structuresindexationk-mer, filterssequencingbioinformatics Séquençage à haut débit Indexation automatique Bioinformatique Les technologies de séquençage à haut débit génèrent des quantités massives de jeux de données de séquences biologiques à mesure que les coûts diminuent. L'un des défis actuels pour exploiter ces données consiste à développer des moteurs de recherche pour ces jeux d'une taille de l'ordre du pétaoctet. La plupart des méthodes existantes reposent sur l'indexation des séquences via leurs mots de longueur k, appelés kmers. Dans de nombreux domaines de la bioinformatique, il est nécessaire de retrouver l'abondance d'un kmer dans un ensemble de données. Des structures de données, appelées AMQ, sont largement utilisées pour représenter ces grands ensembles de kmers. D'autres structures de données simililaires, les cAMQ, représentent des multiensembles, de façon à pouvoir retrouver l'abondance d'un kmer dans un jeu. Cependant, par nature, ces AMQs renvoient des faux positifs et, dans le cas d'un multiensemble, ont tendence à surestimer l'abondance des kmers. Dans ce manuscrit, nous présentons deux contributions, findere et fimpera, qui permettent d'améliorer les performances des (c)AMQs. Appliqué au filtre de Bloom, qui est largement utilisé en bioinformatique, findere réduit son taux de faux positifs de deux ordres de grandeur tout en accélérant ses requêtes. fimpera réduit le taux de faux positifs d'un filtre de Bloom avec comptage tout en améliorant la précision des abondances renvoyées. High throughput sequencing technologies generate massive amounts of biological sequence datasets as costs fall. One of the current algorithmic challenges for exploiting these data on a global scale consists in providing efficient query engines on these petabyte-scale datasets. Most methods indexing those datasets rely on indexing sequence datasets through their constituent words of fixed length k, called kmers. In many applications, it is required to retrieve the abundance of a kmer in a dataset. Approximate membership query (AMQ) data structures are widely used for representing these large sets of kmers. A counting AMQ (cAMQ) can index the abundance of kmers along with their presence in a dataset. However, these (c)AMQs suffer by nature from non-avoidable false-positive calls and overestimated calls that bias downstream analyses. In this work, we propose two contributions, findere and fimpera, that enable the improvement of any (c)AMQ performance. Applied to the widely used Bloom filter, findere reduces the false positive rate by two orders of magnitude while speeding up the queries. fimpera reduces the false positive rate of a counting Bloom filter while improving the precision of the reported abundances. Electronic Thesis or DissertationText en application/pdf1 : 1567 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/f8b4afd6-598a-4a03-99a7-f9caea3fddd7 Robidou Lucas 1997-01-13 FR 273576755 luc.robidou@gmail.com 2023URENS039 http://www.theses.fr/2023URENS039 2023-09-21 Informatique Université de Rennesthesis.degree.grantor_1 26693823X Doctorat non ouiPeterlongoPierreintervenant_112482062XNicolasJacquesintervenant_2116276142MaignienLoisintervenant_323097077XErmanno PibiriGiuliointervenant_627357681XPisantiNadiaintervenant_4155514008BonizzoniPaolaintervenant_5151672156 MATISSEecoleDoctorale_1 267602553 IRISA partenaireRecherche_1 026386909 ddc:004 PeterlongoPierreNicolasJacquesMaignienLoisPisantiNadiaBonizzoniPaolaErmanno PibiriGiulioUniversité de RennesMATISSE IRISA ASCII PDF 1604931