The diagonal-traverse homology search algorithm for locating similarities between two sequences

C. Thomas White, Stephen C. Hardies, Clyde A. Hutchison, Marshall H. Edgell

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

We present a fast computer algorithm for finding homology between two DNA sequences. It generates a two-dimensional display in which a diagonal string of dots represents a stretch of homology between the two sequences. Our algorithm performs the search very rapidly, and has no internal data storage requirement except for the sequences themselves. These characteristics make it particularly well suited for execution on microcomputers. Without slowing execution, the matching criterion can be that a specified fraction of contiguous bases must be identical. Even with gapped sequences, we have found large search windows to be surprisingly good for detecting poor homologies with nearly complete background suppression. A diagonal search pattern is used that reports the finds in a compact and logically ordered form. A simple and rapid plotting algorithm for unsophisticated printers is also reported.

Original languageEnglish (US)
Pages (from-to)751-766
Number of pages16
JournalNucleic acids research
Volume12
Issue number1 PART2
DOIs
Publication statusPublished - Jan 11 1984

    Fingerprint

ASJC Scopus subject areas

  • Genetics

Cite this