Settling the Intractability of Multiple Alignment

Citations Over TimeTop 10% of 2006 papers

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.

Related Papers

• → Generalized Substring Compression(2009)9 cited
• → The Efficient Computation of Complete and Concise Substring Scales with Suffix Trees(2007)10 cited
• → Efficiently Enumerating Substrings with Statistically Significant Frequencies of Locally Optimal Occurrences in Gigantic String(2020)2 cited
• → On Harrison's substring testing technique(1973)4 cited
• → An Efficient Algorithm for Identifying the Most Contributory Substring(2007)