Mostra la font per a K-mer

{{DISPLAYTITLE:''k''-mer}}
El terme '''''k-mer''''' fa referència a totes les subcadenes possibles de longitud k contingudes en una cadena. En [[genòmica computacional]], els k-mers són les subsequències possibles (de longitud k) d'una lectura obtinguda a patir d'un procés de seqüenciació de l'ADN. La quantitat de k-mers possibles donada una cadena de longitud L és <math>L-k+1</math>, mentre que el nombre de possibles k-mers donades n possibilitats (4 en el cas d'ADN, p. ex. ACTG) és <math>n^{k}</math>. Els k-mers s'utilitzen normalment en l'[[assemblatge de seqüències]], però també en l'[[alineament de seqüències]].<ref name="Ref">{{Ref-publicació|cognom=Compeau|nom=Phillip E C|cognom2=Pevzner|nom2=Pavel A|cognom3=Tesler|nom3=Glenn|article=How to apply de Bruijn graphs to genome assembly|publicació=Nature Biotechnology|llengua=En|url=https://doi.org/10.1038/nbt.2023|volum=29|exemplar=11|data=2011/11|pàgines=987–991|doi=10.1038/nbt.2023|issn=1546-1696}}</ref> En el context del [[genoma humà]], k-mers de diverses longituds s'han utilitzat per explicar la variabilitat dels índexs de mutació.<ref name="SamochaRobinson2014">{{ref-publicació|cognom1=Samocha|nom1=Kaitlin E|cognom2=Robinson|nom2=Elise B|cognom3=Sanders|nom3=Stephan J|cognom4=Stevens|nom4=Christine|cognom5=Sabo|nom5=Aniko|cognom6=McGrath|nom6=Lauren M|cognom7=Kosmicki|nom7=Jack A|cognom8=Rehnström|nom8=Karola|cognom9=Mallick|nom9=Swapan|last10=Kirby|first10=Andrew|last11=Wall|first11=Dennis P|last12=MacArthur|first12=Daniel G|last13=Gabriel|first13=Stacey B|last14=DePristo|first14=Mark|last15=Purcell|first15=Shaun M|last16=Palotie|first16=Aarno|last17=Boerwinkle|first17=Eric|last18=Buxbaum|first18=Joseph D|last19=Cook|first19=Edwin H|last20=Gibbs|first20=Richard A|last21=Schellenberg|first21=Gerard D|last22=Sutcliffe|first22=James S|last23=Devlin|first23=Bernie|last24=Roeder|first24=Kathryn|author24-link=Kathryn Roeder|last25=Neale|first25=Benjamin M|last26=Daly|first26=Mark J|títol=A framework for the interpretation of de novo mutation in human disease|publicació=Nature Genetics|volum=46|exemplar=9|any=2014|pàgines=944–950|issn=1061-4036|doi=10.1038/ng.3050}}</ref><ref name="AggarwalaVoight2016">{{ref-publicació|cognom1=Aggarwala|nom1=Varun|cognom2=Voight|nom2=Benjamin F|títol=An expanded sequence context model broadly explains variability in polymorphism levels across the human genome|publicació=Nature Genetics|volum=48|exemplar=4|any=2016|pàgines=349–355|issn=1061-4036|doi=10.1038/ng.3511|pmid=26878723|pmc=4811712}}</ref>

