ProbCons explained

In bioinformatics and proteomics, ProbCons is an open source software for 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.^[1] ^[2]

Algorithm

The following describes the basic outline of the ProbCons algorithm.^[3]

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 P(x_i \sim y_i|x,y) \ \overset& \ \Pr[x_i \sim y_i \text{ in some } a|x,y] \\[8pt] =& \ \sum_ \Pr[a|x,y] \\[2pt] =& \ \sum_ \mathbf\ \Pr[a|x,y]\end$

(Where

1\{x_i\simy_i\ina\}

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

is defined as the number of common aligned pairs divided by the length of the shorter sequence.

Calculate expected accuracy of each sequence:

$\beginE_(\operatorname(a^*,a)) & = \sum_\Pr[a|x,y] \operatorname(a^*,a) \\& = \frac \cdot \sum_\mathbf\ \Pr[a|x,y]\\& = \frac \cdot \sum_ P(x_i \sim y_j|x,y)\end$

This yields a maximum expected accuracy (MEA) alignment:

$E(x,y) = \arg\max_ \; E_(\operatorname(a^*,a))$

Step 3: Probabilistic Consistency Transformation

All pairs of sequences x,y from the set of all sequences

l{S}

are now re-estimated using all intermediate sequences z:

$P'(x_i - y_i|x,y) = \frac$

\sum_ \sum_ 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.

Notes and References

10.1101/gr.2821705 . Do CB, Mahabhashyam MS, Brudno M, Batzoglou S . 2005 . PROBCONS: Probabilistic Consistency-based Multiple Sequence Alignment . Genome Research . 15 . 2 . 330–340 . 15687296 . 546535.
Book: Roshan, Usman. Multiple Sequence Alignment Methods. 1079. 2014-01-01. Humana Press. 9781627036450. Russell. David J. Methods in Molecular Biology. 147–153. English. 10.1007/978-1-62703-646-7_9. 24170400. Multiple Sequence Alignment Using Probcons and Probalign.
http://www.bioinf.uni-freiburg.de//Lehre/Courses/2011_WS/V_BioinfoII/slides_probcons.pdf Lecture "Bioinformatics II" at University of Freiburg