Probalign

Probalign is a sequence alignment tool that calculates a maximum expected accuracy alignment using partition function posterior probabilities. Base pair probabilities are estimated using an estimate similar to Boltzmann distribution. The partition function is calculated using a dynamic programming approach.

Algorithm

The following describes the algorithm used by probalign to determine the base pair probabilities.Lecture "Bioinformatics II" at University of Freiburg
/ref>

Alignment score

To score an alignment of two sequences two things are needed:
* a similarity function $\sigma(x,y)$ (e.g. PAM, BLOSUM,...)
* affine gap penalty: $g(k) = \alpha + \beta k$
The score $S(a)$ of an alignment a is defined as:

$S(a) = \sum_ \sigma(x_i,y_j) + \text$

Now the boltzmann weighted score of an alignment a is:

$e^ = e^ = \left( \prod_ e^ \right) \cdot e^$

Where $T$ is a scaling factor.

The probability of an alignment assuming boltzmann distribution is given by

Pr x,y= \frac

Where $Z$ is the partition function, i.e. the sum of the boltzmann weights of all alignments.

Dynamic Programming

Let $Z_$ denote the partition function of the prefixes $x_0,x_1,...,x_i$ and $y_0,y_1,...,y_j$. Three different cases are considered:
# $Z^_:$ the partition function of all alignments of the two prefixes that end in a match.
# $Z^_:$ the partition function of all alignments of the two prefixes that end in an insertion $(-,y_j)$.
# $Z^_:$ the partition function of all alignments of the two prefixes that end in a deletion $(x_i,-)$.
Then we have: $Z_ = Z^_ + Z^_ + Z^_$

Initialization

The matrixes are initialized as follows:
* $Z^_ = Z^_ = 0$
* $Z^_ = 1$
* $Z^_ = 0$
* $Z^_ = 0$

Recursion

The partition function for the alignments of two sequences $x$ and $y$ is given by $Z_$, which can be recursively computed:
* $Z^_ = Z_ \cdot e^$
* $Z^_ = Z^_ \cdot e^ + Z^_ \cdot e^ + Z^_ \cdot e^$
* $Z^_$ analogously

Base pair probability

Finally the probability that positions $x_i$ and $y_j$ form a base pair is given by:

$P(x_i - y_j, x,y) = \frac$

$Z', i', j'$ are the respective values for the recalculated $Z$ with inversed base pair strings.

See also

* ProbCons
* Multiple Sequence Alignment

References

{{Reflist

External links

Probalign Webservice

Sequence alignment algorithms