Optimisation par algorithme génétique pour la résolution du problème d’assemblage de fragments d’ADN

Abstract

Le problème d'assemblage de fragments consiste à construire une séquence d'ADN à partir de plusieurs centaines (voire des milliers) de fragments obtenus par les biologistes du laboratoire. Il s'agit donc d'un problème d'optimisation combinatoire, connu comme étant NP-difficile. Pour résoudre ce problème, nous avons adopté l’algorithme génétique (AG). Pour améliorer la recherche de bonne solution, nous avons intégré l’algorithme PALS (Problem Aware Local search) comme un opérateur de recherche additionnel dans l’AG. Une étude expérimentale a montré que l’hybridation de l’AG avec PALS a donné de bons résultats par rapport à ceux de l’AG.