On the complexity of multiple sequence alignment. [J Comput Biol. 1994]

SearchDatabase nameforSearch term

Advanced Search (beta)

Your browser version may not work well with NCBI's Web applications. More information here...

Display Show

All: 1

Review: 0

Click to change filter selection through MyNCBI.

1: J Comput Biol. 1994 Winter;1(4):337-48.Links

On the complexity of multiple sequence alignment.

Wang L, Jiang T.

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

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.

PMID: 8790475 [PubMed - indexed for MEDLINE]

A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment. [J Comput Biol. 1995]
Computational complexity of multiple sequence alignment with SP-score. [J Comput Biol. 2001]
Settling the intractability of multiple alignment. [J Comput Biol. 2006]
Ancestral maximum likelihood of evolutionary trees is hard. [J Bioinform Comput Biol. 2004]
Bayesian coestimation of phylogeny and sequence alignment. [BMC Bioinformatics. 2005]
» See all Related Articles...

Display Show

On the complexity of multiple sequence alignment.

Related Articles