# US 12,002,548 B2 · Method for genome sequence alignment and apparatus thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,002,548 B2
- Document ID: US12002548B2
- Status: Granted
- Kind: B2
- Application number: 17/070,452
- Filed: 2020-10-14
- Published: 2021-09-16
- Granted: 2024-06-04
- Earliest claimed: 2020-03-11
- Assignees: Electronics and Telecommunications Research Institute
- Applicants: Electronics and Telecommunications Research Institute
- Inventors: Changdae Kim; Kwang-Won Koh; Kang Ho Kim
- Web page: https://patentgrep.com/patent/US12002548B2

## CPC

- G16B 30/10: Sequence alignment; Homology search
- G16B 50/50: Compression of genetic data
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY

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

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the determining the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size includes:
checking whether the hash value of each read matches a hash value of each seed in a hash table of the first seed size;
determining a location of the matched seed as candidate position;
calculating differences by comparing the target nucleotide sequence and the reference genome with respect to each candidate position; and
determining a position of the seed having the smallest difference among the candidate positions having a difference of less than a threshold as a position to be aligned to the target nucleotide sequence.

### Claim 3 (depends on 1)

The method of claim 1, further comprising reporting a genetic sequence alignment failure when there is no matched seed to the target nucleotide sequence on the hash table having the smallest seed size.

### Claim 4

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.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein the instructions when executed by the processor, further cause the apparatus to: report a genetic sequence alignment failure when the genetic sequence alignment of the target nucleotide sequence using the hash table with the smallest seed size fails.

### Claim 6 (depends on 4)

The apparatus of claim 4, wherein when determine the success or failure of the genetic sequence alignment of the target nucleotide sequence using the hash table of the first seed size, the instructions when executed by the processor, further cause the apparatus to: check whether the hash value of each read matches a hash value of each seed in a hash table of the first seed size, determine a location of the matched seed as candidate position, calculate differences by comparing the target nucleotide sequence and the reference genome with respect to each candidate position, and determine a position of the seed having the smallest difference among the candidate positions having a difference of less than a threshold as a position to be aligned to the target nucleotide sequence.