Finding motifs using random projections

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding motifs using random projections

Full text

Pdf (147 KB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the fifth annual international conference on Computational biology table of contents

Montreal, Quebec, Canada

Pages: 69 - 76

Year of Publication: 2001

ISBN:1-58113-353-7

Authors

Jeremy Buhler	Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA
Martin Tompa	Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 61, Citation Count: 26

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/369133.369172 What is a DOI?

Warning: The download time has expired please click on the item to try again.

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. D. Andersen, S. J. Taplitz, S. Wong, G. Bristol, B. Larkin, and H. R. Herschman. Metal-dependent binding of a factor in vivo to the metal-responsive elements of the metallothionein 1 gene promoter. Molecular and Cellular Biology, 7:3574-81, 1987.
	2	Timothy L. Bailey , Charles Elkan, Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization, Machine Learning, v.21 n.1-2, p.51-80, Oct./Nov. 1995 [doi>10.1007/BF00993379]
	3	Mathieu Blanchette, Algorithms for phylogenetic footprinting, Proceedings of the fifth annual international conference on Computational biology, p.49-58, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369170]
	4	Mathieu Blanchette , Benno Schwikowski , Martin Tompa, An Exact Algorithm to Identify Motifs in Orthologous Sequences from Multiple Species, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.37-45, August 19-23, 2000
	5	D. S. W. Boam, A. R. Clark, and K. Docherty. Positive and negative regulation of the human insulin gene by multiple trans-acting factors. Journal of Biological Chemistry, 265:8285-96, 1990.
	6	A. Brazma, I. Jonassen, J. Vilo, and E. Ukkonen. Predicting gene regulatory elements in silico on a genomic scale. Genome Research, 15:1202-1215, 1998.
	7	J. Buhler. Efficient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics, 2001. To appear.
	8	A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1-38, 1977.
	9	Y. M. Fraenkel, Y. Mandel, D. Friedberg, and H. Margalit. Identification of common motifs in unaligned DNA sequences: application to Escherichia coli Lrp regulon. Computer Applications in the Biosciences, 11(4):379-387, 1995.
	10	D. J. Galas, M. Eggert, and M. S. Waterman. Rigorous pattern-recognition methods for DNA sequences: Analysis of promoter sequences from Escherichia coli. Journal of Molecular Biology, 186(1):117-128, Nov. 1985.
	11	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	12	W. S. Hayes and M. Borodovsky. Deriving ribosomal binding site (RBS) statistical models from unannotated DNA sequences and the use of the RBS model for N-terminal prediction. In Pacific Symposium on Biocomputing, pages 279-290, 1998.
	13	G. Z. Hertz and G. D. Stormo. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics, 15(7/8):563-577, July/August 1999.
	14	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	15	M. Kozak. Comparison of initiation of protein synthesis in procaryotes, eucaryotes, and organelles. Microbiological Reviews, 47(1):1-45, 1983.
	16	C. E. Lawrence, S. F. Altschul, M. S. Boguski, J. S. Liu, A. F. Neuwald, and J. C. Wootton. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science, 262:208-214, 8 October 1993.
	17	C. E. Lawrence and A. A. Reilly. An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences. Proteins: Structure, Function, and Genetics, 7:41-51, 1990.
	18	B. Lewin. Genes VI. Oxford University Press, 1997.
	19	M. Linial, N. Linial, N. Tishby, and G. Yona. Global self-organization of all known protein sequences reveals inherent biological signatures. Journal of Molecular Biology, 268:539-556, 1997.
	20	C. J. McInerny, J. F. Partridge, G. E. Mikesell, D. P. Creemer, and L. L. Breeden. A novel Mcm1-dependent element in the SWI4, CLN3, CDC6, and CDC47 promoters activates M/G-specific transcription. Genes & Development, 11:1277-1288, 1997.
	21	A. L. Means and P. G. Farnham. Transcription initiation from the dihydrofolate reductase promoter is positioned by hip1 binding at the initiation site. Molecular and Cellular Biology, 10:653-61, 1990.
	22	S. Natsan and M. Gilman. Yy1 facilitates the association of serum response factor with the c-fos serum response element. Molecular and Cellular Biology, 15:5975-82, 1995.
	23	Pavel A. Pevzner , Sing-Hoi Sze, Combinatorial Approaches to Finding Subtle Signals in DNA Sequences, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.269-278, August 19-23, 2000
	24	Isidore Rigoutsos , Aris Floratos, Motif discovery without alignment or enumeration (extended abstract), Proceedings of the second annual international conference on Computational molecular biology, p.221-227, March 22-25, 1998, New York, New York, United States [doi>10.1145/279069.279118]
	25	Emily Rocke , Martin Tompa, An algorithm for finding novel gapped motifs in DNA sequences, Proceedings of the second annual international conference on Computational molecular biology, p.228-233, March 22-25, 1998, New York, New York, United States [doi>10.1145/279069.279119]
	26	Marie-France Sagot, Spelling Approximate Repeated or Common Motifs Using a Suffix Tree, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.374-390, April 20-24, 1998
	27	Saurabh Sinha , Martin Tompa, A Statistical Method for Finding Transcription Factor Binding Sites, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.344-354, August 19-23, 2000
	28	R. Staden. Methods for discovering novel motifs in nucleic acid sequences. Computer Applications in the Biosciences, 5(4):293-298, 1989.
	29	Martin Tompa, An Exact Method for Finding Short Motifs in Sequences, with Application to the Ribosome Binding Site Problem, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.262-271, August 06-10, 1999
	30	J. van Helden, B. Andr~, and J. Collado-Vides. Extracting regulatory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies. Journal of Molecular Biology, 281(5):827-842, Sept. 4 1998.
	31	E. Wingender, P. Dietze, H. Karas, and R. Kn~ppel. TRANSFAC: a database on transcription factors and their DNA binding sites. Nucleic Acids Research, 24(1):238-241, 1996. http://transfac.gbfbraunschweig. de/TRANSFAC/.

