Principe de l’approche de De Bruijn pour l’assemblage d’un génome
Les lectures (reads) obtenues par séquençage de l'ADN sont décomposées en k-mers, des petits fragments de taille k (ici, k = 5). On reconstruit alors le graphe de De Bruijn, dont les nœuds sont les (k – 1)-mers, et dont les arêtes relient deux (k – 1)-mers, si les nœuds partagent un chevauchement de séquence nucléotidique de taille (k – 2). La reconstruction de la séquence initiale s'appuie sur la recherche d'un chemin eulérien, passant par toutes les arêtes du graphe. D'après Y. Ponty, « Bio-algorithmique des ARN : petite promenade aux interfaces », in Bulletin de la Société informatique de France, vol. 4, pp. 23–53, 2014.
Encyclopædia Universalis France - Conditions d'utilisation