Note ABES Comparaisons de séquences biologiques sur architecture massivement multi-coeurs Bioinformatics sequence comparisons on manycore processors Gpu 005.74 Bioinformatique Calcul intensif (informatique) Parallélisme (informatique) Microprocesseurs multi-coeurs Cartes graphiques (informatique) Séquençage des acides nucléiques Méthode comparative Algorithmes d'approximation Heuristique Rechercher les similarités entre séquences est une opération fondamentale en bioinformatique, que cela soit pour étudier des questions biologiques ou bien pour traiter les données issues de séquenceurs haut-débit. Il y a un vrai besoin d'algorithmes capables de traiter des millions de séquences rapidement. Pour trouver des similarités approchées, on peut tout d'abord considérer de petits mots exacts présents dans les deux séquences, les graines, puis essayer d'étendre les similarités aux voisinages de ces graines. Cette thèse se focalise sur la deuxième étape des heuristiques à base de graines : comment récupérer et comparer efficacement ces voisinages des graines, pour ne garder que les bons candidats ? La thèse explore différentes solutions adaptées aux processeurs massivement multicœurs: aujourd'hui, les GPUs sont en train de démocratiser le calcul parallèle et préparent les processeurs de demain. La thèse propose des approches directes (extension de l'algorithme bit-parallèle de Wu-Manber, publiée à PBC 2011, et recherche ichotomique) ou bien avec un index supplémentaire (utilisation de fonctions de hash parfaites). Chaque solution a été pensée pour tirer le meilleur profit des architectures avec un fort parallélisme à grain fin, en utilisant des calculs intensifs mais homogènes. Toutes les méthodes proposées ont été implémentés en OpenCL, et comparées sur leur temps d'exécution. La thèse se termine par un prototype de read mapper parallèle, MAROSE, utilisant ces concepts. Dans certaines situations, MAROSE est plus rapide que les solutions existantes avec une sensibilité similaire. Searching similarities between sequences is a fundamental operation in bioinformatics, providing insight in biological functions as well as tools for high-throughput data. There is a need to have algorithms able to process efficiently billions of sequences. To look for approximate similarities,a common heuristic is to consider short words that appear exactly in both sequences, the seeds, then to try to extend this similarity to the neighborhoods of the seeds. The thesis focuses on this second stage of seed-based heuristics : how can we retrieve and compare efficiently the neighborhoods of the seeds ? The thesis proposes several solutions tailored for manycore processors such as today’s GPUs. Such processors are making massively parallel computing more and more popular. The thesis proposes direct approaches (extension of bit-parallel Wu-Manber algorithm, published in PBC 2011, and binary search) and approaches with another index (with perfect hash functions). Each one of these solutions was conceived to obtain as much fine-grained parallelism as possible, requiring intensive but homogeneous computational operations. All proposed methods were implemented in OpenCL and benchmarked. Finally, the thesis presents MAROSE, a prototype parallel read mapper using these concepts. In some situations, MAROSE is more efficient than the existing read mappers with a comparable sensitivity. Electronic Thesis or Dissertation Text en PDF 1764004 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2012/50376-2012-Tran.pdf https://theses.fr/2012LIL10138/abes Tran Tuan Tu Tran 1981-12-07 VN 169256278 https://theses.fr/2012LIL10138 2012LIL10138 https://doi.org/10.70675/f1ea6aa2zc379z410czb7f2zdcf2219a3460 2012-12-21 Informatique Lille 1 026404184 Doctorat Docteur es non oui Varré Jean-Stéphane MADS_DIRECTEUR_DE_THESE_1 060904208 Giraud Mathieu MADS_DIRECTEUR_DE_THESE_2 094640610 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Laboratoire d'informatique fondamentale de Lille (2002-2014) MADS_PARTENAIRE_DE_RECHERCHE_1 077703553 ddc:000 Varré Jean-Stéphane Giraud Mathieu École doctorale Sciences pour l'Ingénieur (Lille) Laboratoire d'informatique fondamentale de Lille (LIFL) PDF 1764004