Non-approximability of weighted multiple sequence alignment.

DOI10.1016/S0304-3975(02)00439-5zbMath1044.68160OpenAlexW2044622052MaRDI QIDQ1401267

Bodo Manthey

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00439-5

zbMATH Keywords

SP-scoreComputational biologyMultiple sequence alignmentNon-approximability

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (3)

Partially local multi-way alignments ⋮ Compositional properties of alignments ⋮ Non-approximability of weighted multiple sequence alignment for arbitrary metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment
• Proof verification and the hardness of approximation problems
• The Multiple Sequence Alignment Problem in Biology
• Algorithms on Strings, Trees and Sequences
• Gadgets, Approximation, and Linear Programming
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Mapping the genome
• Some optimal inapproximability results
• The complexity of multiple sequence alignment with SP-score that is a metric

This page was built for publication: Non-approximability of weighted multiple sequence alignment.