Patent US5632041A successfully refreshed from Google Patents.
US5632041A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sequence information signal processor for local and global string comparisons
Assignee: California Institute of Technology
•
Filing: 1993-11-18
•
Granted: 1997-05-20
•
Expires: 2013-11-18
Abstract
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.
Inventors
- 👤 John C. Peterson
- 👤 Edward T. Chow
- 👤 Michael S. Waterman
- 👤 Timothy J. Hunkapillar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 15:18
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/202; G06F11/2023; G06F11/2028; G06F11/2051; G06F17/00; G06F17/10; G06F7/00; G06F7/02; G06F11/2035; G06F11/2043; G06F11/22; G06F11/2205; G06F11/2236; G06F2201/00; G06F2201/83
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
182 words
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.
Claim 2
Dependent Claim
182 words
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.
Claim 3
Dependent Claim
31 words
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.
Claim 4
Dependent Claim
19 words
The apparatus recited in claim 2 wherein said basing means permits independently controllable similarity measures in said respective processors.
Claim 5
Dependent Claim
53 words
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.
Claim 6
Dependent Claim
31 words
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.
Claim 7
Dependent Claim
39 words
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.
Claim 8
Dependent Claim
16 words
The apparatus recited in claim 1 wherein said processors are arranged in a linear systolic array.
Claim 9
Dependent Claim
39 words
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.
Claim 10
Dependent Claim
20 words
The apparatus recited in claim 7 further comprising means for interconnecting said array of processors to additional arrays of processors.
Claim 11
Dependent Claim
12 words
The apparatus recited in claim 1 wherein each said group of processors.
Claim 12
Dependent Claim
15 words
The apparatus recited in claim 1 further comprising memory means for storing said maximum scores.
Claim 13
Dependent Claim
14 words
The apparatus recited in claim 1 further comprising clock means for synchronizing said processors.
Claim 14
Independent Claim
183 words
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 1 , a 2 . . . a n B=b 1 , b 2 . . . 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.
Claim 15
Independent Claim
183 words
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 1 , a 2 . . . a n B=b 1 , b 2 . . . 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.
Claim 16
Dependent Claim
27 words
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.
Claim 17
Dependent Claim
35 words
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.
Claim 18
Dependent Claim
19 words
The apparatus recited in claim 15 wherein said basing means permits independently controllable similarity measures in said respective processors.
Claim 19
Dependent Claim
53 words
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.
Claim 20
Dependent Claim
31 words
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.
Claim 21
Dependent Claim
39 words
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.
Claim 22
Dependent Claim
16 words
The apparatus recited in claim 13 wherein said processors are arranged in a linear systolic array.
Claim 23
Dependent Claim
39 words
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.
Claim 24
Dependent Claim
20 words
The apparatus recited in claim 21 further comprising means for interconnecting said array of processors to additional arrays of processors.
Claim 25
Dependent Claim
15 words
The apparatus recited in claim 13 further comprising memory means for storing said maximum score.
Claim 26
Dependent Claim
14 words
The apparatus recited in claim 13 further comprising clock means for synchronizing said processors.
Claim 27
Dependent Claim
167 words
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.
Claim 28
Dependent Claim
167 words
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.
Claim 29
Dependent Claim
24 words
The apparatus recited in claim 25 further comprising means for establishing a threshold score and for ignoring all said scores below said threshold score.
Claim 30
Dependent Claim
53 words
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.
Claim 31
Dependent Claim
30 words
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.
Claim 32
Dependent Claim
39 words
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.
Claim 33
Dependent Claim
16 words
The apparatus recited in claim 25 wherein said processors are arranged in a linear systolic array.
Claim 34
Dependent Claim
39 words
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.
Claim 35
Dependent Claim
22 words
The apparatus recited in claim 25 wherein said processors and said determining means are all located on a unitary integrated circuit device.
Claim 36
Dependent Claim
20 words
The apparatus recited in claim 30 further comprising means for interconnecting said array of processors to additional arrays of processors.
Claim 37
Dependent Claim
15 words
The apparatus recited in claim 25 further comprising memory means for storing said maximum score.
Claim 38
Dependent Claim
14 words
The apparatus recited in claim 25 further comprising clock means for synchronizing said processors.
Claim 39
Dependent Claim
298 words
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.
Claim 40
Dependent Claim
298 words
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.
Claim 41
Dependent Claim
18 words
The system recited in claim 36 further comprising a clock for synchronizing the operation of said data processor.
Claim 42
Dependent Claim
29 words
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.
Claim 43
Dependent Claim
27 words
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.
Claim 44
Dependent Claim
220 words
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.
Claim 45
Dependent Claim
220 words
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.
Claim 46
Dependent Claim
20 words
The apparatus recited in claim 40 further comprising means for basing said measure on similarity measures of each processor's elements.
Claim 47
Dependent Claim
35 words
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.
Claim 48
Dependent Claim
27 words
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.
Claim 49
Dependent Claim
26 words
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.
Claim 50
Dependent Claim
20 words
The apparatus recited in claim 40 further comprising means for interconnecting said array of processors to additional arrays of processors.
Claim 51
Dependent Claim
14 words
The apparatus recited in claim 40 further comprising clock means for synchronizing said processors.
Claim 52
Dependent Claim
169 words
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.
Claim 53
Dependent Claim
169 words
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.
Claim 54
Dependent Claim
209 words
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.
Claim 55
Dependent Claim
209 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-19 | 2000-11-18 | 2001-05-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-19 | 2004-11-18 | 2005-05-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-19 | 2008-11-18 | 2009-05-20 | $7700.00 | Window Closed / Lapsed |