ProbCons

ProbCons is an open source probabilistic consistency-based multiple alignment of amino acid sequences. It is one of the most efficient protein multiple sequence alignment programs, since it has repeatedly demonstrated a statistically significant advantage in accuracy over similar tools, including Clustal and MAFFT.

Algorithm

The following describes the basic outline of the ProbCons algorithm.

Step 1: Reliability of an alignment edge

For every pair of sequences compute the probability that letters $x_i$ and $y_i$ are paired in $a^{*}$ an alignment that is generated by the model.

$\begin{array}{rl}P(x_i\sim y_i|x,y)& \stackrel{def}{=}Pr[x_i\sim y_i\text{ in some a }|x,y]\\ & =\sum _{\text{alignment a with }{x}_i-y_i}Pr[a|x,y]\\ & =\sum _{\text{alignment a}}\mathbf{𝟏}\{x_i-y_i\in a\}Pr[a|x,y]\end{array}$

(Where $\mathbf{𝟏}\{x_i\sim y_i\in a\}$ is equal to 1 if $x_i$ and $y_i$ are in the alignment and 0 otherwise.)

Step 2: Maximum expected accuracy

The accuracy of an alignment $a^{*}$ with respect to another alignment $a$ is defined as the number of common aligned pairs divided by the length of the shorter sequence.

Calculate expected accuracy of each sequence:

$\begin{array}{rl}{E}_{Pr[a|x,y]}(acc(a^{*},a))& =\sum _{a}Pr[a|x,y]acc(a^{*},a)\\ & =\frac{1}{min(|x|,|y|)}\cdot \sum _a\mathbf{𝟏}\{x_i\sim y_i\in a\}Pr[a|x,y]\\ & =\frac{1}{min(|x|,|y|)}\cdot \sum _{x_i-y_i}P(x_i\sim y_j|x,y)\end{array}$

This yields a maximum expected accuracy (MEA) alignment:

$E(x,y)=\arg \underset{a^{*}}{\max }{E}_{Pr[a|x,y]}(acc(a^{*},a))$

Step 3: Probabilistic Consistency Transformation

All pairs of sequences x,y from the set of all sequences ${𝒮}$ are now re-estimated using all intermediate sequences z:

$P^{\prime }(x_i-y_i|x,y)=\frac{1}{|{𝒮}|}\sum _z\sum _{1\le k\le |z|}P(x_i\sim z_i|x,z)\cdot P(z_i\sim y_i|z,y)$

This step can be iterated.

Step 4: Computation of guide tree

Construct a guide tree by hierarchical clustering using MEA score as sequence similarity score. Cluster similarity is defined using weighted average over pairwise sequence similarity.

Step 5: Compute MSA

Finally compute the MSA using progressive alignment or iterative alignment.

See also

• Sequence alignment software
• Clustal
• MUSCLE
• AMAP
• T-Coffee
• Probalign