Settling the Intractability of Multiple Alignment
- 1 September 2006
- journal article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 13 (7), 1323-1339
- https://doi.org/10.1089/cmb.2006.13.1323
Abstract
Multiple alignment is a core problem in computational biology that has received much attention over the years, both in the line of heuristics and hardness results. In most expositions of the problem it is referred to as NP-hard and references are given to one of the available hardness results. However, previous to this paper not even the most elementary variation of the problem, multiple alignment under the unit metric, had been proved hard. The aim of this paper is to settle the NP-hardness of the most common variations of multiple alignment. The following variations are shown NP-hard for all metrics over binary or larger alphabets: MULTIPLE ALIGNMENT WITH SP-SCORE, STAR ALIGNMENT, and TREE ALIGNMENT (for a given phylogeny). In addition, NP-hardness results are provided for CONSENSUS PATTERNS and SUBSTRING PARSIMONY.Keywords
This publication has 8 references indexed in Scilit:
- Algorithms for Phylogenetic FootprintingJournal of Computational Biology, 2002
- Finding Motifs Using Random ProjectionsJournal of Computational Biology, 2002
- Computational Complexity of Multiple Sequence Alignment with SP-ScoreJournal of Computational Biology, 2001
- The complexity of multiple sequence alignment with SP-score that is a metricTheoretical Computer Science, 2001
- A More Efficient Approximation Scheme for Tree AlignmentSIAM Journal on Computing, 2000
- Finding similar regions in many stringsPublished by Association for Computing Machinery (ACM) ,1999
- Approximation Algorithms for Tree Alignment with a Given PhylogenyAlgorithmica, 1996
- On the Complexity of Multiple Sequence AlignmentJournal of Computational Biology, 1994