Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Manthey, Bodo

Publication date

January 2005

DOI

10.1016/j.ipl.2005.04.010

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

Extracted data

We use cookies to provide a better user experience.

Data Protection

Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Abstract

Extracted data

Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Abstract

Extracted data

Topics

Related items

Related items

Topics