'''Probalign''' is a sequence alignment tool that calculates a maximum expected accuracy alignment using partition function posterior probabilities.<ref>U. Roshan and D. R. Livesay, Probalign: multiple sequence alignment using partition function posterior probabilities, Bioinformatics, 22(22):2715-21, 2006 ([https://web.archive.org/web/20090409002832/http://bioinformatics.oxfordjournals.org/cgi/reprint/btl472?ijkey=GR3m5VV6yTz1jEx&keytype=ref PDF])</ref> Base pair probabilities are estimated using an estimate similar to the 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.<ref>[http://www.bioinf.uni-freiburg.de//Lehre/Courses/2011_WS/V_BioinfoII/probalign-partition-func.pdf Lecture "Bioinformatics II" at University of Freiburg]</ref>
=== Alignment score === To score an alignment of two sequences two things are needed: * a similarity function <math>\sigma(x,y)</math> (e.g. PAM, BLOSUM,...) * affine gap penalty: <math> g(k) = \alpha + \beta k</math> The score <math>S(a)</math> of an alignment a is defined as:
<math> S(a) = \sum_{x_i-y_j \in a} \sigma(x_i,y_j) + \text{gap cost}</math>
Now the boltzmann weighted score of an alignment a is:
<math> e^{\frac{S(a)}{T}} = e^{\frac{\sum_{x_i-y_j \in a} \sigma(x_i,y_j) + \text{gap cost}}{T}} = \left( \prod_{x_i - y_i \in a} e^{\frac{\sigma(x_i,y_j)}{T}} \right) \cdot e^{\frac{gapcost}{T}}</math>
Where <math>T</math> is a scaling factor.
The probability of an alignment assuming boltzmann distribution is given by
<math>Pr[a|x,y] = \frac{e^{\frac{S(a)}{T}}}{Z}</math>
Where <math>Z</math> is the partition function, i.e. the sum of the boltzmann weights of all alignments.
=== Dynamic programming === Let <math>Z_{i,j}</math> denote the partition function of the prefixes <math>x_0,x_1,...,x_i</math> and <math>y_0,y_1,...,y_j</math>. Three different cases are considered: # <math>Z^{M}_{i,j}:</math> the partition function of all alignments of the two prefixes that end in a match. # <math>Z^{I}_{i,j}:</math> the partition function of all alignments of the two prefixes that end in an insertion <math>(-,y_j)</math>. # <math>Z^{D}_{i,j}:</math> the partition function of all alignments of the two prefixes that end in a deletion <math>(x_i,-)</math>. Then we have: <math>Z_{i,j} = Z^{M}_{i,j} + Z^{D}_{i,j} + Z^{I}_{i,j}</math>
==== Initialization ==== The matrixes are initialized as follows: * <math>Z^{M}_{0,j} = Z^{M}_{i,0} = 0</math> * <math>Z^{M}_{0,0} = 1</math> * <math>Z^{D}_{0,j} = 0</math> * <math>Z^{I}_{i,0} = 0</math>
==== Recursion ==== The partition function for the alignments of two sequences <math>x</math> and <math>y</math> is given by <math>Z_{|x|,|y|}</math>, which can be recursively computed: * <math>Z^{M}_{i,j} = Z_{i-1,j-1} \cdot e^{\frac{\sigma(x_i,y_j)}{T}}</math> * <math>Z^{D}_{i,j} = Z^{D}_{i-1,j} \cdot e^{\frac{\beta}{T}} + Z^{M}_{i-1,j} \cdot e^{\frac{g(1)}{T}} + Z^{I}_{i-1,j} \cdot e^{\frac{g(1)}{T}}</math> * <math>Z^{I}_{i,j}</math> analogously
=== Base pair probability === Finally the probability that positions <math>x_i</math> and <math>y_j</math> form a base pair is given by:
<math>P(x_i - y_j|x,y) = \frac{Z_{i-1,j-1} \cdot e^{\frac{\sigma(x_i,y_j)}{T}} \cdot Z'_{i',j'}}{Z_{|x|,|y|}}</math>
<math> Z', i', j'</math> are the respective values for the recalculated <math>Z</math> with inversed base pair strings.
== See also == * ProbCons * Multiple Sequence Alignment
== References == {{Reflist}}
== External links == * [http://probalign.njit.edu/probalign/login Probalign Webservice]
Category:Sequence alignment algorithms