PMS6MC: A Multicore Algorithm for Motif Discovery

Algorithms. 2013;6(4):805-823 DOI 10.3390/a6040805

 

Journal Homepage

Journal Title: Algorithms

ISSN: 1999-4893 (Online)

Publisher: MDPI AG

LCC Subject Category: Technology: Technology (General): Industrial engineering. Management engineering | Science: Mathematics: Instruments and machines: Electronic computers. Computer science

Country of publisher: Switzerland

Language of fulltext: English

Full-text formats available: PDF, HTML, XML

 

AUTHORS

Shibdas Bandyopadhyay (VMware Inc, 3401 Hillview Avenue, Palo Alto, CA 94304, USA)
Sartaj Sahni (Department of CISE, University of Florida, Gainesville, FL 32611, USA)
Sanguthevar Rajasekaran (Department of CSE, University of Connecticut, Storrs, CT 06269, USA)

EDITORIAL INFORMATION

Blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 11 weeks

 

Abstract | Full Text

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.