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.
