CROSS REFERENCE TO RELATED APPLICATIONS

This application is a U.S. National Phase patent application of PCT/EP2016/074301, filed Oct. 11, 2016, which is hereby incorporated by reference in the present disclosure in its entirety.

TECHNICAL FIELD

The present application provides new methods for efficient storing, access and transmission of bioinformatics data and in particular genomic sequencing data.

BACKGROUND

An appropriate representation of genome sequencing data is fundamental to enable efficient processing, storage and transmission of genomic data to render possible and facilitate analysis applications such as genome variants calling and all analysis performed, with various purposes, by processing the sequencing data and metadata. Today, genome sequencing information are generated by High Throughput Sequencing (HTS) machines in the form of sequences of nucleotides (a.k.a. bases) represented by strings of letters from a defined vocabulary.

These sequencing machines do not read out an entire genome or genes, but they produce short random fragments of nucleotide sequences known as sequence reads.

A quality score is associated to each nucleotide in a sequence read. Such number represents the confidence level given by the machine to the read of a specific nucleotide at a specific location in the nucleotide sequence.

This raw sequencing data generated by NGS machines are commonly stored in FASTQ files (see alsoFIG. 1).

The smallest vocabulary to represent sequences of nucleotides obtained by a sequencing process is composed by five symbols: {A, C, G, T, N} representing the 4 types of nucleotides present in DNA namely Adenine, Cytosine, Guanine, and Thymine plus the symbol N to indicate that the sequencing machine was not able to call any base with a sufficient level of confidence, so the type of base in such position remains undetermined in the reading process. In RNA Thymine is replaced by Uracil (U). The nucleotides sequences produced by sequencing machines are called “reads”. In case of paired reads the term “template” is used to designate the original sequence from which the read pair has been extracted. Sequence reads can be composed by a number of nucleotides in a range from a few dozen up to several thousand. Some technologies produce sequence reads in pairs where each read can come from one of the two DNA strands.

In the genome sequencing field the term “coverage” is used to express the level of redundancy of the sequence data with respect to a reference genome. For example, to reach a coverage of 30× on a human genome (3.2 billion bases long) a sequencing machine shall produce a total of about 30×3.2 billion bases so that in average each position in the reference is “covered” 30 times.

State of the Art Solutions

The most used genome information representations of sequencing data are based on FASTQ and SAM file formats which are commonly made available in zipped form to reduce the original size. The traditional file formats, respectively FASTQ and SAM for non-aligned and aligned sequencing data, are constituted by plain text characters and are thus compressed by using general purpose approaches such as LZ (from Lem pel and Ziv, the authors who published the first versions) schemes (the well-known zip, gzip etc). When general purpose compressors such as gzip are used, the result of the compression is usually a single blob of binary data. The information in such monolithic form results quite difficult to archive, transfer and elaborate particularly in the case of high throughput sequencing when the volumes of data are extremely large.

After sequencing, each stage of a genomic information processing pipeline produces data represented by a completely new data structure (file format) despite the fact that in reality only a small fraction of the generated data is new with respect to the previous stage.

FIG. 1shows the main stages of a typical genomic information processing pipeline with the indication of the associated file format representation.

Commonly used solutions presents several drawbacks: data archival is inefficient for the fact that a different file format is used at each stage of the genomic information processing pipelines which implies the multiple replication of data, with the consequent rapid increase of the required storage space. This is not efficient by itself because not logically necessary, but it is inefficient and unnecessary and it is also becoming not sustainable for the increase of the data volume generated by HTS machines. This has in fact consequences in terms of available storage space and generated costs, and it is also hindering the benefits of genomic analysis in healthcare from reaching a larger portion of the population. The impact of the IT costs generated by the exponential growth of sequence data to be stored and analysed is currently one of the main challenges the scientific community and that the healthcare industry have to face (see Scott D. Kahn “On the future of genomic data”—Science 331, 728 (2011) and Pavlichin, D. S., Weissman, T., and G. Yona. 2013. “The human genome contracts again” Bioinformatics 29(17): 2199-2202). At the same time several are the initiatives attempting to scale genome sequencing from a few selected individuals to large populations (see Josh P. Roberts “Million Veterans Sequenced”—Nature Biotechnology 31, 470 (2013))

