Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Bodo Manthey

doi:10.1016/j.ipl.2005.04.010

Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

96 Downloads (Pure)

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 language	English
Pages (from-to)	389-395
Number of pages	7
Journal	Information processing letters
Volume	95
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2005.04.010
Publication status	Published - 2005

Keywords

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

Access to Document

10.1016/j.ipl.2005.04.010

Manthey2003non-approximabilityAccepted author version, 184 KB

Cite this

@article{67028846f9524d64a9dedb216bc8e298,

title = "Non-approximability of weighted multiple sequence alignment for arbitrary metrics",

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.",

keywords = "EWI-21267, Sum-of-pairs score, Computational biology, Multiple sequence alignment, IR-79424, Algorithms, Approximation hardness",

author = "Bodo Manthey",

year = "2005",

doi = "10.1016/j.ipl.2005.04.010",

language = "English",

volume = "95",

pages = "389--395",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Non-approximability of weighted multiple sequence alignment for arbitrary metrics

AU - Manthey, Bodo

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - EWI-21267

KW - Sum-of-pairs score

KW - Computational biology

KW - Multiple sequence alignment

KW - IR-79424

KW - Algorithms

KW - Approximation hardness

U2 - 10.1016/j.ipl.2005.04.010

DO - 10.1016/j.ipl.2005.04.010

M3 - Article

SN - 0020-0190

VL - 95

SP - 389

EP - 395

JO - Information processing letters

JF - Information processing letters

IS - 3

ER -

Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Abstract

Keywords

Access to Document

Fingerprint

Cite this