Method and device for generating pileup file from compressed genomic data

Provided are a method and apparatus for generating a pileup file from a reference-based compression file. The method includes receiving a reference-based compression file comprising a plurality of pieces of read data that are compressed, partially decompressing the plurality of pieces of read data to acquire a differential string associated with the plurality of pieces of read data, and generating the pileup file by decoding the differential string based on a plurality of conversion rules.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of Indian Patent Application No. 2510/CHE/2015, filed on May 19, 2015, in the Office of the Controller General of Patents, Designs, and Trademarks of India, and Korean Patent Application No. 10-2016-0025763, filed on Mar. 3, 2016, in the Korean Intellectual Property Office, the disclosures of which are incorporated herein in their entireties by reference.

BACKGROUND

The present disclosure relates to data compression in next generation sequencing (NGS) in general, and more particularly to a mechanism for generating a pileup file from compressed NGS genomic data.

2. Description of the Related Art

In computational biology, next generation sequencing (NGS) refers to new, high-throughput technology for sequencing DNA or RNA. NGS may be used to analyze the genome of an individual or a collection of individuals to, for example, comprehensively catalog genetic variation in population samples. The NGS-based diagnostics may have a significant impact on prescribing effective treatment to an individual. Such personalization is often based on a set of mutations obtained from analyzing an individual's DNA data through an NGS analysis pipeline. The mutations that characterize the individual's disease help clinicians tailor therapy to that individual. Typically, the NGS methods amplify the DNA molecule being sequenced and divide the replicates into smaller strands called reads (made up of few tens to few thousands of contiguous base pairs). These reads are sequenced and the output is stored in a FASTQ file (unaligned NGS sequence reads+quality data is stored in a FASTQ file).

To analyze the genomic data obtained through NGS sequencing, the reads are first aligned to a reference (indicates a reference standard of the genomic data, which may be understood as the genomic data that represents each species) and then stored in a Sequence Alignment Map (SAM) file. Corresponding to each read, the SAM file has multiple fields such as the read sequence, quality values, read-level quality value, alignment location relative to the reference and a Compact Idiosyncratic Gapped Alignment Report (CIGAR) string. The CIGAR string contains a presentation of differences between the read and the reference. The SAM file may range from several megabytes (MBs) to gigabytes (GBs) in size. Analysis of the genomic data requires steps such as variation calling, which requires a pileup file of the genomic data to be analyzed.

In general, analysis or processing of compressed genomic data such as pileup file generation and variation calling is performed on a binary SAM file called a Binary Alignment Map (BAM) file. The BAM file size may increase up to a few MBs to a few GBs. In the case that the SAM data is compressed, in order to perform variation calling and generate a pileup file, the compressed genomic data of the SAM file is first decompressed and then converted into the BAM format before invoking the pileup and variation calling. This consumes a large amount of memory space and processing power, thereby increasing time for genomic data analysis.

SUMMARY

Provided are a method and device for generating a pileup file from a reference based compression file that compresses next generation sequencing (NGS) read information relative to a reference. The pileup file is generated by decompressing one or more reads from the reference based compression file. The decompression is partial decompression.

Also provided is a method of partially decompressing one or more reads by obtaining differential strings corresponding to each of the reads.

Also provided is a method of generating a pileup file by decoding the differential strings using one or more conversion rules.

According to an embodiment, a method of generating a pileup file includes receiving a reference based compression file including a plurality of pieces of read data that are compressed; partially decompressing the plurality of pieces of read data to acquire a differential string associated with the plurality of pieces of read data; and generating the pileup file by decoding the differential string based on a plurality of conversion rules.

According to another embodiment, an apparatus for generating a pileup file includes a memory configured to store at least one instruction; and a processor configured to execute the at least one instruction stored in the memory. The processor is configured to receive a reference based compression file including a plurality of pieces of read data that are compressed, partially decompress the plurality of pieces of read data to acquire a differential string associated with the plurality of pieces of read data, and generate the pileup file by decoding the differential string based on a plurality of conversion rules.

