AN EXACT QUADRATIC ALGORITHM FOR THE SHORTEST TREE TRANSFORMATION

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The article proposes a new exact quadratic algorithm in complexity that solves the problem of the shortest transformation (“alignment”) of one loaded tree into another, taking into account arbitrary prices of operations on trees. Three operations are considered: adding vertex deletions to an edge or root of a tree and shifting a subtree with deletions.

About the authors

K. Yu. Gorbunov

Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)

Email: gorbunov@iitp.ru
Moscow, Russia

V. A. Lyubetsky

Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute); Lomonosov Moscow State University

Email: lyubetsk@iitp.ru
Moscow, Russia; Moscow, Russia

References

  1. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология (пер. с англ.). СПб.: Невский Диалект; БХВ-Петербург, 2003, 654 с.
  2. Горбунов К. Ю., Любецкий В. А. Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций // ДАН. 2020. Т. 494. № 1. С. 26–29. https://doi.org/10.31857/S2686954320050343
  3. Yuan M., Yang X., Lin J., Cao X., Chen F., Zhang X., Li Z., Zheng G., Wang X., Chen X., Yang J-R. Alignment of Cell Lineage Trees Elucidates Genetic Programs for the Development and Evolution of Cell Types // iScience. 2020. V. 23. Art. 101273. https://doi.org/10.1016/j.isci.2020.101273
  4. https://github.com/Chenjy0212/mdelta (Дата обращения: 20.01.2024).
  5. Bringmann K., Gawrychowski P., Mozes Sh., Weimann O. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can) // ACM Trans. Algorithms. 2020. V. 16. № 4. Art. 48. https://doi.org/10.1145/3381878

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences