title: Pattern matching of biological sequences with limited storage.
abstract: Existing methods for getting the locally best matched alignments between a pair of biological sequences require O(N2) computational steps and O(N2) storage, where N is the average sequence length. An improved method is presented with which the storage requirement is greatly reduced, while the computational steps remain O(N2). Only a small number of additional steps are required to display any common sub-sequences with similarity scores greater than a given threshold. The aligments found by the algorithm are optimal in the sense that their scores are locally maximal, where each score is a sum of weights given to individual matches/replacements, insertions and deletions involved in the alignment. The algorithm was implemented in C programming language on a personal computer. Data area of 64 kbytes on random access memory and a few hundred kbytes on a disk is sufficient for comparing two protein or nucleic acid sequences of 2500 residues. The programs are particularly valuable when used in combination with fast sequence search programs.
authors.affiliation: Department of Biochemistry, Saitama Cancer Center Research Institute, Japan.
authors.forename: O
authors.initials: O
authors.lastname: Gotoh
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D008838:Microcomputers; D010363:Pattern Recognition, Automated; D012984:Software