A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

✍ Scribed by B. Morgenstern

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 534 KB
• Volume: 15
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/s0893-9659(01)00085-4

✦ Synopsis

In the segment-based approach to sequence alignment. nucleic acid, and protein sequence alignments are constructed from fragments, i.e., from pairs of ungapped segments of the input sequences.

Given a set F of candidate fragments and a weighting function w : F + FL:, the score of an alignment is defined as the sum of weights of the fragments it consists of. and the optimization problem is to find a consistent collection of painuzse dislomt fragments wzth nmxin~um swn of wezghts. Herein, a sparse dynamic programming algorithm is described that solves the pairwise segment-alignment problem in O(L + Nmax ) space where L is the maximum length of t,he input sequences while N ,nax 5 #F holds. With a recently introduced weighting function 1~. small sets F of candidate fragments are sufficient to obtain alignments of high quality. As a result, the proposed algorithm runs in essentially linear space.