1+ <i>ε</i> approximation of tree edit distance in quadratic time

Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin

2019 · 11 citations · 29 references

Concepts

Abstract

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.

References

29