CITED BY 26

	Uri Keich , Pavel A. Pevzner, Finding motifs in the twilight zone, Proceedings of the sixth annual international conference on Computational biology, p.195-204, April 18-21, 2002, Washington, DC, USA
	Yoseph Barash , Gal Elidan , Nir Friedman , Tommy Kaplan, Modeling dependencies in protein-DNA binding sites, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.28-37, April 10-14, 2003, Berlin, Germany
	Darya Chudova , Padhraic Smyth, Pattern discovery in sequences under a Markov assumption, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Eleazar Eskin, From profiles to patterns and back again: a branch and bound algorithm for finding near optimal motif profiles, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.115-124, March 27-31, 2004, San Diego, California, USA
	Xiaoming Wu , Bo Wang , Changxin Song , Jingzhi Cheng, A combined model and a varied Gibbs sampling algorithm used for motif discovery, Proceedings of the second conference on Asia-Pacific bioinformatics, p.99-104, January 01, 2004, Dunedin, New Zealand
	Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California
	Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Bill Chiu , Eamonn Keogh , Stefano Lonardi, Probabilistic discovery of time series motifs, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Jeremy Buhler, Provably sensitive Indexing strategies for biosequence similarity search, Proceedings of the sixth annual international conference on Computational biology, p.90-99, April 18-21, 2002, Washington, DC, USA
	Yoshiki Tanaka , Kazuhisa Iwamoto , Kuniaki Uehara, Discovery of Time-Series Motif from Multi-Dimensional Data Based on MDL Principle, Machine Learning, v.58 n.2-3, p.269-300, February 2005
	Alexandr Andoni , Piotr Indyk, Efficient algorithms for substring near neighbor problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1203-1212, January 22-26, 2006, Miami, Florida
	Jessica Lin , Eamonn Keogh , Li Wei , Stefano Lonardi, Experiencing SAX: a novel symbolic representation of time series, Data Mining and Knowledge Discovery, v.15 n.2, p.107-144, October 2007
	Andrea F. Lobo , Ganesh R. Baliga, NP-completeness for all computer science undergraduates: a novel project-based curriculum, Journal of Computing Sciences in Colleges, v.21 n.6, p.53-63, June 2006
	C. Iliopoulos , K. Perdikuri , E. Theodoridis , A. Tsakalidis , K. Tsichlas, Algorithms for extracting motifs from biological weighted sequences, Journal of Discrete Algorithms, v.5 n.2, p.229-242, June, 2007
	Dragomir Yankov , Eamonn Keogh , Jose Medina , Bill Chiu , Victor Zordan, Detecting time series motifs under uniform scaling, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Eran Segal , Yoseph Barash , Itamar Simon , Nir Friedman , Daphne Koller, From promoter sequence to expression: a probabilistic framework, Proceedings of the sixth annual international conference on Computational biology, p.263-272, April 18-21, 2002, Washington, DC, USA
	Bill C. Chang , Asanga Ratnaweera , Saman K. Halgamuge , Harry C. Watson, Particle Swarm Optimisation for Protein Motif Discovery, Genetic Programming and Evolvable Machines, v.5 n.2, p.203-214, June 2004
	Li Wei , Eamonn Keogh , Xiaopeng Xi , Melissa Yoder, Efficiently finding unusual shapes in large image databases, Data Mining and Knowledge Discovery, v.17 n.3, p.343-376, December 2008
	Alexandr Andoni , Piotr Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, v.51 n.1, January 2008
	Henry C. M. Leung , Francis Y. L. Chin, An efficient motif discovery algorithm with unknown motif length and number of binding sites, International Journal of Data Mining and Bioinformatics, v.1 n.2, p.201-215, September 2006
	Jaime Davila , Sudha Balla , Sanguthevar Rajasekaran, Fast and Practical Algorithms for Planted (l, d) Motif Search, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.4, p.544-552, October 2007
	Mehmet Kaya, MOGAMOD: Multi-objective genetic algorithm for motif discovery, Expert Systems with Applications: An International Journal, v.36 n.2, p.1039-1047, March, 2009
	Ruqian Lu , Caiyan Jia , Shaofang Zhang , Lusheng Chen , Hongyu Zhang, An Exact Data Mining Method for Finding Center Strings and All Their Instances, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.509-522, April 2007
	Francis Chin , Henry C. M. Leung, DNA Motif Representation with Nucleotide Dependency, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.1, p.110-119, January 2008
	Dietmar H. Dorr , Anne M. Denton, Establishing relationships among patterns in stock market data, Data & Knowledge Engineering, v.68 n.3, p.318-337, March, 2009
	Stefano Lonardi , Jessica Lin , Eamonn Keogh , Bill Chiu, Efficient discovery of unusual patterns in time series, New Generation Computing, v.25 n.1, p.61-93, January 2007