Advertisement
Published in:
2007 | OriginalPaper | Chapter
A New Dynamic Programming Algorithm for Multiple Sequence Alignment
Authors : Jean-Michel Richer, Vincent Derrien, Jin-Kao Hao
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Multiple sequence alignment (MSA) is one of the most basic and central tasks for many studies in modern biology. In this paper, we present a new progressive alignment algorithm for this very difficult problem. Given two groups A and B of aligned sequences, this algorithm uses Dynamic Programming and the sum-of-pairs objective function to determine an optimal alignment C of A and B. The proposed algorithm has a much lower time complexity compared with a previously published algorithm for the same task [11]. Its performance is extensively assessed on the well-known BAliBase benchmarks and compared with several state-of-the-art MSA tools.