Decomposition algorithms for the tree edit distance problem

DOI10.1016/j.jda.2004.08.018zbMath1129.68099OpenAlexW1978872422MaRDI QIDQ2569420

Hélène Touzet, Dulucq, Serge

Publication date: 27 October 2005

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

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

zbMATH Keywords

treealgorithmalignmentcomputational biologyedit distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Protein sequences, DNA sequences (92D20) Distance in graphs (05C12)

Related Items

A survey on tree matching and XML retrieval ⋮ On the hardness of computing the edit distance of shallow trees ⋮ A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes ⋮ Unnamed Item ⋮ Learning probabilistic models of tree edit distance ⋮ Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems ⋮ An improved algorithm for tree edit distance with applications for RNA secondary structure comparison

Cites Work

• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• The tree-to-tree editing problem
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Tree edit distance with gaps
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Fast Algorithms for Finding Nearest Common Ancestors
• The Tree-to-Tree Correction Problem
• The String-to-String Correction Problem