Non-approximability of weighted multiple sequence alignment

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)


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(log2n) where n is the number of sequences. We prove that WMSA alignment is MAX$\mathcal{S N P}$-hard and establish a numerical lower bound on its approximability, namely $\frac{324}{323}$$ -\in $. 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.
Original languageEnglish
Pages (from-to)179-192
Number of pages14
JournalTheoretical computer science
Issue number1
Publication statusPublished - 2003


  • Computational biology
  • SP-score
  • Non-approximability
  • Multiple sequence alignment


Dive into the research topics of 'Non-approximability of weighted multiple sequence alignment'. Together they form a unique fingerprint.

Cite this