Home LiteratureArticle Details

PMID: 8790475 Published · ppublish English Journal Article Research Support, Non-U.S. Gov't

On the complexity of multiple sequence alignment.

Journal of computational biology : a journal of computational molecular cell biology ·Vol. 1 ·No. 4 ·1994-00-00 ·Pages 337-48

Wang L, Jiang T

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.

MeSH Terms

Algorithms Models, Theoretical Phylogeny Sequence Alignment/methods

Authors & Affiliations

2 authors, click to expand affiliations / ORCID

Wang L

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

Jiang T

Article Info

Journal

Journal of computational biology : a journal of computational molecular cell biology

Abbr.

J Comput Biol

ISSN

1066-5277

DOI

10.1089/cmb.1994.1.337

Published

1994-00-00

Pages

337-48

Language

English

Region

United States

NLM ID

9433358

Subset

External Links

PubMed source DOI: 10.1089/cmb.1994.1.337 View journal details

Analysis Services

On the complexity of multiple sequence alignment.

Contact

WeChat Official Account