Moteur de recherche pour données de séquençage génomique requêtes approximées de présence, structure de données, indexation, kmers, filtres

Defense type
Thesis
Starting date
End date
Location
IRISA Rennes
Room
Salle Métivier
Speaker
Lucas ROBIDOU (EQUIPE GENSCALE)
Theme

Résumé : 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 existentes 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.

 

Composition of the jury
Paola BONIZZONI , Full Professor, Università de Milano-Bicocca, Rapporteure avant soutenance
Nadia PISANTI , Associate Professor, Università de Pisa, Rapporteure avant soutenance
Giulio ERMANNO-PIBIRI , Assistant Professor, CA'Foscari, Università de Venice, Examinateur
Loïs MAIGNIEN , Assistant Professor, UBO Brest, Examinateur
Jacques NICOLAS , Directeur de Recherche, Centre Inria de l'Université de Rennes, Examinateur
Pierre PETERLONGO , Directeur de Recherche, Centre Inria de l'Université de Rennes, Directeur de Thèse