Abstract
We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. It is shown that the first problem is NP-complete and the second is MAX SNP-hard. The complexity of tree alignment with a given phylogeny is also considered.
Keywords
Multiple sequence alignmentAlignment-free sequence analysisComputational complexity theorySequence (biology)Sequence alignmentTree (set theory)Computer scienceAlgorithmComputational biologyMathematicsTheoretical computer scienceBiologyCombinatoricsGeneticsGenePeptide sequence
Affiliated Institutions
Related Publications
Generating consensus sequences from partialorder multiple sequence alignment graphs
Abstract Motivation: Consensus sequence generation is important in many kinds of sequence analysis ranging from sequence assembly to profile-based iterative search methods. Howe...
Maximum likelihood of evolutionary trees: hardness and approximation
(1) We show that ML under the assumption of molecular clock is still computationally intractable (NP-hard). (2) We show that not only is it computationally intractable to find t...
DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment.
Abstract MOTIVATION: The performance and time complexity of an improved version of the segment-to-segment approach to multiple sequence alignment is discussed. In this approach,...
PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences
Abstract Motivation: To construct a multiple sequence alignment (MSA) of a large number (>∼10 000) of sequences, the calculation of a guide tree with a complexity of O(N2...
Automated generation of heuristics for biological sequence comparison
Abstract Background Exhaustive methods of sequence alignment are accurate but slow, whereas heuristic approaches run quickly, but their complexity makes them more difficult to i...
Publication Info
- Year
- 1994
- Type
- article
- Volume
- 1
- Issue
- 4
- Pages
- 337-348
- Citations
- 931
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
931
OpenAlex
Cite This
Lusheng Wang,
Tao Jiang
(1994).
On the Complexity of Multiple Sequence Alignment.
Journal of Computational Biology
, 1
(4)
, 337-348.
https://doi.org/10.1089/cmb.1994.1.337
Identifiers
- DOI
- 10.1089/cmb.1994.1.337