Pair Hidden Markov Model for generating posterior probabilities

The algorithm starts first by determining posterior probabilities of alignment ${\displaystyle \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.”