NDLI: An algorithm for finding the largest approximately common substructures of two trees

Content Provider	IEEE Xplore Digital Library
Author	Wang, J.T.L. Shapiro, B.A. Shasha, D. Zhang, K. Currey, K.M.
Copyright Year	1979
Abstract	Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology and natural language processing. We consider a substructure of an ordered labeled tree T to be a connected subgraph of T. Given two ordered labeled trees T/sub 1/ and T/sub 2/ and an integer d, the largest approximately common substructure problem is to find a substructure U/sub 1/ of T/sub 1/ and a substructure U/sub 2/ of T/sub 2/ such that U/sub 1/ is within edit distance d of U/sub 2/ and where there does not exist any other substructure V/sub 1/ of T/sub 1/ and V/sub 2/ of T/sub 2/ such that V/sub 1/ and V/sub 2/ satisfy the distance constraint and the sum of the sizes of V/sub 1/ and V/sub 2/ is greater than the sum of the sizes of U/sub 1/ and U/sub 2/. We present a dynamic programming algorithm to solve this problem, which runs as fast as the fastest known algorithm for computing the edit distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to discovering motifs in multiple RNA secondary structures (which are ordered labeled trees).
Sponsorship	IEEE Computer Society
Starting Page	889
Ending Page	895
Page Count	7
File Size	136315
File Format	PDF
ISSN	01628828
Volume Number	20
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1998-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	RNA Tree graphs Pattern recognition Costs Pediatrics Natural language processing Dynamic programming Sequences Tree data structures Heuristic algorithms
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence Computational Theory and Mathematics Computer Vision and Pattern Recognition Software

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 algorithm for finding a common structure shared by a family of strings

Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment

Document image decoding by heuristic search

A metric between unrooted and unordered trees and its bottom-up computing method

Bayesian and Decision Tree Approaches for Pattern Recognition Including Feature Measurement Costs

A comparative study of two search strategies for connected word recognition: dynamic programming and heuristic search

Polynomial-time metrics for attributed trees

A Dynamic Programming Algorithm for the Distance Between Two Finite Areas

A Tree-to-Tree Distance and Its Application to Cluster Analysis

An algorithm for finding the largest approximately common substructures of two trees

Similar Documents

An algorithm for finding a common structure shared by a family of strings

Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment

Document image decoding by heuristic search

A metric between unrooted and unordered trees and its bottom-up computing method

Bayesian and Decision Tree Approaches for Pattern Recognition Including Feature Measurement Costs

A comparative study of two search strategies for connected word recognition: dynamic programming and heuristic search

Polynomial-time metrics for attributed trees

A Dynamic Programming Algorithm for the Distance Between Two Finite Areas

A Tree-to-Tree Distance and Its Application to Cluster Analysis

An algorithm for finding the largest approximately common substructures of two trees