Systems and methods for sequence encoding, storage, and compression
Genomic data is written to disk in a compact format by dividing the data into segments and encoding each segment with the smallest number of bits per character necessary for whatever alphabet of characters appears in that segment. A computer system dynamically chooses the segment boundaries for maximum space savings. A first one of the segments may use a different number of bits per character than a second one of the segments. In one embodiment, dividing the data into segments comprises scanning the data and keeping track of a number of unique characters, noting positions in the sequence where the number increases to a power of two, calculating a compression that would be obtained by dividing the genomic data into one of the plurality of segments at ones of the noted positions, and dividing the genomic data into the plurality of segments at the positions that yield the best compression.
1. A method for encoding genomic data, the method comprising:
dividing genomic data into a plurality of segments, wherein dividing the genomic data into the plurality of segments comprises:
scanning the genomic data and keeping track of a number of unique characters scanned;
noting positions in the sequence where the number increases to a power of two; and
dividing the genomic data into the plurality of segments based on the positions;
encoding characters within each of the plurality of segments with a smallest number of bits per character needed to represent all unique characters present in each segment, wherein an identity and number of each character is encoded, wherein encoding the characters within each of the plurality of segments comprises creating for each segment a segment header and a corresponding data portion, the header comprising information about an alphabet of characters that is encoded by the corresponding data portion; and
storing the encoded characters in a computer-readable medium.
2. The method of claim 1 , wherein a first one of the segments uses a different number of bits per character than a second one of the segments.
3. The method of claim 1 , wherein, within a segment, every character is encoded using the same number of bits.
4. The method of claim 1 , wherein encoding the characters within each of the plurality of segments comprises:
determining a number N of unique characters in the segment; and
encoding the segment using X bits per character, where 2{circumflex over ( )}(x−1)<N<2{circumflex over ( )}x.
5. The method of claim 1 , wherein the segment header comprises at least two bits that indicate a length of the segment header and a plurality of flag bits, wherein the flag bits identify the alphabet of characters that is encoded by the corresponding data portion.
6. The method of claim 5 , wherein the flag bits identify the alphabet using a bitmap to identify included characters.
7. The method of claim 1 , wherein the genomic data comprises a directed graph representing at least a portion of a plurality of genomes, and wherein encoding the characters within each of the plurality of segments transforms the directed graph into a sequence of bit, the method further comprising transferring the sequence of bits serially from a computer memory device a computer system to a second computer system.