Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Non-approximability of weighted multiple sequence alignment

Share/Save/Bookmark

Manthey, Bodo (2003) Non-approximability of weighted multiple sequence alignment. Theoretical Computer Science, 296 (1). pp. 179-192. ISSN 0304-3975

[img]PDF
Restricted to UT campus only: Request a copy
175Kb
Abstract:We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be $N P$-complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. Weighted multiple sequence alignment (WMSA) can be approximated within a factor of O(log2n) where n is the number of sequences.

We prove that WMSA alignment is MAX$\mathcal{S N P}$-hard and establish a numerical lower bound on its approximability, namely $\frac{324}{323}-\in $. This lower bound is obtained already for the simple binary weighted case where the weights are restricted to 0 and 1. Furthermore, we show that WMSA and its restriction to binary weights can be approximated to the same degree.
Item Type:Article
Copyright:© 2003 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79419
Official URL:http://dx.doi.org/10.1016/S0304-3975(02)00439-5
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page