Fast statistical alignment
Fast statistical alignment is a multiple sequence alignment program for aligning many proteins, 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 multiple 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 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 is used to determine these posterior probabilities of alignment for any two input sequences. The Pair HMM model uses two sets of Delete and Insert 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 pair-wise 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 and aligns characters in different columns based on the increasing accuracy of an alignment.