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^k. Les k-mères sont généralement utilisés lors de l'assemblage de séquences^[1], 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^[2],[3].

L'assemblage de séquences

Aperçu

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.

Cette figure montre le processus de fractionnement de la séquence en petits k-mères (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-mères se chevauchent sur k−1 et peuvent être utilisés dans un graphe de De Bruijn.

Le choix de la taille des k-mères

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 faible taille de k-mères

• 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.

Une grande taille de k-mères

• 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.

Les applications des k-mères dans l'analyse bio-informatique

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é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)^[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]

Pseudocode

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 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 {{mvar|k}}-mère
    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-mères (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 GAGTG 

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

Références

1. P. Compeau, P. Pevzner et G. Teslar, « How to apply de Bruijn graphs to genome assembly », Nature Biotechnology, vol. 29, n^o 11,‎ 2011, p. 987–991 (PMID 22068540, PMCID 5531759, DOI 10.1038/nbt.2023).
2. Kaitlin E Samocha, Elise B Robinson, Stephan J Sanders et Christine Stevens, « A framework for the interpretation of de novo mutation in human disease », Nature Genetics, vol. 46, n^o 9,‎ 2014, p. 944–950 (ISSN 1061-4036, PMID 25086666, PMCID 4222185, DOI 10.1038/ng.3050).
3. Varun Aggarwala et Benjamin F Voight, « An expanded sequence context model broadly explains variability in polymorphism levels across the human genome », Nature Genetics, vol. 48, n^o 4,‎ 2016, p. 349–355 (ISSN 1061-4036, PMID 26878723, PMCID 4811712, DOI 10.1038/ng.3511).
4. Andrzej Zielezinski, Susana Vinga, Jonas Almeida et Wojciech M. Karlowski, « Alignment-free sequence comparison: benefits, applications, and tools », Genome Biology, vol. 18, n^o 1,‎ 3 octobre 2017, p. 186 (ISSN 1474-760X, DOI 10.1186/s13059-017-1319-7, lire en ligne, consulté le 5 septembre 2023)
5. Zerbino, Daniel R. et Birney, Ewan, « Velvet: algorithms for de novo short read assembly using de Bruijn graphs », Genome Research, vol. 18, n^o 5,‎ 2008, p. 821–829 (PMID 18349386, PMCID 2336801, DOI 10.1101/gr.074492.107)
6. "Rachid Ounit, Steve Wanamaker, Timothy J Close and Stefano Lonardi", « CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers », BMC Genomics, vol. 16,‎ 2015, p. 236 (PMID 25879410, PMCID 4428112, DOI 10.1186/s12864-015-1419-2)
7. Dubinkina, Ischenko, Ulyantsev, Tyakht, Alexeev, « Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis », BMC Bioinformatics, vol. 17,‎ 2016, p. 38 (PMID 26774270, PMCID 4715287, DOI 10.1186/s12859-015-0875-7)
8. Zhu, Zheng, « Self-organizing approach for meta-genomes », Computational Biology and Chemistry, vol. 53,‎ 2014, p. 118–124 (PMID 25213854, DOI 10.1016/j.compbiolchem.2014.08.016)
9. Chor, Horn, Goldman, Levy, Massingham, « Genomic DNA k-mer spectra: models and modalities », Genome Biology, vol. 10, n^o 10,‎ 2009, R108 (PMID 19814784, PMCID 2784323, DOI 10.1186/gb-2009-10-10-r108)
10. Meher, Sahu, Rao, « Identification of species based on DNA barcode using k-mer feature vector and Random forest classifier », Gene, vol. 592, n^o 2,‎ 2016, p. 316–324 (PMID 27393648, DOI 10.1016/j.gene.2016.07.010)
11. Li et al, « De novo assembly of human genomes with massively parallel short read sequencing », Genome Research, vol. 20, n^o 2,‎ 2010, p. 265–272 (PMID 20019144, PMCID 2813482, DOI 10.1101/gr.097261.109)
12. Navarro-Gomez et al, « Phy-Mer: a novel alignment-free and reference-independent mitochondrial haplogroup classifier », Bioinformatics, vol. 31, n^o 8,‎ 2015, p. 1310–1312 (PMID 25505086, PMCID 4393525, DOI 10.1093/bioinformatics/btu825)
13. Phillippy, Schatz, Pop, « Genome assembly forensics: finding the elusive mis-assembly », Bioinformatics, vol. 9, n^o 3,‎ 2008, R55 (PMID 18341692, PMCID 2397507, DOI 10.1186/gb-2008-9-3-r55)
14. Price, Jones, Pevzner, « De novo identification of repeat families in large genomes », Bioinformatics, vol. 21(supp 1),‎ 2005, i351–8 (PMID 15961478, DOI 10.1093/bioinformatics/bti1018)
15. Newburger, Bulyk, « UniPROBE: an online database of protein binding microarray data on protein–DNA interactions », Nucleic Acids Research, vol. 37(supp 1), n^o Database issue,‎ 2009, D77–82 (PMID 18842628, PMCID 2686578, DOI 10.1093/nar/gkn660)
16. Better filtering with gapped q-grams, vol. 56, coll. « Lecture Notes in Computer Science » (n^o 1–2), 2002, 51–70 p. (ISBN 978-3-540-43862-5, DOI 10.1007/3-540-45452-7_19, lire en ligne)
17. Keich et al, « On spaced seeds for similarity search », Discrete Applied Mathematics, vol. 138, n^o 3,‎ 2004, p. 253–263 (DOI 10.1016/S0166-218X(03)00382-2)
18. Ghandi et al, « Enhanced regulatory sequence prediction using gapped k-mer features », PLoS Computational Biology, vol. 10, n^o 7,‎ 2014, e1003711 (PMID 25033408, PMCID 4102394, DOI 10.1371/journal.pcbi.1003711, Bibcode 2014PLSCB..10E3711G)
19. Nordstrom et al, « Mutation identification by direct comparison of whole-genome sequencing data from mutant and wild-type individuals using k-mers », Nature Biotechnology, vol. 31, n^o 4,‎ 2013, p. 325–330 (PMID 23475072, DOI 10.1038/nbt.2515)
20. Chae et al, « Comparative analysis using K-mer and K-flank patterns provides evidence for CpG island sequence evolution in mammalian genomes », Nucleic Acids Research, vol. 41, n^o 9,‎ 2013, p. 4783–4791 (PMID 23519616, PMCID 3643570, DOI 10.1093/nar/gkt144)
21. Mohamed Hashim, Abdullah, « Rare k-mer DNA: Identification of sequence motifs and prediction of CpG island and promoter », Journal of Theoretical Biology, vol. 387,‎ 2015, p. 88–100 (PMID 26427337, DOI 10.1016/j.jtbi.2015.09.014)
22. Jaron, Moravec, Martinkova, « SigHunt: horizontal gene transfer finder optimized for eukaryotic genomes », Bioinformatics, vol. 30, n^o 8,‎ 2014, p. 1081–1086 (PMID 24371153, DOI 10.1093/bioinformatics/btt727)
23. Delmont, Eren, « Identifying contamination with advanced visualization and analysis practices: metagenomic approaches for eukaryotic genome assemblies », PeerJ, vol. 4,‎ 2016, e1839 (DOI 10.7717/Fpeerj.1839)
24. Bemm et al, « Genome of a tardigrade: Horizontal gene transfer or bacterial contamination? », Proceedings of the National Academy of Sciences, vol. 113, n^o 22,‎ 2016, E3054–E3056 (PMID 27173902, PMCID 4896698, DOI 10.1073/pnas.1525116113)
25. Wang, Xu, Liu, « Recombination spot identification Based on gapped k-mers », Scientific Reports, vol. 6,‎ 2016, p. 23934 (PMID 27030570, PMCID 4814916, DOI 10.1038/srep23934, Bibcode 2016NatSR...623934W)
26. Hozza, Vinar, Brejova « How big is that genome? estimating genomesize and coverage from k-mer abundance spectra » (2015) (DOI 10.1007/978-3-319-23826-5_20)
    —SPIRE 2015
27. Lamichhaney et al, « Structural genomic changes underlie alternative reproductive strategies in the ruff (Philomachus pugnax) », Nature Genetics, vol. 48, n^o 1,‎ 2016, p. 84–88 (PMID 26569123, DOI 10.1038/ng.3430)
28. Patro, Mount, Kingsford, « Sailfish enables alignment-free isoform quantification from RNA-seq reads using lightweight algorithms », Nature Biotechnology, vol. 32, n^o 5,‎ 2014, p. 462–464 (PMID 24752080, PMCID 4077321, DOI 10.1038/nbt.2862, arXiv 1308.3700)

Liens externes

• Sciencedirect sujet:k-mer
• bioXriv:k-mer
• arXiv: k-mer

• Portail de la biologie