TY - JOUR
T1 - On the complexity of multiple sequence alignment.
AU - Wang, L.
AU - Jiang, T.
PY - 1994/12
Y1 - 1994/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0028679709&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0028679709&origin=recordpage
U2 - 10.1089/cmb.1994.1.337
DO - 10.1089/cmb.1994.1.337
M3 - RGC 21 - Publication in refereed journal
C2 - 8790475
SN - 1066-5277
VL - 1
SP - 337
EP - 348
JO - Journal of computational biology : a journal of computational molecular cell biology
JF - Journal of computational biology : a journal of computational molecular cell biology
IS - 4
ER -