- PII
- 10.31857/S2686954324050058-1
- DOI
- 10.31857/S2686954324050058
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 519 / Issue number 1
- Pages
- 22-27
- 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.
- Keywords
- дискретная оптимизация кратчайшее преобразование дерева операции над деревом цена операции точный алгоритм квадратичной сложности алгоритм выравнивание деревьев.
- Date of publication
- 15.04.2024
- Year of publication
- 2024
- Number of purchasers
- 0
- Views
- 40
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
