On the complexity of multiple sequence alignment

L Wang; T Jiang

doi:10.1089/cmb.1994.1.337

On the complexity of multiple sequence alignment

J Comput Biol. 1994 Winter;1(4):337-48. doi: 10.1089/cmb.1994.1.337.

Authors

L Wang¹, T Jiang

Affiliation

¹ Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada.

PMID: 8790475
DOI: 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.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Models, Theoretical*
Phylogeny
Sequence Alignment / methods*