== Assemblatge de seqüències ==
=== Resum ===
En el context de l'assemblatge de seqüències, els k-mers s'utilitzen en el procés de creació de [[Graf de Brujin|grafs de Bruijn]]. Per tal de crear-ne un, les cadenes que s'emmagatzemen en cada aresta amb una longitud, <math>L</math>, han de solapar-se amb una altra cadena en una altra aresta per <math>L-1</math> per tal de crear un [[Vèrtex (teoria de grafs)|vertex.]] Les lectures obtingudes del procés de seqüenciació tindran diferents longituds. Posem el cas, amb la seqüenciació d'[[Illumina (empresa)|Illumina]] es poden generar 100-mers. Tanmateix, el problema amb la seqüenciació és que només fraccions petites dels possibles 100-mers presents en el genoma són generats al final. Això és a causa dels errors de lectura, però sobretot, simplement buits de cobertura que ocorren durant la seqüenciació. El problema és tanmateix, que aquestes fraccions més petites dels possible k-mers viola la suposició clau dels grafs de Bruijn que totes les lectures de k-mer han de sobreposar-se els seus k-mers adjunts en el genoma per <math>k-1</math> (que no pot passar quan tots els k-mers no són presents). La solució a aquest problema és trencar aquestes lectures de mides del k-mer a una mida més petita que la dels k-mers, per tal que els k-mers més petits resultants representin tots el possibles k-mers d'aquella mida més petita que són present al genoma.<ref name="Ref"/> A més, partint el k-mers a mides més petites també ajudes a alleugerir el problema de diferents longituds de lectura inicials. Un exemple de solució de partir les lectures a k-mers més petits és mostra a la figura 1. En aquest exemple les 5 lectures no compten tot els possibles 7-mers del genoma, i com a tal, no pot crear-se un graf de Bruijn. Però quan es parteixi a 4-mers, les subcadenes resultants són suficients per a reconstruir el genoma que utilitza un graf de Bruijn.[[Fitxer:K-mer-example.png|center|miniatura|Aquesta figura mostra el procés de partir les lectures en k-mers més petits (4-mers en aquest cas) per tal de poder utilitzar-se en un [[graf de Bruijn]]. (A) Mostra el segment inicial de l'ADN seqüenciat. (B) Mostra les lectures sortint de la seqüenciació i també es mostra com s'alineen. No obstant, el problema amb aquest alineament és que se solapen per k-2, no per k-1 (que és necessari en els grafs de Bruijn). (C) Mostra les lectures partides en 4-mers més petits. (D) Es descarten els 4-mers repetits i es mostren els alineaments entre ells. Cal notar que aquests k-mers se solapen per k-1 i llavors poden utilitzar-se en un graf de Bruijn.|849x849px]]

=== Elecció de k-mer ===
L'elecció de la mida del k-mer té moltes implicacions en l'assemblatge de seqüències. Aquests efectes varien molt entre aquells k-mers de mida major i menor. A continuació es descriuen alguns dels efectes segons les mides.

==== k-mers de mides menors ====
* Un k-mer de mida menor disminueix la quantitat d'arestes emmagatzemades en el graf, i com a tal, ajudarà a disminuir la quantitat d'espai necessari per a emmagatzemar les seqüències d'ADN.
* Les mides menors augmenten la possibilitat que tots el k-mers se solapin, i com a tal, tenen així les subseqüències suficients per a construir el graf de Bruijn.<ref>{{Ref-publicació|cognom=Zerbino|nom=Daniel R.|cognom2=Birney|nom2=Ewan|article=Velvet: Algorithms for de novo short read assembly using de Bruijn graphs|publicació=Genome Research|url=http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2336801/|volum=18|exemplar=5|data=2008-5|pàgines=821–829|doi=10.1101/gr.074492.107|issn=1088-9051|pmc=PMC2336801|pmid=18349386}}</ref>
* Tanmateix, en tenir mides de k-mers més petites, també hi ha el risc de tenir més vèrtexs en el graf que dirigeixen a un sol k-mer. Per això, això farà la reconstrucció del genoma més difícil mentre hi hagi un nivell més alt d'ambigüitats de camí a causa de la major quantitat vèrtexs que cal que es recorrin.
* La informació es perd a mesura que el k-mers són menors.
** '''''P.'' ex.''', la possibilitat de AGTCGTAGATGCTG és menor que ACGT, i com a tal, conté una quantitat major d'informació (vegeu [[entropia de Shannon]]).
* Els k-mers més petits també tenen el problema de no ser capaç de resoldre àrees a l'ADN on hi hagi microsatèl·lits o repeticions. Això és perquè els k-mers més petits tendiran a caure enterament dins d'una regió repetitiva i per això es difícil determinar la quantitat de repetició que ha tingut lloc.
** '''''P.'' ex.''', per a la subseqüència ATGTGTGTGTGTGTACG, la quantitat de les repeticions de TG es perdran si es tria un k-mer de mida menor de 16. Això és perquè la majoria del k-mers cauran en la regió repetida i només pot ser descartada mentre repeteixi el mateix k-mer en comptes de referir-se la quantitat de repeticions.

