{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:14:19Z","timestamp":1760220859397,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,11,18]],"date-time":"2013-11-18T00:00:00Z","timestamp":1384732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a6040805","type":"journal-article","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T03:19:41Z","timestamp":1384831181000},"page":"805-823","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["PMS6MC: A Multicore Algorithm for Motif Discovery"],"prefix":"10.3390","volume":"6","author":[{"given":"Shibdas","family":"Bandyopadhyay","sequence":"first","affiliation":[{"name":"VMware Inc, 3401 Hillview Avenue, Palo Alto, CA 94304, USA"}]},{"given":"Sartaj","family":"Sahni","sequence":"additional","affiliation":[{"name":"Department of CISE, University of Florida, Gainesville, FL 32611, USA"}]},{"given":"Sanguthevar","family":"Rajasekaran","sequence":"additional","affiliation":[{"name":"Department of CSE, University of Connecticut, Storrs, CT 06269, USA"}]}],"member":"1968","published-online":{"date-parts":[[2013,11,18]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Bandyopadhyay, S., Sahni, S., and Rajasekaran, S. (2013, January 12\u201314). PSM6MC: A Multicore Algorithm for Motif Discovery. Proceedings of the Third IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), New Orleans, LA, USA.","key":"ref_1","DOI":"10.1109\/ICCABS.2013.6629205"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/S0304-3975(03)00320-7","article-title":"On the complexity of finding common approximate substrings","volume":"306","author":"Evans","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1093\/nar\/gkl198","article-title":"MEME: Discovering and analyzing DNA","volume":"34","author":"Bailey","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1126\/science.8211139","article-title":"Detecting subtle sequence signals: A Gibbs sampling strategy for multiple alignment","volume":"262","author":"Lawrence","year":"2003","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1093\/bioinformatics\/15.7.563","article-title":"Identifying DNA and protein patterns with statistically significant alignments of multiple sequences","volume":"15","author":"Hertz","year":"1999","journal-title":"Bioinformatics"},{"doi-asserted-by":"crossref","unstructured":"Buhler, J., and Tompa, M. (2001, January 22\u201325). Finding Motifs Using Random Projections. Proceedings of the Fifth Annual International Conference on Computational Molecular Biology(RECOMB), Montreal, QC, Canada.","key":"ref_6","DOI":"10.1145\/369133.369172"},{"doi-asserted-by":"crossref","unstructured":"Price, A., Ramabhadran, S., and Pevzner, P. (2003, January 27\u201330). Finding Subtle Motifs by Branching from the Sample Strings. Bioinformatics Supplementary Edition. Proceedings of the Second European Conference on Computational Biology (ECCB), Paris, France.","key":"ref_7","DOI":"10.1093\/bioinformatics\/btg1072"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1093\/bioinformatics\/18.10.1374","article-title":"Finding motifs in the twilight zone","volume":"18","author":"Keich","year":"2002","journal-title":"Bioinformatics"},{"unstructured":"Pevzner, P., and Sze, S.H. (2000, January 19\u201323). Combinatorial Approaches to Finding Subtle Signals in DNA Sequences. Proceedings of the English International Conference on Intelligent Systems for Molecular Biology, San Diego, CA, USA.","key":"ref_9"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1093\/bioinformatics\/18.suppl_1.S354","article-title":"Finding composite regulatory patterns in DNA sequences","volume":"18","author":"Eskin","year":"2002","journal-title":"Bioinformatics"},{"doi-asserted-by":"crossref","unstructured":"Sagot, M. (1998, January 20\u201324). Spelling Approximate Repeated or Common Motifs Using a Suffix Tree. Proceedings of the Third Latin American Theoretical Informatics Symposium (LATIN), Campinas, Brazil.","key":"ref_11","DOI":"10.1007\/BFb0054337"},{"doi-asserted-by":"crossref","unstructured":"Marsan, L., and Sagot, M.F. (2000, January 8\u201311). Extracting Structured Motifs Using a Suffix Tree\u2013Algorithms And Application to Promoter Consensus Identification. Proceedings of the Fourth Annual International Conference on Computational Molecular Biology(RECOMB), Tokyo, Japan.","key":"ref_12","DOI":"10.1145\/332306.332553"},{"doi-asserted-by":"crossref","unstructured":"Carvalho, A.M., Freitas, A.T., Oliveira, A.L., and Sagot, M.F. (2005, January 17\u201321). A Highly Scalable Algorithm for the Extraction of Cis-Regulatory Regions. Proceedings of the Third Asia Pacfic Bioinformatics Conference (APBC), Singapore, Singapore.","key":"ref_13","DOI":"10.1142\/9781860947322_0027"},{"unstructured":"Pisanti, N., Carvalho, A.M., Marsan, L., and Sagot, M. (2003, January 27\u201330). Finding Subtle Motifs by Branching from the Sample Strings. Bioinformatics Supplementary Edition. Proceedings of the Second European Conference on Computational Biology (ECCB), Paris, France.","key":"ref_14"},{"unstructured":"Evans, P., and Smith, A. (August, January 30). Toward Optimal Motif Enumeration. Proceedings of Algorithms and Data Structures, 8th International Workshop (WADS), Ontario, ON, Canada.","key":"ref_15"},{"doi-asserted-by":"crossref","unstructured":"Chin, F.Y.L., and Leung, H.C.M. (2005, January 17\u201321). Voting Algorithms for Discovering Long Motifs. Proceedings of the Third Asia-Pacific Bioinformatics Conference (APBC), Singapore, Singapore.","key":"ref_16","DOI":"10.1142\/9781860947322_0026"},{"doi-asserted-by":"crossref","unstructured":"Kuksa, P.P., and Pavlovic, V. (2010). Efficient motif finding algorithms for large-alphabet inputs. BMC Bioinf., 11.","key":"ref_17","DOI":"10.1186\/1471-2105-11-S8-S1"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1089\/cmb.2005.12.1117","article-title":"Exact algorithms for planted motif challenge problems","volume":"12","author":"Rajasekaran","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1756-0500-4-54","article-title":"A speedup technique for (l, d) motif finding algorithms","volume":"4","author":"Rajasekaran","year":"2011","journal-title":"BMC Res. Notes"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/TCBB.2007.70241","article-title":"Fast and practical algorithms for planted (l, d) motif search","volume":"4","author":"Davila","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"doi-asserted-by":"crossref","unstructured":"Davila, J., Balla, S., and Rajasekaran, S. (2007). Fast and Practical Algorithms for Planted (l, d) Motif Search, University of Connecticut. Technical Report.","key":"ref_21","DOI":"10.1109\/TCBB.2007.70241"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1186\/1471-2105-12-410","article-title":"PMS5: An efficient exact algorithm for the (l,d) motif finding problem","volume":"12","author":"Dinh","year":"2011","journal-title":"BMC Bioinf."},{"doi-asserted-by":"crossref","unstructured":"Bandyopadhyay, S., and Sahni, S. (2012, January 23\u201325). PSM6: A Fast Algorithm for Motif Discovery. Proceedings of the Second IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), Las Vegas, NV, USA.","key":"ref_23","DOI":"10.1109\/ICCABS.2012.6182627"},{"unstructured":"Dasai, N.S., Desh, R., and Zubair, M. (July, January 28). An Efficient Multicore Implementation of Planted Motif Problem. Proceedings of the International Conference on High Performance Computing and Simulation (HPCS), Caen, France.","key":"ref_24"},{"doi-asserted-by":"crossref","unstructured":"Dasai, N.S., Desh, R., and Zubair, M. (2011, January 4\u20138). High Performance Implementation of Planted Motif Problem using Suffix trees. Proceedings of the International Conference on High Performance Computing and Simulation (HPCS), Istanbul, Turkey.","key":"ref_25","DOI":"10.1109\/HPCSim.2011.5999825"},{"unstructured":"Horowitz, E., Sahni, S., and Mehta, D. (2007). Fundamentals of Data Structures in C++, Silicon Press.","key":"ref_26"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/805\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:50:42Z","timestamp":1760219442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,18]]},"references-count":26,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040805"],"URL":"https:\/\/doi.org\/10.3390\/a6040805","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,11,18]]}}}