AN EFFICIENT ALGORITHM FOR COMPARING 2 PROTEIN SEQUENCES - IMPLEMENTATION FOR MICROCOMPUTERS

An algorithm which can be used on microcomputers to compare two protein sequences is presented. It is based on the algorithm developed by S. B. Needleman & C. D. Wunsch. The original algorithm requires memory space of mn and computing time proportional to mn**2 where m and n are the lengths of the two sequences. Because of these space and time requirements, the algorithm is of limited use on microcomputers. The modified algorithm presented here reduces the computing time proportional to mn and the size of directly accessed memory to 2n, thus making this algorithm usable by many currently available microcomputers. The time saving part of the algorithm will also improve the efficiency of computations on larger computers.