# Difference between revisions of "Needleman-Wunsch"

(New page: Needleman-Wunsch is a nonlinear global optimization method for DNA sequence alignments. The potential pairs of sequences are organized in a 2D matrix. In the first step, the algorithm fil...) |
|||

Line 7: | Line 7: | ||

In the second step, the maximum path is traced backward to deduce the optimal | In the second step, the maximum path is traced backward to deduce the optimal | ||

alignment. | alignment. | ||

+ | |||

+ | A step-by-step illustration of this algorithm can be found in this [http://www.ludwig.edu.au/course/lectures2005/Likic.pdf link]. | ||

+ | |||

+ | Our CPU version can be found [http://www.people.virginia.edu/~sc5nf/needle_cpu.zip here]. | ||

+ | |||

+ | Our CUDA implementation only parallelizes the first step,can be found [http://www.people.virginia.edu/~sc5nf/needle_gpu.zip here]. |

## Revision as of 12:16, 16 July 2008

Needleman-Wunsch is a nonlinear global optimization method for DNA sequence alignments. The potential pairs of sequences are organized in a 2D matrix. In the first step, the algorithm fills the matrix from top left to bottom right, step-by-step. The optimum alignment is the pathway through the array with maximum score, where the score is the value of the maximum weighted path ending at that cell. Thus, the value of each data element depends on the values of its northwest-, north- and west-adjacent elements. In the second step, the maximum path is traced backward to deduce the optimal alignment.

A step-by-step illustration of this algorithm can be found in this link.

Our CPU version can be found here.

Our CUDA implementation only parallelizes the first step,can be found here.