# US 8,280,640 B2 · System and method for pattern recognition in sequential data

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

- Number: US 8,280,640 B2
- Document ID: US8280640B2
- Status: Granted
- Kind: B2
- Application number: 10/916,370
- Filed: 2004-08-11
- Published: 2005-08-25
- Granted: 2012-10-02
- Earliest claimed: 2003-08-11
- Assignees: Eloret Corporation
- Inventors: Eugene Levin; Martha Elizabeth Corey
- Web page: https://patentgrep.com/patent/US8280640B2

## CPC

- G06F 7/02: Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence)
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 30/10: Sequence alignment; Homology search
- G06F 2207/025: String search, i.e. pattern matching, e.g. find identical word or best match in a string
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY

## Abstract

The present invention is based on the encoding of sequential data or sequences in a novel manner that permits efficient storage and processing of sequential data, as well as methods for searching sequences or databases of sequences. The methods and systems of the current invention may be adapted broadly to various fields of application and to a variety of sequences types. For example, the current invention has broad application including to the fields of bioinformatics, molecular biology, pharmacogenomics, phonetic sequences, lexicographic sequences, signal analysis, game playing, law enforcement, biometrics, medical diagnosis, equipment maintenance and micro-array data analysis.

## Claims

### Claim 1

A method of comparing sequential data using a computer system, comprising:
(a) providing to a first storage device a target sequence having at least a first binary string n bits in length and a second binary string n bits in length, the second binary string aligned with the first binary string to form n groups of aligned bits, each group of aligned bits including one bit from the first string and the corresponding bit from the second string, each group of aligned bits defining a component member of the target sequence;
(b) providing to a second storage device a query sequence having at least a first binary string m bits in length (m≦n) and a second binary string m bits in length, the second binary string aligned with the first binary string to form m groups of aligned bits, each group of aligned bits including one bit from the first string and the corresponding bit from the second string, each group of aligned bits defining a component member of the query sequence;
(c) comparing the m bits contained in the first binary string of the query sequence against the n bits contained in the first binary string of the target sequence to determine first matches between the first binary string of the query sequence and the first binary string of the target sequence, each first match, if any, defining an m-bit segment having a match position m bits in length in the first binary string of the target sequence, and, for each first match, if any, associating the match position in the first binary string of the target sequence to the corresponding m-bit segment of the second binary string of the target sequence;
(d) for each first match, if any, comparing the m bits contained in the second binary string of the query sequence against m-bit segments of the second binary string of the target sequence corresponding to such first match to determine second matches, if any, between the target and query sequences;
(e) generating an indication of matches, if any, between one or more of the binary strings of the target sequence and the binary strings of the query sequence and outputting said indication to a user interface.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
(a) for each second match, if any, associating the match position in the second binary string of the target sequence to corresponding m-bit segments of a third binary string of the target sequence; and
(b) comparing the m bits contained in a third binary string of the query sequence against one or more of the m-bit segments of the third binary string of the target sequence to determine third matches, if any, between the target and query sequences.

### Claim 3 (depends on 1)

The method of claim 1, wherein said indication of matches includes information identifying at least one of the first matches.

### Claim 4 (depends on 1)

The method of claim 1, wherein said indication of matches includes information identifying at least one of the first matches and at least one of the second matches.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first and second storage devices include random access memory locations of said computer system.

### Claim 6 (depends on 1)

The method of claim 1, wherein said user interface is connected to said computer system through a communications interface.

### Claim 7 (depends on 1)

The method of claim 1, wherein said component members of said target and query sequences represent component members of amino acid sequences.

### Claim 8 (depends on 1)

The method of claim 1, wherein said component members of said target and query sequences represent component members of nucleotide sequences.

### Claim 9 (depends on 1)

The method of claim 1, wherein the method further comprises the step of terminating all subsequent comparison steps if no first match is found, generating an indication of no first match being found and outputting said indication to a user interface.

### Claim 10 (depends on 1)

The method of claim 1, wherein the method comprises the step of ordering said m-bit segments of the second binary string of the target sequence into an auxiliary binary string of length N*m (where N equals said number of first matches) and comparing the m bits contained in the second binary string of the query sequence against the auxiliary binary string to determine second matches, if any, between the target and query sequences.

### Claim 11 (depends on 1)

The method of claim 1, further comprising the step of comparing the m bits contained in the first binary string of the query sequence against the n bits contained in the first binary string of the target sequence to determine partial matches between the first binary string of the query sequence and the first binary string of the target sequence.

### Claim 12 (depends on 1)

The method of claim 1, wherein said first matches, if any, include partial matches determined using a subset of the m bits contained in the first binary string of the query sequence.

### Claim 13 (depends on 1)

The method of claim 1, wherein said second matches, if any, include partial matches determined using a subset of the m bits contained in the second binary string of the query sequence.

### Claim 14

An apparatus for comparing sequential data, comprising:
(a) a first digital storage device configured to store a target sequence having at least a first binary string n bits in length and a second binary string n bits in length, the second binary string aligned with the first binary string to form n groups of aligned bits, each group of aligned bits including one bit from the first string and the corresponding bit from the second string, each group of aligned bits defining a component member of the target sequence;
(b) a second digital storage device configured to store a query sequence having at least a first binary string m bits in length (m≦n) and a second binary string m bits in length, the second binary string aligned with the first binary string to form m groups of aligned bits, each group of aligned bits including one bit from the first string and the corresponding bit from the second string, each group of aligned bits defining a component member of the query sequence;
(c) first digital processor configured to compare the m bits contained in the first binary string of the query sequence against the n bits contained in the first binary string of the target sequence to determine first matches between the first binary string of the query sequence and the first binary string of the target sequence, each first match, if any, defining an m-bit segment having a match position m bits in length in the first binary string of the target sequence;
(d) a second digital processor configured to compare the m bits contained in the second binary string of the query sequence against each m-bit segments of the second binary string of the target sequence corresponding to each first match to determine second matches, if any, between the target and query sequences;
(e) a third digital processor configured to generate an indication of matches, if any, between one or more of the binary strings of the target sequence and the binary strings of the query sequence and to output said indication to a user interface.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the first and second digital storage devices include random access memory locations of a computer system.

### Claim 16 (depends on 14)

The apparatus of claim 14, wherein one or more of the first, second and third digital processors is a field programmable gate array.

### Claim 17 (depends on 14)

The apparatus of claim 14, wherein one or more of the first, second and third digital processors is an application specific integrated circuit.

### Claim 18 (depends on 14)

The apparatus of claim 14, further comprising a fourth digital processor configured to generate a score for one or more of said first and second matches, if any, based on the number of identical bits appearing in each said match.
