Title :
PMS6MC: A multicore algorithm for motif discovery
Author :
Bandyopadhyay, Shibdas ; Sahni, Sartaj ; Rajasekaran, Sanguthevar
Author_Institution :
VMware Inc., Palo Alto, CA, USA
Abstract :
We develop an efficient multicore algorithm, PMS6MC, for the (l, d)-motif discovery problem in which we are to find all strings of length l that appear in every string of a given set of strings with at most d mismatches. PMS6MC is based on PMS6, which is currently the fastest single-core algorithm for motif discovery in large instances. The speedup, relative to PMS6, attained by our multicore algorithm ranges from a high of 6.62 for the (17,6) challenging instances to a low of 2.75 for the (13,4) challenging instances on an Intel 6-core system. We estimate that PMS6MC is 2 to 4 times faster than other parallel algorithms for motif search on large instances.
Keywords :
medical computing; parallel algorithms; PMS6MC; motif discovery problem; multicore algorithm; parallel string algorithm; single-core algorithm; Algorithm design and analysis; Approximation algorithms; Approximation methods; Instruction sets; Multicore processing; Parallel processing; Search problems; Planted motif search; multi-core algorithms; parallel string algorithms;
Conference_Titel :
Computational Advances in Bio and Medical Sciences (ICCABS), 2013 IEEE 3rd International Conference on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ICCABS.2013.6629205
