An optimized and parallel hardware design for dot plot algorithm.

L. Hasan; H. Zafar; A. Khattak; T. Ali; I. Din

No Detail Found!

An optimized and parallel hardware design for dot plot algorithm.

Author(s)

L. Hasan Department of Computer Systems Engineering, University of Engineering and Technology, Peshawar, Pakistan

H. Zafar Department of Computer Systems Engineering, University of Engineering and Technology, Peshawar, Pakistan

A. Khattak Department of Electrical Engineering, University of Engineering and Technology, Peshawar, Pakistan

T. Ali Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Netherlands

I. Din WIT lab, Department of Electronics Engineering, University of Incheon, South Korea

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

Publication Details

Page(s) 449-452

DOI DOI not available

Published Journal: Sindh University Research Journal, Volume: 44, Issue: 3, Year: 2012

Request the full text from PASTIC

Citations

Downloads

Views