Algorithme De Recherche Locale Pour Le Problème D’assemblage De Fragments D’ADN Sur Processeurs Graphiques GPU

Abstract

Le séquençage d’un ADN revient à lire la séquence de bases nucléotidiques A, T, C et G le constituant. Les technologies actuelles ne permettent pas d’effectuer un séquençage direct que sur des génomes de petite taille. C’est ainsi qu’est apparu le séquençage aléatoire (shotgun) consistant en la fragmentation de l’ADN, puis le séquençage individuel des fragments, et enfin l’assemblage des séquences résultantes à base de leurs ressemblances deux à deux. La résolution d’un problème d’assemblage de fragments ADN, de classe NP-difficile, est une partie importante de ce processus. Plusieurs travaux de recherches ont été menés afin de mettre en œuvre des assembleurs à la fois précis, complets et efficaces. La nature du problème fait du regroupement de ces trois critères un idéal jamais atteint. Les méta heuristiques présentent un outil essentiel permettant d’atteindre des résultats acceptables et relativement bons, et le calcul parallèle permet une amélioration considérable de la performance des solutions proposées. Nous proposons dans ce travail un algorithme d’assemblage de fragments ADN, qui consiste en une recherche locale itérative à double voisinage, ainsi qu’un modèle de parallélisassions destiné à une exécution sur GPU. L’algorithme a été implémenté en utilisant le langage C, et son équivalent GPU est écrit en CUDA C, exécutable sur les technologies nVIDIA. Les tests sont réalisés sur des séquences ADN benchmarks générées artificiellement.