Software accelerated genomic read mapping

Abstract

Methods, systems, apparatus, and computer programs are disclosed for software-accelerated genomic data read mapping. In one aspect, the methods can include actions of obtaining a k-mer seed from a genomic data read, generating a genomic signature based on the obtained k-mer seed, determining a reference sequence location that match at least a portion of the k-mer seed using a hash data structure, wherein the hash data structure comprises N data cells comprising a first portion storing a predetermined genomic signature and a second portion storing a value that corresponds to a first occurrence of a reference sequence location that match at least a portion of the k-mer seed from which the predetermined genomic signature was derived, and selecting the determined reference sequence location as an actual alignment for the obtained k-mer seed based on one or more alignment scores.

1 - 20 . (canceled) 
     
     
         21 . A method for software-accelerated genomic data read mapping, the method comprising:
 obtaining, by one or more computers, a k-mer seed from a genomic data read;   generating, by one or more computers, a genomic signature using a first hash function operating on the obtained k-mer seed;   determining, by one or more computers, a reference sequence location that matches at least a portion of the k-mer seed using the genomic signature and a hash data structure, wherein the hash data structure comprises N data cells comprising a first portion stored at an index generated using a second hash function operating on a reference k-mer seed and a second portion storing a value indicating a reference sequence location of the reference k-mer seed; and   selecting, by one or more computers, the reference sequence location as an actual alignment for the obtained k-mer seed based on one or more alignment scores.   
     
     
         22 . The method of  claim 21 , wherein the first portion occupies one byte of memory storage. 
     
     
         23 . The method of  claim 21 , wherein the second portion occupies four bytes of memory storage. 
     
     
         24 . The method of  claim 21 , wherein the hash data structure is a single array of N data cells. 
     
     
         25 . The method of  claim 21 , further comprising:
 filtering, by one or more computers, the genomic data read based on a first set of values corresponding to one or more k-mer seeds of the genomic data read.   
     
     
         26 . The method of  claim 25 , wherein the first set of values comprises a result of a predetermined operation applied to the one or more k-mer seeds of the genomic data read, and wherein the first set of values is used to obtain the k-mer seed from the genomic data read. 
     
     
         27 . The method of  claim 26 , wherein the predetermined operation comprises generating a hash value based on the one or more k-mer seeds of the genomic data read and a hash function. 
     
     
         28 . The method of  claim 21 , wherein determining the reference sequence location comprises:
 computing, by one or more computers, a first position for the k-mer seed of the genomic data read, wherein the first position corresponds to a location of the k-mer seed within the genomic data read; and   computing, by one or more computers, a second position for the k-mer seed, wherein the second position corresponds to a location of the k-mer seed within reference genomic data, and wherein the second position is computed based on the hash data structure.   
     
     
         29 . The method of  claim 21 , further comprising:
 sorting, by one or more computers, one or more reference sequence locations based on the hash data structure and the genomic data read.   
     
     
         30 . The method of  claim 21 , further comprising:
 generating, by one or more computers, the one or more alignment scores based on sorting one or more reference sequence locations.   
     
     
         31 . The method of  claim 21 , wherein selecting the reference sequence location as the actual alignment for the obtained k-mer seed comprises comparing the one or more alignment scores to a threshold value. 
     
     
         32 . The method of  claim 21 , wherein the one or more alignment scores comprise a numerical value representing a number of mismatches between the obtained k-mer seed from the genomic data read and the reference sequence location. 
     
     
         33 . The method of  claim 21 , wherein each subsequent occurrences of a reference sequence location that matches at least a portion of the k-mer seed from which the genomic signature was derived after a first occurrence is discarded. 
     
     
         34 . A system for software-accelerated genomic data read mapping, the system comprising:
 one or more computers; and   one or more memories storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations, the operations comprising:
 obtaining a k-mer seed from a genomic data read; 
 generating a genomic signature using a first hash function operating on the obtained k-mer seed; 
 determining a reference sequence location that matches at least a portion of the k-mer seed using the genomic signature and a hash data structure, wherein the hash data structure comprises N data cells comprising a first portion stored at an index generated using a second hash function operating on a reference k-mer seed and a second portion storing a value indicating a reference sequence location of the reference k-mer seed; and 
 selecting the reference sequence location as an actual alignment for the obtained k-mer seed based on one or more alignment scores. 
   
     
     
         35 . The system of  claim 34 , wherein the first portion occupies one byte of memory storage. 
     
     
         36 . The system of  claim 34 , wherein the value occupies four bytes of memory storage. 
     
     
         37 . The system of  claim 34 , wherein the hash data structure is a single array of N data cells. 
     
     
         38 . The system of  claim 34 , wherein the operations comprise:
 filtering the genomic data read based on a first set of values corresponding to one or more k-mer seeds of the genomic data read.   
     
     
         39 . The system of  claim 38 , wherein the first set of values comprises a result of a predetermined operation applied to the one or more k-mer seeds of the genomic data read, and wherein the first set of values is used to obtain the k-mer seed from the genomic data read. 
     
     
         40 . A computer-readable medium storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations for software-accelerated genomic data read mapping, the operations comprising:
 obtaining, by one or more computers, a k-mer seed from a genomic data read;   generating, by the one or more computers, a genomic signature using a first hash function operating on the obtained k-mer seed;   determining, by one or more computers, a reference sequence location that matches at least a portion of the k-mer seed using the genomic signature and a hash data structure, wherein the hash data structure comprises N data cells comprising a first portion stored at an index generated using a second hash function operating on a reference k-mer seed and a second portion storing a value indicating a reference sequence location of the reference k-mer seed; and   selecting, by one or more computers, the reference sequence location as an actual alignment for the obtained k-mer seed based on one or more alignment scores.