AN EXACT QUADRATIC ALGORITHM FOR THE SHORTEST TREE TRANSFORMATION

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

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.

Sobre autores

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

Bibliografia

  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

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © Russian Academy of Sciences, 2024