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

Sorting a permutation by reversals is a famous problem in genomerearrangements. Since 1997, quite some biological evidence were found that inmany genomes the reversed regions are usually flanked by a pair of invertedrepeats. This type of reversals are called symmetric reversals, which,unfortunately, were largely ignored until recently. In this paper, weinvestigate the problem of sorting by symmetric reversals, which requires aseries of symmetric reversals to transform one chromosome $A$ into the anotherchromosome $B$. The decision problem of sorting by symmetric reversals isreferred to as {\em SSR} (when the input chromosomes $A$ and $B$ are given, weuse {\em SSR(A,B)}) and the corresponding optimization version (i.e., when theanswer for {\em SSR(A,B)} is yes, using the minimum number of symmetricreversals to convert $A$ to $B$), is referred to as {\em SMSR(A,B)}. The mainresults of this paper are summarized as follows, where the input is a pair ofchromosomes $A$ and $B$ with $n$ repeats. (1) We present an $O(n^2)$ timealgorithm to solve the decision problem {\em SSR(A,B)}, i.e., determine whethera chromosome $A$ can be transformed into $B$ by a series of symmetricreversals. (2) We design an $O(n^2)$ time algorithm for a special 2-balancedcase of {\em SMSR(A,B)}, where chromosomes $A$ and $B$ both have duplicationnumber 2 and every repeat appears twice in different orientations in $A$ and$B$. (3) We show that SMSR is NP-hard even if the duplication number of theinput chromosomes are at most 2, hence showing that the above positiveoptimization result is the best possible. As a by-product, we show that the\emph{minimum Steiner tree} problem on \emph{circle graphs} is NP-hard,settling the complexity status of a 38-year old open problem.

Men Can't Always be Transformed into Mice: Decision Algorithms and Complexity for Sorting by Symmetric Reversals