Affordable Access

Fast optimal alignment.

Authors
  • Fickett, J W
Type
Published Article
Journal
Nucleic acids research
Publication Date
Jan 11, 1984
Volume
12
Issue
1 Pt 1
Pages
175–179
Identifiers
PMID: 6694900
Source
Medline
License
Unknown

Abstract

We show how to speed up sequence alignment algorithms of the type introduced by Needleman and Wunsch (and generalized by Sellers and others). Faster alignment algorithms have been introduced, but always at the cost of possibly getting sub-optimal alignments. Our modification results in the optimal alignment still being found, often in 1/10 the usual time. What we do is reorder the computation of the usual alignment matrix so that the optimal alignment is ordinarily found when only a small fraction of the matrix is filled. The number of matrix elements which have to be computed is related to the distance between the sequences being aligned; the better the optimal alignment, the faster the algorithm runs.

Report this publication

Statistics

Seen <100 times