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.