Method for the Compression of Genome Sequence Data

Abstract

The invention relates to a reference-based method for the compression of genome sequence data produced by a sequencing machine. The sequences of nucleotides or bases, that have been previously aligned to a reference sequence, are determined to be perfectly mapped, imperfectly mapped or unmapped with the reference sequence; and then coded according to said determination. The determining step comprises comparing, for each imperfectly mapped sequence, the number of mismatches between said sequence and the reference sequence with a reference threshold value, and encoding the imperfectly mapped sequences according to distinct encoding processes, depending on the result of said comparison method for the compression of genome sequence data produced by a sequencing machine.

1 - 49 . (canceled) 
     
     
         50 . A method for compressing genomic sequence data, the method comprising:
 accessing, by the one or more processors, a storage device storing a plurality of read records in manner that preserves a sequence ordering of the read records as produced by a mapping and aligning module, the plurality of read records each corresponding to a perfectly mapped read or an imperfectly mapped read;   for each particular read record of the plurality of read records:
 obtaining, by the one or more processors, the particular read record generated based on data output by the mapping and aligning module, wherein the particular read record includes data indicating whether a read that corresponds to the particular read record is perfectly mapped or imperfectly mapped; 
 determining, by the one or more processors and based on the particular read record, whether the particular read record corresponds to a read that is perfectly mapped to a reference sequence or imperfectly mapped to the reference sequence; 
 based on determining, by the one or more processors, that the particular read record corresponds to a read that is imperfectly mapped to the reference sequence, determining, by the one or more processors, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches; 
 based on determining that the number of mismatches satisfies the predetermined threshold number of mismatches, encoding, by the one or more processors, each mismatch of the imperfectly mapped read into a compressed record having a predetermined compressed record size; and 
 storing, by the one or more processors, the compressed record in the storage device while maintaining the sequence ordering of the plurality of read records. 
   
     
     
         51 . The method of  claim 50 , wherein each read record of the plurality of read records further includes:
 data indicating an absolute starting position of the aligned read with respect to the reference sequence,   data indicating a length of the read,   data indicating a number of mismatches identified in the read,   data indicating whether the read includes at least one undetermined base N,   data indicating a number of undetermined bases N in the read,   data indicating whether the read is mapped or unmapped,   data indicating a position of the read record in a sequence of read records output by the mapping and aligning module, and   data indicating a relative position of said possible mismatches in the read.   
     
     
         52 . The method of  claim 50 , wherein the predetermined compressed record size is one byte. 
     
     
         53 . The method of  claim 52 , wherein encoding each mismatch of the imperfectly mapped read into a compressed record having a size of one byte comprises for each particular mismatch:
 encoding, by one or more processors, a first two bits of the byte to include data representing an alternate nucleotide or base present in the read instead of a corresponding reference nucleotide or base in the reference sequence; and   encoding, by one or more processors, a six remaining bits of the byte to include data representing a position of the mismatch in the reference sequence, said position being computed as an offset from a previous mismatch of the read.   
     
     
         54 . The method of  claim 50 , the method further comprising:
 determining, by one or more processors, whether the offset is greater than a maximum encodable value;   based on determining that the offset is greater than the maximum encoded value, inserting, by one or more processors, at least one fake mismatch between the particular mismatch and the previous mismatch.   
     
     
         55 . The method of  claim 50 , wherein the method further comprises:
 based on determining that the number of mismatches does not satisfy the predetermined threshold number of mismatches, encoding, by one or more processors, a list of positions of the reference sequence corresponding to a position of each of the mismatches to the reference sequence using a reduced information entropy encoding process.   
     
     
         56 . The method of  claim 50 , wherein the method further comprises:
 based on determining that the read record corresponds to a read that is perfectly mapped to the reference sequence, encoding, by the one or more processors, at least a portion of the read record using reduced information entropy encoding.   
     
     
         57 . The method of  claim 50 , wherein determining, by the one or more processors, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches comprises:
 determining, by the one or more processors, whether the number of mismatches of the imperfectly mapped read is greater than the reference threshold.   
     
     
         58 . A system for compressing genomic sequence data, the system comprising:
 one or more computers and one or more storage devices storing instructions that are operable, when executed by one or more computers, to cause the one or more computers to perform the operations comprising:   accessing, by the one or more computers, a storage device storing a plurality of read records in manner that preserves a sequence ordering of the read records as produced by a mapping and aligning module, the plurality of read records each corresponding to a perfectly mapped read or an imperfectly mapped read;   for each particular read record of the plurality of read records:
 obtaining, by the one or more computers, the particular read record generated based on data output by the mapping and aligning module, wherein the particular read record includes data indicating whether a read that corresponds to the particular read record is perfectly mapped or imperfectly mapped; 
 determining, by the one or more computers and based on the particular read record, whether the particular read record corresponds to a read that is perfectly mapped to a reference sequence or imperfectly mapped to the reference sequence; 
 based on determining, by the one or more computers, that the particular read record corresponds to a read that is imperfectly mapped to the reference sequence, determining, by the one or more computers, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches; 
 based on determining that the number of mismatches satisfies the predetermined threshold number of mismatches, encoding, by the one or more computers, each mismatch of the imperfectly mapped read into a compressed record having a predetermined compressed record size; and 
 storing, by the one or more computers, the compressed record in the storage device while maintaining the sequence ordering of the plurality of read records. 
   
     
     
         59 . The system of  claim 58 , wherein each read record of the plurality of read records further includes:
 data indicating an absolute starting position of the aligned read with respect to the reference sequence,   data indicating a length of the read,   
       data indicating a number of mismatches identified in the read,
 data indicating whether the read includes at least one undetermined base N, 
 data indicating a number of undetermined bases N in the read, 
 data indicating whether the read is mapped or unmapped, 
 data indicating a position of the read record in a sequence of read records output by the mapping and aligning module, and 
 data indicating a relative position of said possible mismatches in the read. 
 
     
     
         60 . The system of  claim 58 , wherein the predetermined compressed record size is one byte. 
     
     
         61 . The system of  claim 60 , wherein encoding each mismatch of the imperfectly mapped read into a compressed record having a size of one byte comprises for each particular mismatch:
 encoding, by one or more computers, a first two bits of the byte to include data representing an alternate nucleotide or base present in the read instead of a corresponding reference nucleotide or base in the reference sequence; and   encoding, by one or more computers, a six remaining bits of the byte to include data representing a position of the mismatch in the reference sequence, said position being computed as an offset from a previous mismatch of the read.   
     
     
         62 . The system of  claim 58 , the operations further comprising:
 determining, by the one or more computers, whether the offset is greater than a maximum encodable value;   based on determining that the offset is greater than the maximum encoded value, inserting, by the one or more computers, at least one fake mismatch between the particular mismatch and the previous mismatch.   
     
     
         63 . The system of  claim 58 , the operations further comprising:
 based on determining that the number of mismatches does not satisfy the predetermined threshold number of mismatches, encoding, by one or more computers, a list of positions of the reference sequence corresponding to a position of each of the mismatches to the reference sequence using a reduced information entropy encoding process.   
     
     
         64 . The system of  claim 58 , the operations further comprising:
 based on determining that the read record corresponds to a read that is perfectly mapped to the reference sequence, encoding, by one or more computers, at least a portion of the read record using reduced information entropy encoding.   
     
     
         65 . The system of  claim 58 , wherein determining, by the one or more computers, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches comprises:
 determining, by the one or more computers, whether the number of mismatches of the imperfectly mapped read is greater than the predetermined threshold number of mismatches.   
     
     
         66 . A computer-readable storage device having stored thereon instructions, which, when executed by a data processing apparatus, cause the data processing apparatus to perform operations for compressing genomic sequence data, the operations comprising:
 accessing a storage device storing a plurality of read records in manner that preserves a sequence ordering of the read records as produced by a mapping and aligning module, the plurality of read records each corresponding to a perfectly mapped read or an imperfectly mapped read;   for each particular read record of the plurality of read records:
 obtaining the particular read record generated based on data output by the mapping and aligning module, wherein the particular read record includes data indicating whether a read that corresponds to the particular read record is perfectly mapped or imperfectly mapped; 
 determining, based on the particular read record, whether the particular read record corresponds to a read that is perfectly mapped to a reference sequence or imperfectly mapped to the reference sequence; 
 based on determining that the particular read record corresponds to a read that is imperfectly mapped to the reference sequence, determining whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches; 
 based on determining that the number of mismatches satisfies the predetermined threshold number of mismatches, encoding each mismatch of the imperfectly mapped read into a compressed record having a predetermined compressed record size; and 
 storing the compressed record in the storage device while maintaining the sequence ordering of the plurality of read records. 
   
     
     
         67 . The computer-readable storage device of  claim 66 , wherein each read record of the plurality of read records comprises:
 data indicating an absolute starting position of the aligned read with respect to the reference sequence,   data indicating a length of the read,   data indicating a number of mismatches identified in the read,   data indicating whether the read includes at least one undetermined base N,   data indicating a number of undetermined bases N in the read,   data indicating whether the read is mapped or unmapped,   data indicating a position of the read record in a sequence of read records output by the mapping and aligning module, and   data indicating a relative position of said possible mismatches in the read.   
     
     
         68 . The computer-readable storage device of  claim 66 , wherein the predetermined compressed record size is one byte. 
     
     
         69 . The computer-readable storage device of  claim 68 , wherein encoding each mismatch of the imperfectly mapped read into a compressed record having a size of one byte comprises for each particular mismatch:
 encoding a first two bits of the byte to include data representing an alternate nucleotide or base present in the read instead of a corresponding reference nucleotide or base in the reference sequence; and   encoding a six remaining bits of the byte to include data representing a position of the mismatch in the reference sequence, said position being computed as an offset from a previous mismatch of the read.   
     
     
         70 . The computer-readable storage device of  claim 66 , the operations further comprising:
 determining whether the offset is greater than a maximum encodable value;   based on determining that the offset is greater than the maximum encoded value, inserting at least one fake mismatch between the particular mismatch and the previous mismatch.   
     
     
         71 . The computer-readable storage device of  claim 66 , the operations further comprising:
 based on determining that the number of mismatches does not satisfy the predetermined threshold number of mismatches, encoding a list of positions of the reference sequence corresponding to a position of each of the mismatches to the reference sequence using a reduced information entropy encoding process.   
     
     
         72 . The computer-readable storage device of  claim 66 , the operations further comprising:
 based on determining that the read record corresponds to a read that is perfectly mapped to the reference sequence, encoding at least a portion of the read record using reduced information entropy encoding.   
     
     
         73 . The computer-readable storage device of  claim 66 , wherein determining whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches comprises:
 determining whether the number of mismatches of the imperfectly mapped read is greater than the predetermined threshold number of mismatches.   
     
     
         74 . A hardware processor that includes hardware processing circuitry that is configured to perform one or more operations, the one or more operations comprising:
 accessing, by the hardware processing circuitry, a storage device storing a plurality of read records in manner that preserves a sequence ordering of the read records as produced by a mapping and aligning module, the plurality of read records each corresponding to a perfectly mapped read or an imperfectly mapped read;   for each particular read record of the plurality of read records:
 obtaining, by the hardware processing circuitry, the particular read record generated based on data output by the mapping and aligning module, wherein the particular read record includes data indicating whether a read that corresponds to the particular read record is perfectly mapped or imperfectly mapped; 
 determining, by the hardware processing circuitry and based on the particular read record, whether the particular read record corresponds to a read that is perfectly mapped to a reference sequence or imperfectly mapped to the reference sequence; 
 based on determining, by the hardware processing circuitry, that the particular read record corresponds to a read that is imperfectly mapped to the reference sequence, determining, by the hardware processing circuitry, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches; 
 based on determining that the number of mismatches satisfies the predetermined threshold number of mismatches, encoding, by the hardware processing circuitry, each mismatch of the imperfectly mapped read into a compressed record having a predetermined compressed record size; and 
 storing, by the hardware processing circuitry, the compressed record in the storage device while maintaining the sequence ordering of the plurality of read records. 
   
     
     
         75 . The hardware processor of  claim 74 , wherein each read record of the plurality of read records further include:
 data indicating an absolute starting position of the aligned read with respect to the reference sequence,   data indicating a length of the read,   data indicating a number of mismatches identified in the read,   data indicating whether the read includes at least one undetermined base N,   data indicating a number of undetermined bases N in the read,   data indicating whether the read is mapped or unmapped,   data indicating a position of the read record in a sequence of read records output by the mapping and aligning module, and   data indicating a relative position of said possible mismatches in the read.   
     
     
         76 . The hardware processor of  claim 74 , wherein the predetermined compressed record size is one byte. 
     
     
         77 . The hardware processor of  claim 76 , wherein encoding each mismatch of the imperfectly mapped read into a compressed record having a size of one byte comprises for each particular mismatch:
 encoding, by the hardware processing circuitry, a first two bits of the byte to include data representing an alternate nucleotide or base present in the read instead of a corresponding reference nucleotide or base in the reference sequence; and   encoding, by the hardware processing circuitry, a six remaining bits of the byte to include data representing a position of the mismatch in the reference sequence, said position being computed as an offset from a previous mismatch of the read.   
     
     
         78 . The hardware processor of  claim 74 , the hardware processor further comprising:
 determining, by the hardware processing circuitry, whether the offset is greater than a maximum encodable value;   based on determining that the offset is greater than the maximum encoded value, inserting, by the hardware processing circuitry, at least one fake mismatch between the particular mismatch and the previous mismatch.   
     
     
         79 . The hardware processor of  claim 74 , the hardware processor further comprising:
 based on determining that the number of mismatches does not satisfy the predetermined threshold number of mismatches, encoding, by the hardware processing circuitry, a list of positions of the reference sequence corresponding to a position of each of the mismatches to the reference sequence using a reduced information entropy encoding process.   
     
     
         80 . The hardware processor of  claim 74 , the hardware processor further comprising:
 based on determining that the read record corresponds to a read that is perfectly mapped to the reference sequence, encoding, by the hardware processing circuitry, at least a portion of the read record using reduced information entropy encoding.   
     
     
         81 . The hardware processor of  claim 74 , wherein determining, by the hardware processing circuitry, whether a number of mismatches of the imperfectly mapped read satisfies a predetermined threshold number of mismatches comprises:
 determining, by the hardware processing circuitry, whether the number of mismatches of the imperfectly mapped read is greater than the predetermined threshold number of mismatches.