Sequence information signal processor for local and global string comparisons

• US 5,632,041 A
• Filed: 11/18/1993
• Issued: 05/20/1997
• Est. Priority Date: 05/02/1990
• Status: Expired due to Fees

• Current Assignee: California Institute of Technology, University of Southern California
• Original Assignee: California Institute of Technology
• Inventors: Peterson, John C., Waterman, Michael S., Hunkapillar, Timothy J., Chow, Edward T.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US08/154,633
• Time in Patent Office: 1,279 Days
• Field of Search: 395/375, 395/800, 395/425, 395/24, 395/2.48, 395/21
• US Class Current: 712/16
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2043 where the redundant components share a common memory address space
• CPC Class Codes: G06F 11/2051 in regular structures
• CPC Class Codes: G06F 11/2236 to test CPU or processors
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

A sequence information signal processing integrated circuit chip designed to perform high speed calculation of a dynamic programming algorithm based upon the algorithm defined by Waterman and Smith. The signal processing chip of the present invention is designed to be a building block of a linear systolic array, the performance of which can be increased by connecting additional sequence information signal processing chips to the array. The chip provides a high speed, low cost linear array processor that can locate highly similar global sequences or segments thereof such as contiguous subsequences from two different DNA or protein sequences. The chip is implemented in a preferred embodiment using CMOS VLSI technology to provide the equivalent of about 400,000 transistors or 100,000 gates. Each chip provides 16 processing elements, and is designed to provide 16 bit, two'"'"'s compliment operation for maximum score precision of between -32,768 and +32,767. It is designed to provide a comparison between sequences as long as 4,194,304 elements without external software and between sequences of unlimited numbers of elements with the aid of external software.

Each sequence can be assigned different deletion and insertion weight functions. Each processor is provided with a similarity measure device which is independently variable. Thus, each processor can contribute to maximum value score calculation using a different similarity measure.

Claims

1. A computational apparatus for dynamically comparing against one another a first element sequence having a first number of elements and a second element sequence having a second number of elements by providing a plurality of scores indicative of the degree of similarity of respective segments of the sequences;

the apparatus comprising;

a plurality of processors segregated into distinct groups of processors, each such processor having means for generating respective ones of said scores for said segments ending at selected elements of said respective sequences, said means for generating said scores including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion;

means for determining the maximum one of said processor-generated scores and the ending elements of segments at which such maximum score occurs; and

means in each of said groups for establishing a threshold score and for ignoring all said scores below said threshold score, the threshold score in each said group being independently selected from the threshold score in all of the remaining groups.

2. The apparatus recited in claim 1 further comprising means for basing said scores on similarity measures of said ending elements, each said processor having a selected similarity measure associated with it.

3. The apparatus recited in claim 2 wherein said basing means permits independently controllable similarity measures in said respective processors.

4. The apparatus recited in claim 1 further comprising means for basing said scores on whether or not said respective segments differ from one another as a result of one or more deletions and insertions in said segments, wherein said basing is a function of the occurrence and length of such deletions and insertions.

5. The apparatus recited in claim 4 wherein said basing means permits differences in score effects between deletions and insertions in one segment and deletions and insertions in the other second segment.

6. The apparatus recited in claim 1 further comprising means controlling said processors for simultaneous generation of said scores in said plurality of processors, each of said simultaneously-generated scores being for segments ending at different ones of said selected elements.

7. The apparatus recited in claim 1 wherein said processors are arranged in a linear systolic array.

8. The apparatus recited in claim 7 further comprising means wherein each processor during sequence comparing, is associated with a respective element a_i of sequence A and generates a score for each respective element b_j of sequence B.

9. The apparatus recited in claim 7 further comprising means for interconnecting said array of processors to additional arrays of processors.

10. The apparatus recited in claim 1 wherein each said group of processors.

11. The apparatus recited in claim 1 further comprising memory means for storing said maximum scores.

12. The apparatus recited in claim 1 further comprising clock means for synchronizing said processors.

13. An apparatus of the type having a plurality of VLSI circuit devices for receiving signals representative of at least two data sequences A and B, where A=a₁, a₂ . . . a_n B=b₁, b₂ . . . b_m, and for dynamically comparing sequences A and B by generating score signals representative of the degree to which segments of A and B are similar;

