|
Abstract
Implementation of a Dynamic Programming Algorithm for DNA Sequence
Alignment on the Cell Matrix Architecture
Wang, B.
|
DNA sequence alignment is an important tool for modern molecular biology.
The algorithm used by most sequence alignment tools is the dynamic
programming algorithm
introduced by Needleman and Wunsch in 1970. This algorithm has a time
complexity of O(n2), where n is the length of the input sequence. This
dynamic programming algorithm has been implemented on a new parallel
computing architecture called Cell Matrix. The approach taken in this
work was to configure a block of Cell Matrix cells as a custom processor to
perform the
comparison and scoring function in the dynamic programming algorithm. The
custom processors were then configured into a 2D array that closely
matched the dynamic programming algorithm and allowed them to function in
parallel.
For an appropriately large Cell Matrix, the implementation in this thesis
achieves a time complexity of O(n) in finding the optimal alignment score
for two DNA sequences.
|
|