PMS6MC: A Multicore Algorithm for Motif Discovery

Overview

Journal Algorithms

Publisher MDPI

Date 2014 Oct 14

PMID 25309700

Authors

Shibdas Bandyopadhyay

Sartaj Sahni

Sanguthevar Rajasekaran

Affiliations

Soon will be listed here.

Abstract

We develop an efficient multicore algorithm, PMS6MC, for the ()-motif discovery problem in which we are to find all strings of length that appear in every string of a given set of strings with at most 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.

References

Hertz G, Stormo G . Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics. 1999; 15(7-8):563-77. DOI: 10.1093/bioinformatics/15.7.563. View

Dinh H, Rajasekaran S, Kundeti V . PMS5: an efficient exact algorithm for the (ℓ, d)-motif finding problem. BMC Bioinformatics. 2011; 12:410. PMC: 3269969. DOI: 10.1186/1471-2105-12-410. View

Buhler J, Tompa M . Finding motifs using random projections. J Comput Biol. 2002; 9(2):225-42. DOI: 10.1089/10665270252935430. View

Marsan L, Sagot M . Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification. J Comput Biol. 2000; 7(3-4):345-62. DOI: 10.1089/106652700750050826. View

Bailey T, Williams N, Misleh C, Li W . MEME: discovering and analyzing DNA and protein sequence motifs. Nucleic Acids Res. 2006; 34(Web Server issue):W369-73. PMC: 1538909. DOI: 10.1093/nar/gkl198. View

Lawrence C, Altschul S, Boguski M, Liu J, Neuwald A, Wootton J . Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science. 1993; 262(5131):208-14. DOI: 10.1126/science.8211139. View

Rajasekaran S, Balla S, Huang C . Exact algorithms for planted motif problems. J Comput Biol. 2005; 12(8):1117-28. DOI: 10.1089/cmb.2005.12.1117. View

Keich U, Pevzner P . Finding motifs in the twilight zone. Bioinformatics. 2002; 18(10):1374-81. DOI: 10.1093/bioinformatics/18.10.1374. View

Davila J, Balla S, Rajasekaran S . Fast and practical algorithms for planted (l, d) motif search. IEEE/ACM Trans Comput Biol Bioinform. 2007; 4(4):544-52. DOI: 10.1109/TCBB.2007.70241. View

10.

Eskin E, Pevzner P . Finding composite regulatory patterns in DNA sequences. Bioinformatics. 2002; 18 Suppl 1:S354-63. DOI: 10.1093/bioinformatics/18.suppl_1.s354. View

11.

Price A, Ramabhadran S, Pevzner P . Finding subtle motifs by branching from sample strings. Bioinformatics. 2003; 19 Suppl 2:ii149-55. DOI: 10.1093/bioinformatics/btg1072. View

12.

Rajasekaran S, Dinh H . A speedup technique for (l, d)-motif finding algorithms. BMC Res Notes. 2011; 4:54. PMC: 3063805. DOI: 10.1186/1756-0500-4-54. View

13.

Bandyopadhyay S, Sahni S, Rajasekaran S . PMS6: A Fast Algorithm for Motif Discovery. IEEE Int Conf Comput Adv Bio Med Sci. 2013; :1-6. PMC: 3744182. DOI: 10.1109/ICCABS.2012.6182627. View

14.

Pevzner P, Sze S . Combinatorial approaches to finding subtle signals in DNA sequences. Proc Int Conf Intell Syst Mol Biol. 2000; 8:269-78. View

15.

Kuksa P, Pavlovic V . Efficient motif finding algorithms for large-alphabet inputs. BMC Bioinformatics. 2010; 11 Suppl 8:S1. PMC: 2966288. DOI: 10.1186/1471-2105-11-S8-S1. View