Methods and systems for improved K-mer storage and retrieval
AssigneeThe Board of Trustees of the Leland Stanford Junior University
InventorsHoJoon Lee, Hanlee P. Ji, Tsachy Weissman, Dmitri Pavlichin
Life of this patent
Estimating the term…
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.
Claims17
A method for indexing K-mers, comprising:
- obtaining a nucleotide sequence;
- defining a K-mer size;
- and
- indexing K-mers of the nucleotide sequence according to the K-mer size,
- wherein each K-mer represents a sequence segment of the nucleotide sequence;
- wherein each sequence segment comprises a prefix portion and a remainder portion, wherein the prefix portion is defined a prefix value and the remainder portion is defined by a remainder value;
- wherein the K-mers are stored in a data structure defined by a plurality of slots,
- wherein each slot has an address and stores data, the address is defined by the prefix value of each K-mer, and the slot stores the remainder value,
- wherein indexing the K-mers comprises Fibonacci hashing to compute the prefix value and the remainder value of each K-mer;
- wherein indexing the K-mers comprises linear hash-collision resolution when a slot is already filled by a K-mer sharing the same prefix value.
A data structure for storing genetic or genomic data, comprising:
- a plurality of memory slots and a plurality of K-mers, wherein each K-mer represents a sequence segment of a nucleotide sequence, wherein each sequence segment comprises a prefix portion and a remainder portion, wherein the prefix portion is defined a prefix value and the remainder portion is defined by a remainder value, wherein each memory slot is associated with an address, wherein each K-mer is stored in a specific memory slot based on the prefix value of the K-mer, and the remainder value is stored in the memory slot, wherein the prefix value and the remainder value of each K-mer are yielded by a Fibonacci hash function, wherein the remainder value of a subset of K-mers comprise an increment or a decrement corresponding to a linear hash-collision resolution.
A method to identify genomic events, comprising:
- accessing a data structure, wherein the data structure comprises a plurality of memory slots and a plurality of K-mers, wherein each K-mer represents a sequence segment of a nucleotide sequence, wherein each sequence segment comprises a prefix portion and a remainder portion, wherein the prefix portion is defined a prefix value and the remainder portion is defined by a remainder value, wherein each memory slot is associated with an address, wherein each K-mer is stored in a specific memory slot based on an integer value of the prefix value of the K-mer, and the remainder value is stored in the memory slot, wherein the prefix value and the remainder value of each K-mer are yielded by a Fibonacci hash function, wherein the remainder value of a subset of K-mers comprise an increment or a decrement corresponding to a linear hash-collision resolution;
- querying the data structure to obtain a set of K-mers associated with a genomic event;
- and
- outputting the set of K-mers associated with the genomic event.
Dependencies are inferred from the claim text.