title: PMS6: A Fast Algorithm for Motif Discovery.
abstract: We propose a new algorithm, PMS6, 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. The run time ratio PMS5/PMS6, where PMS5 is the fastest previously known algorithm for motif discovery in large instances, ranges from a high of 2.20 for the (21,8) challenge instances to a low of 1.69 for the (17,6) challenge instances. Both PMS5 and PMS6 require some amount of preprocessing. The preprocessing time for PMS6 is 34 times faster than that for PMS5 for (23,9) instances. When preprocessing time is factored in, the run time ratio PMS5/PMS6 is as high as 2.75 for (13,4) instances and as low as 1.95 for (17,6) instances.
authors: Department of CISE, University of Florida, Gainesville, FL 32611.
authors: Shibdas
authors: S
authors: Bandyopadhyay
authors: Sartaj
authors: S
authors: Sahni
authors: Sanguthevar
authors: S
authors: Rajasekaran
keywords: Planted motif search; string algorithms
references: Bioinformatics. 1999 Jul-Aug;15(7-8):563-77
references: 10487864
references: BMC Bioinformatics. 2011 Oct 24;12:410
references: 22024209
references: J Comput Biol. 2002;9(2):225-42
references: 12015879
references: BMC Res Notes. 2011 Mar 08;4:54
references: 21385438
references: J Comput Biol. 2000;7(3-4):345-62
references: 11108467
references: Nucleic Acids Res. 2006 Jul 1;34(Web Server issue):W369-73
references: 16845028
references: Science. 1993 Oct 8;262(5131):208-14
references: 8211139
references: J Comput Biol. 2005 Oct;12(8):1117-28
references: 16241901
references: Bioinformatics. 2002 Oct;18(10):1374-81
references: 12376382
references: IEEE/ACM Trans Comput Biol Bioinform. 2007 Oct-Dec;4(4):544-52
references: 17975266
references: Bioinformatics. 2002;18 Suppl 1:S354-63
references: 12169566
references: Bioinformatics. 2003 Oct;19 Suppl 2:ii149-55
references: 14534184
references: Proc Int Conf Intell Syst Mol Biol. 2000;8:269-78
references: 10977088
references: BMC Bioinformatics. 2010 Oct 26;11 Suppl 8:S1
references: 21034426