each such device comprising;

a plurality of processors, each such processor having means for periodically generating respective ones of said scores for said segments ending at selected elements of said respective sequences, said means for periodically generating said scores including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion; and

means for determining the maximum one of said processor-generated scores and the ending elements of segments at which such maximum score occurs;

each said device having a distinct selected score threshold which can be different from the score thresholds in the remaining devices.

14. The apparatus recited in claim 13, each said device further comprising means for establishing said threshold score and for ignoring all said scores below said threshold score.

15. The apparatus recited in claim 13, each said device further comprising means for basing said scores on similarity measures of said ending elements, each said device having independent basing means associated with each said processor.

16. The apparatus recited in claim 15 wherein said basing means permits independently controllable similarity measures in said respective processors.

17. The apparatus recited in claim 13 further comprising means for basing said scores on whether or not said respective segments differ from one another as a result of one or more deletions and insertions in said segments, wherein said basing is a function of the occurrence and length of such deletions and insertions.

18. The apparatus recited in claim 17 wherein said basing means permits differences in score effects between deletions and insertions in one segment and deletions and insertions in the other second segment.

19. The apparatus recited in claim 13 further comprising means controlling said processors for simultaneous generation of said scores in said plurality of processors, each of said simultaneously-generated scores being for segments ending at different ones of said selected elements.

20. The apparatus recited in claim 13 wherein said processors are arranged in a linear systolic array.

21. The apparatus recited in claim 20 further comprising means wherein each processor during sequence comparing, is associated with a respective element a_i of sequence A and generates a score for each respective element b_j of sequence B.

22. The apparatus recited in claim 21 further comprising means for interconnecting said array of processors to additional arrays of processors.

23. The apparatus recited in claim 13 further comprising memory means for storing said maximum score.

24. The apparatus recited in claim 13 further comprising clock means for synchronizing said processors.

25. An integrated circuit apparatus for dynamically comparing against one another a first element sequence having a first number of elements and a second element sequence having a second number of elements by providing a plurality of scores indicative of the degree of similarity of the sequences;

the apparatus comprising;

a plurality of processors, each such processor having means for generating respective ones of said scores for segments ending at selected elements of said respective sequences, said means for generating said scores including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion;

means for determining the maximum one of said processor-generated scores and the ending elements at which such maximum score occurs;

each said processor having a similarity measuring memory which is independent of the similarity measuring memories of all of the remaining processors whereby each processor contributes to said maximum score determining means using an independent measure of similarity.

26. The apparatus recited in claim 25 further comprising means for establishing a threshold score and for ignoring all said scores below said threshold score.

27. The apparatus recited in claim 25 further comprising means for basing said scores on whether or not said respective sequences differ from one another as a result of one or more deletions and insertions in said sequences, wherein said basing is a function of the occurrence and length of such deletions and insertions.

28. The apparatus recited in claim 27 wherein said basing means permits differences in score effects between deletions and insertions in one sequence and deletions and insertions in the other sequence.

29. The apparatus recited in claim 25 further comprising means controlling said processors for simultaneous generation of said scores in said plurality of processors, each of said simultaneously-generated scores being for segments ending at different ones of said selected elements.

30. The apparatus recited in claim 25 wherein said processors are arranged in a linear systolic array.

31. The apparatus recited in claim 30 further comprising means wherein each processor during sequence comparing, is associated with a respective element a_i of sequence A and generates a score for each respective element b_j of sequence B.

32. The apparatus recited in claim 25 wherein said processors and said determining means are all located on a unitary integrated circuit device.

33. The apparatus recited in claim 30 further comprising means for interconnecting said array of processors to additional arrays of processors.

34. The apparatus recited in claim 25 further comprising memory means for storing said maximum score.

35. The apparatus recited in claim 25 further comprising clock means for synchronizing said processors.

36. An electronic system for the dynamic comparison of a first sequence having a first number of character elements with a second sequence having a second number of character elements, the system comprising:

a plurality of data processors arranged in a series with each data processor being coupled to the next subsequent data processor in said series;

means for storing representations of said first sequence of character elements in said series of data processors, with each character element being associated with a respective one of said data processors, a series of discrete independently variable digital similarity tables stored in a memory device associated respectively with each data processor and character elements included in said first sequence of character elements;