The transfer of genomic data is slow and inefficient because the currently used data formats are organized into monolithic files of up to several hundred Gigabytes of size which need to be entirely transferred at the receiving end in order to be processed. This implies that the analysis of a small segment of the data requires the transfer of the entire file with significant costs in terms of consumed bandwidth and waiting time. Often online transfer is prohibitive for the large volumes of the data to be transferred, and the transport of the data is performed by physically moving storage media such as hard disk drives or storage servers from one location to another.

These limitations occurring when employing state of the art approaches are overcome by the present invention. Processing the data is slow and inefficient for to the fact that the information is not structured in such a way that the portions of the different classes of data and metadata required by commonly used analysis applications cannot be retrieved without the need of accessing the data in its totality. This fact implies that common analysis pipelines can require to run for days or weeks wasting precious and costly processing resources because of the need, at each stage of accessing, of parsing and filtering large volumes of data even if the portions of data relevant for the specific analysis purpose is much smaller.

These limitations are preventing health care professionals from timely obtaining genomic analysis reports and promptly reacting to diseases outbreaks. The present invention provides a solution to this need.

There is another technical limitation that is overcome by the present invention.

In fact the invention aims at providing an appropriate genomic sequencing data and metadata representation by organizing and partitioning the data so that the compression of data and metadata is maximized and several functionality such as selective access and support for incremental updates and many others are efficiently enabled.

A key aspect of the invention is a specific definition of classes of data and metadata to be represented by an appropriate source model, coded (i.e. compressed) separately by being structured in specific layers. The most important achievements of this invention with respect to existing state of the art methods consist in:The increase of compression performance due to the reduction of the information source entropy constituted by providing an efficient model for each class of data or metadata;the possibility of performing selective accesses to portions of the compressed data and metadata for any further processing purpose;the possibility to incrementally (without the need of re-encoding) update and add encoded data and metadata with new sequencing data and/or metadata and/or new analysis results;the possibility of efficiently process data as soon as they are produced by the sequencing machine or alignment tools without the need to wait the end of the sequencing or alignment process.

The present application discloses a method and system addressing the problem of efficient manipulation, storage and transmission of very large amounts of genomic sequencing data, by employing a structured access units approach.

The present application overcomes all the limitations of the prior art approaches related to the functionality of genomic data accessibility, efficient processing of data subsets, transmission and streaming functionality combined with an efficient compression.

Today the most used representation format for genomic data is the Sequence Alignment Mapping (SAM) textual format and its binary correspondent BAM. SAM files are human readable ASCII text files whereas BAM adopts a block based variant of gzip. BAM files can be indexed to enable a limited modality of random access. This is supported by the creation of a separate index file.

The BAM format is characterized by poor compression performance for the following reasons:1. It focus on compressing the inefficient and redundant SAM file format rather than on extracting the actual genomic information conveyed by SAM files and using appropriate models for compressing it.2. It employs a general purpose text compression algorithm such as gzip rather than exploiting the specific nature of each data source (the genomic information itself).3. It lacks any concept related to data classification that would enable a selective access to specific classes of genomic data.

