NDLI: Discovery of Delta Closed Patterns and Noninduced Patterns from Sequences

Content Provider	IEEE Xplore Digital Library
Author	Wong, A.K.C. Zhuang, D. Li, G.C.L. Lee, E.-S.A.
Copyright Year	1989
Abstract	Discovering patterns from sequence data has significant impact in many aspects of science and society, especially in genomics and proteomics. Here we consider multiple strings as input sequence data and substrings as patterns. In the real world, usually a large set of patterns could be discovered yet many of them are redundant, thus degrading the output quality. This paper improves the output quality by removing two types of redundant patterns. First, the notion of delta tolerance closed itemset is employed to remove redundant patterns that are not delta closed. Second, the concept of statistically induced patterns is proposed to capture redundant patterns which seem to be statistically significant yet their significance is induced by their strong significant subpatterns. It is computationally intense to mine these nonredundant patterns (delta closed patterns and noninduced patterns). To efficiently discover these patterns in very large sequence data, two efficient algorithms have been developed through innovative use of suffix tree. Three sets of experiments were conducted to evaluate their performance. They render excellent results when applying to genomics. The experiments confirm that the proposed algorithms are efficient and that they produce a relatively small set of patterns which reveal interesting information in the sequences.
Sponsorship	IEEE IEEE Comput. Soc. Tech. Committee on Data Eng IEEE Computer Society
Starting Page	1408
Ending Page	1421
Page Count	14
File Size	1961589
File Format	PDF
ISSN	10414347
Volume Number	24
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Itemsets Data mining Hidden Markov models Markov processes Algorithm design and analysis Frequency measurement Genomics suffix tree. Sequence pattern discovery delta closed patterns statistically induced patterns
Content Type	Text
Resource Type	Article
Subject	Information Systems Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An O(N/sup 2/) algorithm for discovering optimal Boolean pattern pairs

Mining Partially-Ordered Sequential Rules Common to Multiple Sequences

Discovering frequent episodes and learning hidden Markov models: a formal connection

FPS-Tree Algorithm to Find Top-k Closed Itemsets in Data Streams

Efficient Updating of Biological Sequence Analyses

Improving Activity Recognition by Segmental Pattern Mining

Efficient and Accurate Discovery of Patterns in Sequence Data Sets

New Methods for Inference of Local Tree Topologies with Recombinant SNP Sequences in Populations

An efficient algorithm for mining closed itemsets

Discovery of Delta Closed Patterns and Noninduced Patterns from Sequences

Similar Documents

An O(N/sup 2/) algorithm for discovering optimal Boolean pattern pairs

Mining Partially-Ordered Sequential Rules Common to Multiple Sequences

Discovering frequent episodes and learning hidden Markov models: a formal connection

FPS-Tree Algorithm to Find Top-k Closed Itemsets in Data Streams

Efficient Updating of Biological Sequence Analyses

Improving Activity Recognition by Segmental Pattern Mining

Efficient and Accurate Discovery of Patterns in Sequence Data Sets

New Methods for Inference of Local Tree Topologies with Recombinant SNP Sequences in Populations

An efficient algorithm for mining closed itemsets

Discovery of Delta Closed Patterns and Noninduced Patterns from Sequences