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

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

doi:10.1093/nar/12.1Part2.751

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 journal › Article › peer-review

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 language	English (US)
Pages (from-to)	751-766
Number of pages	16
Journal	Nucleic acids research
Volume	12
Issue number	1 PART2
DOIs	https://doi.org/10.1093/nar/12.1Part2.751
State	Published - Jan 11 1984
Externally published	Yes

ASJC Scopus subject areas

Genetics

Access to Document

10.1093/nar/12.1Part2.751

Cite this

@article{1621891c8eed4d9d866a6df8aac0072e,

title = "The diagonal-traverse homology search algorithm for locating similarities between two sequences",

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.",

author = "White, {C. Thomas} and Hardies, {Stephen C.} and Hutchison, {Clyde A.} and Edgell, {Marshall H.}",

year = "1984",

month = jan,

day = "11",

doi = "10.1093/nar/12.1Part2.751",

language = "English (US)",

volume = "12",

pages = "751--766",

journal = "Nucleic Acids Research",

issn = "0305-1048",

publisher = "Oxford University Press",

number = "1 PART2",

}

TY - JOUR

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

AU - White, C. Thomas

AU - Hardies, Stephen C.

AU - Hutchison, Clyde A.

AU - Edgell, Marshall H.

PY - 1984/1/11

Y1 - 1984/1/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021760103&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021760103&partnerID=8YFLogxK

U2 - 10.1093/nar/12.1Part2.751

DO - 10.1093/nar/12.1Part2.751

M3 - Article

C2 - 6320108

AN - SCOPUS:0021760103

SN - 0305-1048

VL - 12

SP - 751

EP - 766

JO - Nucleic Acids Research

JF - Nucleic Acids Research

IS - 1 PART2

ER -

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

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this