A more sophisticated approach to genomic data compression that is less commonly used, but more efficient than BAM is CRAM (CRAM specification: https://samtools.github.io/hts-specs/CRAMv3.pdf). CRAM provides a more efficient compression for the adoption of differential encoding with respect to an existing reference (it partially exploits the data source redundance), but it still lacks features such as incremental updates, support for streaming and selective access to specific classes of compressed data.

CRAM relies on the concept of the CRAM record. Each CRAM record encodes a single mapped or unmapped reads by encoding all the elements necessary to reconstruct it.

The main differences of the disclosed invention with respect to the CRAM approach are:1. For CRAM, data indexing is out of the scope of the specification (see section 12 of CRAM specification v 3.0) and it is implemented as a separate file. In the present invention the data indexing is integrated with the encoding process and indexes are embedded in the encoded bit stream.2. In CRAM all core data blocks can contain any type of mapped reads (perfectly matching reads, reads with substitutions only, reads with indels). In the present invention there is no notion of classification and grouping of reads in classes according to the result of a mapping with respect to a reference sequence.3. In the described invention there is no notion of record encapsulating each read because the data needed to reconstruct each read is scattered among several data containers called “layers”. This enables a more efficient access to set of reads with specific biological characteristics (e.g. reads with substitutions, but without indels, or perfectly mapped reads) without the need of decoding each (block of) read(s) to inspect its features.4. In a CRAM record each type of data is denoted by a specific flag. Differently from CRAM in the present invention there is no notion of flag denoting data because this is intrinsically defined by the “layer” the data belongs to. This implies a largely reduced number of symbols to be used and a consequent reduction of the information source entropy which results into a more efficient compression. This is due to the fact that the use of different “layers” enables the encoder to reuse the same symbol across each layer with different meanings. In CRAM each flag must always have the same meaning as there is no notion of contexts and each CRAM record can contain any type of data.5. In CRAM substitutions, insertions and deletions are expressed according to different syntaxes, whereas the present invention uses a single alphabet and encoding for substitutions, insertions and deletions. This makes the encoding and decoding process simpler and produces a lower entropy source model which coding yields bitstreams characterized by higher compression performance.

Genomic compression algorithms used in the state of the art can be classified into these categories:Transform-basedLZ-basedRead reorderingAssembly-basedStatistical modeling

The first two categories share the disadvantage of not exploiting the specific characteristics of the data source (genomic sequence reads) and process the genomic data as string of text to be compressed without taking into account the specific properties of such kind of information (e.g. redundancy among reads, reference to an existing sample). Two of the most advanced toolkits for genomic data compression, namely CRAM and Goby (“Compression of structured high-throughput sequencing data”, F. Campagne, K. C. Dorff, N. Chambwe, J. T. Robinson, J. P. Mesirov, T. D. Wu), make a poor use of arithmetic coding as they implicitly model data as independent and identically distributed by a Geometric distribution. Goby is slightly more sophisticated since it converts all the fields to a list of integers and each list is encoded independently using arithmetic coding without using any context. In the most efficient mode of operation, Goby is able to perform some inter-list modeling over the integer lists to improve compression. These prior art solutions yield poor compression ratios and data structures that are difficult if not impossible to selectively access and manipulate once compressed. Downstream analysis stages can result to be inefficient and very slow due to the necessity of handling large and rigid data structures even to perform simple operation or to access selected regions of the genomic dataset.

A simplified vision of the relation among the file formats used in genome processing pipelines is depicted inFIG. 1. In this diagram file inclusion does not imply the existence of a nested file structure, but it only represents the type and amount of information that can be encoded for each format (i.e. SAM contains all information in FASTQ, but organized in a different file structure). CRAM contains the same genomic information as SAM/BAM, but it has more flexibility in the type of compression that can be used, therefore it is represented as a superset of SAM/BAM.

The use of multiple file formats for the storage of genomic information is highly inefficient and costly. Having different file formats at different stages of the genomic information life cycle implies a linear growth of utilized storage space even if the incremental information is minimal. Further disadvantages of prior art solutions are listed below.1. Accessing, analysing or adding annotations (metadata) to raw data stored in compressed FastQ files or any combination thereof requires the decompression and recompression of the entire file with extensive usage of computational resources and time.2. Retrieving specific subsets of information such as read mapping position, read variant position and type, indels position and types, or any other metadata and annotation contained in aligned data stored in BAM files requires to access the whole data volume associated to each read. Selective access to a single class of metadata is not possible with prior art solutions.3. Prior art file formats require that the whole file is received at the end user before processing can start. For example the alignment of reads could start before the sequencing process has been completed relying on an appropriate data representation. Sequencing, alignment and analysis could proceed and run in parallel.4. Prior art solutions do not support structuring and are not able of distinguishing genomic data obtained by different sequencing processes according to their specific generation semantic (e.g. sequencing obtained at different time of the life of the same individual). The same limitation occurs for sequencing obtained by different types of biological samples of the same individual.5. The encryption of entire or selected portions of the data is not supported by prior art solutions. For example the encryption of:a. selected DNA regionsb. only those sequences containing variantsc. chimeric sequences onlyd. unmapped sequences onlye. specific metadata (e.g. origin of the sequenced sample, identity of sequenced individual, type of sample)6. The transcoding from sequencing data aligned to a given reference (i.e. a SAM/BAM file) to a new reference requires to process the entire data volume even if the new reference differs only by a single nucleotide position from the previous reference.

There is therefore a need of an appropriate Genomic Information Storage Layer (Genomic File Format) that enables efficient compression, supports the selective access in the compressed domain, supports the incremental addition of heterogeneous metadata in the compressed domain at all levels of the different stages of the genomic data processing.

The present invention provides a solution to the limitations of the state of the art by employing the method, devices and computer programs as claimed in the accompanying set of claims.

