Settling the Intractability of Multiple Alignment
2006 (English)In: Journal of Computational Biology, ISSN 1066-5277, E-ISSN 1557-8666, Vol. 13, no 7, 1323-1339 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2006. Vol. 13, no 7, 1323-1339 p.
multiple alignment, NP-hard, SP-score, star alignment, tree alignment, consensus patterns, substring parsimony
IdentifiersURN: urn:nbn:se:kth:diva-6352ISI: 000241414800004ScopusID: 2-s2.0-33846197539OAI: oai:DiVA.org:kth-6352DiVA: diva2:11041
QC 201101212006-11-152006-11-152011-01-21Bibliographically approved