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 ${\displaystyle L-k+1}$, mentre que el nombre de possibles k-mers donades n possibilitats (4 en el cas d'ADN, p. ex. ACTG) és ${\displaystyle n^{k}}$. Els k-mers s'utilitzen normalment en l'assemblatge de seqüències, però també en l'alineament de seqüències.^[1] En el context del genoma humà, k-mers de diverses longituds s'han utilitzat per explicar la variabilitat dels índexs de mutació.^[2][3]

En el context de l'assemblatge de seqüències, els k-mers s'utilitzen en el procés de creació de grafs de Bruijn. Per tal de crear-ne un, les cadenes que s'emmagatzemen en cada aresta amb una longitud, ${\displaystyle L}$, han de solapar-se amb una altra cadena en una altra aresta per ${\displaystyle L-1}$ per tal de crear un vertex. Les lectures obtingudes del procés de seqüenciació tindran diferents longituds. Posem el cas, amb la seqüenciació d'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 ${\displaystyle k-1}$ (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.^[1] 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.

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.

• 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.^[4]
• 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.

• 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.^[5]
• 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 ${\displaystyle k-1}$. Això pot portar a desunions en les lectures, i a un major nombre de 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.

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üè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, microbioma);^[6][7] pot afegir-se informació de fase/marc de lectura^[8]
• Barcoding d'ADN d'espècies^[9][10]
• Assemblatge de seqüències de novo^[11]
• Classificació de l'haplogrup mitocondrial humà^[12]
• Detecció d'assemblatge incorrecte de genoma^[13]
• Detecció de novo de seqüències repetides com ara elements transposables^[14]
• Caracterització d'un motiu de seqüència d'unió a proteïnes.^[15] A més dels k-mer, també es poden utilitzar k-mers amb buits (també anomenats q-grams amb buits o llavors espaiades)^[16]
• Identificació de mutacions o polimorfismes utilitzant dades de sequenciació^[17]
• Caracterització d'illes CpG per regions flanquejants
• Detecció de transferència horitzontal
• Detecció de contaminació bacteriana en l'assemblatge d'un genoma eucariota
• Detecció de llocs de 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

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:

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

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

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