Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
30 Downloads (Pure)


We prove that the multiple sequence alignment problem with weighted sum-of-pairs score is APX-hard for arbitrary metric scoring functions over the binary alphabet. This holds even when the weights are restricted to zero and one.
Original languageEnglish
Pages (from-to)389-395
Number of pages7
JournalInformation processing letters
Issue number3
Publication statusPublished - 2005


  • EWI-21267
  • Sum-of-pairs score
  • Computational biology
  • Multiple sequence alignment
  • IR-79424
  • Algorithms
  • Approximation hardness


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

Cite this