Methods and systems for improved K-mer storage and retrieval
Inventors
Lee, Hojoon • Ji, Hanlee P. • Weissman, Tsachy • Pavlichin, Dmitri
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Assignees
Leland Stanford Junior University
MemberStanford UniversityStanford UniversityTodd Coleman is an associate professor of bioengineering at Stanford University. His research combines applied probability, physiology, and bioelectronics to develop methods and devices for monitoring and modulating nervous-system and other physiological activity, including brain and visceral-organ signals.
Todd Coleman is an associate professor of bioengineering at Stanford University. His research combines applied probability, physiology, and bioelectronics to develop methods and devices for monitoring and modulating nervous-system and other physiological activity, including brain and visceral-organ signals.
Publication Number
US-12749557-B2
Publication Date
2026-09-29
Expiration Date
Abstract
Systems and methods of storing and retrieving K-mer data in a data structure are provided. In certain embodiments, the K-mer data is stored as an integer value that defines an address of a slot in the data structure. In many embodiments, each slot in the data structure stores the remaining portion of the K-mer that is not part of the prefix. Additional embodiments are directed to genetic or genomic analysis using a data structure for storing K-mer data.
Core Innovation
The invention describes a compact K-mer index for nucleotide sequences. Each K-mer is represented by a prefix portion and a remainder portion, with the prefix value defining a slot address and the remainder value stored in that slot. Fibonacci hashing computes the values, while linear hash-collision resolution addresses a slot already filled by a K-mer sharing the same prefix value.
The index supports metadata association, retrieval, and queries for K-mers associated with genomic events, including short and structural variants, fusions, and haplotypes. Figures illustrate K-mer representations of genomic events and variant frequencies distinguishing tumor from normal samples. Demonstrations also report K-mer counting and somatic mutation detection results, while the background section and the problem being solved are not explicitly described.
Claims Coverage
The three independent claims are claims 1, 16, and 17, covering three inventive features: a method for indexing K-mers, a data structure for storing K-mers, and a method for identifying genomic events.
K-mer indexing using Fibonacci hashing
Independent claim 1 covers obtaining a nucleotide sequence, defining a K-mer size, and indexing its K-mers in a slot-based data structure. A prefix value defines each slot address, a remainder value is stored in the slot, and Fibonacci hashing computes both values. Linear hash-collision resolution is used when a slot is already filled by a K-mer sharing the same prefix value.
Slot-based K-mer data structure
Independent claim 16 covers a data structure for storing genetic or genomic data in memory slots. Each K-mer is stored in a specific slot based on its prefix value, with its remainder value stored in that slot. A Fibonacci hash function yields the prefix and remainder values, and a subset of remainder values includes an increment or decrement corresponding to linear hash-collision resolution.
Identification of genomic events by querying K-mers
Independent claim 17 covers accessing a data structure containing K-mers stored in memory slots according to their prefix values, with their remainder values stored in the slots. A Fibonacci hash function yields the values, and increments or decrements correspond to linear hash-collision resolution. The method queries the data structure to obtain and output a set of K-mers associated with a genomic event.
The independent claims cover K-mer indexing, a slot-based K-mer storage structure, and genomic event identification by querying that structure. Across these features, the claims specify Fibonacci hashing and linear hash-collision resolution.
Stated Advantages
Fibonacci hashing is reported to improve key distribution.
A reported demonstration performs K-mer counting approximately four times faster than Jellyfish.
A reported implementation supports about one million queries per second.
Unique somatic K-mer counts are reported to correlate with validated mutation calls, with R²=0.959.
Documented Applications
Querying for K-mers associated with genomic events, including short variants, structural variants, haplotypes, and other genomic events.
Somatic mutation detection through unique somatic K-mer counts correlated with validated mutation calls.
Associating metadata with K-mers and retrieving K-mers from the index.
Representing gene fusions, tandem repeats, microsatellite regions, and variant-associated K-mer frequencies in normal and tumor samples, including neo-K-mers distinguishing tumor from normal.
Interested in licensing this patent?