BACKGROUND
in a previous publication  <cit> , we have argued that intergenic sizes were a crucial parameter to infer genome rearrangement distances.
indeed, ignoring this information, as all published distance estimations were doing so far  <cit> , leads to strong biases in all estimations and validation procedures.
here we explore the information contained in intergene size distributions, not for rearrangement distances but for rearrangement scenarios.
we use a weighted dcj operation that acts both on gene order and intergene sizes  <cit> .
in addition, in order to account for all the size variations in intergenic regions, we introduce the possibility of performing indels in intergenes.
we present a polynomial-time algorithm that reconstructs a dcj scenario which optimizes on the number of dcjs, and given this optimal number of dcjs, optimizes on the total size of the indels.
we use it to restrict the solution space of rearrangement scenarios.
indeed it is known that such a space is huge  <cit> , which makes it hard to analyze; several methods have thus been devised to add genomic or epigenomic constraints to restrict the search space .
so far, the potential of intergenic sizes has only been explored for distance computations  <cit> .
we show that it can also contain information on the scenarios, by characterizing categories of dcjs that can be used in optimal dcjs and indels scenarios.
in “statement of the problem” section we define the model, give mathematical objects for genomes and rearrangement operations, from which we derive and prove some useful properties.
then we describe our algorithm in “methods” section.
we finally give the results of an implementation of our algorithm on simulated genomes, showing the limits of optimizing on indel sizes due to signal saturation, and how this optimization can improve the statistical properties of inferred dcj scenarios.
in the last section we explicit the limits of using this approach on biological data, and discuss some possible improvements on the model.
statement of the problem
genomes and dcj
a genome
g is defined as a set of n pairwise disjoint edges within a set of 2n vertices v .
a genome is weighted if a non negative integer weight  is assigned to each edge, and unweighted otherwise.
for the relation of this definition with various usual definitions of genomes in the context of rearrangements, see  <cit> .
a dcj is an operation on an unweighted genome transforming any pair of edges ab and cd into ac and bd.
a wdcj  <cit>  acts similarly on a weighted genome, and additionally reassigns weights to the newly formed edges with the condition that w+w=w+w, while the weight of the other edges remains unchanged.
to any wdcj can thus be associated an underlying dcj, of which it is said to be a weighted realization.
an indel of size δ  is an operation on a weighted genome consisting in increasing or decreasing the weight of an edge by δ.
breakpoint graph and valid scenario
given two genomes g
<dig> and g
<dig> on the same vertex set v, we define the breakpoint graph as bg=.
this is a 2-regular multi-graph which can be partitioned into vertex-disjoint cycles, each of even length .
a cycle of length  <dig>  is called trivial.
in the case of weighted genomes, a trivial cycle containing edges e
<dig> and e
<dig> is said to be balanced if w=w.
a dcj  on g
<dig> or g
<dig> is valid if, after it is applied, the number of cycles in the corresponding breakpoint graph is increased by one.
note that a valid dcj  necessarily acts on two edges that belong to the same cycle .
the dcj-distance  <cit>  between two unweighted genomes is the minimum number of successive dcjs one needs to apply to g
<dig>  to obtain a breakpoint graph containing only trivial cycles.
this distance is equal to n−c ), and can be achieved by applying any valid dcj at each step.
such a series of successive valid dcjs is called a valid dcj scenario.
we similarly define a valid wdcj  if the underlying dcj  is valid.
note however that when genomes are weighted, a valid wdcj scenario gives a breakpoint graph that is composed of n trivial cycles, but these may not all be balanced.
fig.
<dig> illustration of a dcj acting on edges e and f in a cycle c of a breakpoint graph.
this dcj is valid: two cycles are obtained from c, thus the number of cycles is increased
a wdcj scenario with indels is a sequence of wdcjs and indels transforming one genome into the other  into n trivial balanced cycles).
it is valid if the underlying wdcj scenario is valid.
its cost
c is the sum of the sizes of the indels it contains.
balancing cycles
given a path  p of a breakpoint graph bg, seen as a set of edges, let wi=∑e∈p∩giw for i∈{ <dig> }.
path p has imbalance i=w
1−w
<dig> and absolute imbalance |i|.
the imbalance of a breakpoint graph i) is the sum of the absolute imbalances of the cycles it contains.
given g
<dig> and g
<dig>  a wdcj on g
<dig> that yields g1′ is called steady  if the imbalance of the breakpoint graph remains unchanged , i.e.
i)=i) )<i), i)>i)).
sorting by wdcjs and indels in intergenes
we introduce the following optimization problem.
sorting by wdcjs and indels in intergenes
instance : two genomes g
<dig> and g
in other words, the above problem asks for a wdcj scenario of minimum length  that, on the way, performs small indels in order to balance the intergene size.
this definition is motivated by a parsimony argument: we look for a scenario minimizing the amount of genome events, especially large-scale events such as dcjs.
in the following, for ease of presentation, instead of considering wdcj scenarios with indels that act on only one genome  in order to reach the other, we actually consider wdcj scenarios with indels acting on both
g
<dig> and g
<dig>  until both genomes become identical .
this approach implicitly yields a scenario of same cost for transforming g
<dig> into g
2: first apply all wdcjs and indels for g
<dig>  in the same order, then apply all inverses of the wdcjs and indels for g
<dig> in reverse order.
in the following, we prove that in any wdcjs and indels scenario, the minimum cost of the indels is equal to the total imbalance of the breakpoint graph, i).
we also provide a polynomial-time algorithm that outputs a valid wdcj scenario with indels which achieves such cost.
methods
in this section, we present our algorithm for sorting by wdcjs and indels in intergenes.
in the following, we define a simple condition on the weights of a pair of edges in bg.
if this condition is fulfilled, such a pair will be called bounded.
we then prove that there always exists a pair of bounded edges in a breakpoint graph , and that any valid dcj using a bounded pair of edges can be extended into a weighted realization keeping the total imbalance of the graph unchanged .
along the way, we additionally show that no valid wdcj can decrease the imbalance of the breakpoint graph, and that any steady scenario  must use only bounded pairs.
in other words, we give a necessary and sufficient condition for a wdcj to belong to an optimal scenario in terms of number of dcjs plus sizes of indels.
definition 1
consider two edges e,f of a breakpoint graph in the same cycle c and in the same genome , and let p
<dig> and p
<dig> denote the two paths obtained from c after removing e and f. let also w=w+w.
then the pair  is said to be bounded if both paths p∈{p
<dig> p
2} satisfy the following conditions:
ifi≥0:i≥−wifi≤0:i≤ <dig>
if e,f are both in g
<dig>  the same definition applies using −i instead of i for computing the imbalance.
we first prove that there is always a bounded pair in a breakpoint graph of two weighted genomes.
lemma 1
let c be a non-trivial cycle, e
m be an edge of minimum weight in c, and e,f be the two neighboring edges of e
m in c. then  is a bounded pair.
proof
assume wlog that e
m is in g
<dig> and e,f are in g
<dig>  after removing e,f, one obtains two paths: p
1={e
m} and p
2=c∖{e,f,e
m}.
let w=w+w.
for the first path, we have i≤ <dig> and i≥− min,w)≥−w, since i=−w.
consider now p
<dig>  and note that i=i−w+w.
hence, if i≥ <dig>  we have i≥−w.
otherwise, since w≤w, we have i≤i≤ <dig>  □
we now prove that bounded pairs can be used to perform wdcjs preserving the total imbalance of the breakpoint graph.
lemma 2
let g
<dig> and g
<dig> be two weighted genomes, and consider a valid wdcj transforming g
<dig> into g1′.
then this wdcj cannot be decreasing, and, if it is steady, then the pair of edges it is applied on is bounded.
conversely, any bounded pair of edges can be used to form a valid steady wdcj.
proof
let e and f be the edges used by the wdcj, e
′ and f
′ be the two edges it creates, c be the cycle containing both e and f, p
<dig> p
<dig> be the two paths obtained by removing e,f from c, and c
1=p
1∪{e
′} and c
2=p
2∪{f
′} be the two cycles created by the wdcj.
clearly, the imbalance of any other cycle than c remains unchanged.
thus the difference in the imbalance of the breakpoint graph, Δ, satisfies
Δ=|i|+|i|−|i|
note that the imbalance can be decomposed as follows:
i=i+i+w+w=i+i+w+w=i+i.
hence Δ= <dig> if both i and i have the same sign , and Δ> <dig> otherwise.
thus, we already know that this wdcj cannot be decreasing.
assume now that it is steady .
let w=w+w=w+w.
we distinguish two cases.
if i≥ <dig>  then i≥ <dig> and i≥ <dig>  hence, i+w≥ <dig> and i≥−w.
similarly i≥−w.
if i< <dig>  then i≤ <dig> and i≤ <dig>  hence, i+w≤ <dig> and i≤ <dig>  similarly i≤ <dig>
in both cases, the pair  is bounded.
we now look at the converse case: any bounded pair of edges e,f can clearly be used to form a valid wdcj.
using the same notations as before, it remains to assign weights to e
′ and f
′ to create a steady wdcj.
let w=w+w, and note that i+i+w=i.
we consider several cases:
if i≥ <dig> and i≤ <dig>  let w:=−i and w:=w−w=w+i.
then both quantities are positive ≥−w), i=i+w≥ <dig>  and i=i+w=i≥ <dig>
if i≥ <dig>  i≥ <dig> and i≥ <dig>  then any assignment of the weights =w:=w/2) satisfies i≥ <dig>  and i≥ <dig>
if i≥ <dig> and i≤ <dig>  we are in a case similar to the first one: it thus suffices to set w:=−i and w:=w−w.
if i< <dig>  then i≤ <dig> and i≤ <dig>  and i+i+w=i.
we let w:= min,w) and w:=w−w.
then i=i+w≤i+), and consequently i≤ <dig>
we now have two cases to consider.
if −i≥w, then w=w.
thus i=i+w−w=i, from which we conclude i≤ <dig>
if −i<w, then w=−i, and consequently i=i+w+i=i, and we also have i≤ <dig>
in all cases, the imbalance of the two created cycles have the same sign as the imbalance of c, so |i|=|i|+|i|, and the wdcj is steady.
□
by the above lemma, we know that no valid wdcj scenario can be decreasing.
consequently, only an indel can reduce the imbalance of the breakpoint graph.
we thus have the following corollary.
corollary 1
any valid wdcj scenario with indels between two weighted genomes g
<dig> and g
<dig> satisfies c≥i).
we now formally introduce our algorithm that optimally solves sorting by wdcjs and indels in intergenes for two genomes g
<dig> and g
<dig> .
theorem 1
algorithm  <dig> solves sorting by wdcjs and indels in intergenes in time o.
proof
we first need a straightforward sanity check on algorithm  <dig>  first note that applying line  <dig> is always possible due to lemmas  <dig> and  <dig> .
algorithm  <dig> yields two scenarios transforming g
<dig>  into identical genomes , which in turn is equivalent to outputting a single scenario from g
<dig> to g
<dig> with the same cost.
by corollary  <dig>  we know that i) is a lower bound on the cost of any valid wdcj scenario with indels.
moreover, during the first while loop  our algorithm produces a scenario using only steady wdcjs, hence the imbalance of any intermediate breakpoint graph is the same as the original, i.e.
i).
during the second while loop , an indel of size |i| is performed for each imbalanced cycle, hence the total cost of indels is i).
overall algorithm  <dig> is correct and reaches the lower bound of i) for the cost of the indels, hence it is optimal.
the running time can be achieved by sorting the edges by weight once  time), and then keeping this structure sorted through wdcjs  each time).
□
RESULTS
in order to test the efficiency of our model and algorithmic result, we constructed simulated data in the following way: start with an arbitrary genome with n= <dig>  <dig> edges, with arbitrary non negative integer weights of total sum  <dig> 000·n.
perform a burn-in step of  <dig>  <dig> wdcjs, such that each couple of distinct edges ab and cd is equiprobable, and transform these edges into ac and bd .
the weights of the resulting edges ac and bd are chosen by picking two random numbers r
<dig> and r
<dig> uniformly in resp.
and .
the abovementioned burn-in step is performed so that the weight distribution reaches an equilibrium.
then from the resulting genome, we perform  <dig> wdcjs in the same way.
we limited ourselves to  <dig> wdcjs after the starting point because it is the expected point where real scenarios stop to be parsimonious in terms of the number of dcjs.
so over this point, computing parsimonious scenarios and comparing them to the real ones has less sense.
concerning the indels, between two wdcjs, we perform an indel in each edge with a certain probability p. we generated four sets of simulated data, one for each p∈{ <dig> − <dig> − <dig> −1}.
an indel consists in picking a random number in an exponential law with mean  <dig>  and randomly adding or retracting its integer part δ to the edge weight.
in order to evaluate the capacity of the model to infer the right indel size, we first computed, at each step, the difference between the total size of the simulated indels and the sum of the cycle imbalances, which we intepret as indels in the scenarios .
the result is shown on fig.
<dig>  for p∈{ <dig> −3}, the estimations are very good .
for larger p the signal saturates, as the number of real indels becomes quickly much larger than the number of inferred ones.
this is explained by indels hitting several times the same cycle with high probability.
fig.
<dig> a simulation for n= <dig>  <dig> edges, and k= <dig> successive wdcjs.
the x axis is the step of the simulation, and the y axis is the difference between the real and inferred indel size
we then discarded the simulation with probability p= <dig> , since the results are too divergent from the simulated numbers – in other words, our model cannot handle such an indel rate.
for each of the three remaining simulations, we first computed a random dcj scenario, consisting in picking a random valid dcj at each step, without consideration towards the weights.
we then drew a random wdcj scenario with indels – that we will denote by wdcj scenario in the following.
the wdcj scenario is constructed from a randomized variant of algorithm  <dig> which works as follows: in line  <dig>  instead of picking a bounded pair of edges in a deterministic way, we pick a random bounded pair of edges, by sampling random wdcjs until one is picked that acts on a bounded pair of edges.
in order to verify first that there indeed is some signal on the scenario within intergene sizes, we computed the frequency at which a random dcj scenario could lead to an optimal wdcj scenario, in terms of total indel sizes.
the result is shown on fig.
<dig>  random dcj scenarios, if genomes are sufficiently distant, are very improbably compatible with a scenario guided by intergene sizes.
indeed after approximately  <dig> wdcjs in the simulation, no scenario was using only bounded dcjs, i.e.
dcjs acting on bounded pairs.
fig.
<dig> a simulation for n= <dig>  <dig> edges, and k= <dig> successive wdcjs.
the x axis is the step of the simulation, and the y axis is the proportion of random wdcj scenarios which contain only bounded wdcjs
we then tested the ability of our algorithm to produce scenarios that are closer to the real ones.
we measured in particular, for each vertex of the breakpoint graph , how many times a wdcj chose an incident edge in one scenario.
this gives, for one scenario, a vector with one entry per vertex, and a reconstructed scenario can be compared with a real one.
we could compare two scenarios by computing the sum of the squares of the differences between each vector entry.
we checked that with this measure the computed wdcj scenario was in mean less distant to the real scenario than a random wdcj scenario, for all simulation conditions .
this again argues for the existence of information on the real scenario in the intergene sizes.
however the difference with random scenarios, while real, is not sufficiently spectacular to encourage us to test the algorithm on real genomic data.
this would require a finer model.
CONCLUSIONS
the contribution of this paper is twofold.
first, the definition of weighted genomes  <cit>  opens combinatorial questions, one of which being the transformation of a genome into another in a minimum number of steps.
in a previous paper  <cit>  we solved the strict version of this problem, where genomes were forced to have the same total intergene sizes and only wdcjs were allowed.
here we add some flexibility to the problem, which allows all pairs of genomes to be compared, while indels are introduced to account for possible deviations in intergene sizes.
thus the present model is definitely closer to reality, where two genomes, even very close, cannot be expected to contain exactly the same total intergene sizes.
we give a polynomial solution to the distance problem, where only wdcj optimal scenarios are allowed, and the total indel size of a scenario is minimized.
second, this combinatorial question is related to the choice of a dcj scenario among the many possible ones.
it is a crucial question for several biological studies, about potential rearrangement hotspots for example  <cit> .
pevzner and tesler  <cit>  concluded about the existence of hotspots from the inversion distance computation, but were unable to localize them.
it has even been argued that the conclusion on the existence of hotspots might depend on the choice of the scenario  <cit> .
so it is important to exploit every available information on what might have been real scenarios.
we show that some information is available in intergene sizes, by defining a necessary and sufficient property for a wdcj to participate to an optimal scenario.
additional work is necessary to use this information on biological data.
indeed, if there is information about the scenarios in intergene sizes, our combinatorial algorithm does not exploit it entirely.
the solution space of our restricted version is still too large to propose a small number of scenarios with confidence.
statistical properties of the sub-space of solutions are only slightly closer to true scenarios than statistical properties of the whole space.
consequently, this work opens several perspectives concerning the model, and more precisely the scoring function that should be used.
one possibility is to weight indels differently.
for example, one could weight an indel by an affine or an exponential function of its length.
this would be biologically more relevant and would also restrict further the scenario space.
another possibility is to extend our model so as to allow other wdcjs than valid ones, i.e.
wdcjs that either decrease or do not change the number of cycles in the breakpoint graph.
this would allow more flexibility as, for instance, merging two unbalanced cycles may lead to a balanced one, and may thus avoid some further indels.
this, however, raises the question of a good scoring function, since four events are allowed in that case , and one should cleverly weight each such event.
in all cases, the study of such optimization problems, ranging from combinatorial properties to algorithmic solutions to validation of the model  remains open.
declaration
publication of this supplement has been funded by inria.
this article has been published as part of bmc bioinformatics vol  <dig> suppl  <dig>  2016: proceedings of the 14th annual research in computational molecular biology  comparative genomics satellite workshop: bioinformatics.
the full contents of the supplement are available online at https://bmcbioinformatics.biomedcentral.com/articles/supplements/volume-17-supplement- <dig>
availability of data and material
not applicable.
authors’ contributions
all authors contributed equally to this paper.
all authors read and approved the final manuscript.
competing interests
the authors declare that they have no competing interests.
consent for publication
not applicable.
ethics approval and consent to participate
not applicable.

 in a previous publication, we have argued that intergenic sizes were a crucial parameter to infer genome rearrangement distances. indeed, ignoring this information, as all published distance estimations were doing so far, leads to strong biases in all estimations and validation procedures. here we explore the information contained in intergene size distributions, not for rearrangement distances but for rearrangement scenarios. we use a weighted dcj operation that acts both on gene order and intergene sizes. in addition, in order to account for all the size variations in intergenic regions, we introduce the possibility of performing indels in intergenes. we present a polynomial-time algorithm that reconstructs a dcj scenario which optimizes on the number of dcjs, and given this optimal number of dcjs, optimizes on the total size of the indels. we use it to restrict the solution space of rearrangement scenarios. indeed it is known that such a space is huge, which makes it hard to analyze; several methods have thus been devised to add genomic or epigenomic constraints to restrict the search space. so far, the potential of intergenic sizes has only been explored for distance computations. we show that it can also contain information on the scenarios, by characterizing categories of dcjs that can be used in optimal dcjs and indels scenarios. in “statement of the problem” section we define the model, give mathematical objects for genomes and rearrangement operations, from which we derive and prove some useful properties. then we describe our algorithm in “methods” section. we finally give the results of an implementation of our algorithm on simulated genomes, showing the limits of optimizing on indel sizes due to signal saturation, and how this optimization can improve the statistical properties of inferred dcj scenarios. in the last section we explicit the limits of using this approach on biological data, and discuss some possible improvements on the model. statement of the problem genomes and dcj a genome g is defined as a set of n pairwise disjoint edges within a set of 2n vertices v. a genome is weighted if a non negative integer weight is assigned to each edge, and unweighted otherwise. for the relation of this definition with various usual definitions of genomes in the context of rearrangements, see. a dcj is an operation on an unweighted genome transforming any pair of edges ab and cd into ac and bd. a wdcj acts similarly on a weighted genome, and additionally reassigns weights to the newly formed edges with the condition that w+w=w+w, while the weight of the other edges remains unchanged. to any wdcj can thus be associated an underlying dcj, of which it is said to be a weighted realization. an indel of size δ is an operation on a weighted genome consisting in increasing or decreasing the weight of an edge by δ. breakpoint graph and valid scenario given two genomes g and g on the same vertex set v, we define the breakpoint graph as bg=. this is a 2-regular multi-graph which can be partitioned into vertex-disjoint cycles, each of even length. a cycle of length is called trivial. in the case of weighted genomes, a trivial cycle containing edges e and e is said to be balanced if w=w. a dcj on g or g is valid if, after it is applied, the number of cycles in the corresponding breakpoint graph is increased by one. note that a valid dcj necessarily acts on two edges that belong to the same cycle. the dcj-distance between two unweighted genomes is the minimum number of successive dcjs one needs to apply to g to obtain a breakpoint graph containing only trivial cycles. this distance is equal to n−c ), and can be achieved by applying any valid dcj at each step. such a series of successive valid dcjs is called a valid dcj scenario. we similarly define a valid wdcj if the underlying dcj is valid. note however that when genomes are weighted, a valid wdcj scenario gives a breakpoint graph that is composed of n trivial cycles, but these may not all be balanced. fig. illustration of a dcj acting on edges e and f in a cycle c of a breakpoint graph. this dcj is valid: two cycles are obtained from c, thus the number of cycles is increased a wdcj scenario with indels is a sequence of wdcjs and indels transforming one genome into the other into n trivial balanced cycles). it is valid if the underlying wdcj scenario is valid. its cost c is the sum of the sizes of the indels it contains. balancing cycles given a path p of a breakpoint graph bg, seen as a set of edges, let wi=∑e∈p∩giw for i∈{ }. path p has imbalance i=w 1−w and absolute imbalance |i|. the imbalance of a breakpoint graph i) is the sum of the absolute imbalances of the cycles it contains. given g and g a wdcj on g that yields g1′ is called steady if the imbalance of the breakpoint graph remains unchanged, i.e. i)=i) )<i), i)>i)). sorting by wdcjs and indels in intergenes we introduce the following optimization problem. sorting by wdcjs and indels in intergenes instance: two genomes g and g in other words, the above problem asks for a wdcj scenario of minimum length that, on the way, performs small indels in order to balance the intergene size. this definition is motivated by a parsimony argument: we look for a scenario minimizing the amount of genome events, especially large-scale events such as dcjs. in the following, for ease of presentation, instead of considering wdcj scenarios with indels that act on only one genome in order to reach the other, we actually consider wdcj scenarios with indels acting on both g and g until both genomes become identical. this approach implicitly yields a scenario of same cost for transforming g into g 2: first apply all wdcjs and indels for g in the same order, then apply all inverses of the wdcjs and indels for g in reverse order. in the following, we prove that in any wdcjs and indels scenario, the minimum cost of the indels is equal to the total imbalance of the breakpoint graph, i). we also provide a polynomial-time algorithm that outputs a valid wdcj scenario with indels which achieves such cost. methods in this section, we present our algorithm for sorting by wdcjs and indels in intergenes. in the following, we define a simple condition on the weights of a pair of edges in bg. if this condition is fulfilled, such a pair will be called bounded. we then prove that there always exists a pair of bounded edges in a breakpoint graph, and that any valid dcj using a bounded pair of edges can be extended into a weighted realization keeping the total imbalance of the graph unchanged. along the way, we additionally show that no valid wdcj can decrease the imbalance of the breakpoint graph, and that any steady scenario must use only bounded pairs. in other words, we give a necessary and sufficient condition for a wdcj to belong to an optimal scenario in terms of number of dcjs plus sizes of indels. definition 1 consider two edges e,f of a breakpoint graph in the same cycle c and in the same genome, and let p and p denote the two paths obtained from c after removing e and f. let also w=w+w. then the pair is said to be bounded if both paths p∈{p p 2} satisfy the following conditions: ifi≥0:i≥−wifi≤0:i≤ if e,f are both in g the same definition applies using −i instead of i for computing the imbalance. we first prove that there is always a bounded pair in a breakpoint graph of two weighted genomes. lemma 1 let c be a non-trivial cycle, e m be an edge of minimum weight in c, and e,f be the two neighboring edges of e m in c. then is a bounded pair. proof assume wlog that e m is in g and e,f are in g after removing e,f, one obtains two paths: p 1={e m} and p 2=c∖{e,f,e m}. let w=w+w. for the first path, we have i≤ and i≥− min,w)≥−w, since i=−w. consider now p and note that i=i−w+w. hence, if i≥ we have i≥−w. otherwise, since w≤w, we have i≤i≤ □ we now prove that bounded pairs can be used to perform wdcjs preserving the total imbalance of the breakpoint graph. lemma 2 let g and g be two weighted genomes, and consider a valid wdcj transforming g into g1′. then this wdcj cannot be decreasing, and, if it is steady, then the pair of edges it is applied on is bounded. conversely, any bounded pair of edges can be used to form a valid steady wdcj. proof let e and f be the edges used by the wdcj, e ′ and f ′ be the two edges it creates, c be the cycle containing both e and f, p p be the two paths obtained by removing e,f from c, and c 1=p 1∪{e ′} and c 2=p 2∪{f ′} be the two cycles created by the wdcj. clearly, the imbalance of any other cycle than c remains unchanged. thus the difference in the imbalance of the breakpoint graph, Δ, satisfies Δ=|i|+|i|−|i| note that the imbalance can be decomposed as follows: i=i+i+w+w=i+i+w+w=i+i. hence Δ= if both i and i have the same sign, and Δ> otherwise. thus, we already know that this wdcj cannot be decreasing. assume now that it is steady. let w=w+w=w+w. we distinguish two cases. if i≥ then i≥ and i≥ hence, i+w≥ and i≥−w. similarly i≥−w. if i< then i≤ and i≤ hence, i+w≤ and i≤ similarly i≤ in both cases, the pair is bounded. we now look at the converse case: any bounded pair of edges e,f can clearly be used to form a valid wdcj. using the same notations as before, it remains to assign weights to e ′ and f ′ to create a steady wdcj. let w=w+w, and note that i+i+w=i. we consider several cases: if i≥ and i≤ let w:=−i and w:=w−w=w+i. then both quantities are positive ≥−w), i=i+w≥ and i=i+w=i≥ if i≥ i≥ and i≥ then any assignment of the weights =w:=w/2) satisfies i≥ and i≥ if i≥ and i≤ we are in a case similar to the first one: it thus suffices to set w:=−i and w:=w−w. if i< then i≤ and i≤ and i+i+w=i. we let w:= min,w) and w:=w−w. then i=i+w≤i+), and consequently i≤ we now have two cases to consider. if −i≥w, then w=w. thus i=i+w−w=i, from which we conclude i≤ if −i<w, then w=−i, and consequently i=i+w+i=i, and we also have i≤ in all cases, the imbalance of the two created cycles have the same sign as the imbalance of c, so |i|=|i|+|i|, and the wdcj is steady. □ by the above lemma, we know that no valid wdcj scenario can be decreasing. consequently, only an indel can reduce the imbalance of the breakpoint graph. we thus have the following corollary. corollary 1 any valid wdcj scenario with indels between two weighted genomes g and g satisfies c≥i). we now formally introduce our algorithm that optimally solves sorting by wdcjs and indels in intergenes for two genomes g and g. theorem 1 algorithm solves sorting by wdcjs and indels in intergenes in time o. proof we first need a straightforward sanity check on algorithm first note that applying line is always possible due to lemmas and. algorithm yields two scenarios transforming g into identical genomes, which in turn is equivalent to outputting a single scenario from g to g with the same cost. by corollary we know that i) is a lower bound on the cost of any valid wdcj scenario with indels. moreover, during the first while loop our algorithm produces a scenario using only steady wdcjs, hence the imbalance of any intermediate breakpoint graph is the same as the original, i.e. i). during the second while loop, an indel of size |i| is performed for each imbalanced cycle, hence the total cost of indels is i). overall algorithm is correct and reaches the lower bound of i) for the cost of the indels, hence it is optimal. the running time can be achieved by sorting the edges by weight once time), and then keeping this structure sorted through wdcjs each time). □  in order to test the efficiency of our model and algorithmic result, we constructed simulated data in the following way: start with an arbitrary genome with n= edges, with arbitrary non negative integer weights of total sum 000·n. perform a burn-in step of wdcjs, such that each couple of distinct edges ab and cd is equiprobable, and transform these edges into ac and bd. the weights of the resulting edges ac and bd are chosen by picking two random numbers r and r uniformly in resp. and. the abovementioned burn-in step is performed so that the weight distribution reaches an equilibrium. then from the resulting genome, we perform wdcjs in the same way. we limited ourselves to wdcjs after the starting point because it is the expected point where real scenarios stop to be parsimonious in terms of the number of dcjs. so over this point, computing parsimonious scenarios and comparing them to the real ones has less sense. concerning the indels, between two wdcjs, we perform an indel in each edge with a certain probability p. we generated four sets of simulated data, one for each p∈{ − − −1}. an indel consists in picking a random number in an exponential law with mean and randomly adding or retracting its integer part δ to the edge weight. in order to evaluate the capacity of the model to infer the right indel size, we first computed, at each step, the difference between the total size of the simulated indels and the sum of the cycle imbalances, which we intepret as indels in the scenarios. the result is shown on fig. for p∈{ −3}, the estimations are very good. for larger p the signal saturates, as the number of real indels becomes quickly much larger than the number of inferred ones. this is explained by indels hitting several times the same cycle with high probability. fig. a simulation for n= edges, and k= successive wdcjs. the x axis is the step of the simulation, and the y axis is the difference between the real and inferred indel size we then discarded the simulation with probability p=, since the results are too divergent from the simulated numbers – in other words, our model cannot handle such an indel rate. for each of the three remaining simulations, we first computed a random dcj scenario, consisting in picking a random valid dcj at each step, without consideration towards the weights. we then drew a random wdcj scenario with indels – that we will denote by wdcj scenario in the following. the wdcj scenario is constructed from a randomized variant of algorithm which works as follows: in line instead of picking a bounded pair of edges in a deterministic way, we pick a random bounded pair of edges, by sampling random wdcjs until one is picked that acts on a bounded pair of edges. in order to verify first that there indeed is some signal on the scenario within intergene sizes, we computed the frequency at which a random dcj scenario could lead to an optimal wdcj scenario, in terms of total indel sizes. the result is shown on fig. random dcj scenarios, if genomes are sufficiently distant, are very improbably compatible with a scenario guided by intergene sizes. indeed after approximately wdcjs in the simulation, no scenario was using only bounded dcjs, i.e. dcjs acting on bounded pairs. fig. a simulation for n= edges, and k= successive wdcjs. the x axis is the step of the simulation, and the y axis is the proportion of random wdcj scenarios which contain only bounded wdcjs we then tested the ability of our algorithm to produce scenarios that are closer to the real ones. we measured in particular, for each vertex of the breakpoint graph, how many times a wdcj chose an incident edge in one scenario. this gives, for one scenario, a vector with one entry per vertex, and a reconstructed scenario can be compared with a real one. we could compare two scenarios by computing the sum of the squares of the differences between each vector entry. we checked that with this measure the computed wdcj scenario was in mean less distant to the real scenario than a random wdcj scenario, for all simulation conditions. this again argues for the existence of information on the real scenario in the intergene sizes. however the difference with random scenarios, while real, is not sufficiently spectacular to encourage us to test the algorithm on real genomic data. this would require a finer model.  the contribution of this paper is twofold. first, the definition of weighted genomes opens combinatorial questions, one of which being the transformation of a genome into another in a minimum number of steps. in a previous paper we solved the strict version of this problem, where genomes were forced to have the same total intergene sizes and only wdcjs were allowed. here we add some flexibility to the problem, which allows all pairs of genomes to be compared, while indels are introduced to account for possible deviations in intergene sizes. thus the present model is definitely closer to reality, where two genomes, even very close, cannot be expected to contain exactly the same total intergene sizes. we give a polynomial solution to the distance problem, where only wdcj optimal scenarios are allowed, and the total indel size of a scenario is minimized. second, this combinatorial question is related to the choice of a dcj scenario among the many possible ones. it is a crucial question for several biological studies, about potential rearrangement hotspots for example. pevzner and tesler concluded about the existence of hotspots from the inversion distance computation, but were unable to localize them. it has even been argued that the conclusion on the existence of hotspots might depend on the choice of the scenario. so it is important to exploit every available information on what might have been real scenarios. we show that some information is available in intergene sizes, by defining a necessary and sufficient property for a wdcj to participate to an optimal scenario. additional work is necessary to use this information on biological data. indeed, if there is information about the scenarios in intergene sizes, our combinatorial algorithm does not exploit it entirely. the solution space of our restricted version is still too large to propose a small number of scenarios with confidence. statistical properties of the sub-space of solutions are only slightly closer to true scenarios than statistical properties of the whole space. consequently, this work opens several perspectives concerning the model, and more precisely the scoring function that should be used. one possibility is to weight indels differently. for example, one could weight an indel by an affine or an exponential function of its length. this would be biologically more relevant and would also restrict further the scenario space. another possibility is to extend our model so as to allow other wdcjs than valid ones, i.e. wdcjs that either decrease or do not change the number of cycles in the breakpoint graph. this would allow more flexibility as, for instance, merging two unbalanced cycles may lead to a balanced one, and may thus avoid some further indels. this, however, raises the question of a good scoring function, since four events are allowed in that case, and one should cleverly weight each such event. in all cases, the study of such optimization problems, ranging from combinatorial properties to algorithmic solutions to validation of the model remains open. declaration publication of this supplement has been funded by inria. this article has been published as part of bmc bioinformatics vol suppl 2016: proceedings of the 14th annual research in computational molecular biology comparative genomics satellite workshop: bioinformatics. the full contents of the supplement are available online at https://bmcbioinformatics.biomedcentral.com/articles/supplements/volume-17-supplement- availability of data and material not applicable. authors’ contributions all authors contributed equally to this paper. all authors read and approved the final manuscript. competing interests the authors declare that they have no competing interests. consent for publication not applicable. ethics approval and consent to participate not applicable.
