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.Lecture "Bioinformatics II" at University of Freiburg
/ref>

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) & \stackrel Pr x,y\\
& = \sum_ Pr x,y\
& = \sum_ \mathbf\ Pr x,y\end

(Where $\mathbf\$ 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
E_(acc(a^*,a)) & = \sum_Pr x,ycc(a^*,a) \\
& = \frac \cdot \sum_\mathbf\ Pr 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_(acc(a^*,a))$

Step 3: Probabilistic Consistency Transformation

All pairs of sequences x,y from the set of all sequences $\mathcal$ 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.

See also

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

References

External links

*{{Official website, http://probcons.stanford.edu/

Computational phylogenetics