Probalign

Algorithm

The following describes the algorithm used by probalign to determine the base pair probabilities.

Alignment score

To score an alignment of two sequences two things are needed:

The score S ( a ) of an alignment a is defined as:

S ( a ) = ∑ x i − y j ∈ a σ ( x i , y j ) + gap cost

Now the boltzmann weighted score of an alignment a is:

e S ( a ) T = e ∑ x i − y j ∈ a σ ( x i , y j ) + gap cost T = ( ∏ x i − y i ∈ a e ∑ x i − y j ∈ a σ ( x i , y j ) T ) ⋅ e g a p c o s t T

Where T is a scaling factor.

The probability of an alignment assuming boltzmann distribution is given by

P r [ 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:

1. Z i , j M : the partition function of all alignments of the two prefixes that end in a match.
2. Z i , j I : the partition function of all alignments of the two prefixes that end in an insertion ( − , y j ) .
3. Z i , j D : the partition function of all alignments of the two prefixes that end in a deletion ( x i , − ) .

Then we have: Z i , j = Z i , j M + Z i , j D + Z i , j I

Initialization

The matrixes are initialized as follows:

Recursion

The partition function for the alignments of two sequences x and y is given by Z | x | , | y | , which can be recursively computed:

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 σ ( 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.