Systems and methods for sequence encoding, storage, and compression
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12205679-B2
Publication Date
2025-01-21
Expiration Date
Abstract
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.
Core Innovation
The invention describes Dynamic Alphabet Coding (DAC) for lossless encoding of genomic data. The method scans the genomic data, keeps track of a number of unique characters scanned, and notes positions in the sequence where the number increases to a power of two. The genomic data is then divided into a plurality of segments based on the positions where the unique-character count reaches powers of two.
Each segment is encoded using the smallest number of bits per character needed to represent all unique characters present in that segment. For each segment, an identity and number of each character is encoded, and encoding comprises creating a segment header and a corresponding data portion. The segment header comprises information about an alphabet of characters that is encoded by the corresponding data portion.
The invention further specifies metadata compression and graph-related encoding. It describes linearizing graph metadata and performing a reversible byte reordering to create local pockets of self-similarity before applying DAC to byte segments. It also describes representing genomic data as a directed graph of genomes, encoding characters in segments to transform the graph into a serial bit sequence, and transferring that bit sequence serially between computer systems.
Claims Coverage
The independent claims are directed to encoding genomic data using Dynamic Alphabet Coding with power-of-two segmentation and segment-local alphabets, with additional refinements that specify bit-width selection, segment-header structure, alphabet identification mechanisms, optional segment bit-width variability, and an alternate directed-graph genome representation with serial transfer.
Power-of-two unique-character segmentation
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 a plurality of segments based on the positions.
Segment-local smallest bits per character with alphabet identity and number
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; and 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.
Explicit unique-character count constraint for bits per character
Determining the number N of unique characters and encoding the segment using X bits per character such that 2^(x−1) < N < 2^x.
Segment header length bits and flag bits for alphabet information
Specifying that a segment header includes at least two bits for indicating the segment header length and multiple flag bits that identify the alphabet of characters encoded by the associated data portion.
Alphabet identification using bitmap flag bits
Specifying that flag bits indicate the alphabet by using a bitmap to show which characters are included.
Segment-dependent bits per character variability
Configuring that a first segment and a second segment use different numbers of bits per character.
Directed graph genome representation with serial bit transfer
Representing genomic data as a directed graph of genomes, encoding characters in segments to transform the graph into a serial bit sequence, and transferring that bit sequence serially from one computer system memory device to a second computer system.
Across the independent-claim scope, the core inventive coverage includes power-of-two segmentation based on a scanned unique-character count, segment-local smallest bits-per-character encoding with an encoded alphabet in a segment header, and refinements that define header fields and alphabet identification, segment-to-segment bit-width variability, and an alternate directed-graph genome representation with serial transfer.
Stated Advantages
lossless decoding (lossless encoding/decoding of the encoded data streams).
maximum space savings by selecting boundaries that yield the largest compression space savings (as described in the provided content).
simplified decoding support via segment headers that include alphabet information.
Documented Applications
encoding directed graph genomes (directed graph representing relationships among genomes).
serialization/transfer of encoded bit/byte streams, including conversion of a graph representation into a serial bit sequence and streaming between systems.
optional random-access support via block offset tables (as described in the provided content).
variable-byte encoding scheme using LFR8/LR8 length-flag-representation within headers to avoid prior decoder knowledge (as described in the provided content).
Interested in licensing this patent?