title: A uniform projection method for motif discovery in DNA sequences.
abstract: Buhler and Tompa introduced the random projection algorithm for the motif discovery problem and demonstrated that this algorithm performs well on both simulated and biological samples. We describe a modification of the random projection algorithm, called the uniform projection algorithm, which utilizes a different choice of projections. We replace the random selection of projections by a greedy heuristic that approximately equalizes the coverage of the projections. We show that this change in selection of projections leads to improved performance on motif discovery problems. Furthermore, the uniform projection algorithm is directly applicable to other problems where the random projection algorithm has been used, including comparison of protein sequence databases.
authors.affiliation: Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093-0114, USA. braphael@ucsd.edu
authors.forename: Benjamin
authors.initials: B
authors.lastname: Raphael
authors.forename: Lung-Tien
authors.initials: LT
authors.lastname: Liu
authors.forename: George
authors.initials: G
authors.lastname: Varghese
mesh_terms: D000465:Algorithms; D001665:Binding Sites / Q000235:genetics; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000737:chemistry / Q000235:genetics* / Q000378:metabolism; D009010:Monte Carlo Method; D009154:Mutation / Q000235:genetics; D050436:Regulatory Elements, Transcriptional / Q000235:genetics*; D014157:Transcription Factors / Q000378:metabolism
chemical_list: D014157:Transcription Factors; D004247:DNA