“Methods To Compress, Encrypt And Retrieve Genomic Alignment Data” in Patent Application Approval Process (USPTO 20190087601)

2019 APR 10 (NewsRx) -- By a News Reporter-Staff News Editor at Insurance Daily News -- A patent application by the inventors MOLYNEAUX, Adam (Blonay, CH); AYDAY, Erman (Renens, CH); HUBAUX, Jean-Pierre (Saint-Sulpice, CH); GARCIA, Jesus (Saint Sulpice, CH); HUANG, Zhicong (Saint Sulpice, CH); LIN, Huang (Saint Sulpice, CH), filed on March 8, 2017, was made available online on March 21, 2019, according to news reporting originating from Washington, D.C., by NewsRx correspondents.

This patent application is assigned to Sophia Genetics S.A. (Saint Sulpice, Switzerland).

The following quote was obtained by the news editors from the background information supplied by the inventors: “Next-Generation Sequencing Data Processing

“Next-generation sequencing (NGS) or massively parallel sequencing (MPS) technologies have significantly decreased the cost of DNA sequencing in the past decade. NGS has broad application in biology and dramatically changed the way of research or diagnosis methodologies. Advances in high-throughput sequencing technologies are spurring the production of a huge amount of genomic data. For example, the 1000 Genomes Project generated more data in its first six months than the NCBI Genbank database had accumulated in 21 years of existence. As of 2007, when the first high-throughput sequencing technology was released to the market, the growth rate of genomic data has outpaced Moore’s law--more than doubling each year (http://www.genome.gov/sequencingcosts/). For example, the HiSeq X Ten System, released by Illumina in 2014, can deliver over 18,000 human genomes per year, at the price of $1000 per genome. Big data researchers estimate the current worldwide sequencing capacity to exceed 35 petabases per year. Furthermore, it is currently estimated that for every 3 billion bases of human genome sequence, 30-fold more data (about 100 gigabases) must be collected because of errors in sequencing and alignment. Even nowadays, more than 100 petabytes of storage are already used by 20 largest institutions; this corresponds to more than 1 million dollars of storage maintenance cost if we consider the Amazon cloud storage pricing (https://aws.amazon.com/s3/pricing/). This number continues to grow and 2-40 exabytes of storage capacity will be needed by 2025 for the human genomes. Hundreds of thousands of human genomes will be sequenced in the coming years, which necessitates more efficient compression approaches to genomic data storage.

“Moreover, next generation sequencing data are more and more used as a tool in medical practice such as routine diagnosis, where security and privacy come as a major concern. The main threats to genomic data are (i) the disclosure of an individual’s genetic characteristics due to the leakage of his/her genomic data and (ii) the identification of an individual from his/her own genome sequence. For example, as part of a clinical trial, the genetic information of a patient, once leaked, could be linked to the disease under study (or to other diseases), which can have serious consequences such as denial of access to life insurance or to employment for the individual participant. There is therefore a need for more secure genomic data management methods that address the privacy threat models that are specific to the genomic data processing systems and workflows.

“Next Generation Sequencing Data Formats and Workflows

“Next generation sequencers typically output a series of short reads, a few hundred nucleotides sequences with the associated quality score estimates in data files such as the FASTQ files. This raw sequencing data is further analyzed in the bioinformatics pipeline by aligning the raw short reads to a reference genome, and identifying the specific variants as the differences relative to the reference genome.

“In general, geneticists prefer storing aligned, raw genomic data of the patients, in addition to their variant calls (which include each nucleotide on the DNA sequence once, hence is much more compact). Sequence alignment/map files such as the human readable SAM files and their more compact, machine-readable binary version BAM files are the de facto standards used for DNA alignment data produced by next-generation DNA sequencers (http://samtools.github.io/hts-specs/SAMv1.pdf). There are hundreds of millions of short sequencing reads (each including between 100 and 400 nucleotides) in the SAM file of a patient. Each nucleotide is present in several short reads in order to have statistically high coverage of each patient’s DNA.

“Genomic Data Compression

“There are different approaches to dealing with the compression of genomic data. Before high-throughput technologies were introduced, there existed algorithms designed for compressing genomic sequences of relatively small size (e.g., tens of megabases), for instance BioCompress (in Grumbach, S. & Tahi, F. Compression of DNA sequences, in Data Compression Conference, 1993. DCC ‘93. 340-350), GenCompress (in Chen, X., Kwong, S. & Li, M. A Compression algorithm for DNA sequences and its applications in genome comparison. in Proceedings of the Fourth Annual International Conference on Computational Molecular Biology 107--ACM, 2000), and DNACompress (in Chen, X., Li, M., Ma, B. & Tromp, J. DNACompress: Fast and effective DNA sequence compression. Bioinformatics 18, 1696-1698-2002). These compression algorithms exploit the redundancy within DNA sequences and compress the data by identifying highly repetitive subsequences. The next generation sequencing technologies however pose new challenges for the compression of genomic data in terms of data size and structure. Due to the high similarity of DNA sequences among individuals, it is inefficient to store and transfer entirely a newly assembled genomic sequence because more than 99% of the data for two assembled human genomes are redundant. In Christley, S., Lu, Y., Li, C. & Xie, X. Human genomes as email attachments. Bioinformatics 25, 274-275 (2009), Christley et al proposed to store DNAzip, a reference-based compression algorithm where only differences to a reference sequence are stored. In next generation sequencing, individual sequenced data are typically organized as millions of short reads that represent short sequences, each of which comprises between 100 and 400 bases (nucleotides). Each genomic position is usually covered by multiple short reads (coverage). Li et al. (Li, H. et al. The Sequence Alignment/Map format and SAMtools. Bioinformatics 25, 2078-2079-2009) proposed to apply a general-purpose compression algorithm, such as BGZF (Blocked GNU Zip format--http//samtools.github.io/hts-specs/SAMv1.pdf), to these datasets as the basis for the the BAM format, the binary version of the SAM format, which is still the de facto standard of storing aligned short reads.

“More recently, various advanced compression algorithms have been proposed to further improve the compression of high-throughput DNA sequence data, such as Quip (Jones, D. C., Ruzzo, W. L., Peng, X. & Katze, M. G. Compression of next-generation sequencing reads aided by highly efficient de novo assembly. Nucl. Acids Res. gks754-2012), Samcomp (Bonfield, J. K. & Mahoney, M. V. Compression of FASTQ and SAM Format Sequencing Data. PLoS ONE 8, e59190-2013), HUGO (Li, P. et al. HUGO: Hierarchical Multi-reference Genome Compression for aligned reads. Journal of the American Medical Informatics Association 21, 363-373-2014), and CRAM, a reference-based compression algorithm for aligned data (Fritz, M. H.-Y., Leinonen, R., Cochrane, G. & Birney, E. Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Res. 21, 734-740-2011). CRAM is used for instance by the 1000 genomes project (http://www.1000genomes.org/). Most of these algorithms use conventional entropy coding techniques, such as Huffman variable-length encoding, Golomb, or arithmetic coding, to compress the metadata text strings (e.g., read name, position, mapping quality, etc.). Recently, Massie et al. (Massie, M. et al. Adam: Genomics formats and processing patterns for cloud scale computing. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2013-207-2013) proposed ADAM, a cloud-computing framework for genomic data compression, which combines various data compression engineering techniques such as dictionary coding and gzip compression in combination with distributed processing to reduce 25% of the storage costs compared to the BAM de facto standard. The ADAM scheme also achieves significant (2-10.times.) speedup in decompression performance for genomics data access patterns.

“Genomic Data Security

“Some genomic data encryption solutions have been proposed on top of some compression algorithms, such as for instance the encryption option in cramtools for the CRAM genomic data compression format (http://www.ebi.ac.uk/ena/software/cram-toolkit), but they remain straightforward applications of encryption standards and do not take into consideration the specific genomic data storage and genomic data processing threat models even if the solution uses highly secure encryption primitives (e.g., the AES encryption method). In particular, the data retrieval process may cause incidental leakage of sensitive genomic information. Once leaked, genomic information could be abused in various ways, such as for denial of employment and health insurance, blackmail or even genetic discrimination. Establishing a secure and privacy-preserving solution for genomic data storage is therefore needed in order to facilitate the trusted usage, storage and transmission of genomic data.

“Recent research works have thus highlighted a number of specific threats to be addressed by genomic data security and privacy-preserving technologies. For instance, public aggregated statistics in genome-wide association studies (GWAS) may lead to a potential privacy breach for participants of the study, because attackers can determine, through powerful statistical tests, whether a participant is in a case group (Homer, N. et al. Resolving Individuals Contributing Trace Amounts of DNA to Highly Complex Mixtures Using High-Density SNP Genotyping Microarrays. PLoS Genet 4, e1000167-2008). Data de-identification (removal of the personal identifiers) has also been proven insufficient for protecting genetic privacy (Erlich, Y. & Narayanan, A. Routes for breaching and protecting genetic privacy. Nat Rev Genet 15, 409-421-2014). Coarse-grained encryption and access control to genomic data may also lead to incidental genomic findings that doctors would prefer to avoid (Ayday, E., Raisaro, J. L., Hengartner, U., Molyneaux, A. & Hubaux, J.-P. Privacy-Preserving Processing of Raw Genomic Data. in Data Privacy Management and Autonomous Spontaneous Security, 133-147-Springer Berlin Heidelberg, 2014).

“Storing sequenced data on a cloud seems to be an attractive option, considering the size and the required availability of the data, so that it can be more easily shared by different parties. Accessing the remote data stored with standard compression schemes require to decrypt it first so the data owner has to trust insiders on the cloud (e.g., the cloud administrator, or high-privileged system software) to access the genomic information in the clear and multi-party key management systems have to be carefully designed accordingly. Ayday et al. (Ayday, E., Raisaro, J. L., Hengartner, U., Molyneaux, A. & Hubaux, J.-P. Privacy-Preserving Processing of Raw Genomic Data. in Data Privacy Management and Autonomous Spontaneous Security, 133-147--Springer Berlin Heidelberg, 2014 and WO2014/202615) proposed the use of order-preserving encryption to enable genetic data retrieval without requiring full decryption of the genomic data. While it addresses the security issues associated with genomic information privacy threats, the latter scheme requires further data overhead, which induces extra storage and processing costs requirements and make it impractical for certain clinical genomic applications.

“Therefore, it will be of great benefit to the future development of sequenced data analysis if a compression solution can also integrate encryption methods that are secure and suitable for preserving the privacy of genomic information in the decompression and decryption process.

“Genomic Data Access

“For clinical or research purpose, the most valuable information from human genomic data is the set of genetic variants that are identified among the three billion genome positions. However, current state-of-the-art sequencers produce millions of short reads, scattered over the whole genome and covering each position multiple times. Typically, sequenced data are taken as input for a pipeline and retrieved for downstream analyses, e.g., variant calling. Taking this usage scenario into account, it is also crucial to have a storage format that is efficient for downstream analyses. For example, it is a common practice to aggregate information on a position from all short reads that cover the position (pileup), hence it is desirable that the storage format organizes information in this manner.

“An increasing number of medical units (pharmaceutical companies or physicians) are willing to outsource the storage of genomes generated in clinical trials. As the medical unit would not own the genome, this is a good argument to convince clinical-trial participants to be sequenced and use their genomes to stratify clinical trials. Acting as a third party, a biobank storage unit could store patients’ genomic data that would be used by the medical units for clinical trials. In the meantime, the patient can also benefit from the stored genomic information by interrogating his own genomic data, together with his family doctor, for specific genetic predispositions, susceptibilities and metabolical capacities. The major challenge here is to manage the data access rights to preserve the privacy of patients’ genomic data while allowing the medical units to operate on specific parts of the genome (for which they are authorized). In WO2014/202615, Ayday et al. proposed a privacy-preserving genomic data processing system based on order-preserving encryption that is suitable to encrypt, store and facilitate the private partial retrieval of aligned genomic data files such as SAM files in a biobank. However this system does not address the storage compression efficiency and there is therefore a need to further improve it.

“In addition to combining the compression and encryption of next-generation-sequencing (NGS) data for efficient and privacy-preserving storage, this would also require us to consider who can access the data, which part they can access and how the data can be partially retrieved. Without these precautions, there could be incidental leakage during data retrieval, even if it is stored in an encrypted form. Furthermore, the storage and access efficiency of sequenced data needs to be further optimized without compromising the security requirements. Better methods and systems to process genomic data information are needed that consistently address all these problems (security and privacy, storage, partial retrieval) to minimize the storage cost without compromising the privacy of genomic data information while optimizing the performance of downstream analysis (e.g., variant calling).”

In addition to the background information obtained for this patent application, NewsRx journalists also obtained the inventors’ summary information for this patent application: “Some embodiments of the present disclosure are directed to methods to encode genomic data alignment information organized as a read-based alignment information data stream, comprising the steps of: transposing, with a processor, the read-based alignment information data stream into a position-based alignment information data stream; encoding, with a processor, the position-based alignment information data stream into a reference-based compressed position data stream; and encrypting, with a processor, the reference-based compressed position data stream into a compressed encrypted alignment data stream.

“In some embodiments, encoding the position-based alignment information data stream into a reference-based compressed position data stream may comprise a step of differential encoding. In a possible embodiment, differential encoding may comprise recording, for each position in the reference-based compressed position data stream, the alignment differences relative to the alignment reference sequence. In a possible embodiment, encoding the position-based alignment information data stream into a reference-based compressed position data file may comprise a step of entropy coding.

“In some embodiments, encrypting the reference-based compression position data stream into a compressed encrypted alignment data stream may comprise a step of encrypting the position information with an order-preserving encryption scheme. In a possible embodiment, encrypting the reference-based compression position data stream into a compressed encrypted alignment data stream may comprise a step of encrypting the position-based alignment information with a symmetric encryption scheme. The symmetric encryption scheme may be a stream cipher, such as the AES scheme in CTR mode.

“Some embodiments of the present disclosure are directed to methods to retrieve genomic data alignment information from a compressed encrypted alignment data stream, recorded on a storage unit, comprising the steps of: receiving a genomic alignment range query [Pos1, Pos2] from a genomic data analysis system; retrieving from the storage unit, with a processor, the subset of the compressed encrypted alignment data stream corresponding to the genomic alignment range [Pos1, Pos2] in the compressed encrypted alignment data stream; decrypting, with a processor, the compressed encrypted alignment data stream into a reference-based compressed position data stream corresponding to the genomic alignment range [Pos1, Pos2]; and decoding, with a processor, the reference-based compressed position data stream into a position-based alignment information data stream corresponding to the genomic alignment range [Pos1, Pos2].

“In a possible embodiment, retrieving genomic data alignment information from a compressed encrypted alignment data stream, recorded on a storage unit, may further comprise a step of reverse transposing, with a processor, the position-based alignment information data stream into a read-based alignment information data.

“In a possible embodiment, retrieving the subset of the compressed encrypted alignment data stream for the genomic alignment range [Pos1, Pos2] comprises retrieving the symmetric encrypted data and the metadata stored in data blocks between the order-preserving encrypted position associated with Pos1 and the order-preserving encrypted position associated with Pos2.

“In a possible embodiment, decrypting the compressed encrypted alignment data stream into a reference-based compressed position data stream corresponding to the genomic alignment range [Pos1, Pos2] comprises symmetric decryption of the symmetric encrypted data between the order-preserving encrypted position associated with Pos1 and the order-preserving encrypted position associated with Pos2. In a possible embodiment, the symmetric decryption scheme may be a stream decipher, such as the AES scheme in CTR mode.

“In a possible embodiment, decoding the position-based alignment information data stream into reference-based compressed position data stream may comprise a step of entropy decoding. In a possible embodiment, decoding the position-based alignment information data stream into reference-based compressed position data stream may comprise a step of differential decoding.”

The claims supplied by the inventors are:

“1. A method to encode genomic data alignment information organized as a read-based alignment information data stream, comprising: Transposing, with a processor, the read-based alignment information data stream into a position-based alignment information data stream; Encoding, with a processor, the position-based alignment information data stream into a reference-based compressed position data stream; Encrypting, with a processor, the reference-based compressed position data stream into a compressed encrypted alignment data stream.

“2. The method of claim 1, wherein encoding the position-based alignment information data stream into a reference-based compressed position data stream comprises differential encoding.

“3. The method of claim 2, wherein differential encoding comprises recording, for each position in the reference-based compressed position data stream, the alignment differences relative to the alignment reference sequence.

“4. The method of claim 1, wherein encoding the position-based alignment information data stream into a reference-based compressed position data file further comprises entropy coding.

“5. The method of claim 1, wherein encrypting the reference-based compression position data stream into a compressed encrypted alignment data stream comprises encrypting the position information with an order-preserving encryption scheme.

“6. The method of claim 1, wherein encrypting the reference-based compression position data stream into a compressed encrypted alignment data stream comprises encrypting the position-based alignment information with a symmetric encryption scheme.

“7. The method of claim 6, wherein the symmetric encryption scheme is a stream cipher.

“8. The method of claim 7, wherein the symmetric encryption scheme is a block cipher operating in a stream cipher mode.

“9. A method to retrieve genomic data alignment information from a compressed encrypted alignment data stream, recorded on a storage unit, comprising: Receiving a genomic alignment range query [Pos1, Pos2] from a genomic data analysis system; Retrieving from the storage unit, with a processor, the subset of the compressed encrypted alignment data stream corresponding to the genomic alignment range [Pos1, Pos2] in the compressed encrypted alignment data stream; Decrypting, with a processor, the compressed encrypted alignment data stream into a reference-based compressed position data stream corresponding to the genomic alignment range [Pos1, Pos2]; Decoding, with a processor, the reference-based compressed position data stream into a position-based alignment information data stream corresponding to the genomic alignment range [Pos1, Pos2].

“10. The method of claim 9, further comprising reverse transposing, with a processor, the position-based alignment information data stream into a read-based alignment information data

“11. The method of claim 9, wherein retrieving the subset of the compressed encrypted alignment data stream for the genomic alignment range [Pos1, Pos2] comprises retrieving the symmetric encrypted data and the metadata stored in data blocks between the order-preserving encrypted position associated with Pos1 and the order-preserving encrypted position associated with Pos2.

“12. The method of claim 11, wherein decrypting the compressed encrypted alignment data stream into a reference-based compressed position data stream corresponding to the genomic alignment range [Pos1, Pos2] comprises symmetric decryption of the symmetric encrypted data between the order-preserving encrypted position associated with Pos1 and the order-preserving encrypted position associated with Pos2;

“13. The method of claim 12, wherein the symmetric decryption scheme is a stream decipher.

“14. The method of claim 12, wherein the symmetric decryption scheme is a block decipher operating in a stream decipher mode.

“15. The method of claim 9, wherein decoding the position-based alignment information data stream into reference-based compressed position data stream comprises entropy decoding.

“16. The method of claim 9, wherein decoding the position-based alignment information data stream into reference-based compressed position data stream comprises differential decoding.”

URL and more information on this patent application, see: MOLYNEAUX, Adam; AYDAY, Erman; HUBAUX, Jean-Pierre; GARCIA, Jesus; HUANG, Zhicong; LIN, Huang. Methods To Compress, Encrypt And Retrieve Genomic Alignment Data. Filed March 8, 2017 and posted March 21, 2019. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220190087601%22.PGNR.&OS=DN/20190087601&RS=DN/20190087601

(Our reports deliver fact-based news of research and discoveries from around the world.)