k-mère

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 ${\displaystyle L}$ , doivent se chevaucher l'une l'autre sur une longueur ${\displaystyle L-1}$ 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. En outre, le fractionnement des k-mères en plus petites tailles aide également à soulager le problème des différentes longueurs de lecture initiale.
Un exemple de la solution de diviser la séquence lue en petits k-mères est montré dans la figure 1. Dans cet exemple, les séquences de 5 nucléotides ne tiennent pas compte de tous les k-mères de longueur 7 du génome, et dans ce cas, un graphe de de Bruijn ne peut pas être créé. Mais quand ils sont divisés en k-mères de longueur 4, les sous-séquences résultantes sont assez nombreuses et variées pour reconstituer le génome à l'aide d'un graphe de de Bruijn.

Le choix de la taille des k-mères a beaucoup d'effets différents sur l'assemblage des séquences. Ces effets varient grandement entre les plus petites tailles de k-mères et les tailles de k-mères plus grandes. Par conséquent, la compréhension des différentes tailles de k-mères doit être connue afin de choisir une taille appropriée, qui équilibre les effets. Les effets des tailles sont décrits ci-dessous.

Dans la pratique, une valeur de k de 2 à 6 permet d'obtenir des comparaisons stables et optimales de séquences de protéines sur un large éventail de distances phylogénétiques différentes^[4].

• Une diminution de la taille des k-mères va diminuer la diversité de séquences stockées dans le graphique dû à la diminution des possibilités de combinaison, et en tant que telle, aide à diminuer la quantité d'espace nécessaire pour stocker une séquence d'ADN.
• Avoir une plus petite taille permettra d'augmenter les chances que tous les k-mères se chevauchent, et en tant que telles, les sous-séquences dans le but de construire le graphe de de Bruijn^[5].
• Cependant, en ayant une taille de k-mères plus petite, on risque d'avoir de nombreux chevauchements dans le graphe pour un seul k-mère. Par conséquent, la reconstruction du génome sera plus difficile car il y aura un nombre plus élevé de chemins ambigus dû à la plus grande quantité de k-mères qui devront être parcourus.
• L'information est perdue lorsque les k-mères deviennent plus petits.
  • E. g. Les possibilités de combinaison pour AGTCGTAGATGCTG sont inférieures à celles pour ACGT, et en tant que tel, le premier est porteur d'un plus grand nombre d'informations (reportez-vous à l'entropie (la théorie de l'information) pour plus d'informations).
• De plus petits k-mères posent le problème de ne pas être en mesure de résoudre certains points dans l'ADN, comme dans les microsatellites où plusieurs répétitions peuvent se produire. C'est à cause du fait que les petits k-mères auront tendance à revenir entièrement sur eux dans ces régions de répétition et il est donc difficile de déterminer le nombre de répétitions qui ont effectivement eut lieu.
  • E. g. Pour la sous-suite ATGTGTGTGTGTGTACG, le nombre de répétitions de la TG seront perdues si un k-mère de taille de moins de 16 est choisi. C'est parce que la plupart des k-mères vont revenir dans la région répétée et que le nombre de répétitions du même k-mère sera perdu au lieu de mentionner la quantité de répétitions.

• Avoir de plus grande taille de k-mères augmentera la quantité d'arêtes dans le graphe, ce qui, à son tour, va augmenter la quantité de mémoire nécessaire pour stocker la séquence d'ADN.
• En augmentant la taille du k-mère, le nombre de sommets diminuera également. Cela va aider à la construction du génome puisqu'il y aura moins de chemins à parcourir dans le graphique.
• Une plus grande taille de k-mère court également un risque plus élevé de ne pas aller vers l'extérieur des sommets de chaque k-mère. C'est pour cette raison qu'une plus grande taille de k-mères augmente le risque qu'ils ne se chevauchent pas avec un autre k-mère sur une longueur de ${\displaystyle k-1}$ . Par conséquent, cela peut conduire à une non-continuité dans la séquence lue, et en tant que tel, peut conduire à une plus grande quantité de petits contigs.
• Une plus grande taille de k-mère aide à atténuer le problème des petites régions de répétition. Cela est dû au fait que le k-mère contiendra un équilibre entre la région de répétition et la séquences d'ADN (étant donné qu'ils sont d'une assez grande taille) qui peuvent aider à résoudre le nombre de répétitions dans ce domaine particulier.

La fréquence d'un ensemble de k-mères, dans le génome d'une espèce, dans une région génomique, ou dans une classe de séquences, peut être utiliséeen tant que "signature" de sous-séquence. La comparaison de ces fréquences est mathématiquement plus facile que l'alignement de la séquence, et est une méthode importante dans l'alignement sans l'analyse de la séquence. Elle peut également être utilisée comme une première étape d'analyse avant un alignement.

• la séparation de différentes espèces dans un mélange de matériel génétique (métagénomique, microbiome)^[6],[7];des phases/cadres d'information peut être ajoutée^[8]
• Barcoding moléculaire (DNA barcoding) des espèces^[9],[10]
• assemblage de novo^[11]
• classification haplogroupe mitochondriale humaine ^[12]
• détecter le mauvais assemblage de génome^[13]
• la détection de novo de séquence répétée comme élément transposable^[14]
• caractériser une protéine de liaison à motif de séquence^[15]. En plus de k-mère, incisés k-mères (également nommé écartement q-grammes^[16] ou espacées graines^[17]) peut également être utilisé ^[18]
• l'identification de mutations ou d'un polymorphisme à l'aide de séquençage de prochaine génération des données^[19]
• la caractérisation de l'îlot CpG par les régions flanquantes ^[20],[21]
• détecter des transferts horizontaux ^[22]
• détecter la contamination bactérienne dans un génome eucaryote assemblé ^[23],[24]
• détecter la recombinaison site ^[25]
• en utilisant la fréquence des k-mères par rapport à la profondeur k-mère à l'estimation de la taille du génome ^[26],[27]
• estimation de la proportion d'ARN séquencé ^[28]

Déterminer la taille de lecture des k-mères peut être fait simplement en bouclant sur la taille de la longueur de la chaîne, en augmentant progressivement la position dans la chaîne et en prenant chaque sous-chaîne de longueur k. Le pseudo-code qui réalise cette opération est comme suit :

fonction K-mer(Chaine_caractere, k) /* k = longueur de chaque {{mvar|k}}-mère */    n = longueur(Chaine_caractere)    /* Boucle sur la longueur de Chaine_caractere jusque la longueur Chaine_caractere - taille des {{mvar|k}}-mère */    Pour i = 1 jusque n-k+1 inclus fait :        /* Sort chaque {{mvar|k}}-mère de longueur k, de la position i à la position i+k dans Chaine_caractere */        sortie Chaine_caractere[position i -> position i+k]    Fin de BoucleFin de fonction

En python3, il sera possible d'implémenter le code comme suit :

def kmer(sequence, k) : # sequence correspond a la sequence ADN, k correspond a la longueur des {{mvar|k}}-mère    n = len(sequence)    kmers = []    for i in range(0,n-k) :        kmers.append(sequence[i:i+k])    return kmers

Voici quelques exemples montrant les possibles k-mères (en spécifiant une valeur de k) à partir de séquences d'ADN:

Lecture: AGATCGAGTG3-mers: AGA GAT ATC TCG CGA GAG AGT GTG 

5-mers: AGATC GATCG ATCGA TCGAG CGAGT GAGTG 

Lecture: GTAGAGCTGT5-mers: GTAGA TAGAG AGAGC GAGCT AGCTG GCTGT