# Non-approximability of weighted multiple sequence alignment

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

PDF
Restricted to UT campus only : Request a copy 180kB |

Abstract: | We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be -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-hard and establish a numerical lower bound on its approximability, namely . 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: | https://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