Fast Statistical Alignment

By Robert K. Bradley, Adam Roberts, Michael E. Smoot, Sudeep Juvekar, Jaeyoung Do, Colin N. Dewey, I. Holmes, Lior S. Pachter. PLoS Comput. Biol., 2009

361 citations recorded by the source corpus.

We describe a new program for the alignment of multiple biological sequences that is both statistically motivated and fast enough for problem sizes that arise in practice. Our Fast Statistical Alignment program is based on pair hidden Markov models which approximate an insertion/deletion process on a tree and uses a sequence annealing algorithm to combine the posterior probabilities estimated from these models into a multiple alignment. FSA uses its explicit statistical model to produce multiple alignments which are accompanied by estimates of the alignment accuracy and uncertainty for every column and character of the alignment—previously available only with alignment programs which use computationally-expensive Markov Chain Monte Carlo approaches—yet can align thousands of long sequences. Moreover, FSA utilizes an unsupervised query-specific learning procedure for parameter estimation which leads to improved accuracy on benchmark reference alignments in comparison to existing programs. The centroid alignment approach taken by FSA, in combination with its learning procedure, drastically reduces the amount of false-positive alignment on biological data in comparison to that given by other methods. The FSA program and a companion visualization tool for exploring uncertainty in alignments can be used via a web interface at http://orangutan.math.berkeley.edu/fsa/, and the source code is available at http://fsa.sourceforge.net/.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/74308374f4801f12be9ccceea77fee24b16803b5

How researchers see this paper

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

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

An alignment confidence score capturing robustness to guide tree uncertainty. (2010, methodology): “Another alignment program that can output an MSA with conﬁdence scores is FSA (Bradley et al. 2009), which uses a statistical model that allows calculation of the uncertainty in the alignment.”
FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments (2010, background): “) representation, both internally and as an output format”
PicXAA-R: Efficient structural alignment of multiple RNA sequences using a greedy approach (2011, methodology): “Recently, several studies have highlighted the eﬀectiveness of the Maximum Expected Accuracy (MEA) approach for aligning biological sequences [30–36] and for predicting the consensus secondary structure of RNAs [12,17,20,29,37–39].”
MACSE: Multiple Alignment of Coding SEquences Accounting for Frameshifts and Stop Codons (2011, methodology): “Numerous tools exist to align DNA sequences, among which are CLUSTAL [12], T-COFFEE [13], DIALIGN [14], MUSCLE [15], MAFFT [16], and the more recently proposed PRANK [3] and FSA [17].”
Pitfalls in supermatrix phylogenomics (2017, neutral): “This can even be extended, as done for instance in BMGE, GUIDANCE and FSA, to mask portions of sequences, which is particularly useful to detect annotation errors or frameshifts in coding sequences.”
A simple method to control over-alignment in the MAFFT multiple sequence alignment program (2016, methodology): “Some MSA methods, including PRANK and BAli-Phy, are aware of this problem (Bradley et al. , 2009; L € oytynoja and Goldman, 2005, 2008; Redelings, 2014; Suchard and Redelings, 2006).”
Integrative annotation of human large intergenic noncoding RNAs reveals global properties and specific subclasses. (2011, methodology): “To assess the alignment quality of the trans-mapped lincRNAs and their syntenic orthologs, we realigned the transcript sequence of all human lincRNAs and their mouse orthologs using the fast statistical alignment algorithmwith default parameters (see the Supplemental Material; Bradley et al. 2009).”