Back to results
US 12,002,548 B2Granted
Method for genome sequence alignment and apparatus thereof
AssigneeElectronics and Telecommunications Research Institute
InventorsChangdae Kim, Kwang-Won Koh, Kang Ho Kim
Life of this patent
Estimating the term…
Abstract
An apparatus for genome sequence alignment attempts a search for the hash tables to align a target nucleotide sequence, from a hash table having a large seed size to a hash table having a small seed size, and when there is at least one matched seed to the target nucleotide sequence on a hash table, aligns the target nucleotide sequence by using candidate positions from the hash table without further hash table searching.
Claims6
A computer-implemented method for genome sequence alignment based on hash tables in an apparatus for genome sequence alignment, the method comprising:
- generating a plurality of hash tables of different seed sizes, wherein generating the plurality of hash tables comprises:
- extracting seeds of a first seed size from a reference nucleotide sequence,
- generating a hash table of the first seed size by calculating a hash value of each seed among the extracted seeds of the first seed size using a hash function,
- extracting seeds of a second seed size from the reference nucleotide sequence,
- generating a hash table of the second seed size by calculating a hash value of each seed among the extracted seeds of the second seed size using the hash function,
- generating reads of the first seed size of a target nucleotide sequence;
- calculating a hash value of each read among the reads of the first seed size using the hash function;
- determining the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size, by comparing the hash value of each read and a hash value of each seed in the hash table of the first seed size;
- when the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size has failed, generating reads of the second seed size of a target nucleotide sequence, wherein the second seed size is smaller than the first seed size;
- calculating a hash value of each read among the reads of the second seed size using the hash function;
- determining the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the second seed size, by comparing the hash value of each read among the reads of the second seed size and a hash value of each seed in the hash table of the second seed size;
- and
- controlling the apparatus for genome sequence alignment to enable terminating of generating reads of the target nucleotide sequence and calculating hash values of reads, based on the determining of the success or failure of the genetic sequence alignment.
10 more elements
An apparatus for genome sequence alignment based on hash tables, the apparatus comprising:
- a processor;
- and
- a memory that stores instructions and a plurality of hash tables having different seed sizes, wherein the instructions when executed by the processor, cause the apparatus to:
- generating a plurality of hash tables of different seed sizes by:
- extracting seeds of a first seed size from a reference nucleotide sequence,
- generating a hash table of the first seed size by calculating a hash value of each seed among the extracted seeds of the first seed size using a hash function,
- extracting seeds of a second seed size from the reference nucleotide sequence, and
- generating a hash table of the second seed size by calculating a hash value of each seed among the extracted seeds of the second seed size using the hash function,
- generate reads of the first seed size of a target nucleotide sequence;
- calculate a hash value of each read among the reads of the first seed size using the hash function;
- determine the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size, by comparing the hash value of each read and a hash value of each seed in the hash table of the first seed size;
- when the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size has failed, generate reads of the second seed size of a target nucleotide sequence, wherein the second seed size is smaller than the first seed size;
- calculate a hash value of each read among the reads of the second seed size using the hash function;
- determine the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the second seed size, by comparing the hash value of each read among the reads of the second seed size and a hash value of each seed in the hash table of the second seed size;
- and
- enable terminating of generating reads of the target nucleotide sequence and calculating hash values of reads, based on the determining of the success or failure of the genetic sequence alignment.
13 more elements
Dependencies are inferred from the claim text.