Combinatorial pattern discovery for scientific data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combinatorial pattern discovery for scientific data: some preliminary results

Full text

Pdf (1.04 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1994 ACM SIGMOD international conference on Management of data table of contents

Minneapolis, Minnesota, United States

Pages: 115 - 125

Year of Publication: 1994

ISBN:0-89791-639-5

Also published in ...

Authors

Jason Tsong-Li Wang	Computer and Information Science, New Jersey Institute of Technology, Newark, NJ
Gung-Wei Chirn	Computer and Information Science, New Jersey Institute of Technology, Newark, NJ
Thomas G. Marr	Cold Spring Harbor Laboratory, 100 Bungtown Rodad, Cold Spring Harbor, NY
Bruce Shapiro	Image Processing Section, Laboratory of Mathematical Biology, Division of Cancer Biology and Diagnosis, National Cancer, Institute, National Institutes of Health, Frederick, MD
Dennis Shasha	Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY
Kaizhong Zhang	Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 50, Citation Count: 42

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/191839.191863 What is a DOI?

ABSTRACT

Suppose you are given a set of natural entities (e.g., proteins, organisms, weather patterns, etc.) that possess some important common externally observable properties. You also have a structural description of the entities (e.g., sequence, topological, or geometrical data) and a distance metric. Combinatorial pattern discovery is the activity of finding patterns in the structural data that might explain these common properties based on the metric.This paper presents an example of combinatorial pattern discovery: the discovery of patterns in protein databases. The structural representation we consider are strings and the distance metric is string edit distance permitting variable length don't cares. Our techniques incorporate string matching algorithms and novel heuristics for discovery and optimization, most of which generalize to other combinatorial structures. Experimental results of applying the techniques to both generated data and functionally related protein families obtained from the Cold Spring Harbor Laboratory show the effectiveness of the proposed techniques. When we apply the discovered patterns to perform protein classification, they give information that is complementary to the best protein classifier available today.

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	Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
	2	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
	3	D. J. Bacon and W. J. Anderson. Multiple sequence alignment. Journal of Molecular Biology, 191:153- 161, 1986.
	4	A. Bairoeh. PROSITE: A dictionary of sites and patterns in proteins. Nucleic Acids Research, 20:2013-2018, 1992.
	5	A. Bairoch and B. Boeekmann. The SWISS- PROT protein sequence data bank. Nucleic Acidn Research, 20:2019-2022, 1992.
	6	W. Buntine and M. D. Alto, editors. Collected Notes on the Workshop for Patfern Discover# in Large Databases. Technical Report FIA-91- 07, NASA Ames Research Center, Mof{'ett Field, California, April 1991.
	7	Andrea Califano , Isidore Rigoutsos, FLASH: A Fast Look-Up Algorithm for String Homology, Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, p.56-64, July 01, 1993
	8	W. G. Cochran. Sampling Techniques. Wiley, 1977.
	9	V. Dhar , A. Tuzhilin, Abstract-Driven Pattern Discovery in Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.926-938, December 1993 [doi>10.1109/69.250075]
	10	W. J. Frawley, G. Piatetsky-Shapiro, and C. J. Matheus. Knowledge discovery in databases: An overview. In G. Piatetsky-Shapiro and W. J. Frawley, editors, Knowledge Discovery in Databases, pages 1-27. AAAI/MIT Press, 1991.
	11	Karen A. Frenkel, The human genome project and informatics, Communications of the ACM, v.34 n.11, p.40-51, Nov. 1991 [doi>10.1145/125490.125492]
	12	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	13	Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
	14	Jiawei Han , Yandong Cai , Nick Cercone, Knowledge Discovery in Databases: An Attribute-Oriented Approach, Proceedings of the 18th International Conference on Very Large Data Bases, p.547-559, August 23-27, 1992
	15	S. Henikoff and J. G. Henikoff. Automated assembly of protein blocks for database searching. Nucleic Acids Research, 19(23):6565-6572, 1991.
	16	Wen-Chi Hou , Gultekin Ozsoyoglu, Statistical estimators for aggregate relational algebra queries, ACM Transactions on Database Systems (TODS), v.16 n.4, p.600-654, Dec. 1991 [doi>10.1145/115302.115300]
	17	Lucas Chi Kwong Hui, Color Set Size Problem with Application to String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.230-243, April 29-May 01, 1992
	18	Lawrence Hunter, Artificial intelligence and molecular biology, American Association for Artificial Intelligence, Menlo Park, CA, 1993
	19	Nabil Kamel , M. Delobel , Thomas G. Marr , Robert Robbins , Jean Thierry-Mieg , Akira Tsugita, Data and Knowledge Bases for Genome Mapping: What Lies Ahead? (Panel), Proceedings of the 17th International Conference on Very Large Data Bases, p.309, September 03-06, 1991
	20	G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989 [doi>10.1016/0196-6774(89)90010-2]
	21	R. J. Lipton, T. G. Marr, and J. D. Welsh. Computational approaches to discovering semantics in molecular biology. Proceedings of the IEEE, 77(7):1056-1060, July 1989.
	22	Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
	23	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	24	Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
	25	F. Olken , D. Rotem, Random sampling from B+ trees, Proceedings of the 15th international conference on Very large data bases, p.269-277, July 1989, Amsterdam, The Netherlands
	26	M. A. Roytberg. A search for common patterns in many sequences. Computer Applications in #he Biosciences, 8(1):57-64, 1992.
	27	D. Sankoff and J. B. Kruskal, editors. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA, 1983.
	28	B. A. Shapiro and K. Zhang. Comparing multipie RNA secondary structures using tree comparisons. Computer Applications in the Biosciences, 6(zl):309-31#, 1000.
	29	D. Shasha, J. T. L. Wang, K. Zhang, and F. Y. Shih. Exact and approximate algorithms for unordered tree matching. IEEE Transactions on Systems, Man and Cybernetics, 24(3), March 1994.
	30	Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990 [doi>10.1145/96105.96111]
	31	Avi Silberschatz , Michael Stonebraker , Jeff Ullman, Database systems: achievements and opportunities, Communications of the ACM, v.34 n.10, p.110-120, Oct. 1991 [doi>10.1145/125223.125272]
	32	Bharathi Subramanian , Stanley B. Zdonik , Theodore W. Leung , Scott L. Vandenberg, Ordered Types in the AQUA Data Model, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.115-135, August 30-September 01, 1993
	33	Shalom Tsur, Data dredging, Data Engineering, v.13 n.4, p.58-63, Dec. 1990
	34	M. Vingron and P. Argos. A fast and sensitive multiple sequence alignment algorithm. Computer Applications in the Biosciences, 5:115-122, 1989.
	35	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
	36	J. T. -L. Wang , K. Zhang , K. Jeong , D. Shasha, A System for Approximate Tree Matching, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.559-571, August 1994 [doi>10.1109/69.298173]
	37	Tsong-Li Wang , Dennis Shasha, Query processing for distance metrics, Proceedings of the sixteenth international conference on Very large databases, p.602-613, September 1990, Brisbane, Australia
	38	Michael S. Waterman, Mathematical Methods for DNA Sequences, CRC Press, Inc., Boca Raton, FL, 1989
	39	Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
	40	K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]
	41	Kaizhong Zhang , Dennis Shasha , Jason T. L. Wang, Approximate tree matching in the presence of variable length don't cares, Journal of Algorithms, v.16 n.1, p.33-66, Jan. 1994 [doi>10.1006/jagm.1994.1003]
	42	G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison Wesley, Reading, MA, 1949.

