Pattern recognition in genetic sequences

Abstract

This paper announces an algorithm for finding pattern similarities between two given finite sequences. Two portions, one from each sequence, are similar if they are close in the metric space of evolutionary distances. In its most general form the algorithm allows a complete list to be made of all pairs of intervals, one from each of the two given sequences, such that each pair displays a maximum local degree of similarity; if the lengths of the sequences are m and n, then the algorithm requires on the order of mn steps. This result lends itself to detecting similarities by computer between pairs of biological sequences, such as proteins and nucleic acids.