2001 FindingMotifsUsingRandomProject

(Buhler & Tompa, 2001) ⇒ Jeremy Buhler, and Martin Tompa. (2001). “Finding Motifs Using Random Projections.” In: Proceedings of the fifth annual International Conference on Computational biology. ISBN:1-58113-353-7 doi:10.1145/369133.369172

Subject Headings: Time-Series Data Mining.

Notes

Cited By

Quotes

Abstract

Pevzner and Sze [23] considered a precise version of the motif discovery problem and simultaneously issued an algorithmic challenge: find a motif M of length 15, where each planted instance differs from M in 4 positions. Whereas previous algorithms all failed to solve this (15, 4) - motif problem. Pevzner and Sze introduced algorithms that succeeded.

However, their algorithms failed to solve the considerably more difficult (14, 4) -, (16, 5) -, and (18, 6) - motif problems.

We introduce a novel motif discovery algorithm based on the use of random projections of the input's substrings.

Experiments on simulated data demonstrate that this algorithm performs better than existing algorithms and, in particular, typically solves the difficult (14, 4) -, (16, 5) -, and (18, 6) - motif problems quite efficiently. A probabilistic estimate shows that the small values of d for which the algorithm fails to recover the planted (l, d) - motif are in all likelihood inherently impossible to solve. We also present experimental results on realistic biological data by identifying ribosome binding sites in prokaryotes as well as a number of known transcriptional regulatory motifs in eukaryotes.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2001 FindingMotifsUsingRandomProject	Jeremy Buhler Martin Tompa			Finding Motifs Using Random Projections				10.1145/369133.369172		2001