According to yet another embodiment, a non-transitory computer-readable recording medium having recorded thereon a program, which, when executed by a computer, performs the method of generating a pileup file, which includes receiving a reference based compression file including a plurality of pieces of read data that are compressed; partially decompressing the plurality of pieces of read data to acquire a differential string associated with the plurality of pieces of read data; and generating the pileup file by decoding the differential string based on a plurality of conversion rules.

DETAILED DESCRIPTION

Terms used herein are selected as general terms used currently as widely as possible considering the functions in the present disclosure, but they may depend on the intentions of one of ordinary skill in the art, legal practice, the appearance of new technologies, etc. In some cases, terms arbitrarily selected by the applicant are also used, and in such cases, their meaning will be described in detail. Thus, it should be noted that the terms used in the specification should be understood not based on their literal names but by their given definitions and descriptions as used throughout the specification.

It will be further understood that the terms “comprises” and/or “comprising” used herein specify the presence of stated features or components, but do not preclude the presence or addition of one or more other features or components. In addition, the terms such as “unit,” “-er(-or),” and “module” described in the specification refer to an element for performing at least one function or operation, and may be implemented in hardware, software, or the combination of hardware and software.

In the embodiments below, a method and device for generating a pileup file (pileup string) from a reference-based compression file will be described. The reference based compression file is typically based on a reference based next generation sequencing (NGS) data compression, in which sequencing is a process of determining the nucleotide order of a given DNA string. The reference-based compression file includes a plurality of pieces of NGS read data (reads). The NGS read data is represented as a differential string relative to a reference sequence. The read data includes spliced overlapping fragments of an amplified DNA strand or string that is to be sequenced. After sequencing, the read data is aligned to matching locations on the reference. The differential string provides difference information of the read with respect to the reference sequence where the read data aligns. The differential string is encoded along with other components of a Sequence Alignment Map (SAM) file for the read data which include, but are not limited to, quality values associated with a base of the read data as well as quality values (quality vectors) of the read data. The read data is completely defined by the reference sequence and the differential string in the reference based compression file using the reference-based NGS data compression.

A method of generating the pileup file according to an embodiment includes obtaining the differential string corresponding to the read data. The generating of the pileup file from the differential string may be performed using one or more conversion rules. Also, the generated pileup file may be used for a plurality of applications. For example, the pileup file may be used in variation calling.

Current pileup file generation methods require complete decompression or reconstruction of compressed read data in a SAM file and conversion to a stored BAM format. However, the method and device of generating the pileup file according to an embodiment do not require the complete decompression or reconstruction of the read data. The pileup file is generated by decompressing compression information to obtain a differential string for every read from a reference based compression file. The differential string may be obtained by partial decompression of read data. Compared to complete decompression or reconstruction of the read data, partial decompression of the read data may provide higher time efficiency for pileup file generation and reduce space complexity.

In an embodiment, usage of a reference-based compression mechanism that compresses the entire genome with random access may provide partial decompression of selective regions only. Also, even when the entire genome data has to be accessed from the reference based compression file, less memory may be utilized in comparison to current methods that uses an equivalent BAM file. This is due to efficient compression and partial decompression of the read data.

Hereinafter, the present embodiments will be described with reference toFIGS. 1 to 5. In the drawings, like reference numerals denote like elements.

FIG. 1is a diagram describing a network implementation100including a device102for generating a pileup file (pileup string) from a reference-based compression file including a reference-based compressed genomic data, according to an embodiment. A device102according to an embodiment may be implemented as an application or module for executing a set of instructions on a server50. The device102may be implemented in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a server, a network server, an electronic device, and the like. In an embodiment, the device102may be implemented in a cloud-based environment. The device102may be accessed by multiple users through one or more user devices1061to106N(hereinafter, the one or more user devices1061to106Nwill be collectively referred to as user devices106) or through applications of the user devices106. For example, the user devices106may include, but are not limited to, a portable computer, a personal digital assistant (PDA), a hand-held device, and a workstation. The user devices106may communicate with the device102via a network104.

In an embodiment, the network104may be a wireless network, a wired network, or a combination thereof. The network104may be implemented as one of different types of networks, such as an intranet, a local area network (LAN), a wide area network (WAN), the Internet, and the like.

