title: Finding motifs in DNA sequences using low-dispersion sequences.
abstract: Motif finding problems, abstracted as the planted (l, d)-motif finding problem, are a major task in molecular biology--finding functioning units and genes. In 2002, the random projection algorithm was introduced to solve the challenging (15, 4)-motif finding problem by using randomly chosen templates. Two years later, a so-called uniform projection algorithm was developed to improve the random projection algorithm by means of low-dispersion sequences generated by coverings. In this article, we introduce an improved projection algorithm called the low-dispersion projection algorithm, which uses low-dispersion sequences generated by developed almost difference families. Compared with the random projection algorithm, the low-dispersion projection algorithm can solve the (l, d)-motif finding problem with fewer templates without decreasing the success rate.
authors.affiliation: 1 Graduate School of Systems and Information Engineering, University of Tsukuba , Tsukuba, Ibaraki, Japan .
authors.forename: Xun
authors.initials: X
authors.lastname: Wang
authors.forename: Ying
authors.initials: Y
authors.lastname: Miao
authors.forename: Minquan
authors.initials: M
authors.lastname: Cheng
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D016384:Consensus Sequence; D017422:Sequence Analysis, DNA / Q000379:methods*