✦ LIBER ✦

Non-approximability of weighted multiple sequence alignment

✍ Scribed by Bodo Manthey

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 167 KB
Volume: 296
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00439-5

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be NP-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(log 2 n) where n is the number of sequences.

We prove that WMSA alignment is MAX SNP-hard and establish a numerical lower bound on its approximability, namely 324 323 -. 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.

📜 SIMILAR VOLUMES

Approximation algorithms for multiple se

Approximation algorithms for multiple sequence alignment

✍ Vineet Bafna; Eugene L. Lawler; Pavel A. Pevzner 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 793 KB

We consider the problem of aligning of k sequences of length n. The cost function is sum of pairs, and satisfies triangle inequality. Earlier results on finding approximation algorithms for this problem are due to Gusfield (1991) who achieved an approximation ratio of 2 -2/k, and Pevzner (1992) who

A novel method of multiple alignment of

A novel method of multiple alignment of biopolymer sequences

✍ L.I. Brodsky; A.L. Drachev; A.M. Leontovich; S.I. Feranchuk 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 983 KB

Hardness of approximation for non-overla

Hardness of approximation for non-overlapping local alignments

✍ Hiroyuki Nagashima; Koichi Yamazaki 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 652 KB

Let S be a set of weighted axis-parallel rectangles such that for each axis no projection of one rectangle properly contains that of another. Two rectangles are in con ict if two projections of the rectangles on an axis intersect. The problem we consider in this paper is to ÿnd a maximum weighted su

Multiplicative approximation of transfer

Multiplicative approximation of transfer functions with frequency weighting

✍ Sang Woo Kim; Brian D.O. Anderson; Anton G. Madievski 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 345 KB

Generation and interpretation of protein

Generation and interpretation of protein sequence and structural multiple alignments

✍ Geoffrey J. Barton; Robert B. Russell; Craig D. Livingstone 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 115 KB

Automatic Discovery of Sub-molecular Seq

Automatic Discovery of Sub-molecular Sequence Domains in Multi-aligned Sequences: A Dynamic Programming Algorithm for Multiple Alignment Segmentation

✍ ERIC POE XING; DENISE M. WOLF; INNA DUBCHAK; SYLVIA SPENGLER; MANFRED ZORN; ILYA 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 446 KB

Automatic identi"cation of sub-structures in multi-aligned sequences is of great importance for e!ective and objective structural/functional domain annotation, phylogenetic treeing and other molecular analyses. We present a segmentation algorithm that optimally partitions a given multi-alignment int