A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences |
| |
Institution: | GSF—National Research Center for Environment and Health Institute of Biomathematics and Biometry Ingolstädter Landstr. 1, 85764 Neuherberg, Germany;Aventis Pharma Limited Rainham Road South, Essex RM10 7XS, U.K. |
| |
Abstract: | 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 → R+0, 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 pairwise disjoint fragments with maximum sum of weights. 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 the input sequences while Nmax ≤ #F holds. With a recently introduced weighting function w, 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|