title: An extension and novel solution to the (l,d)-motif challenge problem.
abstract: The (l,d)-motif challenge problem, as introduced by Pevzner and Sze, is a mathematical abstraction of the DNA functional site discovery task. Here we expand the (l,d)-motif problem to more accurately model this task and present a novel algorithm to solve this extended problem. This algorithm is guaranteed to find all (l,d)-motifs in a set of input sequences with unbounded support and length. We demonstrate the performance of the algorithm on publicly available datasets and show that the algorithm deterministically enumerates the optimal motifs.
authors.affiliation: Department of Chemical Engineering, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA. marksty@mit.edu
authors.forename: Mark P
authors.initials: MP
authors.lastname: Styczynski
authors.forename: Kyle L
authors.initials: KL
authors.lastname: Jensen
authors.forename: Isidore
authors.initials: I
authors.lastname: Rigoutsos
authors.forename: Gregory N
authors.initials: GN
authors.lastname: Stephanopoulos
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D001665:Binding Sites / Q000235:genetics; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D004247:DNA