FIG. 2is a block diagram of the device102for generating a pileup file, according to an embodiment. Referring toFIG. 2, the device102may include a processor202, and an input/output (I/O) interface206. The device102may further include a memory unit204storing various code modules to be executed by the processor202. The device102may be configured to allow the processor202to access the reference-based compression file. In an embodiment, the device102may receive the reference-based compression file from any other storage device through the I/O interface206. The reference-based compression file may include a plurality of pieces of read data or reads stored as the differential string. The device102according to an embodiment may generate the differential string associated with each piece of read data included in the reference-based compression file.

The device102may generate the pileup file by partially decompressing the plurality of pieces of read data included in the reference-based compression file. Also, the device102may generate the pileup file by decoding the differential string of each piece of the read data based on a plurality of conversion rules. The conversion rules will be described later with reference toFIGS. 3 and 4A to 4K. The generated pileup file may be stored in the memory unit204or any other storage device and used in various applications. For example, the generated pileup file may be used for, but is not limited to, variation calling.

FIG. 2is the block diagram of an embodiment the device102for generating the pileup file. The components shown in the block diagram may be combined, include additional components, or omit some component(s) according to the actual implementation of the device102. That is, two or more components may be combined or one component may be separated into two or more components if necessary. Also, functions performed by each block are merely for describing embodiments. Specific operations or devices do not limit the scope of the inventive concept. Furthermore, the device102may include various other modules or components. Also, the device102may include various modules and components interacting locally or remotely along with other hardware or software components to communicate with each other. For example, the components may include, but are not limited to, a process running in a controller or a processor, an object, an executable process, a thread of execution, a program, or a computer.

FIG. 3is a flowchart of a method of generating a pileup file from a reference-based compression file including reference-based compressed genomic data, according to an embodiment. Referring toFIG. 3, in operation302, the method of generating the pileup file according to an embodiment includes receiving the reference-based compression file (compressed genetic information) as an input. The reference-based compression file includes a plurality of pieces of read data that are stored by using a reference-based compression mechanism. In an embodiment, the reference-based compression mechanism may be NGS compressed data that includes the plurality of pieces of read data represented as differential strings. In operation304, the method of generating the pileup file according to an embodiment includes decompressing the plurality of pieces of read data of the reference-based compression file by generating a differential string associated with each piece of the read data. Unlike methods of the related art that include completely decompressing the reads to generate the pileup file, the differential string is generated by partially decompressing the read data. In operation306, the method of generating the pileup file according to an embodiment includes generating the pileup file by decoding the differential string of each piece of the read data based on one or more conversion rules. The conversion rules may enable decoding of each segment of the differential string associated with each piece of read data that may be required for generating the pileup file. The conversion rules will be described later. The generated pileup file may be a standard pileup file that includes a plurality of fields corresponding to each of the decoded differential strings. The plurality of fields may include a position field of the read data relative to a reference, a reference field (reference read data), a read base information field (a vector of matches and mismatches), and a quality information field (quality vector). A length of the vector at each position is approximately equivalent to a depth of the SAM file. The quality vector represents quality values corresponding to strings in vector fields. An example pileup string corresponding to a particular read is shown in Table 1 below.

The generated pileup file may be used for a plurality of applications including, but not limited to, variation calling.

The device102according to an embodiment may generate the pileup file based on partial decompression of the reads by performing the method of generating the pileup file including operations302to306.

Various operations, actions, blocks, steps, and the like of the method of generating the pileup file may be performed in the aforementioned order, in a different order, or simultaneously. According to another embodiment, some operations, actions, blocks, steps, and the like may be omitted, added, modified, and the like without departing from the scope of the inventive concept.

FIG. 4Ais a diagram of an example of read data for generating a pileup string, according to an embodiment.FIG. 4Ashows alignments of read data with respect to a reference, according to an embodiment.FIG. 4Ashows a reference402a, a read404a, a read406ain alignment with respect to the reference, and a CIGAR and a differential string408a. The CIGAR string is used to store differences of the read and the reference in an existing SAM file format. The CIGAR may also be viewed as a differential string, but does not include information on specific changes such as substitutions and mismatches as well as locations of such changes in the read with respect to the equivalent position on the reference.

