AN EXACT QUADRATIC ALGORITHM FOR THE SHORTEST TREE TRANSFORMATION

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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.

作者简介

K. Gorbunov

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

Email: gorbunov@iitp.ru
Moscow, Russia

V. 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

参考

  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

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2024