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

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 grafs de Bruijn. Per tal de crear-ne un, les cadenes que s'emmagatzemen en cada aresta amb una longitud, $L$, han de solapar-se amb una altra cadena en una altra aresta per $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 $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. 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.

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.

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

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üè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); pot afegir-se informació de fase/marc de lectura
• Barcoding d'ADN d'espècies
• Assemblatge de seqüències de novo
• Classificació de l'haplogrup mitocondrial humà
• Detecció d'assemblatge incorrecte de genoma
• Detecció de novo de seqüències repetides com ara elements transposables
• Caracterització d'un motiu de seqüència d'unió a proteïnes. A més dels k-mer, també es poden utilitzar k-mers amb buits (també anomenats q-grams amb buits o llavors espaiades)
• Identificació de mutacions o polimorfismes utilitzant dades de sequenciació
• 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

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:

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

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

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