ProbCons explained

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.^{[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{align} P(x _{i} \sim y _{i|x,y)} & \stackrel{def}{ = } Pr[x _{i} \sim y _{i} insomea |x,y] \\ & = \sum _{alignmentawith x _{i} - y _{i}} Pr[a|x,y]\\ & = \sum _{alignmenta} 1 \{x _{i} - y _{i} \in a\} Pr[a|x,y] \end{align}

(Where

1 \{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{align} E _{Pr[a|x,y]} (acc(a ^{*,a))} & = \sum _{a} Pr[a|x,y]acc(a ^{*,a)} \\ & = (1)/(min(|x|,|y|)) ⋅ \sum _{a} 1 \{x _{i} \sim y _{i} \in a\} Pr[a|x,y]\\ & = (1)/(min(|x|,|y|)) ⋅ \sum _{x _{i} - y _{i}} P(x _{i} \sim y _{j|x,y) \end{align}}

This yields a maximum expected accuracy (MEA) alignment:

E(x,y) = \arg max _{a ^{*}} 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

l{S} are now re-estimated using all intermediate sequences z:P'(x _{i} - y _{i|x,y)} = (1)/(| l{S) |} \sum _{z} \sum _{1} P(x _{i} \sim z _{i|x,z)} ⋅ 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

Notes and References

1. 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.
2. 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.
3. http://www.bioinf.uni-freiburg.de//Lehre/Courses/2011_WS/V_BioinfoII/slides_probcons.pdf Lecture "Bioinformatics II" at University of Freiburg