Method and systems for the reconstruction of genomic reference sequences from compressed genomic sequence reads

Abstract

The method and apparatus described in this disclosure include representing a reference genome in terms of syntax elements describing the differences between said reference genome and previously aligned genomic sequences. Each of the aligned genomic sequence is described by means of a subset of syntax elements. Syntax elements describing all the genomic sequences are partitioned in blocks according to their statistical properties. Each block of syntax elements is entropy coded. The entropy coded blocks are then concatenated to form a compressed bitstream. The differences between the reference genome and the aligned sequences are expressed in terms of syntax elements, which are embedded in the bitstream of coded blocks of syntax elements describing aligned reads. The disclosed method enables the reconstruction of the reference genome used for alignment when decoding the compressed genomic sequences while preserving different options of random access on the compressed data and enabling efficient compression.

1 . A method for encoding aligned 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,   mapping said genomic sequence data to be coded on a reference genome,   assembling said aligned reads thereby creating a contig,   comparing said reference sequence and said contig thereby obtaining information related to the position of mismatches and the type of mismatches,   generating genomic descriptors representing the genomic sequences with respect to the contigs,   entropy coding said genomic descriptors and said information related to the position of mismatches and the type of mismatches with respect to the reference genome with different entropy coders ( 502 ,  503 ), and   multiplexing said coded genomic descriptors and said position and type of mismatches in the a same access unit.   
     
     
         2 . The method of  claim 1 , wherein assembling said aligned reads comprises the step of selecting, for each position on the reference sequence, the nucleotide that is present with the highest frequency in the aligned reads at that position. 
     
     
         3 . The method of  claim 2 , wherein said information related to position of mismatches and the type of mismatches are indicated using, respectively a first descriptor ( 203 ) and a second descriptor ( 204 ). 
     
     
         4 . The method of  claim 3 , wherein said first descriptor and second descriptor are encapsulated in a same Access Unit so to enable the selective reconstruction of the reference sequence used for the alignment at the decoding device. 
     
     
         5 . The method of  claim 4 , wherein the length of said contig is defined as input parameter to the encoder or dynamically adapted by the encoder. 
     
     
         6 . The method of  claim 5 , wherein said first descriptor is binarized using a Split Unit-wise Truncated Unary binarization, wherein said Split Unit-wise Truncated Unary is a concatenation of repeated truncated unary binarizations, where each truncated unary binarization is applied to portions of the value to be binarized which are N bits long, wherein N is a preselected parameter. 
     
     
         7 . The method of  claim 5 , wherein said second descriptor is binarized using a Truncated Unary binarization, wherein the value of said second descriptor is followed by a zero and if said value is equal to the largest possible value to be binarized the trailing 0-bit is discarded. 
     
     
         8 . The method of  claim 5 , wherein said method does not encode information signaling the usage of a specific reference genome. 
     
     
         9 . The method of  claim 6 , wherein said length of said contig is contained in a syntax header. 
     
     
         10 . An apparatus for encoding genome sequence data, said genome sequence data comprising reads of sequences of nucleotides, said apparatus comprising means for:
 aligning said reads to one or more reference sequences thereby creating aligned reads,   mapping said genomic sequence data to be coded on a reference genome,   assembling said aligned reads thereby creating a contig,   comparing said reference sequence and said contig thereby obtaining information related to the position of mismatches and the type of mismatches,   generating genomic descriptors representing the genomic sequences with respect to the contigs,   entropy coding said genomic descriptors and said information related to the position of mismatches and the type of mismatches with respect to the reference genome with different entropy coders ( 502 ,  503 ), and   multiplexing said coded genomic descriptors and said position and type of mismatches in the a same access unit.   
     
     
         11 . The apparatus of  claim 10 , wherein said means for assembling said aligned reads further comprise means for selecting, for each position on the reference sequence, the nucleotide that is present with the highest frequency in the aligned reads at that position. 
     
     
         12 . The apparatus of  claim 11 , further comprising means to indicate said information related to the position of mismatches and the type of mismatches by, respectively a first descriptor ( 203 ) and a second descriptor ( 204 ). 
     
     
         13 . The apparatus of  claim 12 , further comprising means for encapsulating said first descriptor and second descriptor in the same Access Unit so to enable the selective reconstruction of the reference sequence used for the alignment at the decoding device. 
     
     
         14 . The apparatus of  claim 13 , further comprising means to receive the length of said contig as input parameter and means for dynamically adapting length of said contig. 
     
     
         15 . The apparatus of  claim 14 , further comprising binarization means for binarizing said first descriptor by employing a Split Unit-wise Truncated Unary binarization, wherein said Split Unit-wise Truncated Unary is a concatenation of repeated truncated unary binarizations, where each truncated unary binarization is applied to portions of the value to be binarized which are N bits long, wherein N is a preselected parameter. 
     
     
         16 . The apparatus of  claim 14 , further comprising binarization means for binarizing said second descriptor by employing a Truncated Unary binarization, wherein the value of said second descriptor is followed by a zero and if said value is equal to the largest possible value to be binarized the trailing 0-bit is discarded. 
     
     
         17 . The apparatus of  claim 16 , further comprising means for coding said length of said contig in a syntax header. 
     
     
         18 . A method for decoding encoded genome sequence data, comprising the steps of:
 parsing the encoded input file, so to obtain access units of genomic data, demultiplexing ( 401 ) said access units to obtain coded genomic descriptors and information related to position and type of mismatches of a genomic sequence data with respect to a reference genome,   entropy decoding, with a different entropy decoder ( 411 ,  402 ), said genomic descriptors and said information related to position of a mismatch and type of mismatch in a contig, and   modifying the contig by employing said information related to positions and types of mismatches thereby obtaining a genomic sequence of nucleotides which represents the reference genome used for the alignment before compression and further information ( 403 ) to reconstruct the reference genome.   
     
     
         19 . The method of  claim 18 , wherein modifying the contig by employing said information related to positions and types of mismatches thereby obtaining said genomic sequence of nucleotides further comprises entropy decoding of a first descriptor ( 203 ) and a second descriptor ( 204 ). 
     
     
         20 . The method of  claim 19 , further comprising decapsulating from the same Access Unit said first descriptor and second descriptor so to obtain the selective reconstruction of said genomic sequence of nucleotides. 
     
     
         21 . The method of  claim 20 , further comprising decoding the length of said contig from a syntax header contained in the input file. 
     
     
         22 . The method of  claim 19 , further comprising a reverse binarization of said first descriptor, wherein said first descriptor is binarized using a Split Unit-wise Truncated Unary binarization, wherein said Split Unit-wise Truncated Unary is a concatenation of repeated truncated unary binarizations, where each truncated unary binarization is applied to portions of the value to be binarized which are N bits long, wherein N is a preselected parameter. 
     
     
         23 . The method of  claim 19 , further comprising a reverse binarization of said second descriptor wherein said second descriptor is binarized using a Truncated Unary binarization, wherein the value of said second descriptor is followed by a zero and if said value is equal to the largest possible value to be binarized the trailing 0-bit is discarded. 
     
     
         24 . The method of  claim 19 , wherein said input file does not contain information signaling the usage of a specific reference genome. 
     
     
         25 . An apparatus for decoding encoded genome sequence data, comprising means for:
 parsing the encoded input file, so to obtain access units of genomic data,   demultiplexing ( 401 ) said access units to obtain coded genomic descriptors and information related to position and type of mismatches of a genomic sequence data with respect to a reference genome,   entropy decoding, with a different entropy decoder ( 411 ,  402 ), said genomic descriptors and said information related to position of a mismatch and type of mismatch in a contig, and   modifying the contig by employing said information related to positions and types of mismatches thereby obtaining a genomic sequence of nucleotides which represents the reference genome used for the alignment before compression and further information ( 403 ) to reconstruct the reference genome.   
     
     
         26 . The apparatus of  claim 25 , wherein said means for modifying the contig by employing said information related to positions and types of mismatches in a contig thereby obtaining a genomic sequence of nucleotides further comprise means for entropy decoding of a first descriptor ( 203 ) and a second descriptor ( 204 ). 
     
     
         27 . The apparatus of  claim 26 , further comprising means for the selective reconstruction of the genomic sequence of nucleotides, by decapsulating from a same Access Unit said first descriptor and second descriptor. 
     
     
         28 . The apparatus of  claim 27 , further comprising means for decoding from a syntax header contained in the input file the information relating to the length of said contig. 
     
     
         29 . The apparatus of  claim 26 , further comprising means for a reverse binarization of said first descriptor, wherein said first descriptor is binarized using a Split Unit-wise Truncated Unary binarization, wherein said Split Unit-wise Truncated Unary is a concatenation of repeated truncated unary binarizations, where each truncated unary binarization is applied to portions of the value to be binarized which are N bits long, wherein N is a preselected parameter. 
     
     
         30 . The apparatus of  claim 26 , further comprising means for a reverse binarization of said second descriptor wherein said second descriptor is binarized using a Truncated Unary binarization, wherein the value of said second descriptor is followed by a zero and if said value is equal to the largest possible value to be binarized the trailing 0-bit is discarded.