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.


Comments

Post a Comment

Popular posts from this blog

Generating 16k ROM using Xilinx IP COREGEN and simulating it in modelsim

The instruction ROM is an IP Core. so before interfacing with the open8, it has to be generated. The method of generating and simulating a ROM Xilinx IP Core is described here. FIND ALL THE FILES HERE 1. app.coe (the initialization file) 2. rom_16k_core.vhd 3. rom_16k_core.vho 4. rom_16k_core.xco 5. top_level.vhd 6. do_memgen.do Creation of the ROM Xilinx 10.1 1. open ISE 2. create a new project 3. tools -> core generator(12.1) (or right click on the device and add a new file 10.1) 4. In the IP catalog -> Memory and storage elements -> RAM and ROM 5. double click on block memory generator, A new window opens 6. In the new window select single port ROM click next, Write first mode 7. Select Read Width = 8 and Read Depth = 16384 for 16K ROM -> next 8. The output ports are unregistered, load initialization COE if required -> next 9. No need to use the Reset pin -> next 10. Generate. (takes a little time then shows successfully generated) This
Read more

Setting up atalanta ATPG to work on Linux

Atalanta is an ATPG tool that is used to generate test patterns for combinational circuits. atalanta is a windows executable file. I am using Atalanta ATPG tool to generate the test patterns required for generating the Transition fault Test patterns RUNNING ATALANTA (LINUX) You need to have WINE installed to run windows executable binary. Created a symbolic link in the usr/bin to the atalanta.exe, name of the link s atalanta. (not necessary if you do not have root privilages) chmod u+x /place/atalanta/atalanta.exe cd /usr/bin sudo ln -s /place/atalanta/atalanta.exe ./atalanta COMMAND TO RUN ATALANTA atalanta [option] filename //put this in a shell script
Read more

Sparse matrix - 3 tuple representation

//program to 3-tuple representation #include<stdio.h> #include<unistd.h> #define SIZE 3000; void main() { int a[5][5],row,columns,i,j; printf("Enter the order of the matrix(5*5)"); scanf("%d %d",&row,&columns); printf("Enter the element of the matrix\n"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { scanf("%d", &a[i][j]); } printf("3-tuple representation"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { if(a[i][j]!=0) { printf("%d %d %d", (i+1),(j+1),a[i][j]); } } getchar(); }
Read more