Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235475] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Bilu, Y; Kolodny, R, Faster algorithms for optimal Multiple Sequence Alignment based on pairwise comparisons, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3692 LNBI (2005), pp. 315-327, ISSN 0302-9743 [doi]
    (last updated on 2018/08/14)

    Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of (he best known scheme for finding an optimal alignment, based on dynamic programming, increases exponentially with the number of input sequences. Hence, many heuristics were suggested for the problem. We consider the following version of the MSA problem: In a preprocessing stage pairwisc alignments are found for every pair of sequences. The goal is to find an optimal alignment in which matches arc restricted to positions that wore matched at the preprocessing stage. We present several techniques for making the dynamic programming algorithm more efficient, while still finding an optimal solution under these restrictions. Namely, in our formulation the MSA must conform with pairwisc (local) alignments, and in return can he solved more efficiently. We prove that it stiffices to find an optimal alignment of sequence segments, rallier than single letters, thereby reducing the input size and thus improving the running time. © Springer-Verlag Berlin Heidelberg 2005.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320