Premium
High‐performance implementation of planted motif problem on multicore and GPU
Author(s) -
Dasari Naga Shailaja,
Ranjan Desh,
Zubair Mohammad
Publication year - 2013
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.2935
Subject(s) - parallelizable manifold , computer science , multi core processor , parallel computing , enumeration , motif (music) , theoretical computer science , algorithm , mathematics , physics , combinatorics , acoustics
SUMMARY In this paper, we present an efficient, easily parallelizable approach to solve planted motif problem (PMP). PMP is a well‐studied problem in computational biology. It is useful in developing methods for finding transcription factor binding sites, classifying sequences, and building phylogenetic trees. Many approaches to solve PMP can be found in the literature. But the problem with those approaches is that they are difficult to parallelize as they have been designed for serial computers. In this paper, we propose a simple, easily parallelizable enumeration‐based approach called BitBased. As with most other enumeration‐based approaches that have been proposed to solve PMP, BitBased is also limited by memory for solving large‐sized problems. To overcome this limitation, we propose various modifications, which not only reduce the memory requirement but also improve the performance of the approach. We have implemented our approach on multicore and GPU devices. We found that BitBased outperforms all the approaches proposed to solve PMP so far. BitBased is able to solve the (21,8) instance, which was not previously reported as solved in the literature. Copyright © 2012 John Wiley & Sons, Ltd.