Granted Patent B2

US 11,734,231 · App. 17/569,500 · Granted Aug 22, 2023

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

Assignee: ATOMBEAM TECHNOLOGIES INC.

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

Abstract

Claims (60)

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

a computing device comprising a processor, and a memory;

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 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 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;

pass the plurality of deconstructed sourceblocks to a library management module for comparison with sourceblocks already contained in the codebook;

receive a reference code for each of the deconstructed sourceblocks from the library management module; and

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

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.

2. The system of claim 1 , 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.

3. 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.

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

5. The system of claim 1 , 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.

6. A method for bandwidth-efficient encoding of genomic data, 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 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;

passing the plurality of deconstructed sourceblocks to a library management module for comparison with sourceblocks already contained in the codebook;

receiving a reference code for each of the deconstructed sourceblocks from the library management;

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

receiving 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; and

returning the new reference code to the data deconstruction engine.

7. The method of claim 6 , 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.

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

9. The method of claim 8 , wherein the graph is a De Bruijin graph, a directed graph, a bi-edged graph, or a bidirected graph.

10. The method of claim 6 , 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 (9)