Method and systems for the efficient compression of genomic sequence reads

Abstract

Method and apparatus for the compression of genome sequence data produced by genome sequencing machines. Sequence reads are coded by aligning them with respect to pre-existing or constructed reference sequences, the coding process is composed of a classification of the reads into data classes followed by the coding of each class in terms of a multiplicity of genomic descriptors. Genomic descriptors of the same type are organized in blocks which are compressed by applying successive transformation stages, binarization and entropy coding. Specific source models and entropy coders are used for each data class and for each associated descriptor.

1 . A method for encoding genome sequence data, said genome sequence data comprising reads of sequences of nucleotides, said method comprising the steps of:
 aligning said reads to one or more reference sequences thereby creating aligned reads, classifying said aligned reads according to specified matching rules with said one or more reference sequences, thereby creating classes of aligned reads, represented by genomic descriptors arranged in blocks of homogeneous data,   encoding said classified aligned reads as a multiplicity of blocks of syntax elements, and structuring said blocks of syntax elements and said descriptors with header information thereby creating successive Access Units,   wherein said encoding further comprises binarizing and entropy coding said genomic descriptors.   
     
     
         2 . The method of  claim 1 , wherein said binarizing and entropy coding genomic descriptors is such that the binarization and the entropy coding is different for the different descriptors. 
     
     
         3 . The method of  claim 2 , wherein the said descriptors comprise:
 pos for signaling the mapping position of a read on a reference sequence,   rcomp for signaling the DNA or RNA strand the reads was mapped on, and   mapping flags for enabling the aligner to further specify the result of the mapping process.   
     
     
         4 . The method of  claim 3  further comprising coding the following descriptors:
 mmpos for signaling the position of mismatches in aligned reads with respect to reference sequences, and 
 mmtype for signaling the types of mismatches with respect to reference sequences at the associated positions. 
 
     
     
         5 . The method of  claim 4  further comprising coding the clips descriptor for signaling soft or hard clipped nucleotides. 
     
     
         6 . The method of  claim 5 , further comprising coding the rlen descriptor for signaling the length of each encoded sequence read. 
     
     
         7 . The method of  claim 6 , further comprising coding the following descriptors:
 mmap for signaling the multiple mapping positions that are associated to a single read or read pair by the mapping procedure;   msar for signaling the identification of the existence of spliced reads (i.e. reads that when split in chunks find mapping positions with higher degrees of matching accuracy than when they are mapped as single contiguous read mapped on a single position on a reference sequence).   
     
     
         8 . The method of  claim 7 , further comprising coding the mscore descriptor to signal a mapping/alignment score per read as generated by genomic sequence reads aligners. 
     
     
         9 . The method of  claim 8 , further comprising coding the pair descriptor to signal, in case of paired end reads, how the reads are paired. 
     
     
         10 . The method of  claim 9 , further comprising coding the ureads descriptor to signal reads which could not be aligned at any position of the reference sequence. 
     
     
         11 . The method of  claim 10 , further comprising coding the rtype descriptor used to signal the subset of descriptors used to encode sequence reads that cannot be mapped at any position of the reference sequence with specified degrees of matching accuracy. 
     
     
         12 . The method of  claim 11 , further comprising coding the rgroup descriptor to signal to which read group the read belongs to. 
     
     
         13 . The method of  claim 12 , further comprising coding the following descriptors:
 rftp for signaling the position of mismatches between a contig and a reference sequence. Positions of mismatches are terminated by a special terminator character,   rftt for signaling the type of mismatches between a contig and a reference sequence.   
     
     
         14 . The method of  claim 3 , wherein:
 said pos descriptor is binarized using a double truncated unary code or a single double truncated unary code;   said rcomp descriptor is binarized using a truncated unary code; and   said mapping flags descriptors are binarized using binary coding.   
     
     
         15 . The method of  claim 4 , wherein:
 said mmpos descriptor for signaling the position of mismatches in aligned reads with respect to reference sequences is binarized using a split unit wise truncated unary code; and   said mmtype descriptor for signaling the types of mismatches with respect to reference sequences at the associated positions is binarized using a truncated unary code.   
     
     
         16 . The method of  claim 5 , wherein said clips descriptor for signaling soft or hard clipped nucleotides is binarized using a concatenation of Signed Truncated Exponential Golomb, Truncated Unary, Signed Exponential Golomb and Binary Codes. 
     
     
         17 . The method of  claim 6 , wherein said rlen descriptor signaling the length of each encoded sequence read is binarized using a Split Unit-wise Truncated Unary code. 
     
     
         18 . The method of  claim 7 , wherein:
 said mmap descriptor for signaling the multiple mapping positions that are associated to a single read or read pair by the mapping procedure is binarized using a Split Unit-wise Truncated Unary code; and   said msar descriptor for signaling the identification of the existence of spliced reads is binarized using a Signed Exponential Golomb code.   
     
     
         19 . The method of  claim 8 , wherein said mscore descriptor to signal a mapping/alignment score per read as generated by genomic sequence reads aligners is binarized using a Truncated Unary code. 
     
     
         20 . The method of  claim 9 , wherein said pair descriptor to signal, in case of paired end reads, how the reads are paired is binarized using a concatenation of Binary Coding and Split Unit-wise Truncated Unary code. 
     
     
         21 . The method of  claim 10 , wherein said ureads descriptor to signal reads which could not be aligned at any position of the reference sequence is binarized using a Truncated Unary code. 
     
     
         22 . The method of  claim 11 , wherein said rtype descriptor used to signal the subset of descriptors used to encode sequence reads that cannot be mapped at any position of the reference sequence with specified degrees of matching accuracy is binarized using a Truncated Unary code. 
     
     
         23 . The method of  claim 12 , wherein said rgroup descriptor to signal to which read group the read belongs to is binarized using a Truncated Unary code. 
     
     
         24 . The method of  claim 13 , wherein:
 said rftp descriptor for signaling the position of mismatches between a contig and a reference sequence is binarized using a concatenation of Binary Coding and Split Unit-wise Truncated Unary code; and   said rftt descriptor for signaling the type of mismatches between a contig and a reference sequence is binarized using a concatenation of Binary Coding and Truncated Unary code.   
     
     
         25 . The method of  claim 13 , wherein said descriptors are coded by inserting configuration parameters in a syntax header. 
     
     
         26 . The method of  claim 25 , wherein said configuration parameters are updated by creating updated syntax headers to be added to the encoded genomic file. 
     
     
         27 . The method of  claim 26 , wherein said configuration parameters comprise a dataset type for signaling the type of data encoded in Access Units referring to this encoding parameters. 
     
     
         28 . The method of  claim 27 , wherein said configuration parameters further comprise a reads length for signaling the length in nucleotides of sequence reads in case of constant reads length. 
     
     
         29 . The method of  claim 28 , wherein said configuration parameters further comprise a quality values depth parameter for signaling the number of Quality Values associated to each coded nucleotide. 
     
     
         30 . The method of  claim 29 , wherein said configuration parameters further comprise an alignment score depth for signaling the number of alignments scores associated to each coded alignments. 
     
     
         31 . The method of  claim 30 , wherein said configuration parameters further comprise a terminator size for signaling the size in bytes of the terminator symbol used for the mmpos descriptor. 
     
     
         32 . The method of  claim 31 , wherein said configuration parameters further comprise a terminator value for signaling the value of the terminator symbol used for the mmpos descriptor. 
     
     
         33 . The method of  claim 32 , wherein said configuration parameters further comprise the number of classes for signaling the number of data classes encoded in all Access Units referring to said configuration parameters. 
     
     
         34 . The method of  claim 33 , wherein said configuration parameters further comprise class identifiers to signal the identifiers associated to each data class. 
     
     
         35 . The method of  claim 34 , wherein said configuration parameters further comprise the number of descriptors for signaling the total number of descriptors contained in Access Units referring to said configuration parameters. 
     
     
         36 . The method of  claim 35 , wherein said configuration parameters further comprise coding mode identifiers for the different coding modes. 
     
     
         37 . The method of  claim 36 , wherein said configuration parameters further comprise a number of groups parameter for signaling the number of different values of the rgroup descriptor present in all Access Units referring to the current encoding parameters. 
     
     
         38 . The method of  claim 37 , wherein said configuration parameters further comprise one or more group name parameters for signaling one or more read group identifiers. 
     
     
         39 . The method of  claim 38 , wherein said configuration parameters further comprise a multiple alignments flag for signaling the presence of multiple alignments in the Access Unit. 
     
     
         40 . The method of  claim 39 , wherein said configuration parameters further comprise a spliced reads flag for signaling the presence of spliced reads in the Access Unit. 
     
     
         41 . The method of  claim 40 , wherein said configuration parameters further comprise a multiple signature base flag for signaling the use of multiple signatures in an Access Unit containing unmapped sequence reads (Class U). 
     
     
         42 . The method of  claim 41 , wherein said configuration parameters further comprise a signature size for signaling the size in bits of each integer representing an encoded signature. 
     
     
         43 . The method of  claim 42 , wherein said configuration parameters further comprise a score exponent parameters for signaling the number of bits used to encode the exponent part of the multiple alignments score encoded in the mscore descriptor. 
     
     
         44 . The method of  claim 43 , wherein said configuration parameters further comprise a score fractional parameter for signaling the number of bits used to encode the fractional part of the multiple alignments score encoded in the mscore descriptor. 
     
     
         45 . A method for decoding encoded genomic data, wherein said genome sequence data comprising reads of sequences of nucleotides, said method comprising the steps of:
 parsing Access Units containing said encoded genomic data to extract multiple blocks of genomic descriptors by employing header information; and   decoding said multiplicity of blocks;   wherein said decoding of multiplicity of blocks comprise decoding and de-binarizing genomic descriptors arranged in blocks of homogeneous data to extract aligned reads according to specific matching rules defining their classification with respect to one or more reference sequences.   
     
     
         46 . The method of  claim 45 , wherein the said descriptors comprise:
 a pos descriptor for signaling the mapping position of a read on a reference sequence;   a rcomp descriptor for signaling the DNA or RNA strand the reads was mapped on; and   mapping flags for enabling the aligner to further specify the result of the mapping process.   
     
     
         47 . The method of  claim 46  further comprising decoding the following descriptors:
 mmpos for signaling the position of mismatches in aligned reads with respect to reference sequences; and 
 mmtype for signaling the types of mismatches with respect to reference sequences at the associated positions. 
 
     
     
         48 . The method of  claim 47 , further comprising decoding the clips descriptor for signaling soft or hard clipped nucleotides. 
     
     
         49 . The method of  claim 48 , further comprising decoding the rlen descriptor for signaling the length of each encoded sequence read. 
     
     
         50 . The method of  claim 49 , further comprising decoding the following descriptors:
 mmap for signaling the multiple mapping positions that are associated to a single read or read pair by the mapping procedure; and   msar for signaling the identification of the existence of spliced reads (i.e. reads that when split in chunks find mapping positions with higher degrees of matching accuracy than when they are mapped as single contiguous read mapped on a single position on a reference sequence).   
     
     
         51 . The method of  claim 50 , further comprising decoding the mscore descriptor to signal a mapping/alignment score per read as generated by genomic sequence reads aligners. 
     
     
         52 . The method of  claim 51 , further comprising decoding the pair descriptor to signal, in case of paired end reads, how the reads are paired. 
     
     
         53 . The method of  claim 51 , further comprising decoding the ureads descriptor to signal reads which could not be aligned at any position of the reference sequence. 
     
     
         54 . The method of  claim 53 , further comprising decoding the rtype descriptor used to signal the subset of descriptors used to encode sequence reads that cannot be mapped at any position of the reference sequence with specified degrees of matching accuracy. 
     
     
         55 . The method of  claim 54 , further comprising decoding the rgroup descriptor to signal to which read group the read belongs to. 
     
     
         56 . The method of  claim 55 , further comprising decoding the following descriptors:
 rftp for signaling the position of mismatches between a contig and a reference sequence. Positions of mismatches are terminated by a special terminator character; and   rftt for signaling the type of mismatches between a contig and a reference sequence.   
     
     
         57 . The method of  claim 56 , wherein said descriptors are decoded by extracting configuration parameters from a syntax header. 
     
     
         58 . The method of  claim 57 , wherein said configuration parameters comprise a dataset type for signaling the type of data encoded in Access Units referring to this encoding parameters. 
     
     
         59 . The method of  claim 58 , wherein said configuration parameters further comprise a reads length for signaling the length in nucleotides of sequence reads in case of constant reads length. 
     
     
         60 . The method of  claim 59 , wherein said configuration parameters further comprise a quality values depth parameter for signaling the number of Quality Values associated to each coded nucleotide. 
     
     
         61 . The method of  claim 60 , wherein said configuration parameters further comprise an alignment score depth for signaling the number of alignments scores associated to each coded alignment. 
     
     
         62 . The method of  claim 61 , wherein said configuration parameters further comprise a terminator size for signaling the size in bytes of the terminator symbol used for the mmpos descriptor. 
     
     
         63 . The method of  claim 62 , wherein said configuration parameters further comprise a terminator value for signaling the value of the terminator symbol used for the mmpos descriptor. 
     
     
         64 . The method of  claim 63 , wherein said configuration parameters further comprise the number of classes for signaling the number of data classes encoded in all Access Units referring to said configuration parameters. 
     
     
         65 . The method of  claim 64 , wherein said configuration parameters further comprise class identifiers to signal the identifiers associated to each data class. 
     
     
         66 . The method of  claim 65 , wherein said configuration parameters further comprise the number of descriptors for signaling the total number of descriptors contained in Access Units referring to said configuration parameters. 
     
     
         67 . The method of  claim 66 , wherein said configuration parameters further comprise coding mode identifiers for signaling the coding modes defined in this disclosure. 
     
     
         68 . The method of  claim 67 , wherein said configuration parameters further comprise a number of groups parameter for signaling the number of different values of the rgroup descriptor present in all Access Units referring to the current encoding parameters. 
     
     
         69 . The method of  claim 68 , wherein said configuration parameters further comprise one or more group name parameters for signaling one or more read group identifiers. 
     
     
         70 . The method of  claim 69 , wherein said configuration parameters further comprise a multiple alignments flag for signaling the presence of multiple alignments in the Access Unit. 
     
     
         71 . The method of  claim 70 , wherein said configuration parameters further comprise a spliced reads flag for signaling the presence of spliced reads in the Access Unit, with the proviso that when set to 0 no spliced reads are present. 
     
     
         72 . The method of  claim 71 , wherein said configuration parameters further comprise a multiple signature base flag for signaling the use of multiple signatures in an Access Unit containing unmapped sequence reads (Class U). 
     
     
         73 . The method of  claim 72 , wherein said configuration parameters further comprise a signature size for signaling the size in bits of each integer representing an encoded signature. 
     
     
         74 . The method of  claim 73 , wherein said configuration parameters further comprise a score exponent parameters for signaling the number of bits used to encode the exponent part of the multiple alignments score encoded in the mscore descriptor. 
     
     
         75 . The method of  claim 74 , wherein said configuration parameters further comprise a score fractional parameter for signaling the number of bits used to encode the fractional part of the multiple alignments score encoded in the mscore descriptor. 
     
     
         76 . An encoding apparatus comprising encoding means for implementing the encoding method of  claim 1 . 
     
     
         77 . A decoding apparatus comprising decoding means for implementing the decoding method of  claim 45 . 
     
     
         78 . A file format comprising the genomic descriptors as in  claim 13 . 
     
     
         79 . Computer program comprising instructions for executing the encoding method of  claim 1 . 
     
     
         80 . Computer program comprising instructions for executing the decoding method of  claim 45 . 
     
     
         81 . Storage means for storing the computer programs of  claims 79  and  80 . 
     
     
         82 . Storage means for storing a file created with the encoding method of  claim 1 .