An efficient code searching for sequence homology and DNA duplication

This paper presents a very simple and efficient algorithm that searches for sequence homology and gene duplication. The code finds the best alignment of two, short or long, sequences without having to specify how many unmatched bases are allowed to be looped out. Following Needleman & Wunsch (1970), Sellers (1974), Sankoff (1972) and Smith, Waterman & Fitch (1981) gap constraints are incorporated into the program and may be employed. The availability of such a fast computer code enables detection of homologous genes which may fulfill a different function at present, but have arisen from a common gene-ancestor. The code is extremely fast and runs in O(n3/2) units of time. It was applied to the phi X174 sequence.