Non-approximability of weighted multiple sequence alignment for arbitrary metrics

DOI10.1016/j.ipl.2005.04.010zbMath1185.68833OpenAlexW2029013866MaRDI QIDQ1041795

Bodo Manthey

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.04.010

zbMATH Keywords

algorithmsmultiple sequence alignmentcomputational biologyapproximation hardnesssum-of-pairs score

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Formal languages and automata (68Q45)

Related Items (2)

Inapproximability of maximal strip recovery ⋮ Adaptation of the method of musical composition for solving the multiple sequence alignment problem

Cites Work

• Optimization, approximation, and complexity classes
• Approximation algorithms for multiple sequence alignment
• Non-approximability of weighted multiple sequence alignment.
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Algorithms and Computation
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item

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