Local similarity between quotiented ordered trees

DOI10.1016/j.jda.2006.03.010zbMath1140.05301MaRDI QIDQ924539

Laurent Tichit, Aïda Ouangraoua, Pascal Ferraro, Dulucq, Serge

Publication date: 16 May 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.03.010

zbMATH Keywords

dynamic programming; ordered labeled trees; local edition; quotiented graph

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

68W05: Nonnumerical algorithms

90C39: Dynamic programming

92D20: Protein sequences, DNA sequences

Related Items

A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes, A constrained edit distance algorithm between semi-ordered trees, A new constrained edit distance between quotiented ordered trees

Cites Work

• Unnamed Item
• The tree-to-tree editing problem
• Linear trees and RNA secondary structure
• An edit distance between quotiented trees
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Identifying approximately common substructures in trees based on a restricted edit distance
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Error-Correcting Tree Automata for Syntactic Pattern Recognition
• The Tree-to-Tree Correction Problem
• The String-to-String Correction Problem