Display Settings:

Format

Send to:

Choose Destination

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

    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]

    Supplemental Content

    Click here to read