Fast optimal alignment.

AUTOR(ES)

Fickett, J W

RESUMO

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.

Documentos Relacionados

• Gene recognition via spliced sequence alignment.
• A tool for multiple sequence alignment.
• Sequence comparison by exponentially-damped alignment.
• A signal encoded in vertebrate DNA that influences nucleosome positioning and alignment.
• A measure of the similarity of sets of sequences not requiring sequence alignment.