On the Complexity of Multiple Sequence Alignment 论文
1994Journal of Computational Biology引用 945
Algorithms and Data CompressionGenome Rearrangement AlgorithmsGenomics and Chromatin Dynamics
摘要
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.