On the Complexity of Multiple Sequence Alignment

By Lusheng Wang, Tao Jiang. 1994

Subfields: Computational Biology & Bioinformatics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Biology & Bioinformatics

Citations in the corpus

Unsupervised Learning from Narrated Instruction Videos (2015, methodology): “Optimizing the cost (1) is NP-hard [31] because of the combinatorial nature of the problem.”
MUSCLE: a multiple sequence alignment method with reduced time and space complexity (2004, background): “A common heuristic is to seek a multiple alignment that maximizes the SP score (the summed alignment score of each sequence pair), which is NP complete [3].”
COBALT: constraint-based alignment tool for multiple protein sequences (2007, background): “Unfortunately, finding a multiple alignment that rigorously optimizes the commonly used ‘sum-of-pairs’ scoring measure is computationally hard (Wang and Jiang, 1994) and not practical when more than a few sequences are involved (Li et al ., 2000).”
Assembly Algorithms for Next-Generation Sequencing Data (2010, unknown): “Multiple sequence alignment (MSA) determines the precise layout and then the consensus sequence.”
COFFEE: an objective function for multiple sequence alignments (1998, background): “For the sums of pairs, this is a difficult problem that has been shown to be NP-complete (Wang and Jiang, 1994).”
Multiple sequence alignment. (2006, unknown): “8; on test 1aboA [1], CLUSTALW aligns 76% correctly compared with 67% for PROBCONS.”
The CIPRES science gateway: a community resource for phylogenetic analyses (2011, background): “Both steps in this process are NP hard [1, 2] and community codes for analyzing the data must use heuristics to simplify the calculations.”
MUSCLE: multiple sequence alignment with high accuracy and high throughput. (2004, background): “Optimizing the SP score is NP complete (1) and can be achieved by dynamic programming with time and space complexity O(LN) in the sequence length L and number of sequences N (2).”
T-Coffee: a web server for the multiple sequence alignment of protein and RNA sequences using structural information and homology extension (2011, background): “Yet, these functions are not only limited in accuracy but they are also difficult to optimize and it has been shown that, for the most commonly used functions, the computation of an optimal multiple sequence alignment is an NP-complete problem (2).”
Matt: Local Flexibility Aids Protein Multiple Structure Alignment (2008, background): “simplified variants of structure alignment are known to be NP-hard [22,23]; important progress has been recently been made in theoretically rigorous approximation guarantees [24] for pairwise structural alignment using a class of single optimality criteria scores such as the Structal score [1], and ”
k-Shape: Efficient and Accurate Clustering of Time Series (2015, background): “In many cases where alignment of observations is required, this problem is referred to as the multiple sequence alignment problem, which is known to be NP-complete [80].”
SINA: Accurate high-throughput multiple sequence alignment of ribosomal RNA genes (2012, methodology): “The task of computing the optimal alignment [as determined by the Sum-of Pairs (SP) score] was shown to be non-deterministic polynomial (NP)-complete (Wang and Jiang, 1994), and is therefore only feasible for very few sequences.”
T-Coffee: A novel method for fast and accurate multiple sequence alignment. (2000, methodology): “Further, mathematically sound methods for carrying out alignments, using these models, can be extremely demanding in computer resources for more than a handful of sequences (Carrillo & Lipman, 1988; Wang & Jiang, 1994).”
THE AMPHIBIAN TREE OF LIFE (2006, background): “Determining the optimal alignment for a given topology is NP-complete1 (Wang and Jiang, 1994).”
MUSTANG: A multiple structural alignment algorithm (2006, background): “) Were the difficulty of formulating the question not problematic enough, multiple structural alignment is inherently computationally harder than multiple sequence alignment, which itself has been shown to be Non-deterministic Polynomial-time hard (NP-hard).(31,32) Goldman and colleagues(33) have sh”
PHYLOGENETIC SYSTEMATICS OF DART-POISON FROGS AND THEIR RELATIVES (AMPHIBIA: ATHESPHATANURA: DENDROBATIDAE) (2006, background): “Determining the optimal alignment for a given topology is NP-complete2 (Wang and Jiang, 1994).”
A global averaging method for dynamic time warping, with applications to clustering (2011, background): “First, the multiple alignment process takes YðTNÞ operations [24], and is not tractable for more than a few sequences.”
Consequences of Faster Alignment of Sequences (2014, background): “The reduction of Wang and Jiang [56] from the shortest common superstring problem on k strings to a polynomial number of instances of the (global or local) alignment problem on k+2 strings with SP scoring implies that our problem is NP-hard when the number of strings is unbounded.”