Solving the Longest Common Subsequence (LCS) Problem using the Associative ASC Processor with Reconfigurable 2D Mesh

S.S. Virdi, H. Wang, and R.A. Walker (USA)


SIMD, associative computing, processor array, longest common subsequence, sequence analysis, biosequences.


As new genes are sequenced, it is common for molecular biologists to compare the new gene’s DNA to known sequences. One simple form of DNA sequence comparison is done by solving the Longest Common Subsequence (LCS) problem. In this paper, we propose a parallel algorithm and specialized FPGA-based processor (the associative ASC Processor with reconfigurable 2D mesh) to solve the exact and approximate match LCS problems. This solution uses inexpensive hardware and can be reconfigured as new analysis techniques are developed, making it particularly attractive for processing biosequences.

Important Links:

Go Back