Fast Statistical Alignment

• DOI: 10.1371/journal.pcbi.1000392
• Publication Date: 2009-05-28T21:27:18Z
• Authors: Robert K. Bradley; Adam Roberts; Michael Smoot; Sudeep Juvekar; Jaeyoung Do; Colin Dewey; Ian Holmes; Lior Pachter
• Keywords: Multiple sequence alignment; Alignment-free sequence analysis; Computational statistics; Benchmark (surveying); Centroid; Smith–Waterman algorithm; Structural alignment

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