The reference402ais used as a reference sequence for the read404ato generate a reference-based compression file. Difference information between the reference402aand the read404ais stored in the reference-based compression file as the differential string408ain addition to other read related information. In the reference-based NGS data compression, difference information may be encoded, thereby saving a considerable amount of memory. A position of a difference may be encoded using differential offsets. A type of variation between the read and the reference may be encoded followed by a nucleotide sequence (except in the case of a deletion operation). An entropy coder (e.g., an arithmetic coder) may be used for compressing each of the above parameters. The quality values may be compressed using methods relevant to compressing a set of symbols such as those used in compression of unaligned NGS data (e.g., in a FASTQ file).

The differential string that represents a difference between the read and the reference sequence may include indicators including substitution “S,” insertion “I,” deletion “D,” and soft-clipping “@.” According to an embodiment, the differential string408amay be “0@AAA 0SC 3SA 0IAT 0SCG 0D2.”

The device102according to an embodiment may generate the pileup file by using the conversion rules to decode the differential string. The conversion rules according to an embodiment will be described below with reference to Table 2. The fields of the pileup file may include a position field (indicates a position in relation to the reference), a reference field, a read base information field, and a quality information field.

TABLE 2Action1Select a segment of a differential string associated with a read and insertreference base.2If a segment to be decoded is a first segment of the differential string,Insert a start position of the read and a corresponding reference basevalue in a position field and a reference field of a pileup string field.Insert “{circumflex over ( )}” (first symbol) in a “read base information” field to indicate startof the read.Insert a quality value of the read with quality value = ASCII value of (readquality + predefined value) in the read based information field (in anembodiment, the predefined value may be 33).3Identify an indicator for each segment of the differential string.If an indicator at a beginning of the read or an end of the read is a soft-clipping indicator “@,” ignore soft-clipping and corresponding sequence.Else perform:If the indicator is a substitution indicator “S,”Identify one or more substitutions from the differential string.At positions (on the reference) of the substitutions: Insert substitutionbase values from the read in the read base information field of the pileupstring, insert quality values corresponding to the substitution base valuesin a quality information field, insert a reference base value in a referencefield, insert a corresponding reference position in a position field.Determine an internal state as substitution (as represented by S).Increase the positions by the number of substitutions.If the indicator is “I”Insertion is always captured at a previous position.Values of bases inserted at a current position are inserted in the readbase information field, and quality values corresponding to the values areinserted in the quality information field. “+” is added in front of the valuesof the bases.Determine the internal state as “I.”Position value remains unchanged.If the indicator is “D,”Deletions may be marked according to the following two ways.If a deletion is preceded by a matching or a substitution at a previousposition, put a “−” sign at the previous position followed by the number ofbases deleted and actual values of the bases on the reference. Insert “*”in a read base information field corresponding to a position where thedeletion has occurred. Also, “!” (ASCII = 33: Lowest quality) is inserted inquality information fields corresponding to the position where the deletionhas occurred. Relevant values are inserted in the position field and thereference field.If a deletion occurs after an insertion (other cases), insert “*” at a readbase information field corresponding to a position where the deletion hasoccurred. Relevant values are inserted in the position field and thereference field. Also, “!” (ASCII = 33: Lowest quality) is inserted in qualityinformation fields corresponding to the position where the deletion hasoccurred.Determine the internal state as “D.”Internal position is increased by the number of deletions.Change or maintain internal stateChange positionMatches are indicated by inserting “.” into the read base information field,and corresponding quality values into the quality information field. Also,relevant values are inserted in the position field and the reference field.At the end of a read, “$” (second symbol) is inserted at a last entry of theread base information field.

FIGS. 4B to 4Kare exemplary diagrams describing a method of generating a pileup string for the read404abased on the conversion rules, according to an embodiment.

