High‐performance implementation of planted motif problem on multicore and GPU. (18th October 2012)

• Record Type: Journal Article
• Authors: Dasari, Naga Shailaja; Ranjan, Desh; Zubair, Mohammad
• Other Names: Smari Waleed guestEditor.; Fiore Sandro guestEditor.; Hill David guestEditor.
• Is Part Of: Concurrency and computation. Volume 25:Number 10(2013:Jul.)
• Page Start: 1340
• Page End: 1355
• Publication Date: 2012-10-18
• Subjects: PMP -- DNA -- multicore -- BitBased -- parallel -- GPU; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.2935
• Languages: English
• ISSNs: 1532-0626

Abstract

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.