CITED BY 42

	P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, ACM SIGMOD Record, v.25 n.2, p.282-293, June 1996
	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
	Jiong Yang , Wei Wang , Philip S. Yu , Jiawei Han, Mining long sequential patterns in a noisy environment, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Yun-Wu Huang , Philip S. Yu, Adaptive query processing for time-series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.282-286, August 15-18, 1999, San Diego, California, United States
	Helen Pinto , Jiawei Han , Jian Pei , Ke Wang , Qiming Chen , Umeshwar Dayal, Multi-dimensional sequential pattern mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Jason T. L. Wang , Kaizhong Zhang , Dennis Shasha, Pattern matching and pattern discovery in scientific, program, and document databases, ACM SIGMOD Record, v.24 n.2, p.487, May 1995
	Jason T. L. Wang , Qicheng Ma , Dennis Shasha , Cathy H. Wu, Application of neural networks to biological data mining: a case study in protein sequence classification, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.305-309, August 20-23, 2000, Boston, Massachusetts, United States
	Bin Li , Dennis Shasha, Free parallel data mining, ACM SIGMOD Record, v.27 n.2, p.541-543, June 1998
	Laxmi Parida , Isidore Rigoutsos , Aris Floratos , Dan Platt , Yuan Gao, Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.297-308, January 09-11, 2000, San Francisco, California, United States
	Yen-Liang Chen , Shih-Sheng Chen , Ping-Yu Hsu, Mining hybrid sequential patterns and sequential rules, Information Systems, v.27 n.5, p.345-362, July 2002
	Ming-Syan Chen , Jong Soo Park , Philip S. Yu, Efficient Data Mining for Path Traversal Patterns, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.209-221, March 1998
	Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.813-825, September 1997
	Xiong Wang , Jason T. L. Wang , Dennis Shasha , Bruce A. Shapiro , Isidore Rigoutsos , Kaizhong Zhang, Finding Patterns in Three-Dimensional Graphs: Algorithms and Applications to Scientific Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.731-749, July 2002
	Claudio Bettini , X. Sean Wang , Sushil Jajodia , Jia-Ling Lin, Discovering Frequent Event Patterns with Multiple Granularities in Time Sequences, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.222-237, March 1998
	Rong She , Fei Chen , Ke Wang , Martin Ester , Jennifer L. Gardy , Fiona S. L. Brinkman, Frequent-subsequence-based prediction of outer membrane proteins, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	M. Garofalakis , R. Rastogi , K. Shim, Mining Sequential Patterns with Regular Expression Constraints, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.530-552, May 2002
	Masahiro Hirao , Hiromasa Hoshino , Ayumi Shinohara , Masayuki Takeda , Setsuo Arikawa, A practical algorithm to find the best subsequence patterns, Theoretical Computer Science, v.292 n.2, p.465-479, 27 January 2003
	Sanghyun Park , Wesley W. Chu , Jeehee Yoon , Jungim Won, Similarity search of time-warped subsequences via a suffix tree, Information Systems, v.28 n.7, p.867-883, 1 October 2003
	Jia-Wei Han , Jian Pei , Xi-Feng Yan, From sequential pattern mining to structured pattern mining: a pattern-growth approach, Journal of Computer Science and Technology, v.19 n.3, p.257-279, May 2004
	J. T. L. Wang , Q. Ma , D. Shasha , C. H. Wu, New techniques for extracting features from protein sequences, IBM Systems Journal, v.40 n.2, p.426-441, February 2001
	Ke Wang , Yabo Xu , Jeffrey Xu Yu, Scalable sequential pattern mining for biological sequences, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Jianyong Wang , Helen Pinto , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1424-1440, November 2004
	Abhijit Chattaraj , Laxmi Parida, An inexact-suffix-tree-based algorithm for detecting extensible patterns, Theoretical Computer Science, v.335 n.1, p.3-14, 20 May 2005
	Qing Li , Ling Feng , Allan Wong, From intra-transaction to generalized inter-transaction: landscaping multidimensional contexts in association rule mining, Information Sciences—Informatics and Computer Science: An International Journal, v.172 n.3-4, p.361-395, 9 June 2005
	Park Sang Hyun , Chu Wesley W., Discovering and Matching Elastic Rules from Sequence Databases, Fundamenta Informaticae, v.47 n.1-2, p.75-90, January 2001
	Thomas Legler , Wolfgang Lehner , Andrew Ross, Data mining with the SAP NetWeaver BI accelerator, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Senqiang Zhou , Ke Wang, Localization Site Prediction for Membrane Proteins by Integrating Rule and SVM Classification, IEEE Transactions on Knowledge and Data Engineering, v.17 n.12, p.1694-1705, December 2005
	Jiong Yang , Wei Wang , Philip S. Yu, Mining Surprising Periodic Patterns, Data Mining and Knowledge Discovery, v.9 n.2, p.189-216, September 2004
	Ling Feng , Jeffrey Xu Yu , Hongjun Lu , Jiawei Han, A template model for multidimensional inter-transactional association rules, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.2, p.153-175, October 2002
	Mika Klemettinen , Heikki Mannila , Hannu Toivonen, Rule Discovery in Telecommunication AlarmData, Journal of Network and Systems Management, v.7 n.4, p.395-423, 7
	Ke Wang, Discovering Patterns from Large and Dynamic Sequential Data, Journal of Intelligent Information Systems, v.9 n.1, p.33-56, July/Aug. 1997
	Minos Garofalakis , Rajeev Rastogi, Scalable data mining with model constraints, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.39-48, Dec. 2000
	Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
	Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, Proceedings of the 25th International Conference on Very Large Data Bases, p.223-234, September 07-10, 1999
	Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
	Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
	Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999
	Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997
	Enhong Chen , Huanhuan Cao , Qing Li , Tieyun Qian, Efficient strategies for tough aggregate constraint-based sequential pattern mining, Information Sciences: an International Journal, v.178 n.6, p.1498-1518, March, 2008
	Jau-hong Kao , Jen-hui Chuang , Tsaipei Wang, Chromosome classification based on the band profile similarity along approximate medial axis, Pattern Recognition, v.41 n.1, p.77-89, January, 2008
	R. B. V. Subramanyam , A. Goswami , Bhanu Prasad, Mining fuzzy temporal patterns from process instances with weighted temporal graphs, International Journal of Data Analysis Techniques and Strategies, v.1 n.1, p.60-77, August 2008
	Alberto Apostolico , Giorgio Satta, Discovering subword associations in strings in time linear in the output size, Journal of Discrete Algorithms, v.7 n.2, p.227-238, June, 2009