Geodesic
An almost exact linear algorithm for transformation of chain-cycle graphs with optimization of the sum of operation costs
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 26-29 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For weighted directed chain-cycle graphs, an algorithm transforming one graph into another is constructed. The algorithm runs in linear time and yields a sequence of transformations with the smallest, up to an additive error, total cost. The costs of the operations of inserting and deleting an edge segment may differ from each other and from the costs of the other operations. The additive error is estimated in terms of the operation costs.
Keywords: exact algorithm, 2-degree graph, operation cost, DCJ-operations, discrete optimization.
Mots-clés : graph transformation, chain-cycle graph 
@article{DANMA_2020_494_a5,
     author = {K. Yu. Gorbunov and V. A. Lyubetskii},
     title = {An almost exact linear algorithm for transformation of chain-cycle graphs with optimization of the sum of operation costs},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {26--29},
     year = {2020},
     volume = {494},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2020_494_a5/}
}
TY  - JOUR
AU  - K. Yu. Gorbunov
AU  - V. A. Lyubetskii
TI  - An almost exact linear algorithm for transformation of chain-cycle graphs with optimization of the sum of operation costs
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 26
EP  - 29
VL  - 494
UR  - http://geodesic.mathdoc.fr/item/DANMA_2020_494_a5/
LA  - ru
ID  - DANMA_2020_494_a5
ER  - 
%0 Journal Article
%A K. Yu. Gorbunov
%A V. A. Lyubetskii
%T An almost exact linear algorithm for transformation of chain-cycle graphs with optimization of the sum of operation costs
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2020
%P 26-29
%V 494
%U http://geodesic.mathdoc.fr/item/DANMA_2020_494_a5/
%G ru
%F DANMA_2020_494_a5
K. Yu. Gorbunov; V. A. Lyubetskii. An almost exact linear algorithm for transformation of chain-cycle graphs with optimization of the sum of operation costs. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 26-29. http://geodesic.mathdoc.fr/item/DANMA_2020_494_a5/

[1] Yancopoulos S., Attie O., Friedberg R., “Efficient Sorting of Genomic Permutations by Translocation, Inversion and Block Interchange”, Bioinformatics, 21 (2005), 3340–3346 | DOI

[2] Tandy Warnow (ed.), Bioinformatics and Phylogenetics. Seminal Contributions of Bernard Moret, Comput. Biol. Series, Springer Nature Switzerland AG, 2019 | Zbl

[3] Gorbunov K.Yu., Lyubetsky V.A., An Almost Exact Linear Complexity Algorithm of the Shortest Transformation of Chain-Cycle Graphs, 2020, arXiv: 2004.14351 [math.CO] | MR

[4] da Silva P.H., Machado R., Dantas S., Braga M.D.V., “Genomic Distance with High Indel Costs”, J. IEEE/ACM Trans. Comput. Biol. Bioinform., 14:3 (2017), 1–6

[5] Gorbunov K.Yu., Lyubetskii V.A., “Lineinyi algoritm minimalnoi perestroiki struktur”, Problemy peredachi informatsii, 53:1 (2017), 60–78 | MR | Zbl

[6] Alekseyev M.A., Pevzner P.A., “Multi-Break Rearrangements and Chromosomal Evolution”, Theor. Computer Science, 395:2-3 (2008), 193–202 | DOI | MR | Zbl