Friday, February 24, 2012

Model Calculations and Proof of Concept Simulations - Biological Sequence Alignment

MODEL CALCULATIONS

The example under consideration is


The Row 0 and Column 0 are assumed to be known.

Calculating Row 1
w[j] = max ((T[i-1,j] + f(ai , '-'), (T[i-1,j-1] + f(ai , bj))
w[1] = max((T[0,1] – 1), (T(0,0) + f(a1, b1)) = 0
w[2] = max((T[0,2] – 1), (T(0,1) + f(a1, b2)) = -1
w[3] = max((T[0,3] – 1), (T(0,2) + f(a1, b3)) = -2
w[4] = max((T[0,4] – 1), (T(0,3) + f(a1, b4)) = -3
w[5] = max((T[0,5] – 1), (T(0,4) + f(a1, b5)) = -6
w[6] = max((T[0,6] – 1), (T(0,5) + f(a1, b6)) = -5
w[7] = max((T[0,7] – 1), (T(0,6) + f(a1 , b7)) = -6
w[8] = max((T[0,8] – 1), (T(0,7) + f(a1, b8)) = -7

z[j] = w[j] + y[j]
z[1] = w[1] -y[1] = w[1] +1 = 0
z[2] = w[2] -y[2] = w[2] +2 = 0
z[3] = w[3] -y[3] = w[3] +3 = 0
z[4] = w[4] -y[4] = w[4] +4 = 0
z[5] = w[5] -y[5] = w[5] +5 = 0
z[6] = w[6] -y[6] = w[6] +6 = 0
z[7] = w[7] -y[7] = w[7] +7 = 0
z[8] = w[8] -y[8] = w[8] +8 = 0

(Compare with x_reg in the output)

T[1,1] = x[1] + g[1] = x[1] - 1 = -1
T[1,2] = x[2] + g[2] = x[2] - 2 = -2
T[1,3] = x[3] + g[3] = x[3] - 3 = -3
T[1,4] = x[4] + g[4] = x[4] - 4 = -4
T[1,5] = x[5] + g[5] = x[5] - 5 = -5
T[1,6] = x[6] + g[6] = x[6] - 6 = -6
T[1,7] = x[7] + g[7] = x[7] - 7 = -7
T[1,8] = x[8] + g[8] = x[8] - 8 = -8

Compare with outputs y0 to y7 in the simulated output. Row 1 values are calculated.

Simulation of Row 1
 Row 1 values can be checked to be correct.(click to enlarge)

Calculation of Row 2

Row 2
w[j] = max ((T[i-1,j] + f(ai , '-'), (T[i-1,j-1] + f(ai , bj))

w[1] = max((T[1,1] – 1), (T(1,0) + f(a2, b1)) = max(-2,-2) = -2
w[2] = max((T[1,2] – 1), (T(1,1) + f(a2, b2)) = -2
w[3] = max((T[1,3] – 1), (T(1,2) + f(a2, b3)) = -1 (note: f(a2, b3) = 1, match)
w[4] = max((T[1,4] – 1), (T(1,3) + f(a2, b4)) = -4
w[5] = max((T[1,5] – 1), (T(1,4) + f(a2, b5)) = -5
w[6] = max((T[1,6] – 1), (T(1,5) + f(a2, b6)) = -6
w[7] = max((T[1,7] – 1), (T(1,6) + f(a2, b7)) = -7
w[8] = max((T[1,8] – 1), (T(1,7) + f(a2, b8)) = -8

z[j] = w[j] - y[j]
z[1] = w[1] -y[1] = w[1] + 1 = -1
z[2] = w[2] -y[2] = w[2] + 2 = 0
z[3] = w[3] -y[3] = w[3] + 3 = 2
z[4] = w[4] -y[4] = w[4] + 4 = -4
z[5] = w[5] -y[5] = w[5] + 5 = -5
z[6] = w[6] -y[6] = w[6] + 6 = -6
z[7] = w[7] -y[7] = w[7] + 7 = -7
z[8] = w[8] -y[8] = w[8] + 8 = -8
(Compare with w_x_reg in simulated output)

After parallel prefix

x[1] = max( z[1]) = -1
x[2] = max( z[1], z[2]) = 0
x[3] = max( z[1], z[2], z[3]) = 2
x[4] = max( z[1], z[2], z[3], z[4]) = 2
x[5] = max( z[1], z[2], z[3], z[4], z[5]) = 2
x[6] = max( z[1], z[2], z[3], z[4], z[5], z[6]) = 2
x[7] = max( z[1], z[2], z[3], z[4], z[5], z[6], z[7]) = 2
x[8] = max( z[1], z[2], z[3], z[4], z[5], z[6], z[7], z[8]) = 2
(Compare with x_reg in the output)

T[1,1] = x[1] – g[1] = x[1] - 1 = -2
T[1,2] = x[2] – g[2] = x[2] - 2 = -2
T[1,3] = x[3] – g[3] = x[3] - 3 = -1
T[1,4] = x[4] – g[4] = x[4] - 4 = -2
T[1,5] = x[5] – g[5] = x[5] - 5 = -3
T[1,6] = x[6] – g[6] = x[6] - 6 = -4
T[1,7] = x[7] – g[7] = x[7] - 7 = -5
T[1,8] = x[8] – g[8] = x[8] - 8 = -6
Compare with outputs y0 to y7 in the simulated output. Row 2 values are calculated.




































The other values are calculated and documented in this table.










They are in conformance with the values obtained in simulations.


No comments:

Post a Comment