==== k-mers de mides majors ====
* Amb k-mers de mides majors s'augmentarà la quantitat d'arestes en el graf, que implicarà un augment de la quantitat de memòria necessària per emmagatzemar la seqüència d'ADN.
* En augmentar la mida del k-mers, el nombre de vèrtexs també disminuirà. Això ajudarà la construcció del genoma perquè hi hi haurà menys camins per recórrer en el graf.<ref>{{Ref-publicació|cognom=Zerbino|nom=Daniel R.|cognom2=Birney|nom2=Ewan|article=Velvet: Algorithms for de novo short read assembly using de Bruijn graphs|publicació=Genome Research|llengua=en|url=http://genome.cshlp.org/content/18/5/821|volum=18|exemplar=5|data=2008-05-01|pàgines=821–829|doi=10.1101/gr.074492.107|issn=1088-9051|pmid=18349386}}</ref>
* Els k-mers de mides majors corren risc el risc de no tenir vèrtexs de fora de cada k-mer. Això és perquè els k-mers majors augmenten el risc que no se solapin amb un altre k-mer per <math>k-1</math>. Això pot portar a desunions en les lectures, i a un major nombre de [[Còntig|contigs]] menors.

* Els k-mers alleugen el problema de regions repetitives més petites. Això és perquè el k-mer contindrà un equilibri de regions repetitives i seqüències d'ADN adjuntes (donat que siguin d'una mida prou gran) que pot ajudar a resoldre la quantitat de repetició en aquella àrea particular.

== Aplicacions dels k-mers en les anàlisis bioinformàtiques ==
La freqüència d'un conjunt de k-mers en el genoma d'una espècie, en una regió genòmica, o en una classe de seqüències, pot ser
utilitzat com a «signatura» de la seqüència subjacent. Comparar aquestes freqüències és computacionalment més fàcil que un [[Alineament de seqüències|alineament de seqüència]], i és un mètode important en l'anàlisi de seqüències sense alineaments. També pot utilitzar-se com a primer estadi d'anàlisi abans d'un alineament.
* Separació d'espècies diferents en una mescla de material genètic ([[metagenòmica]], [[Microbiota|microbioma]]);<ref>{{Ref-publicació|cognom=Ounit|nom=Rachid|cognom2=Wanamaker|nom2=Steve|cognom3=Close|nom3=Timothy J.|cognom4=Lonardi|nom4=Stefano|article=CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers|publicació=BMC Genomics|url=https://doi.org/10.1186/s12864-015-1419-2|volum=16|data=2015-03-25|pàgines=236|doi=10.1186/s12864-015-1419-2|issn=1471-2164}}</ref><ref>{{Ref-publicació|cognom=Dubinkina|nom=Veronika B.|cognom2=Ischenko|nom2=Dmitry S.|cognom3=Ulyantsev|nom3=Vladimir I.|cognom4=Tyakht|nom4=Alexander V.|cognom5=Alexeev|nom5=Dmitry G.|article=Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis|publicació=BMC Bioinformatics|url=https://doi.org/10.1186/s12859-015-0875-7|volum=17|data=2016-01-16|pàgines=38|doi=10.1186/s12859-015-0875-7|issn=1471-2105}}</ref> pot afegir-se informació de fase/marc de lectura<ref>{{Ref-publicació|cognom=Zhu|nom=Jianfeng|cognom2=Zheng|nom2=Wei-Mou|article=Self-organizing approach for meta-genomes|publicació=Computational Biology and Chemistry|url=http://www.sciencedirect.com/science/article/pii/S1476927114000954|volum=53|exemplar=Part A|data=2014-12-01|pàgines=118–124|doi=10.1016/j.compbiolchem.2014.08.016}}</ref>
* [[DNA barcoding|Barcoding d'ADN]] d'espècies<ref>{{Ref-publicació|cognom=Chor|nom=Benny|cognom2=Horn|nom2=David|cognom3=Goldman|nom3=Nick|cognom4=Levy|nom4=Yaron|cognom5=Massingham|nom5=Tim|article=Genomic DNA k-mer spectra: models and modalities|publicació=Genome Biology|url=https://doi.org/10.1186/gb-2009-10-10-r108|volum=10|data=2009-10-08|pàgines=R108|doi=10.1186/gb-2009-10-10-r108|issn=1474-760X}}</ref><ref>{{Ref-publicació|cognom=Meher|nom=Prabina Kumar|cognom2=Sahu|nom2=Tanmaya Kumar|cognom3=Rao|nom3=A. R.|article=Identification of species based on DNA barcode using k-mer feature vector and Random forest classifier|publicació=Gene|url=http://www.sciencedirect.com/science/article/pii/S0378111916305364|volum=592|exemplar=2|data=2016-11-05|pàgines=316–324|doi=10.1016/j.gene.2016.07.010}}</ref>
* [[Assemblatge de seqüències|Assemblatge de seqüències de novo]]<ref>{{Ref-publicació|cognom=Li|nom=Ruiqiang|cognom2=Zhu|nom2=Hongmei|cognom3=Ruan|nom3=Jue|cognom4=Qian|nom4=Wubin|cognom5=Fang|nom5=Xiaodong|article=De novo assembly of human genomes with massively parallel short read sequencing|publicació=Genome Research|url=http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2813482/|volum=20|exemplar=2|data=2010-2|pàgines=265–272|doi=10.1101/gr.097261.109|issn=1088-9051|pmc=PMC2813482|pmid=20019144}}</ref>
* Classificació de l'[[haplogrup]] [[Mitocondri|mitocondrial]] humà<ref>{{Ref-publicació|cognom=Navarro-Gomez|nom=Daniel|cognom2=Leipzig|nom2=Jeremy|cognom3=Shen|nom3=Lishuang|cognom4=Lott|nom4=Marie|cognom5=Stassen|nom5=Alphons P.M.|article=Phy-Mer: a novel alignment-free and reference-independent mitochondrial haplogroup classifier|publicació=Bioinformatics|llengua=en|url=https://academic.oup.com/bioinformatics/article/31/8/1310/213163|volum=31|exemplar=8|data=2015-04-15|pàgines=1310–1312|doi=10.1093/bioinformatics/btu825|issn=1367-4803}}</ref>
* Detecció d'assemblatge incorrecte de genoma<ref>{{Ref-publicació|cognom=Phillippy|nom=Adam M.|cognom2=Schatz|nom2=Michael C.|cognom3=Pop|nom3=Mihai|article=Genome assembly forensics: finding the elusive mis-assembly|publicació=Genome Biology|url=https://doi.org/10.1186/gb-2008-9-3-r55|volum=9|data=2008-03-14|pàgines=R55|doi=10.1186/gb-2008-9-3-r55|issn=1474-760X}}</ref>
* Detecció ''de novo'' de seqüències repetides com ara [[Transposó|elements transposables]]<ref>{{Ref-publicació|cognom=Price|nom=A. L.|cognom2=Jones|nom2=N. C.|cognom3=Pevzner|nom3=P. A.|article=De novo identification of repeat families in large genomes|publicació=Bioinformatics|llengua=en|url=https://academic.oup.com/bioinformatics/article/21/suppl_1/i351/203096|volum=21|exemplar=Suppl 1|data=2005-06-01|pàgines=i351–i358|doi=10.1093/bioinformatics/bti1018|issn=1367-4803}}</ref>
* Caracterització d'un motiu de seqüència d'unió a [[proteïnes]].<ref>{{Ref-publicació|cognom=Newburger|nom=D. E.|cognom2=Bulyk|nom2=M. L.|article=UniPROBE: an online database of protein binding microarray data on protein-DNA interactions|publicació=Nucleic Acids Research|llengua=en|url=https://academic.oup.com/nar/article/37/suppl_1/D77/1002702|volum=37|exemplar=Database|data=2009-01-01|pàgines=D77–D82|doi=10.1093/nar/gkn660|issn=0305-1048}}</ref> A més dels k-mer, també es poden utilitzar k-mers amb buits (també anomenats q-grams amb buits o llavors espaiades)<ref>{{Ref-publicació|cognom=Ghandi|nom=Mahmoud|cognom2=Lee|nom2=Dongwon|cognom3=Mohammad-Noori|nom3=Morteza|cognom4=Beer|nom4=Michael A.|article=Enhanced Regulatory Sequence Prediction Using Gapped k-mer Features|publicació=PLOS Computational Biology|url=http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1003711|volum=10|exemplar=7|data=2014-07-17|pàgines=e1003711|doi=10.1371/journal.pcbi.1003711|issn=1553-7358}}</ref>
* Identificació de [[Mutació|mutacions]] o [[Polimorfisme (biologia)|polimorfismes]] utilitzant dades de [[Seqüenciació d'ADN|sequenciació]]<ref>{{Ref-publicació|cognom=Nordström|nom=Karl J V|cognom2=Albani|nom2=Maria C|cognom3=James|nom3=Geo Velikkakam|cognom4=Gutjahr|nom4=Caroline|cognom5=Hartwig|nom5=Benjamin|article=Mutation identification by direct comparison of whole-genome sequencing data from mutant and wild-type individuals using k-mers|publicació=Nature Biotechnology|llengua=En|url=https://doi.org/10.1038/nbt.2515|volum=31|exemplar=4|data=2013/04|pàgines=325–330|doi=10.1038/nbt.2515|issn=1546-1696}}</ref>
* Caracterització d'illes CpG per regions flanquejants 
* Detecció de [[Transferència horitzontal de gens|transferència horitzontal]]
* Detecció de contaminació [[Procariotes|bacteriana]] en l'assemblatge d'un genoma [[Eucariotes|eucariota]]
* Detecció de llocs de [[Recombinació genètica|recombinació]]
* Ús de la freqüència del k-mer respecte la profunditat del k-mer per calcular la mida de genoma 
* Estimació del nivell de [[RNA-Seq|RNA-seq]]

== Pseudocodi ==
Determinar els possible k-mers d'una lectura pot fer-se simplement entrant en un bucle prenent la longitud de la cadena per un i prenent cada subcadena de longitud, k. El pseudocodi per a fer-ho podria ser el següent:
<pre>
procediment k-mer(Cadena, k : longitud de cada k-mer)

 n = longitud(Cadena)

 /* itera sobre la longitud de la Cadena fins que es puguin fer k-mers de longitud k */
 itera i = 1 a n-k+1 inclosos fes
 /* sortida de cada k-mer de longitud k, de i a i+k en Cadena*/
 sortida Cadena[i:i+k]
 fi itera

fi procediment

</pre>

=== Python ===
<syntaxhighlight lang="python">
def find_kmers(string, k):

  kmers = []
 n = len(string)

 for i in range(0, n-k+1):
  kmers.append(string[i:i+k])

 return kmers

</syntaxhighlight>

== Exemples ==
A continuació es mostren alguns exemples amb els possibles k-mers de seqüències d'ADN (donat un valor de k determinat):
 '''''Seq''''': AGATCGAGTG
 '''''3-mers''''': AGA GAT ATC TCG CGA GAG AGT GTG

 '''''Seq''''': GTAGAGCTGT
 '''''5-mers''''': GTAGA TAGAG AGAGC GAGCT AGCTG GCTGT

== Referències ==
{{Referències|}}
[[Categoria:Aminoàcids]]
[[Categoria:Matemàtica aplicada]]
[[Categoria:Bioinformàtica]]
[[Categoria:Biofísica]]
[[Categoria:Àcids nucleics]]