On the Complexity of Multiple Sequence Alignment
- 1 January 1994
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 1 (4) , 337-348
- https://doi.org/10.1089/cmb.1994.1.337
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
This publication has 12 references indexed in Scilit:
- Efficient methods for multiple sequence alignment with guaranteed error boundsBulletin of Mathematical Biology, 1993
- Multiple Alignment, Communication Cost, and Graph MatchingSIAM Journal on Applied Mathematics, 1992
- A survey of multiple sequence comparison methodsBulletin of Mathematical Biology, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Mapping and interpreting biological informationCommunications of the ACM, 1991
- Trees, Stars, and Multiple Biological Sequence AlignmentSIAM Journal on Applied Mathematics, 1989
- The Multiple Sequence Alignment Problem in BiologySIAM Journal on Applied Mathematics, 1988
- Multiple sequence alignmentJournal of Molecular Biology, 1986
- The steiner problem in phylogeny is NP-completeAdvances in Applied Mathematics, 1982
- Minimal Mutation Trees of SequencesSIAM Journal on Applied Mathematics, 1975