title: PMS6MC: A Multicore Algorithm for Motif Discovery.
abstract: We develop an efficient multicore algorithm, PMS6MC, for the (l, d)-motif discovery problem in which we are to find all strings of lengthlthat appear in every string of a given set of strings with at mostdmismatches. 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.
authors.affiliation: VMware Inc, Palo Alto,CA 94304, sbandyopadhyay@vmware.com.
authors.forename: Shibdas
authors.initials: S
authors.lastname: Bandyopadhyay
authors.affiliation: Department of CISE, University of Florida, Gainesville, FL 32611, sahni@cise.ufl.edu.
authors.forename: Sartaj
authors.initials: S
authors.lastname: Sahni
authors.affiliation: Department of CSE, University of Connecticut, Storrs, CT 06269, USA, rajasek@engr.uconn.edu.
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
keywords: Planted motif search; multi-core algorithms; parallel string algorithms