Restricciones

Para dar seguimiento a la respuesta de Devon Ryan, pensé que sería un poco divertido escribir un script de Python que demuestre el uso de una matriz de bits para mantener una tabla de presencia / ausencia.

Nota: escribí una Puerto C ++ que incluye una implementación de conjunto de bits personalizada que se puede dimensionar en tiempo de ejecución. Este y el script de Python están disponibles en Github: https://github.com/alexpreynolds/kmer-boolean

  #! / Usr / bin / env pythonimport sysimport osimport bitarray # read FASTAdef read_sequences (): global seqs seqs = [] seq = "" para la línea en sys.stdin: if line.startswith ('>'): if len (seq) > 0: seqs.append (seq) seq = "" else: seq + = line.strip () seqs.append (seq) # construir e inicializar matriz de bits def initialize_bitarray (): global ba ba = bitarray.bitarray (4 ** k) ba.setall (False) sys .stderr.write ("El uso de la memoria de la instancia de bitarray.bitarray es [% ld] bytes \ n"% (ba.buffer_info () [1])) seqs: para i en rango (0, len (seq)): kmer = seq [i: i + k] if len (kmer) == k: observado_kmers [kmer] = Ninguno idx = 0 para j en rango (k-1, -1, -1): idx + = 4 ** (kj-1) * bm [kmer [j]] ba [idx] = Truedef test_bitarray (): test_idx = 0 para j en rango (k-1, -1, -1): test_idx + = 4 ** (kj-1) * bm [test_kmer [j]] test_result = ba [test_idx] if test_result: sys.stdout.write ("% s encontrado \ n "% (test_kmer)) sys.exit (os.EX_OK) else: sys.stdout.write ("% s no encontrado \ n "% (test_kmer)) sys.exit (os.EX_DATAERR) def main (): global kk = int (sys.argv [1]) global bm bm = {'A': 0, 'C': 1, 'T': 2, 'G': 3} read_sequences () initialize_bitarray () process_sequences () intente: global test_kmer test_kmer = sys.argv [2] if len (test_kmer) == k:
test_bitarray () else: raise ValueError ("test kmer (% s) debe ser de longitud k (% d)"% (test_kmer, k)) excepto IndexError como err: keys = list (observe_kmers.keys ()) para i en range (0, len (claves)): sys.stdout.write ("% s encontrado \ n"% (claves [i])) sys.exit (os.EX_OK) if __name __ == "__main__": main () 

Tenga en cuenta que esto no tiene en cuenta los kmers canónicos, por ejemplo , AG se considera un 2mer distinto de su complemento inverso CT .

Para usar este script, ingrese su FASTA, especifique la k y un kmer opcional que desee probar para presencia / ausencia, eg:

  $ echo -e ">foo \ nCATTCTC \ nGGGAC \ n>bar \ nTTATAT \ n>baz \ nTTTATTAG \ nACCTCT" | ./kmer-bool.py 2 El uso de CGMemory de la instancia bitarray.bitarray es [2] bytesCG encontrado  

O:

  $ echo -e ">foo \ nCATTCTC \ nGGGAC \ n>bar \ nTTATAT \ n>baz \ nTTTATTAG \ nACCTCT "| ./kmer-bool.py 3 AAAMemory El uso de la instancia de bitarray.bitarray es [8] bytesAAA no encontrado  

O si la prueba opcional kmer se omite:

  $ echo -e ">foo \ nCATTCTC \ nGGGAC \ n>bar \ nTTATAT \ n>baz \ nTTTATTAG \ nACCTCT" | ./kmer-bool.py 5El uso de memoria de la instancia bitarray.bitarray es [128] bytesCATTC encontradoATTCT encontradoTTCTC encontradoTCTCG encontradoCTCGG encontradoTCGGG encontradoCGGGA encontradoGGGAC encontradoTTATA encontradoTATAT encontradoTTTAT encontradoTTATT encontradoTATTA encontradoATTAG encontradoTCCTAGAACTA encontradoTATTA encontrado O para los ~ 67M kmers en un conjunto de 13 meros, para el cual se reserva una matriz de bits de aproximadamente 8.4 MB:  
  $ echo -e ">foo \ nCATTCTC \ nGGGAC \ n>bar \ nTTATAT \ n>baz \ nTTTATTAG \ nACCTCT "| ./kmer-bool.py 13 El uso de memoria de la instancia de bitarray.bitarray es [8388608] bytesTTTATTAGACCTC encontradoTTATTAGACCTCT encontrado  

Si simplemente necesita un conjunto de k-mers presentes / ausentes y su longitud de kmer es corta, entonces convierta la longitud de secuencia a un número entero (un 13-mer requeriría 26 bits o 4 bytes) y utilícelo como índice en una matriz de bits. Inicialice la matriz a 0 y use 1 para "k-mer present". Si tiene ~ 67 millones de k-mers, entonces su matriz es de 67 millones de bits, que es solo alrededor de 8.5 megas.

Esto escalará "OK", pero eventualmente aumentará a un tamaño enorme si usa k más grandes. -mers. En ese punto, simplemente tiene que usar otras estructuras de datos. La realidad es que la mayoría de las aplicaciones son bastante tolerantes a pequeños errores.

Creo que mis cálculos deben ser incorrectos. De lo contrario, ¿cómo podrían los programas contar kmers en RAM?

Los contadores de k-mer basados ​​en tablas hash solo mantienen los k-mers vistos en los datos. Por $ 16<k \ le32 $, necesita enteros de 64 bits para almacenar un k-mer. Dados $ n $ k-mers distintos, una implementación ingenua con tabla hash de direccionamiento abierto tomaría aproximadamente $ 2n \ cdot 64/8 = 16n $ bytes. Suponemos que la mesa está medio llena; de aquí es de donde proviene el factor 2. Existen varios trucos para reducir la huella de memoria. Será mejor que lea los periódicos. En una nota al margen, no use std :: unordered_map. Desperdicia memoria extra.

Un mapa de bits descrito por otras respuestas toma $ 4 ^ k / 8 = 2 ^ {2k-3} $ bytes, que es una mejor opción a veces, pero rara vez se usa por contadores k-mer ya que tampoco funciona con k long. Los índices trie o de texto completo son exagerados para k-mers fijos y suelen ser más lentos.

Por cierto, esta pregunta me recuerda su pregunta sobre el complemento inverso eficiente. Tenga en cuenta que para el conteo de k-mer, atraviesa ambos hilos al mismo tiempo. No debe complementar todo el k-mer al revés.