English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A "genome structure" is a labeled directed graph with vertices of degree 1 or2. A set of operations over such graphs is fixed, and each of the operationshas a certain cost, a strictly positive number. The transformation problemconsists in the following: for given structures a and b and given costs, find aminimum total cost sequence of operations transforming a into b ("the shortesttransformation of a into b"). Each operation corresponds to an "event", thelatter being a change in the graph caused by executing one of the operationsover it. The possibility of assigning different costs is important inapplications, since it allows to distinguish between frequent and rare events.Apparently, arbitrary costs make the problem NP-hard, which results innontriviality of passing from one restriction on costs to another, if theproblem is solved by a linear or at least polynomial algorithm (assuming that Pis not equal NP). We propose a novel linear time and space algorithm whichconstructs a sequence of operations transforming a to b with total cost closeor equal to the absolute minimum. Namely, if all the so-called DCJ operationshave the same cost w and if deletions and insertions have costs either bothlarger or both less than w, then the algorithm outputs a transformation of ainto b with the total cost differing from the absolute minimum by at most 2w(in the former case) or equal to it (in the latter case). In some cases, thealgorithm outputs an exact solution, e.g., in the case of circular genomestructures. The condition on the costs of deletions and insertions can beomitted (although the proof described below does not include this generalcase).

An Almost Exact Linear Complexity Algorithm of the Shortest Transformation of Chain-Cycle Graphs