said series of data processors including shift registers for storing representations of said second sequence of character elements, with one of said second sequence of character elements being associated with each data processor, and means for stepping said representations of said second sequence of character elements along said shift register, from one data processor to the next, along said series of data processors;

the similarity tables stored in said data processors providing digital values for each pattern of representations of said second series of character elements in said shift registers; and

means for determining the level of correspondence between said first and second sequence of character elements from said digital values, whereby each said data processor can contribute to said level of correspondence based upon a unique similarity table stored in a corresponding memory device, said means for determining the level of correspondence between said first and second sequences including means for processing responsive to insertion of an additional element into one of said first and second sequences during said dynamic comparison a signal indicative of said additional element insertion.

37. The system recited in claim 36 further comprising a clock for synchronizing the operation of said data processor.

38. The system recited in claim 36 further comprising means for manifesting said level of correspondence as scores corresponding to each pair of characters of said first and second sequences.

39. The system recited in claim 38 further comprising means for determining the maximum such score and for identifying the pair of characters corresponding to said maximum score.

40. A multiprocessor apparatus for dynamically comparing against one another a first sequence having a first number of elements and a second sequence having a second number of elements comprising:

a plurality of computational processors arranged in an interconnected serial array;

each such processor being selectively associated with an element of said first sequence of elements;

means for serially propagating said second sequence of elements through said processors; and

means for generating a measure of the similarity of said sequences and alternatively for element segments thereof at each processor for each processor'"'"'s combination of elements from said first and second sequences substantially as said second sequence elements are propagated through said processors, said means for generating said measure of similarity including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion;

means for identifying the respective elements of said first and second sequences for which said measure represents the greatest degree of such similarity;

means for establishing a threshold measure and for ignoring all said measures below said threshold measure;

means for storing all said measures above said threshold measure and for automatically stopping said propagating of said second sequence of elements through said processors when a selected number of said measures are stored.

41. The apparatus recited in claim 40 further comprising means for basing said measure on similarity measures of each processor'"'"'s elements.

42. The apparatus recited in claim 40 further comprising means for basing said measures on whether or not said respective segments differ from one another as a result of one or more deletions in said segments.

43. The apparatus recited in claim 42 wherein said basing means permits differences in score effects between deletions in one segment and deletions in the other second segment.

44. The apparatus recited in claim 40 wherein all of said processors, said propagating means and said generating means are located on a unitary integrated circuit device.

45. The apparatus recited in claim 40 further comprising means for interconnecting said array of processors to additional arrays of processors.

46. The apparatus recited in claim 40 further comprising clock means for synchronizing said processors.

47. An integrated circuit apparatus for dynamically comparing at least one element sequence against a plurality of other element sequences by providing a plurality of scores indicative of the degree of similarity of respective segments of the one element sequence and the other element sequence;

the apparatus comprising;

a plurality of processors, each such processor having means for generating respective ones of said scores for said segments ending at selected elements of said respective sequences, said means for generating said scores including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion; and

means for determining the maximum ones of said processor generated scores for each of said other element sequences and the ending elements of segments at which such maximum scores occur;

each said processor comprising a memory device for storing a similarity table upon which each said score is based, each such table being independently variable from all other such tables.

48. A sequence information signal processing apparatus for dynamically comparing against one another a first sequence having a first number of elements and a second sequence having a second number of elements comprising a plurality of computational processors arranged in an interconnected serial array;

each such processor being selectively associated with an element of said first sequence of elements;

means for serially propagating said second sequence of elements through said processors; and

means for generating a measure of similarity of said sequences and for identifying the respective elements of said sequences for which a maximum measure of similarity occurs, said means for generating said measure of similarity including means for processing responsive to insertion of an additional element into one of said sequences during said dynamic comparison a signal indicative of said additional element insertion;

wherein said processors are arranged in discrete, serially interconnected blocks of processors and wherein said apparatus further comprises means for providing one such maximum measure in each said block, means for comparing the maximum measures of all such blocks and means for automatically resetting the maximum measure in each said block to zero before such maximum measure is compared with the maximum measure of a subsequent block when said maximum measure exceeds a selected measure.