Article ID Journal Published Year Pages File Type
10331959 Information Processing Letters 2005 7 Pages PDF
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
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Non-approximability of weighted multiple sequence alignment for arbitrary metrics
Authors
,