Sequence information signal processor for local and global string comparisons

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.sub.1, a.sub.2 . . . a.sub.n B=b.sub.1, b.sub.2 . . . b.sub.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.

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.

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.

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.

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.

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.