## 3 Pms6 mc
### Inner-Level Parallelization
#### 3.3.1 Finding Equivalence Classes in Parallel:
mSPELLER-16 using 16 cores varies from a low of 0.07 for (13,4) instances to 3.58 for (19,7) instances while the speed up for PMS6 MC using only one CPU with respect to gSPELLER-4 using 4 GPUs varies from a low of 0.03 for (13,4) instances to a high of 1.97 for (19, 7) instances. ## 6 Conclusions

We have developed a multicore version of PMS6 that achieves a speedup that ranges from a low of 2.75 for (13,4) challenging instances to a high of 6.62 for (17,6) challenging instances on a 6-core CPU. Our multicore algorithm is able to solve (23,9) challenging instances in 3.5 h, while the single core PMS6 algorithm takes 19 h. We estimate that our multicore algorithm is faster than other parallel algorithms for the motif search problem on large challenging instances. For example, we estimate that PMS6 MC can solve (19,7) instances 3.6 times faster than using our 6-core CPU mSPELLER-16 using the 16-core CPU of [25] and about two times faster than gSPELLER-4 can using four GPU devices. ## Acknowledgments

This research was supported, in part, by the National Science Foundation under grant 0829916 and the National Institutes of Health under grant R01-LM010101. This paper is an extended version of [1] and this research was supported, in part, by the National Science Foundation under grant 0829916 and the National Institutes of Health under grant R01-LM010101. ## Conflicts of Interest

The authors declare no conflict of interest. ## References

* [PERSON] et al. (2013) [PERSON]; [PERSON]; [PERSON] [PERSON] PSM6 MC: A Multicore Algorithm for Motif Discovery. In Proceedings of the Third IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), New Orleans, LA, USA, 12-14 June 2013. * [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON] On the complexity of finding common approximate substrings. _Theor. Comput. Sci._**2003**, _306_, 407-430. \begin{table}
\begin{tabular}{c c c c c c} \hline Algorithm & (13,4) & (15,5) & (17,6) & (19,7) & (21,8) \\ \hline PMSPrune & 53 s & 9 min & 69 min & 9.2 h & - \\ mSPELLER-16 & 2 s & 16.5 s & 2.5 min & 23.6 min & 3.7 h \\ gSPELLER-4 & 0.8 s & 7.2 s & 1.2 min & 13 min & 2.2 h \\ PMSPrune/mSPELLER-16 & 26.5 & 32.73 & 27.6 & 23.38 & - \\ PMSPrune/gSPELLER-4 & 66.25 & 75 & 57.5 & 42.46 & - \\ mSPELLER-16/PMS6 MC & 0.07 & 0.40 & 1.41 & 3.64 & - \\ gSPELLER-4/PMS6 MC & 0.03 & 0.17 & 0.68 & 2 & - \\ \hline \end{tabular}
\end{table} 
Table 5: Comparing mSPELLER and gSPELLER with PMS6 MC. * [PERSON] et al. (2006) [PERSON]; [PERSON]; [PERSON]; [PERSON] MEME: Discovering and analyzing DNA. _Nucleic Acids Res._**2006**, _34_, 369-373. * [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Detecting subtle sequence signals: A Gibbs sampling strategy for multiple alignment. _Science_**2003**, _262_, 208-214. * [PERSON] and [PERSON] (1999) [PERSON]; [PERSON] Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. _Bioinformatics_**1999**, _15_, 563-577. * [PERSON] and [PERSON] (2001) [PERSON]; [PERSON] [PERSON] Finding Motifs Using Random Projections. In Proceedings of the Fifth Annual International Conference on Computational Molecular Biology(RECOMB), Montreal, QC, Canada, 22-25 April 2001. * [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON] Finding Subtle Motifs by Branching from the Sample Strings. Bioinformatics Supplementary Edition. In Proceedings of the Second European Conference on Computational Biology (ECCB), Paris, France, 27-30 September 2003. * [PERSON] and [PERSON] (2002) [PERSON]; [PERSON] Finding motifs in the twilight zone. _Bioinformatics_**2002**, _18_, 1374-1381. * [PERSON] and [PERSON] (2000) [PERSON]; [PERSON] Combinatorial Approaches to Finding Subtle Signals in DNA Sequences. In Proceedings of the English International Conference on Intelligent Systems for Molecular Biology, San Diego, CA, USA, 19-23 August 2000; Volume 8, pp. 269-278. * [PERSON] and [PERSON] (2002) [PERSON]; [PERSON] [PERSON] Finding composite regulatory patterns in DNA sequences.