# Probalign

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Probalign
> Markdown URL: https://mediated.wiki/source/Probalign.md
> Source: https://en.wikipedia.org/wiki/Probalign
> Source revision: 1338333723
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

'''Probalign''' is a sequence alignment tool that calculates a maximum [expected accuracy](/source/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](/source/Boltzmann_distribution). The partition function is calculated using a [dynamic programming](/source/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](/source/PAM_matrix), [BLOSUM](/source/BLOSUM),...)
* affine [gap penalty](/source/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](/source/ProbCons)
* [Multiple Sequence Alignment](/source/Multiple_Sequence_Alignment)

== References ==
{{Reflist}}

== External links ==
* [http://probalign.njit.edu/probalign/login Probalign Webservice]

Category:Sequence alignment algorithms

---
Adapted from the Wikipedia article [Probalign](https://en.wikipedia.org/wiki/Probalign) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Probalign?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.