AN OPTIMIZED AND PARALLEL HARDWARE DESIGN FOR DOT PLOT ALGORITHM

L. HASAN, H. ZAFAR, A. KHATTAK, T. ALI, I. DIN

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).


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Sindh University Research Journal - SURJ (Science Series)

 Copyright © University of Sindh, Jamshoro. 2017 All Rights Reserved.
Printing and Publication by: Sindh University Press.