FIG. 4Billustrates a first step for generating a pileup string402bfor the read404abased on the reference402ashown inFIG. 4B. The differential string408afor the read404ais shown as “0@AAA 0SC 3SA 0IAT 0SCG 0D2 0IAA 0D2.” As 1024 is a start position of the reference402a, the device102may insert “^” indicating start of the read404ain the read base information field, and a base “A” in a reference field of the pileup string402b. Also, the device102inserts a quality value (0) in the read base information field. The quality value is calculated based on ‘quality value=ASCII (value of read+33).

FIG. 4Cillustrates a second step for generating the pileup string402bfor the read404abased on the reference402ashown inFIG. 4C. A segment “0@AAA” of the differential string408aindicates soft-clipping “@” of AAA bases at an index 0 from the start position1024of the reference402a. According to the conversion rules of Table 2, soft-clipping is ignored at the beginning and the end of the read. Also, an internal state is marked as @, and a position on reference remains at1024.

FIG. 4Dillustrates a third step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4D. A segment “0SC” of the differential string408aindicates substitution of a base C at a previously changed position1024. Also, a quality value may be inserted to a quality information field corresponding to the position1024. For example, as shown inFIG. 4D, the device102may insert a quality value ‘#’ corresponding to the base C in the quality information field. Also, a position on the reference may be increased by 1 (the number of substitution) from1024to1025.

FIG. 4Eillustrates a fourth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4E. Two sub steps may be performed for a segment “3SA” of the differential string408a. In a first sub step, the segment “3SA” indicates that there are three matches at positions1025,1026, and1027on the reference402a. Accordingly, the device102may insert “.” in the read base information fields corresponding to the positions1025,1026, and1027. Also, the device102may insert quality values “=”, “+”, and “p” that respectively correspond to bases T, C, and G in the quality information fields respectively corresponding to the positions1025,1026, and1027. The device102may determine the internal state as ‘M’ and change the position on the reference from1024to1027.

Also, in a second sub step, the segment “3SA” indicates that a base C is substituted with a base A at a position1028on the reference402a. In the second sub step, the device102may insert a quality value (e.g., q) of a substituted base (e.g., base A) in the quality information field. Also, the device102may mark the internal state as ‘S,’ and change the position on the reference from1028to1029.

FIG. 4Fillustrates a fifth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4F. A segment “0IAT” of the differential string408aindicates insertion “I” of two bases A and T at a position1029. Since insertion is always captured at a previous position according to the conversion rules, A and T are inserted at1028, which is the previous position of a current position, that is, the position1029. In this case, as shown inFIG. 4F, “+” is added in front of A and T. Also, quality information at the position1029is updated, and ‘r’ and ‘t’ respectively corresponding to A and T are added to the quality information field, as shown inFIG. 4F. Also, the device102marks the internal state as “I,” and maintains the position on the reference at1029.

FIG. 4Gillustrates a sixth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4G. A segment “0SCG” of the differential string408aindicates substitution of two bases C and G. As shown inFIG. 4G, the device102marks substitution of the base C at a read base information field corresponding to the position1029, and marks substitution of the base G at a read base information field corresponding to a position1030. Also, the device102may update quality information of each position, and mark the internal state as “S.” Also, the device102may change the position on reference by increasing 1029 by the number of substituted bases, i.e., two.

FIG. 4Hillustrates a seventh step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4H. A segment “0D2” of the differential string408aindicates that there is a deletion of two bases at a position that is zero distance apart from a position1031. The deletion may be marked in two ways. A first way may be used when the deletion is preceded by “M” (match) or “S” (substitution). The first way indicates that, when the number of deleted bases is ‘n,’‘−n’ and a deleted base value may be inserted in a read base information field corresponding to a previous position. Also, “*” may be marked at a read base information field corresponding to a position where the deletion occurred, and “!” may be inserted in a quality information field corresponding to the position where the deletion occurred. A second way may be used for all other cases expect for when the deletion is preceded by “M” or “S.” According to the second way, “*” may be marked at a position where the deletion occurred, and “!” may be inserted in a quality information field corresponding to the position where the deletion occurred.

