Display Settings:

Format

Send to:

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 1994 Winter;1(4):337-48.

On the complexity of multiple sequence alignment.

Author information

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

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.

PMID:
8790475
[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Loading ...
    Write to the Help Desk