Non-approximability of weighted multiple sequence alignment
We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be N P-complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. Weighted multiple sequence alignment (WMSA) can be approximated within a factor of O(log(2)n) where n is the number of sequences. We prove that WMSA alignment is MAX I N P-hard and establish a numerical lower bound on its approximability, namely 324/323 - epsilon. This lower bound is obtained already for the simple binary weighted case where the weights are restricted to 0 and 1. Furthermore, we show that WMSA and its restriction to binary weights can be approximated to the same degree. (C) 2002 Elsevier Science B.V. All rights reserved.
non-approximability multiple sequence alignment sp-score computational biology