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 - 17 . (canceled) 
     
     
         18 . A computer-implemented method for the compression of genome sequence data produced by a sequencing machine, said genome sequence data comprising reads of sequences of nucleotides or bases that have been aligned to a reference sequence, thereby creating aligned reads, said aligned reads being stored as a list of reads in an initial file, said method comprising the steps of:
 for each aligned read, determining whether said read is perfectly or imperfectly mapped with said reference sequence or whether said read is unmapped with said reference sequence,   encoding the reads according to said determination, wherein the reads that are determined to be perfectly mapped are encoded according to a first encoding process and the reads that are determined to be unmapped are encoded according to a second encoding process,   wherein the determining step comprises comparing, for each imperfectly mapped read, the number of mismatches between said read and said reference sequence with a threshold value,   wherein, in the encoding step, the reads that are determined to be imperfectly mapped are encoded according to the second encoding process or to a third encoding process, the imperfectly mapped reads being encoded according to the second encoding process when said number of mismatches is greater than the threshold value, the imperfectly mapped reads being encoded according to the third encoding process when said number of mismatches is lower than the threshold value,   wherein, in said second encoding process, each nucleotide or base of the read is individually encoded,   wherein said first and third encoding processes comprise distinct sets of descriptors, each set of descriptors univocally representing the reads associated to the corresponding encoding process, each of said first and third encoding processes being a reduced information source entropy encoding process.   
     
     
         19 . The method of  claim 18 , wherein the determining step comprises, when a read is determined to be imperfectly mapped with the reference sequence and has a number of mismatches lower than the threshold value, a further determination as to whether the read is globally or locally mapped with said reference sequence, and wherein the third encoding process comprises a first encoding subprocess and a second encoding subprocess, the reads that are determined to be globally mapped being encoded according to the first encoding subprocess, the reads that are determined to be locally mapped being encoded according to the second encoding subprocess, said first and second encoding subprocesses comprising distinct sets of descriptors, each set of descriptors univocally representing the reads associated to the corresponding encoding subprocess. 
     
     
         20 . The method of  claim 19 , wherein said descriptors of said first encoding subprocess comprise an alignment start position in the reference sequence, a read length and a list of mismatches by substitutions of symbols, and wherein said descriptors of said second encoding subprocess comprise a local alignment start position in the reference sequence, a read length, a list of mismatches by substitutions of symbols, and a length of the clipped portions of the read that are not part of the alignment. 
     
     
         21 . The method of  claim 20 , wherein, in the encoding step, the clipped portions of a read that is to be encoded according to the second encoding subprocess are concatenated, each nucleotide or base of said clipped portions being individually encoded. 
     
     
         22 . The method of any of  claim 18 , wherein, in the encoding step, each mismatch of an imperfectly mapped read is encoded on 1 byte. 
     
     
         23 . The method of  claim 22 , wherein, in the encoding step, each mismatch of an imperfectly mapped read is encoded as follows:
 the two first bits of the byte are used to encode the alternate nucleotide or base present in the read instead of the corresponding reference nucleotide or base in the reference sequence;   the six last bits are used to encode the position of the mismatch in the reference sequence, said position being computed as an offset from the previous mismatch of the read.   
     
     
         24 . The method of  claim 23 , wherein, in the encoding step, if the offset computed between a given mismatch and the previous mismatch is greater than a maximum encodable value, then at least one fake mismatch is inserted between said two mismatches until every offset between each of said mismatches and said at least one fake mismatch is lower than said maximum encodable value, a fake mismatch being defined as a mismatch for which the bits of the byte used to encode the mismatch encode a nucleotide or base that is equal to the corresponding reference nucleotide or base in the reference sequence. 
     
     
         25 . The method of  claim 18 , further comprising an initial step of dividing the list of reads into blocks of reads, with each block beginning with a header containing information needed to decode the block, wherein said compression method is performed block by block. 
     
     
         26 . The method of  claim 25 , wherein the blocks of reads have the same block size. 
     
     
         27 . The method of  claim 18 , further comprising a final step of providing a compressed file comprising a list of encoded reads, said encoded reads being stored in the compressed file in the same order as that of the reads stored in the initial file. 
     
     
         28 . The method of  claim 18 , wherein said threshold value is equal to 31. 
     
     
         29 . The method of  claim 18 , further comprising, for each aligned read, a step of determining whether said read comprises at least one mismatch corresponding to a case in which the sequencing machine was unable to call any base or nucleotide. 
     
     
         30 . The method of  claim 29 , further comprising, for each read comprising at least one mismatch corresponding to a case in which the sequencing machine was unable to call any base or nucleotide, a step of determining the number of such mismatches and a step of comparing said number with a reference threshold value. 
     
     
         31 . The method of  claim 30 , wherein, in the encoding step, if the number of such mismatches is greater than the reference threshold value, each nucleotide or base of a read that is to be encoded according to the second encoding process is individually encoded on 4 bits, and, if the number of such mismatches is lower than the reference threshold value, each nucleotide or base of a read that is to be encoded according to the second encoding process is individually encoded on 2 bits and the encoding step further comprises encoding a list of positions along the reference sequence, said positions corresponding to the positions of such mismatches in the reference sequence. 
     
     
         32 . A computer program product embodied on a computer readable storage medium, said computer program product comprising computer executable instructions which, when executed by a processor, cause the processor to perform operations comprising the steps of the method of  claim 18 . 
     
     
         33 . A computer readable storage medium having computer executable instructions which, when executed by a processor, cause the processor to perform operations comprising the steps of the method of  claim 18 . 
     
     
         34 . An apparatus, comprising:
 a processor; and   a memory operatively coupled to the processor to form a computing device, the memory storing processor-executable instructions which, based at least on being executed on the processor, cause the processor to perform operations comprising the steps of the method of  claim 18 .