K-mère

Un k-mère est une sous-chaîne de longueur k d'une chaîne de caractères plus grande. En génomique computationnelle, les k-mères sont les sous-séquences (de longueur k) résultant d'une lecture par séquençage de l'ADN. Étant donné une chaîne de caractères de longueur L, le nombre de k-mères possibles est L−k+1, tandis que le nombre de k-mères étant donné n possibilités (4 dans le cas de l'ADN, ACTG) est n. Les k-mères sont généralement utilisés lors de l'assemblage de séquences, mais peuvent également être utilisés dans l'alignement de la séquence. Dans le contexte du génome humain, les k-mères de différentes longueurs sont employés pour expliquer la variabilité du taux de mutation. Dans l'assemblage de séquence, les k-mères sont généralement utilisés lors de la construction de graphiques de De Bruijn. Afin de créer un Graphe de De Bruijn, les chaînes stockées dans chaque arête, de longueur , doivent se chevaucher l'une l'autre sur une longueur afin de créer un vertex. Les séquences générées à partir de méthode de séquençage de prochaine génération ont généralement différentes longueurs durant une même session de lecture. Par exemple, les séquences lues par la technologie de séquençage Illumina produit des séquences pouvant être capturées par un k-mère de 100. Cependant, le problème avec le séquençage est qu'une petite fraction de k-mères de 100, des 100-mers, présents dans le génome sont en fait réellement générés. Cela est dû à des erreurs de lecture, mais de façon plus importante encore, par de simples trous de couverture qui se produisent au cours du séquençage. Le problème est que ces petites fractions de k-mères "corrompues", violent l'hypothèse principale des graphiques de Bruijn, que tous les k-mère issus des séquences lues doivent se chevaucher aux k-mères dans le génome par une superposition de longueur k−1 (qui ne peut pas se produire lorsque tous les k-mères ne sont pas présents). La solution à ce problème est de réduire la taille de ces k-mères en petits k-mères, tels que les petits k-mères représentent tous les k-mères de plus petite taille présents dans le génome.