The complexity of multiple sequence alignment with SP-score that is a metric

DOI10.1016/S0304-3975(99)00324-2zbMath0972.68092MaRDI QIDQ5941270

Paola Bonizzoni, G. D. Vedova

Publication date: 20 August 2001

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

zbMATH Keywords

multiple sequence alignmentintractabilitySP-score

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (10)

Constrained pairwise and center-star sequences alignment problems ⋮ A computational model for RNA multiple structural alignment ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Non-approximability of weighted multiple sequence alignment. ⋮ Exact mean computation in dynamic time warping spaces ⋮ Constrained sequence alignment: A general model and the hardness results ⋮ On the kernelization complexity of string problems ⋮ Partially local multi-way alignments ⋮ Optimal global alignment of signals by maximization of Pearson correlation ⋮ Compositional properties of alignments

Cites Work

• Unnamed Item
• Optimization, approximation, and complexity classes
• A survey of multiple sequence comparison methods
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment
• The Multiple Sequence Alignment Problem in Biology
• Mapping the genome

This page was built for publication: The complexity of multiple sequence alignment with SP-score that is a metric