System and method for pattern recognition in sequential data

• US 20050187916A1
• Filed: 08/11/2004
• Published: 08/25/2005
• Est. Priority Date: 08/11/2003
• Status: Active Grant

• Current Assignee: Eloret Corporation
• Original Assignee: Eloret Corporation
• Inventors: Levin, Eugene, Corey, Martha Elizabeth
• Granted Patent: US 8,280,640 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search

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

1. A method of comparing sequential data, comprising:

(a) providing a target sequence and a query sequence, wherein each sequence is encoded as a set of at least two n-bit binary strings wherein each bit of each binary string is aligned with the corresponding bit of the other binary string, thereby identifying n groups of aligned bits, wherein each group of aligned bits defines an identity of a component of the sequence;

(b) determining, by an ordered comparison of the binary strings of the query sequence with corresponding binary strings of the target sequence, a match between the query sequence and the target sequence; and

(c) generating an indication of a match of the target and query sequences based on the ordered comparison.

2. The method of claim 1, wherein less then an entirety of bits in a group of aligned bits defines an aspect of a sequence component.

3. The method of claim 1, wherein the length of the query sequence is different from the length of the target sequence.

4. The method of claim 3, wherein the comparison comprises tandem extension of the shorter sequence and one bit shifts.

5. The method of claim 1, wherein the comparison includes bit-logical summation.

6. The method of claim 1, wherein the comparison comprises a numerical subtraction of two corresponding binary strings.

7. The method of claim 1, wherein the comparison comprises forming a plurality of comparison matrices, each matrix comprising corresponding binary strings for each pair of corresponding binary strings, and combining the matrices using a logical operation capable of identifying common regions.

9. The method of claim 1, wherein the comparison identifies mismatched sequences.

10. The method of claim 1, wherein criteria for a match is selected by a user prior to said ordered comparison.

11. The method of claim 10, wherein results of the comparison are displayed according to criteria selected by a user prior to said ordered comparison.

12. The method of claim 1, wherein the comparison allows introduction of gaps into a sequence of the comparison.

13. The method of claim 1, wherein the match comprises an exact match of sequence components.

14. The method of claim 1, wherein the match comprises a partial match of sequence components.

15. The method of claim 1, wherein the sequences comprise nucleotide sequences.

16. The method of claim 1, wherein the sequences are amino acid sequences.

18. The method of claim 1, wherein the sequences comprise speech pattern sequences.

22. The method of claim 18, wherein the sequences in the database are each associated with a speaker and the comparison allows identification of a speaker.

23. The method of claim 1, wherein the sequences comprise lexicographic sequences.

24. The method of claim 1, wherein the sequences comprise signal analysis sequences.

25. The method of claim 24, wherein the signal analysis sequences comprise electromagnetic, optical, acoustic or seismic data sequences.

35. The method of claim 1, wherein the sequences comprise data derived from a graphic image.

36. The method of claim 35, wherein the graphic image comprises an x-ray image, CAT scan image, MRI image, television image, fingerprint image, or photographic image.

40. The method of claim 36, wherein the data comprises pixel location data.

48. The method of claim 1, wherein the sequences comprise law enforcement related sequence data.

49. The method of claim 48, wherein the law enforcement related sequence data comprises fingerprint data, voiceprint data, or genetic profile data.

55. The method of claim 1, wherein the sequence data comprises gene expression profiles.

8. (canceled)

17. (canceled)

19-21. -21. (canceled)

26-34. -34. (canceled)

37-39. -39. (canceled)

41-47. -47. (canceled)

50-54. -54. (canceled)

56. A method of identifying matching biomolecule sequence data, comprising:

(a) providing a database comprising a target biomolecule sequence and a query biomolecule sequence, wherein each sequence is encoded as a set of at least two n-bit binary strings wherein each bit of each binary string is aligned with the corresponding bit of the other binary string, thereby identifying n groups of aligned bits, wherein each group of aligned bits defines an identity of a component of the sequence;

(b) determining, by an ordered comparison of the binary strings of the query biomolecule sequence with corresponding binary strings of the target biomolecule sequence, a match between the query sequence and the target sequence; and

(c) generating an indication of a match of the target and query biomolecule sequences based on the ordered comparison.

57. The method of claim 56, wherein the sequences comprise nucleotide sequences.

58. The method of claim 57, wherein the nucleotide sequence of the database are each associated with a phenotype.

59. The method of claim 58, wherein the phenotype is indicative of at least one drug metabolism characteristic.

60. The method of claim 59, wherein the results of the comparison comprise a prediction of at least one drug metabolism characteristic associated with the query sequence.

63. The method of claim 56, wherein the sequences are amino acid sequences.

66. The method of claim 56, further comprising scoring mismatching amino acids of the sequences based on the identities of said amino acids.

67. The method of claim 66, wherein said scoring comprises using a scoring matrix.

61-62. -62. (canceled)

64-65. -65. (canceled)

68-69. -69. (canceled)

70. A computer system, comprising:

(a) a searchable database of sequences, wherein each sequence is encoded as a set of at least two n-bit binary strings wherein each bit of each binary string is aligned with the corresponding bit of the other binary string, thereby identifying n groups of aligned bits, wherein each group of aligned bits defines an identity of a component of the sequence; and

(b) a user interface capable of receiving a selection of at least two sequences for determining, by an ordered comparison of corresponding binary strings of the selected sequences, a match between the selected sequences, and displaying the results of the determination.

71-138. -138. (canceled)

139. A method of identifying a region of interest in a sequence, comprising:

(a) providing a query sequence representing a region of interest and a target sequence, wherein each sequence is encoded as a set of at least two n-bit binary strings wherein each bit of each binary string is aligned with the corresponding bit of the other binary string, thereby identifying n groups of aligned bits, wherein each group of aligned bits defines an identity of a component of the sequence;

(b) determining, by an ordered comparison of the binary strings of the query sequence with corresponding binary strings of the target sequence, a match between the query sequence and the target sequence; and

(c) generating an indication of a match of the target and query sequences based on the ordered comparison.

140. The method of 139, further comprising displaying the results of the comparison.

141. The method of 139, wherein the sequences comprise nucleotide sequences, amino acid sequences, phonetic sequences, speech pattern sequences, signal analysis sequences, graphic image sequence data, law enforcement related sequence data, or data related to mechanical equipment status.

142-143. -143. (canceled)

144. A computer-readable data storage medium comprising a plurality of digitally-encoded sequences, wherein each sequence is encoded as a set of at least two n-bit binary strings wherein each bit of each binary string is aligned with the corresponding bit of the other binary string, thereby identifying n groups of aligned bits, wherein each group of aligned bits defines an identity of a component of the sequence.

146. The computer-readable data storage medium of claim 144, wherein a combination of aligned binary string components at an index location defines an identity of a sequence component.

147. The computer-readable data storage medium of claim 144, wherein a combination of less then the entirety of binary string components at an index location defines an aspect of a sequence component.

161. The computer-readable data storage medium of claim 144, wherein the sequences comprise signal analysis sequences.

168. The computer-readable data storage medium of claim 161, wherein the signal analysis sequences comprise continuous sequence data divided into discrete subsets prior to encoding.

184. The computer-readable data storage medium of claim 161, wherein the signal analysis sequences comprise responses to explosions in order to ascertain subsurface features such as oil-bearing dome formations.

145. (canceled)

148-160. -160. (canceled)

162-167. -167. (canceled)

169-183. -183. (canceled)