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 length l that appear in every string of a given set of strings with at most d mismatches. 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 pre-processing. The pre-processing time for PMS6 is 34 times faster than that for PMS5 for (23,9) instances. When pre-processing 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.affiliation: Department of CISE, University of Florida, Gainesville, FL 32611, USA.
authors.forename: Shibdas
authors.initials: S
authors.lastname: Bandyopadhyay
authors.affiliation: Department of CISE, University of Florida, Gainesville, FL 32611, USA.
authors.forename: Sartaj
authors.initials: S
authors.lastname: Sahni
authors.affiliation: Department of CSE, University of Connecticut, Storrs, CT 06269, USA.
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D019295:Computational Biology / Q000379:methods*; D015233:Models, Statistical; D011381:Programming Languages; D020539:Sequence Analysis, Protein / Q000379:methods; D012984:Software
keywords: PMS6; approximate string search; bioinformatics; motif discovery; motif search; planted motifs