Open AccessFast optimal alignment
Author(s) -
James W. Fickett
Publication year - 1984
Publication title -
nucleic acids research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 9.008
H-Index - 537
eISSN - 1362-4954
pISSN - 0305-1048
DOI - 10.1093/nar/12.1part1.175
Subject(s) - computation , multiple sequence alignment , matrix (chemical analysis) , sequence (biology) , sequence alignment , fraction (chemistry) , algorithm , biology , alignment free sequence analysis , computer science , genetics , peptide sequence , materials science , chemistry , organic chemistry , composite material , gene
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.