On the Complexity of Multiple Sequence Alignment

1994937 citationsJournal Article

Authors

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.

Topics & Keywords

Algorithms and Data Compression Genome Rearrangement Algorithms Genomics and Chromatin Dynamics

Publication Details

Published in: Journal of Computational Biology

Volume 1, Issue 4, pp. 337-348

DOI: 10.1089/cmb.1994.1.337

Field-Weighted Citation Impact: 12.45

Command Palette

On the Complexity of Multiple Sequence Alignment

Authors

Abstract

Topics & Keywords

Publication Details