Probalign Explained

Probalign is a sequence alignment tool that calculates a maximum expected accuracy alignment using partition function posterior probabilities.^[1] 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.^[2]

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 _{x _{i-y} _{j} \in a} \sigma(x _{i,y} _{j)} + gapcost

Now the boltzmann weighted score of an alignment a is:

e ^{(S(a))/(T)} = e ^{(\sum _{x _{i-y} _{j} \in a} \sigma(x _{i,y} _{j)} + gapcost)/(T)} = \left( \prod _{x _{i} - y _{i} \in a} e ^{(\sigma(x _{i,y} _{j)})/(T)} \right) ⋅ e ^{(gapcost)/(T)}

Where

T is a scaling factor.

The probability of an alignment assuming boltzmann distribution is given by

Pr[a|x,y] = (e ^{(S(a))/(T)})/(Z)

Where

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

Dynamic programming

Let

Z _{i,j} 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 ^{M} _{i,j} : the partition function of all alignments of the two prefixes that end in a match.Z ^{I} _{i,j} : the partition function of all alignments of the two prefixes that end in an insertion ( - ,y _{j)} .Z ^{D} _{i,j} : the partition function of all alignments of the two prefixes that end in a deletion (x _{i,-)} .Then we have: Z _{i,j} = Z ^{M} _{i,j} + Z ^{D} _{i,j} + Z ^{I} _{i,j}

Initialization

The matrixes are initialized as follows:

Z ^{M} _{0 ,j} = Z ^{M} _{i, 0} = 0 Z ^{M} _{0 , 0} = 1 Z ^{D} _{0 ,j} = 0 Z ^{I} _{i, 0} = 0

Recursion

The partition function for the alignments of two sequences

x and y is given by Z _{|x|,|y|} , which can be recursively computed:Z ^{M} _{i,j} = Z _{i-1,j-1} ⋅ e ^{(\sigma(x _{i,y} _{j)})/(T)} Z ^{D} _{i,j} = Z ^{D} _{i -1 ,j} ⋅ e ^{(\beta)/(T)} + Z ^{M} _{i -1 ,j} ⋅ e ^{(g( 1 ))/(T)} + Z ^{I} _{i -1 ,j} ⋅ e ^{(g( 1 ))/(T)} Z ^{I} _{i,j} 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)} = (Z _{i -1 ,j -1} ⋅ e ^{(\sigma(x _{i,y} _{j)})/(T)} ⋅ Z' _{i',j'})/(Z _{|x|,|y|}) Z', i', j' are the respective values for the recalculated Z with inversed base pair strings.

See also

• ProbCons
• Multiple Sequence Alignment

External links

• Probalign Webservice

Notes and References

1. U. Roshan and D. R. Livesay, Probalign: multiple sequence alignment using partition function posterior probabilities, Bioinformatics, 22(22):2715-21, 2006 (PDF)
2. http://www.bioinf.uni-freiburg.de//Lehre/Courses/2011_WS/V_BioinfoII/probalign-partition-func.pdf Lecture "Bioinformatics II" at University of Freiburg