Fast statistical alignment

FSA

Developer(s)	Robert Bradley (UC Berkeley), Colin Dewey (UW Madison), Lior Pachter (UC Berkeley)
Stable release	1.5.2
Operating system	UNIX, Linux, Mac
Type	Bioinformatics tool
Licence	Open source

Fast statistical alignment or FSA is a multiple sequence alignment program for aligning many proteins or RNAs or long genomic DNA sequences. Along with MUSCLE and MAFFT, FSA is one of the few sequence alignment programs which can align datasets of hundreds or thousands of sequences. FSA uses a different optimization criterion which allows it to more reliably identify non-homologous sequences than these other programs, although this increased accuracy comes at the cost of decreased speed.

FSA is currently being used for projects including sequencing new worm genomes and analyzing in vivo transcription factor binding in flies.

Input/Output

This program accepts sequences in FASTA format and outputs alignments in FASTA format or Stockholm format.

Algorithm

The algorithm for the aligning of the input sequences has 4 core components.

Pair Hidden Markov Model for generating posterior probabilities

The algorithm starts first by determining posterior probabilities of alignment $\mathbb {P} (A|X,Y)$ between any two random sequences from the pool of sequences being aligned. The posterior probabilities for each column reinforce the prediction of alignment probability between a sequence pair and also filter out columns that can be unreliably aligned. These probabilities also allow for the prediction and estimate of homology between any sequence pair. A standard five-state pair hidden Markov model (Pair HMM) is used to determine these posterior probabilities of alignment for any two input sequences. The Pair HMM model uses two sets of Delete (D) and Insert (I) states to account for symbol deletion and insertions between two aligned sequences, but it can also have three states without a significant loss of accuracy.

Since the number of pairwise comparisons needed to determine the posterior probability distributions of any two pairs of sequences is computationally expensive and quadratic in the amount of sequences that are being aligned, it is decreased by using a randomized approach inspired by the Erdos-Renyi theory of random graphs. This significantly reduces the runtimes of datasets and the computational cost of running the multiple alignments.

Merging Probabilities

The posterior probabilities for each column in the sequence pairs are sorted using a weighting function that uses a steepest-ascent algorithm.

Sequence Annealing

Most existing programs that run multiple sequence alignment algorithms are based on progressive alignment where the process starts with a “null alignment,” a state where none of the sequences have been aligned. The pool of sequences is then aligned either through pairwise comparisons or through an alignment of a pair of partial alignments of subsequences. This process can cause issues in alignment because the resulting multiple sequence alignment can and will heavily depend on the sequences that are aligned at the start. There is no realigning of previously aligned sequences that could correct the MSA.

FSA uses the sequence annealing technique to overcome this issue. The sorted posterior probabilities are used with the sequence annealing technique to generate a multiple alignment. The technique finds the alignment between two sequences that minimizes the expected distance to the truth. In this case, the distance between two sequences is the number of columns in which the character from one sequence is not homologous to the character in the same column in the second sequence.

The sequence annealing technique, by determining an alignment with the minimum expected distance to the truth, conversely finds the alignment with the maximum expected accuracy. The accuracy of an alignment depends on a “true” alignment as reference and indicates the fraction of columns where the sequences are homologous. This accuracy is then used as an objective function that starts with the unaligned sequences (null alignment) and aligns characters in different columns based on the increasing accuracy of an alignment.

Ordering of the alignment

FSA aligns multiple sequences based on homology within columns instead of strictly a consideration of indels and substitutions. As such, FSA considers alignments to be equivalent if for every position along the sequences in both alignments, the same statement about homology can be made. For example, when considering pairwise comparisons, if there is a gap at a specific position in two alignments, then it can be said that the two sequences being compared are not homologous at said position. This can result in alignments where gap-open events can differ and yet still be considered equivalent. As such, FSA chooses to output the alignment in which there is a minimum amount of “gap openings.”

Parallelization

To handle overly large datasets, FSA is able to divide the work of running all necessary pairwise comparisons and alignments to different processors. This is handled by using a “fixed-size chunking” strategy that distributes the pairwise comparisons to each available processor in chunks. Each processor is therefore able to run the posterior probability calculation on a chunk of pairwise comparisons before merging the collected data back to a single processor for sequence annealing.

Visualization

The results of the multiple sequence alignment under FSA can be displayed under the FSA's own GUI. The GUI is able to display and color label different measures of alignment quality on the columns of characters within the alignment itself. The five different measures that can be observed and are approximated under the FSA model include accuracy, sensitivity, certainty, specificity, and consistency.

Comparisons to other alignment programs

FSA has been benchmarked against multiple alignment databases for protein (SABmark 1.65 and BAliBASE 3), RNA (BRAliBase 2.1 and Consanmix80), and DNA sequences. These benchmarks were conducted alongside other popular alignment programs such as ClustalW, MAFFT, MUSCLE, T-Coffee, and so on. Overall, at the time that FSA's abstract and research paper was received for review, FSA outperformed most alignment programs in accuracy and positive predictive values with sensitivities being on-par with the better-performing programs such as MAFFT and ProbConsRNA. Runtime comparisons were also conducted by comparing the timings to align 16S ribosomal sequences. MAFFT performed the alignment faster than the other alignment programs while MUSCLE and FSA (using a 3-state HMM and with disabled iterative refinement) were the next fastest programs.

References

Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (2009). "Fast Statistical Alignment". PLOS Computational Biology. 5 (5): e1000392. Bibcode:2009PLSCB...5E0392B. doi:10.1371/journal.pcbi.1000392. PMC 2684580. PMID 19478997.

Schwartz AS, Pachter L (2007) Multiple alignment by sequence annealing. Bioinformatics 23: e24-9.

Eddy SR. Multiple alignment using hidden Markov models. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. PMID 7584426.

External links

• FSA web server
• FSA source code