Your browser version may not work well with NCBI's Web applications. More information
here...
-
On the complexity of multiple sequence alignment.
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]
-
Related Articles