ProbCons

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.

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{\mathrm{d}\mathrm{e}\mathrm{f}}{=}& \mathrm{Pr}[x_i\sim y_i\text{ in some }a|x,y]\\ =& \sum _{\genfrac{}{}{0ex}{}{\text{alignment }a}{\text{with }{x}_i-y_i}}\mathrm{Pr}[a|x,y]\\ =& \sum _{\text{alignment }a}\mathbf{𝟏}\{x_i-y_i\in a\}\mathrm{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}_{\mathrm{Pr}[a|x,y]}(\mathrm{acc}(a^{*},a))& =\sum _a\mathrm{Pr}[a|x,y]\mathrm{acc}(a^{*},a)\\ & =\frac{1}{\min (|x|,|y|)}\cdot \sum _a\mathbf{𝟏}\{x_i\sim y_i\in a\}\mathrm{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}_{\mathrm{Pr}[a|x,y]}(\mathrm{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

External links

• Official website