Biological Sequence Alignment - Needleman-Wunsch Algorithm

The Needleman-Wunsch algorithm is discussed here before going into the details of implementation.

NEEDLEMAN-WUNSCH ALGORITHM

This Algorithm is a Dynamic Programming based algorithm. It finds the best, overall character to character match score between the two sequences. For this, an Alignment Matrix is used to calculate the best overall, character to character match score between the 2 sequences. The result of the algorithm is a singular score which reflects the degree of goodness of the match. A trace-back process is then used to retrieve the actual alignment.

PROPERTIES OF ALIGNMENT MATRIX

1. Alignment takes place in a two-dimensional matrix.
2. Gap characters can never be paired to each other. The matrix is an (m+1) x (n+1) matrix, where ‘m’ and ‘n’ are the lengths of the two sequences.
3. Each cell corresponds to a pairing of one letter from each sequence.
4. Alignment starts at the upper left and follows a mostly diagonal path down and to the right.
5. Each cell of the matrix actually contains two values, a ‘score’ and a ‘pointer.’
6. The score is derived from the scoring scheme.
7. The pointer is a directional indicator (an arrow) that points up, left, or diagonally up and left and navigates the matrix.
8. When two letters are aligned (match/mismatch), the path follows a diagonal trajectory.
9. The path moves horizontally when COELANCANTH is paired to gap characters.
10. The graph moves vertically when the letters from PELICAN are paired with gap characters.
11. Assign values for the first row and column of the matrix.
12. The score of each cell is set to the gap score multiplied by the distance from the origin.
13. Gaps may be present at the beginning of either sequence, and their cost is the same as anywhere else.
14. The arrows all point back to the origin, which ensures that alignments go all the way back to the origin (a requirement for global alignment).
15. We wish to determine the maximum scoring alignment
After computing these scores, assign the maximum value to the cell and point the arrow in the direction of the maximum score. Continue this operation until the entire matrix is filled, and each cell contains the score and pointer to the best possible alignment at that point.

PARALLEL PREFIX

It is abundantly clear, that there exist dependencies between the calculations of cells. At a time, only one cell can be calculated. This poses severe implications on the time and space constraints when we try to speed up the process. Parallel prefix is a remedy to this problem.

Using parallel prefix we reduce the dependencies between the cells and calculate the scores parallel. In fact, we are able to calculate the cells of an entire row in parallel. This allows us to optimize the time as well as space.

The algorithm is optimized in time and is implemented to compare two 8 sequences, each 8 characters long. The time taken for prefix computation is log2(8) = 3 clock cycles. It is a form of data parallel programming

Comments

Post a Comment

Popular posts from this blog

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

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

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