on simulated data we show that statistical properties of the inferred scenarios are closer to the true ones than dcj only scenarios, i.e. we give a polynomial-time algorithm that, given two genomes with arbitrary intergene size distributions, outputs a dcj scenario which optimizes on the number of dcjs, and given this optimal number of dcjs, optimizes on the total sum of the sizes of the indels. we show that there is a valuable information in the intergene sizes concerning the rearrangement scenario itself. scenarios which do not handle intergene sizes. dcjintergenic regionsindelsgenome rearrangements14th annual research in computational molecular biology comparative genomics satellite workshop recomb-cgmontreal, canada 11- october http://www.crm.umontreal.ca/2016/genomics16/index_e.phpissue-copyright-statement© the author 2016
 given two genomes that have diverged by a series of rearrangements, we infer minimum double cut-and-join scenarios to explain their organization differences, coupled with indel scenarios to explain their intergene size distribution, where dcjs themselves also alter the sizes of broken intergenes.  we give a polynomial-time algorithm that, given two genomes with arbitrary intergene size distributions, outputs a dcj scenario which optimizes on the number of dcjs, and given this optimal number of dcjs, optimizes on the total sum of the sizes of the indels.  we show that there is a valuable information in the intergene sizes concerning the rearrangement scenario itself. on simulated data we show that statistical properties of the inferred scenarios are closer to the true ones than dcj only scenarios, i.e. scenarios which do not handle intergene sizes. keywords dcjintergenic regionsindelsgenome rearrangements14th annual research in computational molecular biology comparative genomics satellite workshop recomb-cgmontreal, canada 11- october http://www.crm.umontreal.ca/2016/genomics16/index_e.phpissue-copyright-statement© the author 2016 