Method and apparatus for approximate matching of DNA sequences

• US 7,680,790 B2
• Filed: 10/31/2007
• Issued: 03/16/2010
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron Kaplan
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US11/932,321
• Publication Number:
  US 20080133519A1
• Time in Patent Office: 867 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 711/1, 711/111, 711/112, 711/145, 711/172, 709/214
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and device are disclosed for an associative and approximate, analog or digital scanning of databases that allows for the asynchronous accessing of data from a mass storage medium. The invention includes providing dedicated analog and digital circuitry and decision logic at the mass storage medium level for determining a key identifying the data of interest, continuously comparing the key to a signal generated from a reading of the data from the mass storage medium with an approximate or exact matching circuit to determine a pattern match, determining a correlation value between the key and the data as it is read in a continuous fashion, and determining a match based upon a preselected threshold value for the correlation value. The pattern matching technique eliminates any need to compare data based on its intrinsic structure or value, and instead is based on an analog or digital pattern. The key and data may be either analog or digital. This device and method may be provided as part of a stand-alone computer system, embodied in a network attached storage device, or can otherwise be provided as part of a computer LAN or WAN.

Claims

1. A computer-implemented method for determining whether a DNA query sequence is an approximate match to a DNA sequence within a library of DNA sequences, the method comprising:

streaming the DNA sequences of the library through programmable logic that has been loaded with a key, wherein the key corresponds to a DNA query sequence; and

comparing the streaming DNA sequences with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the streaming DNA sequences, wherein the comparing step comprises;

continuously computing a correlation coefficient between the key and a sliding window of the streaming DNA sequences using the programmable logic, and

judging each computed correlation coefficient against a threshold value to thereby identify an approximate match between the key and the streaming DNA sequences.

2. The method of claim 1 wherein the key comprises an analog key as represented by a plurality of samples, and wherein the streaming step comprises sampling an analog read signal of DNA sequences streaming from a database at a high rate, and wherein the comparing step comprises performing the comparing step on the respective samples of the analog key and the DNA sequences.

3. The method of claim 1 wherein the key comprises a digital key.

4. The method of claim 1 wherein the comparing step comprises determining whether any of the approximate matches exist based on an adjustable threshold using the programmable logic.

5. The method of claim 4 further comprising adjusting the threshold to control a degree of approximate matches which is identified as a result of the comparing step such that a forgivable number of residue mismatches may exist between the key and a window of the streaming DNA sequences while still qualifying as an approximate match.

6. A computer-implemented method for determining whether a DNA query sequence is an approximate match to a DNA sequence within a library of DNA sequences, the method comprising:

streaming the DNA sequences of the library through programmable logic that has been loaded with a key, wherein the key corresponds to a DNA query sequence;

comparing the streaming DNA sequences with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the streaming DNA sequences based on an adjustable threshold; and

adjusting the threshold to control a degree of approximate matches which is identified as a result of the comparing step such that a forgivable number of residue mismatches may exist between the key and a window of the streaming DNA sequences while still qualifying as an approximate match.

7. The method of claim 6 wherein the comparing step comprises pattern comparing the streaming DNA sequences with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the streaming DNA sequences.

8. The method of claim 7 wherein the pattern comparing step comprises pattern comparing the streaming DNA sequences with the key using the programmable logic without framing the streaming DNA sequences.

9. The method of claim 6 wherein the adjusting step comprises adjusting the threshold within the programmable logic.

10. The method of claim 6 wherein the key comprises an analog key as represented by a plurality of samples, and wherein the streaming step comprises sampling an analog read signal of DNA sequences streaming from a database at a high rate, and wherein the comparing step comprises performing the comparing step on the respective samples of the analog key and the DNA sequences.

11. The method of claim 6 wherein the key comprises a digital key.

12. The method of claim 6 further comprising:

receiving a search command from a processor that is in communication with the programmable logic; and

providing information to the processor that is indicative of any approximate matches identified as a result of the comparing step.

13. The method of claim 12 further comprising:

determining the key from the search command using the programmable logic.

14. An apparatus for determining whether a DNA query sequence is an approximate match to a DNA sequence that is stored by a mass storage medium as part of a library of DNA sequences, the apparatus comprising:

an approximate matching unit in communication with a mass storage medium, the approximate matching unit comprising programmable logic, the programmable logic being configured to (1) store a key, the key corresponding to a DNA query sequence, (2) receive a stream of DNA sequences from the mass storage medium, (3) continuously compute a correlation coefficient between the key and a sliding window of the received DNA sequences, and (4) judge the computed correlation coefficients against a threshold value to thereby identify whether any approximate matches exist between the key and the received DNA sequences.

15. The apparatus of claim 14 wherein the key comprises an analog key as represented by a plurality of samples, wherein the approximate matching unit is further configured to sample an analog read signal of DNA sequences streaming from the mass storage medium at a high rate, and wherein the programmable logic is further configured to perform its comparison on the respective samples of the analog key and the DNA sequences.

16. The apparatus of claim 14 wherein the key comprises a digital key.

17. An apparatus for determining whether a DNA query sequence is an approximate match to a DNA sequence that is stored by a mass storage medium as part of a library of DNA sequences, the apparatus comprising:

an approximate matching unit in communication with a mass storage medium, the approximate matching unit comprising programmable logic, the programmable logic having a key loaded thereon, wherein the key corresponds to a DNA query sequence, the approximate matching unit being configured to (1) stream the DNA sequences of the library through the programmable logic, (2) compare the streaming DNA sequences with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the streaming DNA sequences based on an adjustable threshold, and (3) adjust the threshold to control a degree of approximate matches which is identified as a result of the comparison operation such that a forgivable number of residue mismatches may exist between the key and a window of the streaming DNA sequences while still qualifying as an approximate match.

18. The apparatus of claim 17 further comprising the mass storage medium directly coupled to the approximate matching unit.

19. The apparatus of claim 18 wherein the mass storage medium comprises a hard disk drive.

20. The apparatus of claim 18 wherein the mass storage medium comprises a bank of hard disk drives.

21. The apparatus of claim 17 wherein the apparatus further comprises a processor and a system bus, the system bus interconnecting the processor with the approximate matching unit, wherein the approximate matching unit is further configured to (1) receive a search command from the processor via the system bus, and (2) provide information to the processor that is indicative of any approximate matches identified as a result of the comparison.

22. The apparatus of claim 21 wherein the programmable logic is further configured to determine the key from the search command.

23. The apparatus of claim 17 wherein the apparatus further comprises a network interface and a system bus, the system bus interconnecting the network interface with the approximate matching unit, wherein the approximate matching unit is further configured to (1) receive a search command from the network interface via the system bus, and (2) provide information to the network interface that is indicative of any approximate matches identified as a result of the comparison.

24. The apparatus of claim 17 wherein the key comprises a digital key.