2019 · 11 citations · 29 references
Life SciencesBioinformaticsComputer ScienceComputational BiologySequence AnalysisStructural BioinformaticsMolecular SimilarityRna StructureComputational Biology ModelsEdit DistanceTree Distance Metrics
Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree.
29
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Fast Algorithms for Finding Nearest Common Ancestors
Dov Harel, Robert E. Tarjan · SIAM Journal on Computing · 1984 · 1.1K citations
The Tree-to-Tree Correction Problem
Kuo‐Chung Tai · Journal of the ACM · 1979 · 863 citations · Full text