Welcome to the InfoSci Platform
Reference Hub1
Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core

Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core

Marwa A. Radad, Nawal A. El-Fishawy, Hossam M. Faheem
Copyright: © 2013 |Volume: 2 |Issue: 3 |Pages: 18
ISSN: 2160-9586|EISSN: 2160-9594|EISBN13: 9781466633643|DOI: 10.4018/ijsbbt.2013070101
Cite Article Cite Article

MLA

Radad, Marwa A., et al. "Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core." IJSBBT vol.2, no.3 2013: pp.1-18. http://doi.org/10.4018/ijsbbt.2013070101

APA

Radad, M. A., El-Fishawy, N. A., & Faheem, H. M. (2013). Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core. International Journal of Systems Biology and Biomedical Technologies (IJSBBT), 2(3), 1-18. http://doi.org/10.4018/ijsbbt.2013070101

Chicago

Radad, Marwa A., Nawal A. El-Fishawy, and Hossam M. Faheem. "Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core," International Journal of Systems Biology and Biomedical Technologies (IJSBBT) 2, no.3: 1-18. http://doi.org/10.4018/ijsbbt.2013070101

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

Motif is an over-represented pattern in biological sequence. Motif discovery is a major challenge in bioinformatics. Pattern mismatches phenomena makes motif mining very difficult. Brute Force approaches take exponential time with motif length to solve this problem. In this paper, the authors discuss a Recursive-Brute Force algorithm. Its average case time complexity is exponential with the allowed mutations instead of the motif length. Modern Multi-Core architecture revolution encourages us to parallelize our algorithm. We implement the algorithm using two different approaches. A multi-threaded version (OMP-RBF) is implemented using OpenMP. OMP-RBF suffers from a serious performance degradation due to the heap contention problem. The authors have investigated different solutions to solve the heap contention problem. The second implementation is based on MPI that is called MPI-RBF. The efficient handling of the data locality boost the scalability of the MPI-RBF. The authors prove that MPI approach outperforms OpenMP in such computationally-intensive, memory-intensive, and communication-less problem.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.