Granted Patent B2

US 12,189,580 · App. 18/449,706 · Granted Jan 7, 2025

Inventors: Joshua Cooper (Columbia, SC); Aliasghar Riahi (Orinda, CA)

Assignee: ATOMBEAM TECHNOLOGIES INC

G06F16/1752G06F3/0608G06F3/0641G06F3/067

Abstract

Claims (62)

1. A system for bandwidth-efficient data encoding, comprising:

a computing device comprising a processor and a memory;

a sequence analyzer comprising a first plurality of programming instructions stored in the memory and operable on the processor, wherein the first plurality of programming instructions, when operating on the processor, cause the processor to:

receive a sequence dataset;

scan the sequence dataset and maintain a count of the number of unique characters contained within the sequence dataset;

for each occurrence of a unique character which causes the count of the number of unique characters to reach a value equal to a power of two, indicate a position in the sequence dataset corresponding to the unique character;

calculate, for each of the indicated positions, a compaction ratio that would be obtained by dividing the sequence dataset into one of a plurality of segments at one of the indicated positions;

deconstruct the sequence dataset into a plurality of deconstructed sourceblocks at the positions that yield the best compaction ratio; and

pass the plurality of deconstructed sourceblocks to a data deconstruction engine; and

a data deconstruction engine comprising a second plurality of programming instructions stored in the memory and operable on the processor, wherein the second plurality of programming instructions, when operating on the processor, cause the processor to:

receive the plurality of deconstructed sourceblocks from the sequence analyzer; and

create a plurality of codewords for storage or transmission of the sequence dataset.

2. The system of claim 1 , further comprising:

a codebook stored in the memory of the computing device, the codebook comprising a plurality of sourceblocks and for each sourceblock a reference code;

a library management module comprising a third plurality of programming instructions stored in the memory and operable on the processor, wherein the third plurality of programming instructions, when operating on the processor, cause the processor to:

receive the plurality of deconstructed sourceblocks from the data deconstruction engine;

for each of the plurality of deconstructed sourceblocks, return a reference code to the data deconstruction engine, when the respective received deconstructed sourceblock matches an existing sourceblock in the codebook; and

for each received deconstructed sourceblock that is not present in the codebook:

create a new, unique reference code for the respective deconstructed sourceblock;

store both the respective deconstructed sourceblock and the associated reference code in the codebook; and

return the new reference code to the data deconstruction engine; and

wherein the data deconstruction module is further configured to:

pass the plurality of deconstructed sourceblocks to the library management module;

receive a reference code for each of the plurality of deconstructed sourceblocks from the library management module.

3. The system of claim 2 , wherein each of the plurality of codewords contains at least a reference code to a sourceblock in the codebook, and may contain additional information about the location of the reference code within the sequence dataset.

4. The system of claim 1 , wherein the sequence dataset that is encoded comprises a graph representing at least a portion of a plurality of genomes.

5. The system of claim 4 , wherein the graph is a De Bruijn graph, a directed graph, a bi-edged graph, or a bidirected graph.

6. The system of claim 2 , further comprising a data reconstruction engine comprising a fourth plurality of programming instructions stored in the memory and operable on the processor, wherein the fourth plurality of programming instructions, when operating on the processor, cause the processor to:

receive a request for a reconstructed sequence dataset;

retrieve the codewords associated with the requested data from the codebook;

pass the reference codes contained in the codewords to the library management module for retrieval of the sourceblock contained in the codebook associated with the reference codes;

assemble the retrieved sourceblocks in proper order based on location information contained in the codewords; and

send out the reconstructed sequence dataset to the requester.

7. A method for bandwidth-efficient data encoding, comprising the steps of:

storing, in a memory of a computing device, a codebook, the codebook comprising a plurality of sourceblocks and for each sourceblock a reference code;

receiving a sequence dataset;

scanning the sequence dataset and maintaining a count of the number of unique characters contained within the sequence dataset;

for each occurrence of a unique character which causes the count of the number of unique characters to reach a value equal to a power of two:

indicating a position in the sequence dataset corresponding to the unique character;

calculating, for each of the indicated positions, a compaction ratio that would be obtained by dividing the sequence dataset into one of a plurality of segments at one of the indicated positions;

deconstructing the sequence dataset into a plurality of deconstructed sourceblocks at the positions that yield the best compaction ratio;

passing the plurality of deconstructed sourceblocks to a data deconstruction engine;

receiving the plurality of deconstructed sourceblocks from the sequence analyzer;

creating a plurality of codewords for storage or transmission of the sequence dataset.

8. The method of claim 7 , further comprising the steps of:

passing, using the data deconstruction engine, the plurality of deconstructed sourceblocks to a library management module;

receiving, at the library management module, the plurality of deconstructed sourceblocks from the data deconstruction engine;

for each of the plurality of deconstructed sourceblocks, returning a reference code to the data deconstruction engine, when the respective received deconstructed sourceblock matches an existing sourceblock in the codebook; and

for each received deconstructed sourceblock that is not present in the codebook:

creating a new, unique reference code for the respective deconstructed sourceblock;

storing both the respective deconstructed sourceblock and the associated reference code in the codebook;

returning the new reference code to the data deconstruction engine; and

receiving, at the data deconstruction engine, a reference code for each of the plurality of deconstructed sourceblocks from the library management module.

9. The method of claim 8 , wherein each of the plurality of codewords contains at least a reference code to a sourceblock in the codebook, and may contain additional information about the location of the reference code within the sequence dataset.

10. The method of claim 7 , wherein the sequence dataset that is encoded comprises a graph representing at least a portion of a plurality of genomes.

11. The method of claim 10 , wherein the graph is a De Bruijn graph, a directed graph, a bi-edged graph, or a bidirected graph.

12. The method of claim 8 , further comprising the steps of:

receiving a request for a reconstructed sequence dataset;

retrieving the codewords associated with the requested data from the codebook;

passing the reference codes contained in the codewords to the library management module for retrieval of the sourceblock contained in the codebook associated with the reference codes;

assembling the sourceblock in the proper order based on the location information contained in the codewords; and

sending out the reconstructed sequence dataset to the requester.

Assignments (1)

Continuity (13)

References Cited (5)