For the segment “0D2” of the differential string408a, the first way may be used because a substitution has been previously performed. The device102may identify reference bases (in this case, A and A) at the position1031and the position1032. According to the first way, the device102may insert −2AA in a read base information field corresponding to the previous position1030. Also, the device102may insert “*” in read base information fields corresponding to the positions1031and1032, and insert “!” in quality information fields corresponding to the positions1031and1032. Also, the position on reference may be increased from1031by the number of deleted bases, i.e., two, and changed to1033, and the internal state may be marked as “D.”

FIG. 4Iillustrates an eighth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4I. A segment “0IAA” of the differential string408aindicates an insertion of two bases A and A at a position that is zero distance apart from the position1033. Since insertion is always captured at a previous position according to the conversion rules, A and A are inserted at1032, which is the previous position of a current position, that is, the position1033. In this case, as shown inFIG. 4I, “+” is added in front of A and A. Also, quality information at the position1033is updated, and ‘√^’ and ‘−’ respectively corresponding to A and A are added to the quality information field, as shown inFIG. 4I. Also, the internal state is marked as “I,” and the position on the reference is maintained at1033.

FIG. 4Jillustrates a ninth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4J. A segment “0D2” of the differential string408aindicates a deletion of two bases, and the device102may identify two bases at the position1033and a position1034. Since the insertion has been previously performed for the segment “0D2,” the second way of deletion may be used. According to the second way, the device102may insert “*” in read base information fields corresponding to the position1033and1034, and insert “!” in quality information fields corresponding to the positions1033and1034. Also, the device102may change the position on reference to1035from1033by increasing by the number of deleted bases, i.e., two, and mark the internal state as “D.”

FIG. 4Killustrates a tenth step for generating the pileup string402bfor the read404abased on the reference402aofFIG. 4K. In this case, the position on the reference is1035, and no segments in the differential string may be left to be processed. However, the number of reads processed is fourteen while a known read length is sixteen. Therefore, the number of bases left to be processed is two (16−14=2). In this case, when the number of bases left to be processed is greater than 0, the device102may perform a “match” operation for every base left to be processed. For example, the device102may insert “.” in a base information field corresponding to the remaining reference and insert a quality value corresponding to a reference base in a quality information field. Also, as shown inFIG. 4K, the device102may add “$” indicating an end of the read to a last entry of the read base information field.

In an embodiment, the device102may generate the pileup string402bby performing the first to tenth steps described with reference toFIGS. 4B to 4K.

FIG. 5is a diagram of a computing device500for generating a pileup file from a reference-based compression file, according to an embodiment. Referring toFIG. 5, the computing device500may include a processing unit508including a controller504and an arithmetic logic unit (ALU)506, a memory510, a storage unit512, an I/O interface514, and a network interface516.

Also, the processing unit508may process instructions of an algorithm. The processing unit508may receive commands from the controller504to perform processing. Also, any logical and arithmetic operations involved in the execution of the instructions may be performed by the ALU506.

The computing device500according to an embodiment may include a plurality of homogenous and/or heterogeneous cores, different types of central processing units (CPUs), special media, and other accelerators. The processing unit508may be implemented as a single chip or a plurality of chips, but is not limited thereto.

An algorithm including instructions and codes required for execution may be stored in the memory510, the storage unit512, or both. At the time of execution, the instructions may be fetched from the memory510or the storage unit512, and executed by the processing unit508.

In the case of random hardware devices, the computing device500may be connected to various devices via the network interface516. Commands may be received from a user or processing results of the computing device500may be transmitted to the user via the I/O interface514.

The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the various components or elements. The components shown in theFIGS. 1 to 5include blocks which can be at least one of a hardware device, or a combination of a hardware device and a software module.

The method of generating the pileup file according to the embodiments may be embodied as computer-readable code on a computer-readable recording medium. The computer-readable recording medium is any data storage device that can store programs or data which can be thereafter read by a computer system. Examples of the computer-readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, hard disks, floppy disks, flash memory, optical data storage devices, and the like. The computer-readable recording medium can also be distributed over network coupled computer systems so that the computer-readable code is stored and executed in a distributive manner.