On the complexity of multiple sequence alignment.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

659 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)337-348
Journal / PublicationJournal of computational biology : a journal of computational molecular cell biology
Volume1
Issue number4
Publication statusPublished - Dec 1994
Externally publishedYes

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.