An Optimized and Parallel Hardware Design for Dot Plot Algorithm

Abstract

The dot plot algorithm is a useful computational tool for comparative genomics that offers an effective direct method for comparing genetic sequences. It creates a pair wise comparison between two DNA or protein sequences and renders the results as a dot matrix. Implementation in hardware reduces the O(MN) complexity of the dot plot to O(M+N). In this paper, we develop an optimized and parallel hardware design approach that can be implemented on hardware platforms like FPGAs. The approach brings the complexity of the dot plot algorithm further down to O(M).