Top

Journal of Combinatorial Optimization

Published in:

01-01-2014

Algorithms for local similarity between forests

Authors: Zhewei Liang, Kaizhong Zhang

Published in: Journal of Combinatorial Optimization | Issue 1/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

An ordered labelled tree is a tree where the left-to-right order among siblings is significant. Ordered labelled forests are sequences of ordered labelled trees. Given two ordered labelled forests \(F\) and \(G\), the local forest similarity is to find two sub-forests \(F^{\prime }\) and \(G^{\prime }\) of \(F\) and \(G\) respectively such that they are the most similar over all possible \(F^{\prime }\) and \(G^{\prime }\). In this paper, we present efficient algorithms for the local forest similarity problem for two types of sub-forests: sibling subforests and closed subforests. Our algorithms can be used to locate the structurally similar regions in RNA secondary structures since RNA molecules’ secondary structures could be represented as ordered labelled forests.

previous article Radiation hybrid map construction problem parameterized

next article Minimum diameter cost-constrained Steiner trees

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bray T, Paoli J, Sperberg-McQueen CM, Maler E, Yergeau F (2000) Extensible markup language (XML) 1.0. W3C recommendation, 6

Cha S (2007) Comprehensive survey on distance/similarity measures between probability density functions. Int J Math Models Meth Appl Sci 1:300C307

Chen S, Ma B, Zhang K (2009) On the similarity metric and the distance metric. Theory Comput Sci 410(24–25):2365–2376CrossRefMATHMathSciNet

Demaine ED, Mozes S, Rossman B, Weimann O (2007) An optimal decomposition algorithm for tree edit distance. In Proceedings of the 34th international colloquium on automata, languages and programming (ICALP), pp 146–157

Höchsmann M, Töller T, Giegerich R, Kurtz S (2003) Local similarity in RNA secondary structures. In Proceedings of the IEEE Computational systems bioinformatics conference, pp 159–168

Jansson J, Hieu NT, Sung WK (2006) Local gapped subforest alignment and its application in finding RNA structural motifs. J Comput Biol 13(3):702–718CrossRefMathSciNet

Jansson J, Peng Z (2006) Algorithms for Finding a Most Similar Subforest. In Proceedings of the 17th symposium on combinatorial pattern matching, pp 377–388

Jiang T, Wang L, Zhang K (1995) Alignment of trees—an alternative to tree edit. Theor Comput Sci 143:137–148MATHMathSciNet

Liang Z (2011) Efficient algorithms for local forest similarity. Thesis(M.Sc), School of Graduate and Postdoctoral Studies, University of Western Ontario, London

Motifs database. http://subviral.med.uottawa.ca/cgi-bin/motifs.cgi

Peng Z (2005) Algorithms for local forest similarity. In Proceedings of the 16th international symposium on algorithms and computation (ISAAC), pp 704–713

Shapiro BA, Zhang K (1990) Comparing multiple RNA secondary structures using tree comparisons. Comput Appl Biosci 6(4):309–318

Smith TF, Waterman MS (1981) Identification of common molecular subsequences. J Mol Biol 147(1):195–197CrossRef

Tai K-C (1979) The tree-to-tree correction problem. J Assoc Comput Mach 26(3):422–433CrossRefMATHMathSciNet

Wang J, Shapiro BA, Shasha D, Zhang K, Currey KM (1998) An algorithm for finding the largest approximately common substructures of two trees. IEEE Trans Pattern Anal Mach Intell 20(8):889–895CrossRef

Zhang K (1998) Computing similarity between RNA secondary structures. In Proceedings of IEEE international joint symposia on intelligence and systems, Rockville, Maryland, pp 126–132

Zhang K, Shasha D (1989) Simple fast algorithms for the editing distance between trees and related problems. SIAM J Comput 18(6):1245–1262CrossRefMATHMathSciNet

Zhang K, Zhu Y (2010) Algorithms for forest pattern matching. In Proceedings of the 21th symposium on combinatorial pattern matching (CPM), pp 1–12

Title: Algorithms for local similarity between forests
Authors: Zhewei Liang
Kaizhong Zhang
Publication date: 01-01-2014
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2014
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9613-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2014

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Competitive analysis for make-to-order scheduling with reliable lead time quotation

Radiation hybrid map construction problem parameterized

On certain geometric properties of the Yao–Yao graphs

The edge-centered surface area of the arrangement graph

On-line bin packing with restricted repacking

Premium Partner