Multiple Sequence Alignment

By Jonathan Pevsner. Theory and Mathematical Methods for Bioinformatics, 2005

548 citations recorded by the source corpus.

The multiple sequence alignment (MA) plays an important role in sequence analysis. However, it has been proven to be an NP-hard problem. This means the computation complexity of MSA increases exponentially with the number of sequences. The presented algorithms are mostly heuristic and many of them are based on pairwise sequence alignment. Hence we begin with pairwise alignment of multiple sequences and discuss the topological space induced by pairwise alignment of multiple sequences, since different optimization criteria may lead to different results. We discuss several optimization indices here: the sum of pairs (SP); Shannon entropy; similarity rate and the rate of virtual symbols. Based on this discussion, we present a new multiple sequence alignment based on SPA called super multiple sequence alignment (SMA). We give a detailed description of the algorithm and compare it to some popular MA algorithms and find that it works well enough, especially with respect to speed. An example of SARS multiple sequence alignment is given at the end of this chapter.

Subfields: Molecular Biology

View Paper: https://www.semanticscholar.org/paper/15883519c1d72eecaa03d9fa94c8d5e9100cb4f3

How researchers see this paper

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

In Molecular Biology

Citations in the corpus

Profile Prediction: An Alignment-Based Pre-Training Task for Protein Sequence Models (2020, background): “Building an MSA is a common first step in many downstream tasks including predicting structure and finding homologous proteins (Edgar and Batzoglou, 2006).”
BMGE (Block Mapping and Gathering with Entropy): a new software for selection of phylogenetic informative regions from multiple sequence alignments (2010, background): “In spite of constant improvements of the multiple sequence alignment heuristics [5,6], an alignment can contain regions (i.e. sets of contiguous characters, also often called blocks [7,8]) where homology is ambiguous.”
PROMALS3D: a tool for multiple protein sequence and structure alignments (2008, background): “Accurate and fast construction of MSAs has been under extensive research for many years (1,2).”
Fast Statistical Alignment (2009, methodology): “Indeed, in a recent review of multiple sequence alignment [3], the authors remark that ‘‘to the best of our knowledge, no significant improvements have been made to the [ClustalW] algorithm since 1994 and several modern methods achieve better performance in accuracy, speed, or both.’’”
Culture-independent molecular techniques for soil microbial ecology (2010, methodology): “, 1994) but several improved alternatives have been developed including T-COFFEE and PROBCONS (Edgar and Batzoglou, 2006).”
COBALT: constraint-based alignment tool for multiple protein sequences (2007, unknown): “The development of algorithms that can automatically produce biologically plausible multiple alignments is a subject of very active research (Edgar and Batzoglou, 2006; Notredame, 2002).”
Consequences of Faster Alignment of Sequences (2014, background): “There are multiple ways to define the alignment score between k substrings but we focus on two options, the most general k-wise scoring scheme and the most popular Sum of Pairs (SP) scoring scheme [6].”
SATe-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees. (2012, methodology): “Of the alignment methods that can handle very large numbers of taxa, the PartTree method yields among the most accurate alignments in our experience (Liu et al. 2010).”
Mind the gaps: evidence of bias in estimates of multiple sequence alignments. (2007, background): “On the other hand, benchmark testing on large-scale data sets, such as BAliBASE (Thompson et al. 1999a), has demonstrated that most MSA programs have serious shortcomings when confronted with insertions and deletions (Edgar and Batzoglou 2006; Nuin et al. 2006).”
Phylogenetic assessment of alignments reveals neglected tree signal in gaps (2010, result): “In terms of alignment strategy, and contrary to current beliefs [3,4], consis-tency-based alignment methods as a class did not outperform their scoring matrix-based counterparts, yet they were up to 300 times slower (Figure 2, Additional file 1, Figure S6).”
Improvement of phylogenies after removing divergent and ambiguously aligned blocks from protein sequence alignments. (2007, background): “First, differences in phylogenetic performance between different alignments derived from symmetric trees are quantitatively smaller, in agreement with a previous work (Ogden and Rosenberg, 2006).”