On the Complexity of Multiple Sequence Alignment

Overview

Journal J Comput Biol

Specialties Biology
Molecular Biology

Date 1994 Jan 1

PMID 8790475

Citations 102

Authors

L Wang

T Jiang

Affiliations

Soon will be listed here.

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.

Citing Articles

BetaAlign: a deep learning approach for multiple sequence alignment.

Dotan E, Wygoda E, Ecker N, Alburquerque M, Avram O, Belinkov Y Bioinformatics. 2025; 41(1).

PMID: 39775454 PMC: 11758787. DOI: 10.1093/bioinformatics/btaf009.

Fast and exact gap-affine partial order alignment with POASTA.

van Dijk L, Manson A, Earl A, Garimella K, Abeel T Bioinformatics. 2025; 41(1).

PMID: 39752324 PMC: 11755094. DOI: 10.1093/bioinformatics/btae757.

CGRclust: Chaos Game Representation for twin contrastive clustering of unlabelled DNA sequences.

Alipour F, Hill K, Kari L BMC Genomics. 2024; 25(1):1214.

PMID: 39695938 PMC: 11657719. DOI: 10.1186/s12864-024-11135-y.

Species specificity and specificity diversity (SSD) framework: a novel method for detecting the unique and enriched species associated with disease by leveraging the microbiome heterogeneity.

Ma Z BMC Biol. 2024; 22(1):283.

PMID: 39639304 PMC: 11619696. DOI: 10.1186/s12915-024-02024-7.

HAlign 4: a new strategy for rapidly aligning millions of sequences.

Zhou T, Zhang P, Zou Q, Han W Bioinformatics. 2024; 40(12).

PMID: 39607773 PMC: 11646084. DOI: 10.1093/bioinformatics/btae718.