Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

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 languageUndefined
Pages (from-to)389-395
Number of pages7
JournalInformation processing letters
Volume95
Issue number3
DOIs
Publication statusPublished - 2005

Keywords

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

Cite this