Мы используем файлы cookie.
Продолжая использовать сайт, вы даете свое согласие на работу с этими файлами.

K-mer

Другие языки:

K-mer

Подписчиков: 0, рейтинг: 0

Le terme k-mer fait généralement référence à toutes les sous-chaînes de longueur k qui sont contenues dans une chaîne de caractère. En génomique computationnelle, les k-mers font référence à toutes les sous-séquences (de longueur k) à partir d'une lecture obtenues par séquençage de l'ADN. La quantité de k-mers possible étant donné une chaîne de caractères de longueur L est $L-k+1$ tandis que le nombre de k-mers étant donné n possibilités (4 dans le cas de l'ADN par exemple ACTG) est $n^{k}$ . Les k-mers 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-mers de différentes longueurs ont été utilisés pour expliquer la variabilité dans les taux de mutation.

L'assemblage de séquences

Aperçu

Dans l'assemblage de séquence, les k-mers 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 $L$ , doivent se chevaucher l'une l'autre sur une longueur $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-mer de 100. Cependant, le problème avec le séquençage est qu'une petite fraction de k-mers 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-mers "corrompues", violent l'hypothèse principale des graphiques de Bruijn, que tous les k-mer issus des séquences lues doivent se chevaucher aux k-mers dans le génome par une superposition de longueur $k-1$ (qui ne peut pas se produire lorsque tous les k-mers ne sont pas présents). La solution à ce problème est de réduire la taille de ces k-mers en petits k-mers, tels que les petits k-mers représentent tous les k-mers de plus petite taille présents dans le génome. En outre, le fractionnement des k-mers 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-mers est montré dans la figure 1. Dans cet exemple, les séquences de 5 nucléotides ne tiennent pas compte de tous les k-mers 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-mers 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.

Cette figure montre le processus de fractionnement de la séquence en petits k-mers (4-mers dans ce cas) afin de pouvoir être utilisés dans un graphe de de Bruijn. (A) Montre le premier segment de l'ADN en cours de séquençage. (B) Montre les lectures qui ont été générées en sortie à partir du séquençage et montre également la façon dont ils se chevauchent. Le problème avec cet alignement est que les séquences se chevauchent sur une longueur de k-2, or elles doivent se chevaucher sur une longueur de k-1 pour être utilisées dans les graphes de de Bruijn. (C) Montre les séquences divisées en plus petites, de 4-mers. (D) Les séquences dupliquées de 4-mers sont écartées et les séquences restantes montrent l'alignement. Notez que ces k-mers se chevauchent sur k-1 et peuvent être utilisés dans un graphe de De Bruijn.

Le choix de la taille des k-mers

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

Une faible taille de k-mers

Une diminution de la taille des k-mers 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-mers se chevauchent, et en tant que telles, les sous-séquences dans le but de construire le graphe de de Bruijn.
Cependant, en ayant une taille de k-mers plus petite, on risque d'avoir de nombreux chevauchements dans le graphe pour un seul k-mer. 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-mers qui devront être parcourus.
L'information est perdue lorsque les k-mers 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-mers 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-mers 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-mer de taille de moins de 16 est choisi. C'est parce que la plupart des k-mers vont revenir dans la région répétée et que le nombre de répétitions du même k-mer sera perdu au lieu de mentionner la quantité de répétitions.

Une grande taille de k-mers

Avoir de plus grande taille de k-mers 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 de la k-mer, 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-mer court également un risque plus élevé de ne pas aller vers l'extérieur des sommets de chaque k-mer. C'est pour cette raison qu'une plus grande taille de k-mers augmente le risque qu'ils ne se chevauchent pas avec un autre k-mer sur une longueur de $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-mer aide à atténuer le problème des petites régions de répétition. Cela est dû au fait que le k-mer 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.

Les applications des k-mers dans l'analyse bio-informatique

La fréquence d'un ensemble de k-mers, dans le génome d'une espèce, dans une région génomique, ou dans une classe de séquences, peut être utilisée en 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);des phases/cadres d'information peut être ajoutée
Barcoding moléculaire (DNA barcoding) des espèces
assemblage de novo
classification haplogroupe mitochondriale humaine
détecter le mauvais assemblage de génome
la détection de novo de séquence répétée comme élément transposable
caractériser une protéine de liaison à motif de séquence. En plus de k-mer, incisés k-mers (également nommé écartement q-grammes ou espacées graines) peut également être utilisé
l'identification de mutations ou d'un polymorphisme à l'aide de séquençage de prochaine génération des données
la caractérisation de l'îlot CpG par les régions flanquantes
détecter des transferts horizontaux
détecter la contamination bactérienne dans un génome eucaryote assemblé
détecter la recombinaison site
en utilisant la fréquence des k-mers par rapport à la profondeur k-mer à l'estimation de la taille du génome
estimation de la proportion d'ARN séquencé

Pseudocode

Déterminer la taille de lecture des k-mers 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 k-mer */
    n = longueur(Chaine_caractere)
    /* Boucle sur la longueur de Chaine_caractere jusque la longueur Chaine_caractere - taille des k-mer */
    Pour i = 1 jusque n-k+1 inclus fait :
        /* Sort chaque K-mer de longueur k, de la position i à la position i+k dans Chaine_caractere */
        sortie Chaine_caractere[position i -> position i+k]
    Fin de Boucle
Fin 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 k-mer
    n = len(sequence)
    kmers = []
    for i in range(0,n-k) :
        kmers.append(sequence[i:i+k])
    return kmers

Exemples

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

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

5-mers: AGATC GATCG ATCGA TCGAG CGAGT

Lecture: GTAGAGCTGT
5-mers: GTAGA TAGAG AGAGC GAGCT AGCTG GCTGT

Références

Portail de la biologie