K-mer based genomic reference data compression

Patent metadata

Field	Value
Publication number	US-11515011-B2
Application number	US-201916537184-A
Country	US
Kind code	B2
Filing date	Aug 9, 2019
Priority date	Aug 9, 2019
Publication date	Nov 29, 2022
Grant date	Nov 29, 2022

Abstract

A computer-implemented method includes receiving genomic data associated with a plurality of genomes and identifying k-mer sets within the genomic data. The method includes constructing a k-mer subset tree according to the following process: performing iterative pairwise comparisons on the k-mer sets, wherein the iterative pairwise comparisons identify fragments with the most shared k-mers, merging the identified fragments into non-leaf nodes of the k-mer subset tree, and placing each remaining k-mer into a leaf node of the k-mer subset tree. The method includes storing the k-mer subset tree. A computer program product for data compression includes a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a computer to cause the compute to perform the foregoing method. A system includes a processor and logic. The logic is configured to perform the foregoing method.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving genomic data associated with a plurality of genomes;
identifying k-mer sets within the genomic data;
constructing a k-mer subset tree according to the following process:
performing iterative pairwise comparisons on the k-mer sets, wherein the iterative pairwise comparisons identify fragments with the most shared k-mers,
merging the identified fragments into non-leaf nodes of the k-mer subset tree, and
placing each remaining k-mer into a leaf node of the k-mer subset tree; and

storing the k-mer subset tree;
receiving a request for the genomic data; and
reconstituting at least one genome using non-leaf nodes from a spine of the k-mer subset tree and a corresponding leaf node, wherein the reconstituting does not include decompression of the k-mer sets on loading from storage.

2. The computer-implemented method of claim 1 , wherein the iterative pairwise comparisons on the k-mer sets are based on a similarity measure.

3. The computer-implemented method of claim 2 , wherein the similarity measure is a Jaccard index.

4. The computer-implemented method of claim 1 , wherein the k-mers sets are identified in a single canonical form.

5. The computer-implemented method of claim 4 , wherein the canonical form is an alphanumeric form.

6. The computer-implemented method of claim 1 , wherein the non-leaf nodes represent subsets of k-mers that do not exist higher up in the k-mer subset tree.

7. The computer-implemented method of claim 1 , wherein the leaf nodes represent subsets of k-mers that do not exist higher up in the k-mer subset tree.

8. The computer-implemented method of claim 1 , wherein data compression of the k-mers is lossless.

9. The computer-implemented method of claim 1 , wherein the k-mer subset tree is constructed based on a known tree selected from the group consisting of: a taxonomic tree and a phylogenetic reference tree.

10. A computer program product for data compression, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the compute to:
receive, by the computer, genomic data associated with a plurality of genomes;
identify, by the computer, k-mer sets within the genomic data;
construct, by the computer, a k-mer subset tree according to the following process:
perform, by the computer, iterative pairwise comparisons on the k-mer sets, wherein the iterative pairwise comparisons identify fragments with the most shared k-mers,
merge, by the computer, the identified fragments into non-leaf nodes of the k-mer subset tree, and
place, by the computer, each remaining k-mer into a leaf node of the k-mer subset tree; and

store, by the computer, the k-mer subset tree; and
receive, by the computer, a request for the genomic data; and
reconstitute, by the computer, at least one genome using non-leaf nodes of a spine of the k-mer subset tree and a corresponding leaf node, wherein the reconstituting does not include decompression of the k-mer sets on loading from storage.

11. The computer program product of claim 10 , wherein the iterative pairwise comparisons on the k-mer sets are based on a similarity measure.

12. The computer program product of claim 11 , wherein the similarity measure is a Jaccard index.

13. The computer program product of claim 10 , wherein the k-mer sets are identified in a single canonical form.

14. The computer program product of claim 10 , wherein data compression of the k-mers is lossless.

15. The computer program product of claim 10 , wherein the k-mer subset tree is constructed based on a known tree selected from the group consisting of: a taxonomic tree and a phylogenetic reference tree.

16. A system, comprising:
a processor; and
logic integrated with the processor, executable by the processor, or integrated with and executable by the processor, the logic being configured to:
receive genomic data associated with a plurality of genomes;
identify k-mer sets within the genomic data;
construct a k-mer subset tree according to the following process:
perform iterative pairwise comparisons on the k-mer sets, wherein the iterative pairwise comparisons identify fragments with the most shared k-mers,
merge the identified fragments into non-leaf nodes of the k-mer subset tree, and
place each remaining k-mer into a leaf node of the k-mer subset tree; and

store the k-mer subset tree; and
receive a request for the genomic data; and
reconstitute at least one genome using non-leaf nodes of a spine of the k-mer subset tree and a corresponding leaf node, wherein the reconstituting does not include decompression of the k-mer sets on loading from storage.

17. The system of claim 16 , wherein the iterative pairwise comparisons on the k-mer sets are based on a similarity measure.

18. The system of claim 16 , wherein data compression of the k-mers is lossless.

Assignees

• IBM

Inventors

• Waddington Daniel
• Kunitomi Mark
• Abboud Amir
• Rao Samyukta Satish

Classifications

• G16B50/50 Primary

  Compression of genetic data · CPC title

• G06F7/32

  Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence) · CPC title

• G16B30/00

  ICT specially adapted for sequence analysis involving nucleotides or amino acids · CPC title

• H03M7/30

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• H03M7/70

  Type of the data to be coded, other than image and sound · CPC title