Compressing, storing and searching sequence data

Abstract

The redundancy in genomic sequence data is exploited by compressing sequence data in such a way as to allow direct computation on the compressed data using methods that are referred to herein as “compressive” algorithms. This approach reduces the task of computing on many similar genomes to only slightly more than that of operating on just one. In this approach, the redundancy among genomes is translated into computational acceleration by storing genomes in a compressed format that respects the structure of similarities and differences important to analysis. Specifically, these differences are the nucleotide substitutions, insertions, deletions, and rearrangements introduced by evolution. Once such a compressed library has been created, analysis is performed on it in time proportional to its compressed size, rather than having to reconstruct the full data set every time one wishes to query it.

What we claim is as follows: 
     
         1 . A computer program product, executed in one or more computing entities, comprising a non-transitory computer readable medium storing computer program code configured to:
 compress an original data sequence into a data structure having first and second portions, the first portion comprising the original data sequence with one or more sequence fragments therein that have been found sufficiently similar to previously-identified fragments being replaced by links, the second portion comprising the links; and   in response to a query, search the first and second portions of the data structure, in lieu of the original data sequence, to identify a portion of the genomic sequence data.   
     
     
         2 . The computer program product as described in  claim 1  wherein the program code configured to search comprises program code configured to:
 search the first portion to locate one or more hits passing a first, coarse threshold; 
 for each of the one or more hits, examine the second portion to identify other segments of the data sequence that potentially align to the hit; 
 for each of the one or more other segments of the data sequence that potentially align to the hit, recover an actual segment from the original data sequence; and 
 search each actual segment so recovered to locate one or more hits passing a second, fine-grained threshold. 
 
     
     
         3 . The computer program product described in  claim 1  wherein the original data sequence is a genomic sequence. 
     
     
         4 . The computer program product as described in  claim 4  wherein the search of the data structure is carried out using one of: BLAST, and BLAT. 
     
     
         5 . The computer program product as described in  claim 1  wherein the program code configured to compress is executed to trade-off execution speed against an amount of data stored in the first portion of the data structure.