BACKGROUND
the gene order or syntenic arrangement of ancestral genomes may be reconstructed based on comparative evidence from present-day genomes – the phylogenetic approach – or on internal evidence in the case of genomes descended from an ancestral polyploidisation event, or from a combination of the two.
the computational problem at the heart of phylogenetic analysis is the median problem, while internal reconstruction inspires the halving problem, and the combined approach gives rise to guided halving.
how these problems are formulated depends  on the karyotypic framework: the number of chromosomes in a genome and whether they are constrained to be linear, or if circular chromosomes are also permitted, and  on the objective function used to evaluate possible solutions.
this function is based on some notion of genomic distance, either the number of adjacent elements on a chromosome in one genome that are disrupted in another – the breakpoint distance – or the number of evolutionary operations necessary to transform one genome to another.
while the karyotypes allowed in an ancestor vary only according to the dimensions of single versus multiple chromosome, and linear versus circular versus mixed, the genomic distances of interest have proliferated according to the kinds of evolutionary operations considered, from the classic, relatively constrained, reversals/translocations distance to the more inclusive double cut-and-join  measure, and many others  <cit> .
the computational complexity of some of these problems has been settled for some specific distances and karyotypic contexts, and it is sometimes taken for granted that these results carry over to other combinations of context and distance.
this is not necessarily the case.
in this paper, we survey the known results and unsolved cases for three distance measures in three kinds of karyotype.
we include several results presented here for the first time, as well as discussions on the definitions of the distances.
the results contain both new polynomial-time algorithms and np-hardness proofs.
this paper is the full version of an extended abstract that has appeared in  <cit> , which announced the results without giving all the proofs.
in particular, a full discussion on the breakpoint distance definition, as well as the proofs of theorem  <dig>  theorem  <dig>  and theorem  <dig> are added here, which makes this version a complete and definitive one.
genomes, breakpoints and rearrangements
multichromosomal genomes
we follow the general formulation of a genome in  <cit> .
a gene a is an oriented sequence of dna, identified by its tail at and its head ah.
tails and heads are the extremities of the genes.
an adjacency is an unordered pair of gene extremities.
a genome Π is a set of adjacencies on a set of genes.
each adjacency in a genome means that two gene extremities are consecutive on the dna molecule.
in a genome, each gene extremity is adjacent to zero or one other extremity.
an extremity x that is not adjacent to any other extremity is called a telomere, and can be written as an adjacency x∘ with a null symbol ∘.
the adjacency x∘ is called a telomeric adjacency.
for a genome Π on a set of genes , consider the graph gΠ whose vertices are all the extremities of the genes, and the edges include all the non telomeric adjacencies in Π as well as an edge joining the head and the tail of each gene.
this graph is a set of disjoint paths and cycles.
every connected component is called a chromosome of Π. a chromosome is linear if it is a path, and circular if it is a cycle.
a genome with only linear, or only circular, chromosomes is called a linear or circular genome, respectively.
an example of a graph gΠ is given in figure  <dig>
a genome can also be represented as a set of strings, by writing the genes for each chromosome in the order in which they appear in the paths and cycles of the graph gΠ, with a bar over the gene if the head of the gene appears before the tail , and none if the tail appears before the head .
for each linear chromosome, there are two possible equivalent strings, according to the arbitrary chosen starting point.
one is obtained from the other by reversing the order and switching the signs of all the genes.
for circular chromosomes, there are also two possible circular string representations, according to the direction in which the cycle is traversed.
for example, chromosome c <dig> of the genome Π of figure  <dig> may be written  or .
a genome with only one chromosome is called unichromosomal.
these correspond to signed permutations: the two string representations are  signed permutations.
genomes with duplicates
a duplicated gene a is a couple of homologous oriented sequences of dna, identified by two tails a1t and a2t, and two heads a1h and a2h.
an all-duplicates genome Δ is a set of adjacencies on a set of duplicated genes.
for a genome Π on a gene set , a doubled genome Π ⊕ Π is an all-duplicates genome on the set of duplicated genes from  such that if axby  is an  adjacency of Π , either a1xb1y and a2xb2y, or a2xb1y and a1xb2y, are adjacencies of Π ⊕ Π.
note the difference between a general all-duplicates genome and the special case of a doubled genome: the former has two copies of each gene, while in the latter these copies are organised in such a way that there are two identical copies of each chromosome when we ignore the 1's and 2's in the a1x's and a2x's: it has two linear copies of each linear chromosome, and for each circular chromosome, either two circular copies or one circular chromosome containing the two successive copiesnote also that for a genome Π, there is an exponential number of possible doubled genomes Π ⊕ Π .
these definitions correspond to duplicated and perfectly duplicated genomes found in  <cit> , and slightly differs from the perfectly duplicated genome definition found in  <cit> , as discussed in  <cit> .
an example of an all-duplicates genome and a doubled genome is shown in figure  <dig>  doubled genomes are the immediate result of an evolutionary event called whole genome duplication , which is known to have occurred in many evolutionary lineages, from protists  <cit>  to yeasts, to plants, to fish, to amphibians and even to mammals  <cit> .
all-duplicates genomes derive from doubled genomes through a series of rearrangement events.
typically, all-duplicates genomes pertain to extant species, while doubled genomes are ancestral configurations inferred to exist immediately after the wgd, and that are to be reconstructed.
in discussing all-duplicates genomes, we will sometimes contrast them with ordinary genomes which have a single copy of each gene.
the breakpoint distance
the breakpoint distance has been well-studied for permutations, i.e., unichromosomal genomes  <cit> , but only a few published discussions have focused on how it should be defined for multichromosomal genomes .
the distance should depend not only on common adjacencies, or rather their absence, but also on common telomeres  in two genomes.
here we propose a definition that we wish valid for all types of karyotypes, based on a most general approach integrating all possible informations from the two genomes.
for two genomes Π and Γ on a set  of n genes, suppose Π has nΠ chromosomes, and Γ has nΓ chromosomes.
let a be the number of common adjacencies, e be the number of common telomeres of Π and Γ. then insofar as it should depend additively on these components, we may suppose the breakpoint distance has form
where β, θ and γ are positive parameters, while ψ may have either sign.
taking Π = Γ and imposing dbp  =  <dig> yields the relations β =  <dig> and  <dig> - 2θ + 2γ =  <dig>  so θ = γ + 1/ <dig>  and the distance formula reduces to:
it is most plausible to count a total of  <dig> breakpoint for a fusion or fussion of linear chromosomes, which implies γ = ψ =  <dig>  so the most natural choice of breakpoint distance between Π and Γ is
it might be argued that a fussion or fusion should count for as many as  <dig> breakpoints, or anything between  <dig> and  <dig>  so that alternate values of γ and ψ might be entertained, provided γ ∈  <cit> , and ψ ∈ .
this may have an influence on how to calculate the number of breakages within a scenario, as discussed in  <cit> .
for example, the parameters chosen in  <cit>  are γ =  and ψ = , giving rise to the disadvantage of there possibly being more breakpoints between two genomes than adjacencies in either one.
for example, in comparing Π =  and Γ in which five linear chromosomes each contain one gene i ∈ { <dig> ...,5}, the definition in  <cit>  would count  <dig> breakpoints, which seems counterintuitive, while our definition counts  <dig>  which seems more reasonable.
whether all the results presented in this paper also hold for the definition in  <cit>  is open.
the definition of the breakpoint distance is easily transposable to the comparison of two all-duplicates genomes.
for one all-duplicates genome Δ and one ordinary genome Π, the breakpoint distance between Π and Δ is the minimum breakpoint distance between Δ and a doubled genome Π ⊕ Π, that is,
the double cut-and-join distance
given a genome Π, a double-cut-and-join  is an operation ρ acting on two adjacencies pq and rs .
the dcj operation replaces pq and rs either by pr and qs, or ps and qr.
an example of dcj operation on the genome Π of figure  <dig> is drawn in figure  <dig>
a dcj can reverse an interval of a genome, may cause the fussion of one chromosome into two, or the fusion of two chromosomes into a one, or a reciprocal translocation: the exchange of two telomere-containing segments between two chromosomes.
two consecutive dcj operations, excising and circularising a chromosomal segment followed by a re-linearisation of the circular intermediate and reintegration on the same chromosome, using two new cut-points, results in a block interchange: two segments of the genome appear to simply exchange their positions.
in the case these two segments are consecutive, the two dcjs result in a transposition, the apparent movement of a segment from one place on a chromosome to another.
the dcj operation is thus a very general framework, introduced by yancopoulos et al.
<cit> , as well as by lin et al.
in a special case  <cit> , and since been adopted by bergeron et al.
<cit>  and many others, sometimes under other names such as spring  <cit>  or "2-break rearrangement"  <cit> .
if Π and Γ are two genomes on a set  of n genes, the minimum number of dcj operations needed to transform Π into Γ is called the dcj distance and noted ddcj.
this dcj distance is easily defined also for two all-duplicates genomes.
for one all-duplicates genome Δ and one ordinary genome Π, the dcj distance between Π and Δ is ddcj = minΠ⊕Π ddcj.
the reversal/translocation distance
the reversal/translocation distance was introduced by hannenhalli and pevzner  <cit> , and is equivalent to the dcj distance constrained to linear genomes.
if Π is a linear genome, a linear dcj operation is a dcj operation on Π that results in a linear genome.
this allows reversals, chromosome fusions, fussions, and reciprocal translocations.
dcjs that create circular intermediates, temporary circular chromosomes, and thereby mimic block interchanges and transpositions, are not allowed.
chromosome fusions and fussions are particular cases of translocations in this framework, justifying the appellation rt-distance.
if Π and Γ are linear genomes, the rt distance between Π and Γ is the minimum number of linear dcj operations that transform Π into Γ, and is noted drt .
computational problems
the classical literature on genome rearrangements aims at reconstructing the evolutionary events and ancestral configurations that explain the differences between the organization of extant genomes.
the focus has been on the genomic distance, median and halving problems.
more recently the doubled distance and guided halving problems have also emerged as important.
in each of the ensuing sections of this paper, these five problems are examined for a specific combination of distance d  and kind of multichromosomal karyotype .
<dig>  distance.
given two genomes Π, Γ, compute d. once the distance is calculated, an additional problem in the cases of dcj and rt is to reconstruct the rearrangement scenario of length d, i.e.
the putative events that differentiate the genomes.
<dig>  double distance.
given an all-duplicates genome Δ and an ordinary genome Π, compute d. this computation evaluates the evolutionary distance posterior to a wgd of the given genome Π, leading to an all-duplicates genome Δ, and locates the genes of the all-duplicates genome on chromosomes in one of the two ancestral copies of the ordinary genome.
because the assignment of labels "1" or "2" to the two identical  copies of a duplicated gene in Δ is arbitrary, the double distance problem is equivalent to finding such an assignment that minimises the distance between Δ and a genome Π ⊕ Π considered as ordinary genomes, where all the genes on any one chromosome in Π ⊕ Π are uniformly labeled "1" or "2"  <cit> .
the double distance function is not symmetric because Δ is an all-duplicates genome and Π is an ordinary one, thus capturing the presumed asymmetric temporal and evolutionary relationship between the ancestor Π and the present-day genome Δ.
<dig>  median.
given three genomes Π <dig>  Π <dig>  Π <dig>  find a genome m which minimises d + d + d. the median problem estimates the common ancestor of two genomes, given a third one as an outgroup.
this is meaningful even in the "unrooted" case, where it is not specified which of the three genomes is the outgroup, because of the symmetry of the sum to be minimised.
<dig>  halving.
given an all-duplicates genome Δ, find an ordinary genome Π which minimises d, the double distance mentioned above.
the goal of a halving analysis is to reconstruct the ancestor of an all-duplicates genome at the time of a wgd event.
<dig>  guided halving.
given an all-duplicates genome Δ and an ordinary genome Π, find an ordinary genome m which minimises d + d. the guided halving problem is similar to the genome halving problem for Δ, but it takes into account the ordinary genome Π of an organism presumed to share a common ancestor with m, the reconstructed undoubled ancestor of Δ. a variant of the guided halving problem introduced in  <cit>  is to find an ordinary genome m that is a solution to genome halving, that is, minimises d, and which in addition minimises d. this helps choosing, among the numerous solutions to the genome halving problem, the one that is closest to the outgroup.
we do not study this variant here, and it is open for all genomic distances.
we will survey these five computational problems for the three distances that we have introduced, in the cases of multichromosomal genomes containing all linear chromosomes, all circular chromosomes, or permitting both.
the latter are refered as mixed genomes.
while many problems are open for multichromosomal genomes, there is a huge amount of research on these problems for unichromosomal genomes, whether circular or linear .
they are not systematically particular cases of the multichromosomal problems, as the constraint of keeping only one chromosome along a rearrangement scenario can result in more difficult problems.
more precisely, unichromosomal dcj problems reduce to rt multichromosomal ones.
indeed, the rt operations always transform a unichromosomal genome into a unichromosomal one.
as this paper contains very few results on the rt distance, practically the unichromosomal cases are often independent and not generalized here.
results on unichromosomal genomes are summarised in table  <dig>  together with the results for the multichromosomal case we review or present here.
a complete survey on these problems can be found in  <cit> .
RESULTS
breakpoint distance, circular and mixed genomes
in this section, d = dbp, and genomes are considered in their most general definition, that is, multichromosomal with both circular and linear chromosomes allowed.
all the results also stand for circular genomes, but not always for linear genomes, which will be considered in a following section.
as the nuclear genome of a eukaryotic species, a mixed karyotype is rarely observed, so probably unstable.
nevertheless this case is of great theoretical interest, as it is the only combination of distance and karyotype where all five problems mentioned in the previous section prove to be polynomially solvable, including the median problem which is hard for almost every other variant.
furthermore, the solutions in this context may suggest approaches for other variants of the problems, as well as providing a rapid bound for other distances, through the watterson et al.
bound  <cit> .
distance and double distance
the distance computation follows directly from the definition, and is easily achievable in linear time.
the double distance computation is also easy: let Π be a genome and Δ be an all-duplicates genome.
let a be the sum, for every adjacency xy in Π, of the number of adjacencies among x1y <dig>  x1y <dig>  x2y <dig>  x2y <dig> in Δ. let e be the sum, for every telomere x in Π, of the number of telomeres among x <dig> and x <dig> in Δ.
then we obtain
indeed, it is a lower bound on the distance, because a and e are upper bounds on the number of common adjacencies and common telomeres, respectively, between Δ and any Π ⊕ Π. this lower bound is attained by constructing Π ⊕ Π in the following way: let xy be a possibly telomeric adjacency in Π ; if x1y <dig> or x2y <dig> is an adjacency in Δ, choose x1y <dig> and x2y <dig> as adjacencies in Π ⊕ Π; if x1y <dig> or x2y <dig> is an adjacency in Δ, choose x1y <dig> and x2y <dig> as adjacencies in Π ⊕ Π; the two cases are either mutually exclusive if xy is not telomeric, or identical if xy is telomeric, so the assignment is made without ambiguity.
for all adjacencies that have not been assigned, assign them arbitrarily.
median
the following result contrasts with the np-completeness proofs of almost all median problems in the literature  <cit>  .
the problem is np-complete for unichromosomal genomes, that is, when the median genome m is required to be unichromosomal, whether the genomes are linear or circular  <cit> , but the multichromosomal case happens to be easier.
theorem  <dig>  there is a polynomial time algorithm for the breakpoint median problem for multichromosomal genomes.
proof.
let Π <dig>  Π <dig>  Π <dig> be three genomes on a gene set  of size n. for any genome m on , let s = d + d + d be the median score of m.
draw a graph g on the vertex set containing  all extremities of genes in , and  one supplementary vertex tx for every gene extremity x. for any pair of gene extremities x, y, draw an edge xy weighted by the number of genomes, among Π <dig>  Π <dig>  Π <dig>  for which xy is an adjacency.
then there is an edge between each pair of gene extremities, weighted by  <dig>   <dig>   <dig>  or  <dig>  now for any vertex x, draw an edge xtx weighted by half the number of genomes, among Π <dig>  Π <dig>  Π <dig>  having x as a telomere.
each edge xtx is then weighted by  <dig>  ,  <dig>  or .
finally, put an edge of weight  <dig> between tx and ty for all pairs of gene extremities x, y. let m be a perfect matching in g. clearly, the edges joining gene extremities in m define the adjacencies of a genome, which we also call m. the relation between the weight of the perfect matching m and the median score of the genome m is easy to state:
claim  <dig>  the weight w of the perfect matching m in g is 3n - s.
indeed, for any genome Πi, , where ai = a is the number of common adjacencies between m and Πi, and ei = e is the number of common telomeres between m and Πi.
if m and Πi have a common adjacency or a common telomere, this accounts for  <dig> or , respectively, in the weight of the perfect matching m. so the weight of the matching m is , which yields d + d + d = 3n - w.
conversely, any genome m can be extended to a perfect matching m in g such that s = 3n - w: construct the matching m by including the edges xy and txty for each adjacency xy and an edge xtx for each telomere x.
claim  <dig> implies that a maximum weight perfect matching m is a minimum score median genome.
as the maximum weight perfect matching problem is polynomial  <cit> , so is the breakpoint median problem.
□
if the three genomes in the instance are circular, then it is possible to constrain the result to also be circular by restricting the graph g to the extremities of the genes.
then, in the same way, a perfect matching gives a circular solution to the median problem.
this is not the case for linear genomes, since there is no way to guaranty that no chromosome in an instance is circular.
note that a generalisation of this algorithm remains valid if the median of more than three genomes is to be computed.
the phylogeny problems, both "big" and "small" versions, which also generalise the median problem for three genomes, remain open.
the big problem is the search for a steiner tree in the space of genomes, minimising the sum of the distances on its branches, while in the small problem, presumably easier, the graph-theoretical structure of the tree, namely its vertex set and edge or branch set, are given, and only the genomes corresponding to the extra vertices  need to be reconstructed.
halving
to our knowledge, the genome halving with breakpoint distance has not yet been studied.
in this framework, it has an easy solution, using a combination of elements from the maximum weight perfect matching technique in the solution of the median problem presented above, and the double distance computation.
let Δ be an all-duplicates genome on a gene set , and g be the graph on the vertex set containing  all the extremities of the genes in , and  one supplementary vertex tx for every gene extremity x. for any pair of gene extremities x, y, draw an edge in g weighted by zero, one or two according to the number of adjacencies in Δ among x1y <dig>  x1y <dig>  x2y <dig>  and x2y <dig>  now for any vertex x, draw an edge xtx weighted by half the number of telomeres among x <dig> and x <dig> in Δ. finally, put an edge of weight  <dig> between txty for all pairs of gene extremities x, y.
for a genome m on , define a perfect matching, also called m, by including edges xy and txty for each adjacency xy, and an edge xtx for each telomere x. let w be the weight of the matching m.
claim  <dig>  for a genome m on , the perfect matching m thus constructed satisfies w = 2n - d.
indeed, the score of the perfect matching m is , that is, 2n - d, according to the double distance formula .
conversely, it is easy to see that any perfect matching on g defines a genome m such that w = 2n - d. this implies that the maximum weight perfect matching solves the genome halving problem in the breakpoint distance context.
again, it is possible to solve the problem on only circular genomes by restricting the graph g to the gene extremities, dropping the tx supplementary vertices.
guided halving
as is the case for the median problem, this context provides the only polynomial result for the guided genome halving problem up to our knowledge.
the solution combines elements of the three previous results, on the double distance, median and halving problems.
let Δ be an all-duplicates genome on a gene set , and Π be an ordinary genome on .
let g be the graph on the vertex set containing  all the extremities of the genes in , and  one supplementary vertex tx for every gene extremity x.
for any pair of gene extremities x, y, there is an edge in g weighted by the number of adjacencies among x1y <dig>  x1y <dig>  x2y <dig>  x2y <dig> in Δ, and xy in Π. now there is an edge xtx for any gene extremity x weighted by half the number of telomeres among x <dig>  x <dig> in Δ and x in Π. so each edge between gene extremities has an integer weight in { <dig>   <dig>   <dig>  3}, and xtx edges may have weight  <dig>  ,  <dig>  or .
add 0-weight edges txty for all pairs x, y of gene extremities.
for any genome m, let s = d + d. it is possible to construct a perfect matching m in g from genome m by choosing edges xy and txty for every adjacency xy in m. its weight is denoted w.
claim  <dig>  for a genome m, the perfect matching thus constructed satisfies w = 3n - s.
indeed, the weight of the perfect matching m is .
according to the double distance formula , this yields w = 3n - s.
conversely, if m is a perfect matching in g, its edges between gene extremities define the adjacencies of a genome m which satisfies s = 3n - w. this implies that the maximum weight perfect matching solves the guided genome halving problem in the breakpoint distance context.
as is the case for the median problem, it is possible to generalise this statement for an arbitrary number of ordinary outgroup genomes.
the phylogenetic problems are open.
again, we can solve the problem on circular genomes by dropping the tx supplementary vertices in the graph g.
breakpoint distance, linear case
in this section, d = dbp and all genomes must be linear, as is most appropriate for modeling for the eukaryotic nuclear genome.
in contrast to the model of the previous section, all the problems concerning at least three genomes are np-complete.
distance and double distance
the solutions to these problems are the same as in the previous section, where circularity was allowed.
in the double distance computation, it is guaranteed that Π ⊕ Π is linear if Π is linear, because if x is a telomere in Π, then both x <dig> and x <dig> are telomeres in Π ⊕ Π.
median
whereas the median is polynomial in the circular and mixed cases, it changes complexity as soon as median genomes are required to be linear.
this does not prevent the use of the polynomial algorithm described above as a lower bound, but all biologically relevant median problems seem in fact to be np-complete.
theorem  <dig>  the breakpoint median problem for multichromosomal linear genomes is np-hard.
proof.
we use a reduction from the 2-chromosome breakpoint median, for which np-hardness is proved in lemma  <dig>
the 2-chromosome breakpoint median problem takes as input three unichromosomal linear genomes Π <dig>  Π <dig>  and Π <dig> on a set  of genes, all having the same pair of telomeres.
it asks for a linear genome m on  with at most two chromosomes, which minimises its median score s = d + d + d. the following lemma states the difficulty of the breakpoint median problem compared to the 2-chromosome breakpoint median problem, and thus, together with lemma  <dig>  proves theorem  <dig>
lemma  <dig>  let Π <dig>  Π <dig>  Π <dig>  be three unichromosomal linear genomes Π <dig>  Π <dig>  and Π <dig> all having the same pair of telomeres on the gene set  = { <dig> ...,n}, and k be a positive integer.
there exists a genome m on  with at most two linear chromosomes such that s ≤ k if and only if there exists a multichromosomal linear genome m' on  with s ≤ k.
: this direction is trivial: simply take m' = m.
: let m' be a linear multichromosomal genome satisfying s ≤ k, that has as few chromosomes as possible.
we will prove that m' has at most two chromosomes.
suppose m' has at least three chromosomes.
then it has at least six telomeres v <dig> ...,v <dig>  among them, it is possible to identify two telomeres , that belong to different chromosomes and are not telomeres in Π <dig>  Π <dig>  or Π <dig>  because by hypothesis, they all have the same two telomeres.
then the genome constructed from m' by adding the adjacency v1v <dig> has at most the same median score as m' and fewer chromosomes, contradicting the hypothesis on m'.
so choosing m = m' gives a genome with at most two chromosomes such that s ≤ k.   □
we now need to prove the np-hardness of the 2-chromosome breakpoint median problem.
we use a reduction from the hamiltonian cycle problem for directed graphs with vertex degree at most three, similar to the proof of bryant  <cit>  for the breakpoint median problem for unichromosomal circular genomes.
lemma  <dig>  the 2-chromosome breakpoint median problem is np-hard.
proof.
given a directed graph with maximum degree  <dig>  deciding if it has a hamiltonian directed cycle is an np-complete problem  <cit> .
let thus g <dig> be such a digraph.
we will construct an instance of the 2-chromosome breakpoint median problem from g <dig>
first, let g be the directed graph with vertex set v  = v  ∪ {xe : e ∈ e} ∪ {p, q}, and arc set
note that g <dig> has a hamiltonian cycle if and only if there is a cycle in g covering all vertices but p and q. given a subset x ⊆ e of the arcs of a graph g, let gx denote the graph with vertex set v and arc set x.
construct three subsets a, b, c of arcs of g such that every arc of g belongs to exactly one of a, b, c, and a, b, c are either hamiltonian cycles of g or sets of vertex disjoint paths in g. the procedure is straightforward: for all vertex v of g which is a vertex of g <dig>  put all incoming arcs in different subsets, and all outgoing arcs in different subsets.
it can be done independently for every vertex because from the construction of g, no two vertices of g <dig> are neighbors.
eventually put arc pq in any subset.
now perform a series of modifications of g to obtain a graph with three hamiltonian cycles a, b, and c. along these modifications, we maintain a subset of arcs called supplementary arcs, noted s. before any transformation, s is empty.
the goal is to maintain the property that there exists a cycle covering all vertices of g except p and q and not using supplementary arcs if and only if there is a hamiltonian cycle in g <dig>  as already remarked, the property is true at the beginning.
choose x ∈ {a, b, c} such that x is not a hamiltonian cycle in g .
choose two vertices a and b such that adding the arc ab to g and x would either give a graph in which x is a hamiltonian cycle, or a set of disjoint paths with fewer components.
then choose any vertex x of g different from a and b. perform the following transformation illustrated in figure 4: add two new vertices y and z. for each arc xw of g, replace it by the arc zw, and add zw to y ∈ {a, b, c} whenever xw ∈ y. add arcs xy, yz, xz, ay, yb to g. add xz, ay, yb to x. also add xz, ay, yb to s, and add xy, yz to all {a, b, c}\x.
clearly, the property that there exists a cycle covering all vertices of g except p and q and not using supplementary arcs if and only if there is a hamiltonian cycle in g <dig> is still true after this transformation.
repeat this process until a, b and c are all hamiltonian cycles in the resulting graph, which we call g'.
the weight of an arc of g' is the number of hamiltonian cycles among a, b and c which contain this arc.
note that g' has only weight  <dig> and  <dig> arcs.
let v be an arbitrary vertex of g, different from p and q. let  = v\{v} ∪ {v <dig>  v2} be a set of genes .
for every x ∈ {a, b, c}, construct a genome Πx on  such that xhyt is an adjacency in genome x if xy is an arc of x in g' and x, y are different from v; if xv and vy are the arcs of x covering v, add the adjacencies  and .
this gives three linear unichromosomal genomes on  with the same pair of telomeres , thus an instance of the 2-chromosome breakpoint median problem.
for any genome m on , the weight of an adjacency xy is the number of genomes, among Πa, Πb and Πc, which contain this adjacency.
adjacencies uhwt in m such that uw is an arc in s are called supplementary adjacencies.
let λi be the number of arcs of weight i in the graph g', for each  <dig> ≤ i ≤  <dig>  for any genome m on , note s = d + d + d. the following is inspired by a result from  <cit>  used in  <cit> .
claim  <dig>  let n = |v |.
a genome m with nm linear chromosomes on  satisfies s ≥ 2n -  <dig> + nm - λ <dig>  where equality holds if and only if m contains all adjacencies of weight  <dig>  and no adjacency of weight  <dig>
indeed, for a genome m, denote by w the weight of the adjacency xy, and li = |xy adjacency of m: w = i|, for each  <dig> ≤ i ≤  <dig>  let t <dig> =  <dig> if m has  as a telomere, and t <dig> =  <dig> otherwise, and t <dig> =  <dig> if m has  as a telomere, and t <dig> =  <dig> otherwise.
then we may write .
as genome m has nm chromosomes, we have l <dig> + l <dig> + l <dig> + l <dig> = ||nm and || = n +  <dig>  so .
as by construction no arc of g' has weight  <dig>  we may write s ≥ 2n -  <dig> + nm - λ <dig>  equality holds if and only if l <dig> = λ <dig>  l <dig> =  <dig>  and , that is, if and only if m contains all adjacencies of weight at least  <dig>  and no adjacency of weight  <dig>  because l <dig> =  <dig> implies that  and  are telomeres of m, thus .
claim  <dig>  there is a linear genome m on  with at most two chromosomes, with s = 2n -  <dig> + nm - λ <dig> if and only if there is a hamiltonian cycle in g <dig>
suppose there is a linear genome m on  with at most two chromosomes, with s = 2n -  <dig> + nm - λ <dig>  this implies by claim  <dig> that m contains all adjacencies of weight  <dig>  no adjacency of weight  <dig>  and that  and  are telomeres of m. from the construction of g', m cannot contain any supplementary adjacency, since the extremities of supplementary adjacencies all are also extremities of weight two adjacencies, which are all contained in m. note that in g', paths between vertices p and q to other vertices of the graph necessarily contain supplementary arcs.
this yields that m has two chromosomes, one containing gene extremities from p and q, and the other containing the gene extremities from the other vertices, with telomeres  and .
let h ⊆ e contain the arcs xy such that xhyt is an adjacency in m, plus the arcs xv and vy for adjacencies of type  and  in m.
h ∩ e yields a hamiltonian cycle in g <dig>
suppose there is a hamiltonian cycle in g <dig>  then there is a cycle h covering all vertices of g' except p and q. construct genome m on  by adding  adjacencies xhyt whenever xy is in h and x, y are different from v  adjacencies  and  whenever xv or vy are arcs of h,  all weight two adjacencies, and  the adjacency ptqh.
it is easy to check that m is a genome on , and by construction it contains all weight  <dig> adjacencies and no weight  <dig> adjacencies.
this proves that it is np-complete to decide if a median genome reaches the lower bound of claim  <dig> for its score, thus computing the minimum score median genome is np-hard.
□
a byproduct of this proof is the np-hardness of the 2-chromosome breakpoint median problem.
the result implies np-completeness of the general case, where the genomes in the instance do not necessarily have the same pairs of telomeres.
a consequence is that for any fixed k, it is also np-hard to compute a best linear median genome with at most k chromosomes.
halving
surprisingly, this problem has not been treated in the literature.
we conjecture it has a polynomial solution, because the halving problem for all other rearrangement distances is polynomial.
constructing a solution is beyond the scope of this paper, and the problem remains open.
guided halving
this problem is np-hard, as proved in  <cit> , using the np-completeness result for the median proved just above in this section.
dcj distance, general case
in this section, d = ddcj.
genomes can have several chromosomes, circular or linear.
this is the most general context in which the dcj distance has been explicitly formulated  <cit> .
genomes rarely contain both circular and linear chromosomes; eukaryote nuclear genomes contain multiple linear chromosomes while prokaryotes generally contain one large circular chromosome, sometimes with additional plasmids.
nevertheless, the simplicity of the computational framework where both genomes may contain both circular and linear chromosomes makes it attractive to mathematical study.
note that the complexity of the median problem is not established by the work of caprara  <cit> , who proved the unichromosomal result only.
we show the np-hardness of the multichromosomal case here.
alekseyev and pevzner  <cit>  mention that the complexity of the double distance problem in the context of circular genomes is open; we show here that it is np-hard as well.
distance
there is an easy linear solution, both for the distance and the scenario computation  <cit> .
we briefly recall the formula for computing the distance, because the underlying principle will be used in our proofs later on in this paper.
the breakpoint graph of two genomes Π and Γ on a gene set , denoted by bp, is the graph whose vertex set is the set of extremities of the genes in , where there is an edge between two vertices x and y if xy is an adjacency in either Π  or Γ .
note that we do not invoke any ∘ symbols in the construction of the breakpoint graph.
vertices in this graph have degree zero, one or two, so that the graph is a set of paths  and cycles.
it is also the line-graph of the adjacency graph, an alternate representation in  <cit> .
figure  <dig> shows an example of a breakpoint graph.
theorem  <dig> shows how to obtain the distance directly from the graph.
the formula is presented in  <cit>  with the cycles and odd paths of the adjacency graph.
this corresponds to cycles and even paths of the breakpoint graph, as it is the line-graph of the adjacency graph.
theorem  <dig>   <cit> for two genomes Π and Γ on a gene set  of size n, let c be the number of cycles of the breakpoint graph bp, and p be the number of paths with an even number of edges.
then
note the similarity to the breakpoint distance formula in the background section on page  <dig>  the number of genes n is the same in both formulae, the parameter c is related to parameter a in the breakpoint formula in that each common adjacency is a cycle of the breakpoint graph , and parameter p is related to parameter e, as each shared telomere is an even path  in the breakpoint graph.
although these two measures of genomic distance were derived in different contexts and through different reasoning, their formulae show a remarkably similar form.
they differ in that the dcj formula also counts non-trivial cycles and paths, but for distant genomes, both measures tend to give similar values.
double distance
the np-completeness proof for the double distance problem follows the principles of caprara's hardness proof for the median problem in the unichromosomal case  <cit> .
theorem  <dig>  the dcj double distance problem is np-hard for multichromosomal mixed or circular genomes.
proof.
the reduction is from the breakpoint graph decomposition  problem .
a graph g is bicoloured if all its edges are coloured either red or blue; it is balanced if it has only degree  <dig> or degree  <dig> vertices, every vertex is incident to the same number of red and blue edges, and there is no cycle formed by only red or only blue edges.
given a balanced bicoloured graph g, the breakpoint graph decomposition problem is to find a partition of the edges of g into a maximum number of edge-disjoint cycles, each alternating between red and blue edges.
caprara  <cit>  first proved the np-hardness of this problem, and berman and karpinski  <cit>  extended this by proving apx-hardness.
let g be a balanced bicoloured graph on n vertices, defining an instance of the bgd problem.
let w <dig> be the number of degree  <dig> vertices of g, and w <dig> be the number of degree  <dig> vertices of g. define the gene set  as the vertex set of g. construct an all-duplicates genome Δ and a genome Π on  in the following way, as illustrated in figure  <dig>  first, for each gene x of , let xtxh be an adjacency in Π. then, for every vertex x of g, let x1t, x1h, x2t and x2h, be the extremities of the duplicated gene x. if x has degree two in g, add the adjacency x1tx2h in Δ .
then for each blue edge xy in g, choose among x1h and x2h an extremitiy that is not yet involved in an adjacency, and another among y1h and y2h .
add an adjacency between the two chosen extremities in Δ. then for each red edge xy in g, choose among x1t and x2t an extremitiy that is not yet involved in an adjacency, and another among y1t and y2t .
add an adjacency between the two chosen extremities in Δ.
we then have an all-duplicates genome Δ, and a genome Π. note that Π is composed of n circular chromosomes, one for each gene, and that neither Π nor Δ have telomeres.
claim  <dig>  the maximum number of edge-disjoint alternating cycles in g is equal to 2n - d - w <dig>
.
we first prove that the maximum number of edge-disjoint alternating cycles in g is at least 2n - d - w <dig>  let Π ⊕ Π be the doubled genome such that d = d. as no genome has a telomere, by theorem  <dig>  d = 2n - c. therefore there are c edge-disjoint cycles in bg alternating between Π ⊕ Π-edges and Δ-edges.
among them, w <dig> cycles are containing only two edges: if a vertex x of g has degree  <dig>  then Π ⊕ Π has the adjacency x1tx2h and x2tx1h because the other possibility systematically has one cycle less in bg.
the Δ edges of all the other cycles are the edges of an alternating blue-red cycle in g. indeed, every blue edge defines an adjacency in Δ containing two gene heads, and every red edge defines an adjacency containing two gene tails.
the Π ⊕ Π-edges all join one tail and one head, so two consecutive Δ-edges in a cycle of bg have different colours.
this means there are at least 2n - d - w <dig> alternating cycles in g.
conversely, if there are k edge-disjoint alternating cycles in g, then d ≤ 2n - k - w <dig>  indeed, let c be any cycle of this partition.
for every covered vertex x of degree  <dig> in g, let e and f be two consecutive edges of c  which are both incident to x. if e defines an adjacency in Δ which contains x2h and f defines an adjacency which contains x2t, choose x1hx1t and x2hx2t as adjacencies for Π ⊕ Π. if e defines an adjacency which contains x2h  and f defines an adjacency which contains x1t , choose x1hx2t and x2hx1t as adjacencies for Π ⊕ Π. for vertices of degree  <dig>  always choose x1hx2t and x2hx1t as adjacencies for Π ⊕ Π. in this construction, each red-blue alternating cycle in g is a Π ⊕ Π-Δ alternating cycle in bp that has at least k cycles.
and there are w <dig> additional length  <dig> cycles at each degree  <dig> vertex.
so d ≤ 2n - k - w <dig>    □
median
though effective exact algorithms  <cit>  and heuristics  <cit>  are available, we have:
theorem  <dig>  the dcj median problem for multichromosomal genomes is np-hard, even for circular genomes.
proof.
we use a reduction from the breakpoint graph decomposition defined in the proof of theorem  <dig>  in a way very similar to part of caprara's proof  <cit>  for the unichromosomal case.
let g be a balanced bicoloured graph on n vertices.
define the gene set  as a set containing one gene x for every degree  <dig> vertex of g, and two genes x and y for every degree  <dig> vertex of g.
then construct the genomes Π <dig>  Π <dig>  Π <dig> in the following way, which is similar to the transformation in  <cit> , as illustrated in figure  <dig>
for each degree  <dig> vertex v of g, add the two adjacencies xtxh and ytyh to Π <dig>  and the two adjacencies xtyh and ytxh to Π <dig>
now fo every blue edge vw in g, add to Π <dig> an adjacency between heads of genes contructed from v and w .
and for every red edge vu in g, add to Π <dig> an adjacency between tails of genes contructed from v and u .
it is easy to see that Π <dig>  Π <dig>  and Π <dig> define genomes on the set of genes , and they have no telomeres.
let w <dig> be the number of degree  <dig> vertices of g, and w <dig> be the number of degree  <dig> vertices of g.
claim  <dig>  there exists a genome m on  such that d + d + d ≤ w <dig> + 3w <dig> - k if and only if there exists at least k edge-disjoint alternating cycles in g.
: suppose there are k edge-disjoint alternating cycles in g. we will construct a median genome m such that d + d + d = w <dig> + 2w <dig> - k. first, for each degree  <dig> vertex v of g, let xtxh be in m. then, let v be a degree  <dig> vertex in g, and vw be a blue edge incident to v. in an alternating cycle, edge vw is consecutive with a red edge, say uv.
to vw is associated a constructed Π <dig> adjacency, say xhwh.
then either the Π <dig> adjacency associated to uv contains the gene extremity xt, or it contains the extremity yt.
in the first case, let xhxt and yhyt be in m, and in the second case, let xhyt and xty h be in m. the matching m defines the adjacencies of a circular genome on , that we also call m. there are w <dig> + 2w <dig> genes, so by theorem  <dig>  d + d + d =  <dig> -  + c + c).
by construction, we have c + c = 2w <dig> + 3w <dig>  and c = k, so d + d + d = w <dig> + 3w <dig> - k.
: suppose m is a genome such that d + d + d ≤ w <dig> + 3w <dig> - k. suppose m is chosen such that d + d + d is minimum, and among all such genomes, choose m with a maximum number of edges parallel to Π1-edges or Π2-edges.
a circular genome is said to be canonical if it only has adjacencies that belong to Π <dig> or Π <dig>  we will prove that m is canonical.
subclaim.
m is canonical.
suppose m is not canonical.
suppose first that there is a degree  <dig> vertex v in g, such that m does not contain the adjacency xtxh.
suppose m contains adjacencies xta and xhb, where a and b are gene extremities or ∘ symbols if xt or xh is a telomere in m. then replace xta and xhb by xhxt and ab .
by this operation, c and c both increase by at least  <dig>  and c decreases by at most  <dig>  so d + d + d decreases by one, contradicting the hypothesis.
now suppose that there is a degree  <dig> vertex in g, such that m does not contain any of the adjacencies xhxt, yhyt, xhyt, yhxt.
say it contains adjacencies xha, xtb, y hc, ytd, where a, b, c, d may be null symbols if any of xh, xt, y h, yt is a telomere in m. then replace xha, xtb, yhc, ytd by xhxt, yhy t, and either ab, cd, or ac, bd, or ad, bc, according to the combination that creates the largest number of cycles in bp.
suppose now that m contains only one among the adjacencies xhxt, yhy t, xhyt, yhxt, say xhxt, and m has adjacencies ytb and y hc.
then replace edges ytb and y hc by yhyt and bc.
all these operations decrease d + d + d or maintain it constant, while increasing the number of edges parallel to Π <dig> and Π <dig>  contradicting the hypothesis.
so the subclaim is proved.
now, since m is canonical, there are c edge-disjoint alternating cycles in g, since an adjacency of m always joins a head and a tail, so the corresponding edge in g is adjacent to one red edge at one of its vertices and one blue edge at the other.
by theorem  <dig>  c =  <dig> -  + d + d + c + c) and, by hypothesis, c ≥  <dig> - , that is, c ≥ k, which proves the claim.
□
halving
this problem has a polynomial solution, as recently stated for unichromosomal genomes by  <cit>  and in the general case by  <cit> .
all these algorithms are simplified versions of the algorithm by el-mabrouk and sankoff  <cit> , developed for the rt rearrangement distance, which allows reversals, translocations, fusions and fissions, but not the other dcj operations.
guided halving
theorem  <dig>  the dcj guided halving problem is np-complete for multichromosomal genomes.
proof.
again, we use a reduction of the breakpoint graph decomposition problem, as in the proofs of theorems  <dig> and  <dig>
let g be a balanced bicoloured graph on n vertices.
define the gene set  as a set containing one gene x for every degree  <dig> vertex of g, and two genes x and y for every degree  <dig> vertex of g. from g, we define one genome Π and one all-duplicates genome Δ on  as illustrated in figure  <dig>
for every degree  <dig> vertex v of g, let x be the corresponding gene in  and xt and xh its extremities.
for every degree  <dig> vertex v of g, let x and y be the two genes in , and xt and xh, y t and yh their extremities.
for every blue edge uv in g, construct an adjacency in Π between the heads of the genes constructed from u and v, choosing arbitrarily between the heads of vertices x and y if u or v have degree  <dig>  in such a way that no two adjacencies share an extremity .
for every red edge tv in g, construct an adjacency in Π between the tails of the genes constructed from t and v, again choosing arbitrarily between the tails of vertices x and y if t or v have degree  <dig>  this defines a genome Π on  that has no telomere.
now, define the genome Δ in the following way.
for each degree  <dig> vertex of g, Δ contains the adjacencies x1hx1t and x2hx2t defined by the extremities of the two copies of gene x. for each degree  <dig> vertex in g, Δ contains the adjacencies x1hx1t, y2hy2t, x2hy1t, and x2ty1h defined by the extremities of the two copies of the two genes x and y. this defines an all-duplicates genome Δ on  that has no telomere.
let w <dig> be the number of degree  <dig> vertices of g, and w <dig> be the number of degree  <dig> vertices of g.
claim.
there exists a genome m such that d + d ≤ w <dig> + 3w <dig> - k if and only if there exists at least k edge-disjoint alternating cycles in g.
: suppose there are k edge-disjoint alternating cycles in g. we will construct a genome m and a doubled genome m ⊕ m such that d + d ≤ w <dig> + 3w <dig> - k. first, for each degree  <dig> vertex v of g, let xtxh be in m, and m ⊕ m be constructed so that x1tx1h and x2tx2h are in m ⊕ m. then, for every vertex v of degree  <dig> of g, either the blue edge incident to xh is followed by the red edge incident to xt in one alternating cycle, or it is followed by the red edge incident to yt.
in the first case, let xhxt and y hyt be in m, and x1hx1t, x2hx2t, y1hy1t, y2hy2t be in m ⊕m.
in the second case, let xhyt and xtyh be in m, and x2hy1t, x1hy2t, x1ty2h, x2ty1h be in m ⊕ m.
the matching m defines a genome without telomeres, and m ⊕ m is one of its doubled genomes.
there are w <dig> + 2w <dig> genes, so by theorem  <dig>  d = w <dig> + 2w <dig> - c = w <dig> + 2w <dig> - k; and d =  <dig> - .
so d + d = w <dig> + 3w <dig> - k.
: suppose m is a genome such that d + d ≤ w <dig> + 3w <dig> - k. suppose m is chosen such that d + d is minimum, and among all such genomes, choose m with a maximum number of edges of type xtxh for a degree  <dig> vertex in g, or xhxt, yhyt, xhyt and xtyh for degree  <dig> vertices of g. a genome is said to be canonical if it has no telomeres and has only edges of type xtxh for a degree  <dig> vertex in g, or xhxt, yhyt, xhyt and xtyh for degree  <dig> vertices of g. we will prove that m is canonical.
subclaim.
m is canonical.
suppose m is not canonical.
suppose first that there is a degree  <dig> vertex v in g, such that m does not contain the edge xtxh.
suppose m contains edges xtu and xhv, where u and v are gene extremities or ∘ symbols if xt or xh is a telomere in m. then replace xtu and xhv by xhxt and uv .
by this operation, c decreases by at most one, while defining m ⊕ m as containing x1hx1t and x2hx2t makes c increase by at least  <dig>  this contradicts the hypothesis.
now suppose that there is a degree  <dig> vertex in g, such that m does not contain any of the edges xhxt, yhyt, xhyt, yhxt.
say it contains edges xht, xtu, yhv, ytw, where t, u, v, w may be null symbols if any of xh, xt, yh, yt is a telomere in m. then replace xht, xtu, yhv, ytw by xh, xt, yhyt, tu, vw or xhyt, tw, xtyh, uv, depending on the cycles in c.
suppose now that m contains only one among the edges xhxt, yhyt, xhyt, yhxt say xhxt, and m has edges ytu and yhv.
then replace edges ytu and yhv by yhyt and uv.
all these operations decrease d + d or maintain it constant, while increasing the number of edges of type xtxh for a degree  <dig> vertex in g, or xhxt, yhyt, xhy t and xtyh for degree  <dig> vertices of g, contradicting the hypothesis.
at the end of this process, m is canonical, so the subclaim is proved.
now, since m is canonical, there are c edge-disjoint alternating cycles in g, since an edge of m always joins a head and a tail, so that it is adjacent to one red and one blue edge.
by theorem  <dig>  c =  <dig> -  + d + c), and by hypothesis, c ≥  <dig> - ), that is, c ≥ k, which proves the claim.
□
dcj distance, linear chromosomes
in the original formulation of the dcj distance  <cit> , it was shown that there is a solution where each excision of a circular intermediate could be followed directly by its reinsertion.
thus the median and halving problems can be stated in terms of exclusively linear chromosomes in both the data genomes and the reconstructed ancestor.
they all remain open.
reversal/translocation distance
hannenhalli and pevzner proposed a polynomial-time algorithm for calculating drt  for two genomes Π and Γ  <cit> , after solving the problem for unichromsomal genomes  <cit> .
this was reformulated in  <cit> , minor corrections were added in  <cit>  and  <cit> , and bergeron et al.
simplified the formula  <cit>  and investigated the relations between drt and ddcj.
a polynomial time genome halving algorithm was given in  <cit> .
though the constrained dcj distance in the previous section is arguably just as realistic, because of the long history of drt, effective heuristics for rt have been developed and applied for the double distance  <cit> , median  <cit>  and guided halving problems  <cit> , but their complexities remain open questions.
note that  <cit>  gives an np-completeness result on a problem which slightly generalizes the reversal double-distance probem on unichromosomal genomes.
discussion and
CONCLUSIONS
problem context:
status of complexity questions for five problems related to ancestral genome reconstruction, for eight genomic distances in the unichromosomal and multichromosomal contexts.
note that unichromosomal problems require that both input and output genomes be unichromosomal, so all problems involving doubled genomes are computationally defined in the circular case, when the doubled genome consists in a single circular chromosome composed of two successive occurences of the ordinary genome.
other versions of the halving problem are less restrictive  <cit> .
p and np stand for polynomial and np-hard, respectively, and when followed by ?, represent our conjectures.
authors' contributions
et, cz and ds have elaborated the definition and conjectures, proved the results and written the paper.

 the gene order or syntenic arrangement of ancestral genomes may be reconstructed based on comparative evidence from present-day genomes – the phylogenetic approach – or on internal evidence in the case of genomes descended from an ancestral polyploidisation event, or from a combination of the two. the computational problem at the heart of phylogenetic analysis is the median problem, while internal reconstruction inspires the halving problem, and the combined approach gives rise to guided halving. how these problems are formulated depends on the karyotypic framework: the number of chromosomes in a genome and whether they are constrained to be linear, or if circular chromosomes are also permitted, and on the objective function used to evaluate possible solutions. this function is based on some notion of genomic distance, either the number of adjacent elements on a chromosome in one genome that are disrupted in another – the breakpoint distance – or the number of evolutionary operations necessary to transform one genome to another. while the karyotypes allowed in an ancestor vary only according to the dimensions of single versus multiple chromosome, and linear versus circular versus mixed, the genomic distances of interest have proliferated according to the kinds of evolutionary operations considered, from the classic, relatively constrained, reversals/translocations distance to the more inclusive double cut-and-join measure, and many others. the computational complexity of some of these problems has been settled for some specific distances and karyotypic contexts, and it is sometimes taken for granted that these results carry over to other combinations of context and distance. this is not necessarily the case. in this paper, we survey the known results and unsolved cases for three distance measures in three kinds of karyotype. we include several results presented here for the first time, as well as discussions on the definitions of the distances. the results contain both new polynomial-time algorithms and np-hardness proofs. this paper is the full version of an extended abstract that has appeared in, which announced the results without giving all the proofs. in particular, a full discussion on the breakpoint distance definition, as well as the proofs of theorem theorem and theorem are added here, which makes this version a complete and definitive one. genomes, breakpoints and rearrangements multichromosomal genomes we follow the general formulation of a genome in. a gene a is an oriented sequence of dna, identified by its tail at and its head ah. tails and heads are the extremities of the genes. an adjacency is an unordered pair of gene extremities. a genome Π is a set of adjacencies on a set of genes. each adjacency in a genome means that two gene extremities are consecutive on the dna molecule. in a genome, each gene extremity is adjacent to zero or one other extremity. an extremity x that is not adjacent to any other extremity is called a telomere, and can be written as an adjacency x∘ with a null symbol ∘. the adjacency x∘ is called a telomeric adjacency. for a genome Π on a set of genes, consider the graph gΠ whose vertices are all the extremities of the genes, and the edges include all the non telomeric adjacencies in Π as well as an edge joining the head and the tail of each gene. this graph is a set of disjoint paths and cycles. every connected component is called a chromosome of Π. a chromosome is linear if it is a path, and circular if it is a cycle. a genome with only linear, or only circular, chromosomes is called a linear or circular genome, respectively. an example of a graph gΠ is given in figure a genome can also be represented as a set of strings, by writing the genes for each chromosome in the order in which they appear in the paths and cycles of the graph gΠ, with a bar over the gene if the head of the gene appears before the tail, and none if the tail appears before the head. for each linear chromosome, there are two possible equivalent strings, according to the arbitrary chosen starting point. one is obtained from the other by reversing the order and switching the signs of all the genes. for circular chromosomes, there are also two possible circular string representations, according to the direction in which the cycle is traversed. for example, chromosome c of the genome Π of figure may be written or. a genome with only one chromosome is called unichromosomal. these correspond to signed permutations: the two string representations are signed permutations. genomes with duplicates a duplicated gene a is a couple of homologous oriented sequences of dna, identified by two tails a1t and a2t, and two heads a1h and a2h. an all-duplicates genome Δ is a set of adjacencies on a set of duplicated genes. for a genome Π on a gene set, a doubled genome Π ⊕ Π is an all-duplicates genome on the set of duplicated genes from such that if axby is an adjacency of Π, either a1xb1y and a2xb2y, or a2xb1y and a1xb2y, are adjacencies of Π ⊕ Π. note the difference between a general all-duplicates genome and the special case of a doubled genome: the former has two copies of each gene, while in the latter these copies are organised in such a way that there are two identical copies of each chromosome when we ignore the 1's and 2's in the a1x's and a2x's: it has two linear copies of each linear chromosome, and for each circular chromosome, either two circular copies or one circular chromosome containing the two successive copiesnote also that for a genome Π, there is an exponential number of possible doubled genomes Π ⊕ Π. these definitions correspond to duplicated and perfectly duplicated genomes found in, and slightly differs from the perfectly duplicated genome definition found in, as discussed in. an example of an all-duplicates genome and a doubled genome is shown in figure doubled genomes are the immediate result of an evolutionary event called whole genome duplication, which is known to have occurred in many evolutionary lineages, from protists to yeasts, to plants, to fish, to amphibians and even to mammals. all-duplicates genomes derive from doubled genomes through a series of rearrangement events. typically, all-duplicates genomes pertain to extant species, while doubled genomes are ancestral configurations inferred to exist immediately after the wgd, and that are to be reconstructed. in discussing all-duplicates genomes, we will sometimes contrast them with ordinary genomes which have a single copy of each gene. the breakpoint distance the breakpoint distance has been well-studied for permutations, i.e., unichromosomal genomes, but only a few published discussions have focused on how it should be defined for multichromosomal genomes. the distance should depend not only on common adjacencies, or rather their absence, but also on common telomeres in two genomes. here we propose a definition that we wish valid for all types of karyotypes, based on a most general approach integrating all possible informations from the two genomes. for two genomes Π and Γ on a set of n genes, suppose Π has nΠ chromosomes, and Γ has nΓ chromosomes. let a be the number of common adjacencies, e be the number of common telomeres of Π and Γ. then insofar as it should depend additively on these components, we may suppose the breakpoint distance has form where β, θ and γ are positive parameters, while ψ may have either sign. taking Π = Γ and imposing dbp = yields the relations β = and - 2θ + 2γ = so θ = γ + 1/ and the distance formula reduces to: it is most plausible to count a total of breakpoint for a fusion or fussion of linear chromosomes, which implies γ = ψ = so the most natural choice of breakpoint distance between Π and Γ is it might be argued that a fussion or fusion should count for as many as breakpoints, or anything between and so that alternate values of γ and ψ might be entertained, provided γ ∈, and ψ ∈. this may have an influence on how to calculate the number of breakages within a scenario, as discussed in. for example, the parameters chosen in are γ = and ψ =, giving rise to the disadvantage of there possibly being more breakpoints between two genomes than adjacencies in either one. for example, in comparing Π = and Γ in which five linear chromosomes each contain one gene i ∈ {...,5}, the definition in would count breakpoints, which seems counterintuitive, while our definition counts which seems more reasonable. whether all the results presented in this paper also hold for the definition in is open. the definition of the breakpoint distance is easily transposable to the comparison of two all-duplicates genomes. for one all-duplicates genome Δ and one ordinary genome Π, the breakpoint distance between Π and Δ is the minimum breakpoint distance between Δ and a doubled genome Π ⊕ Π, that is, the double cut-and-join distance given a genome Π, a double-cut-and-join is an operation ρ acting on two adjacencies pq and rs. the dcj operation replaces pq and rs either by pr and qs, or ps and qr. an example of dcj operation on the genome Π of figure is drawn in figure a dcj can reverse an interval of a genome, may cause the fussion of one chromosome into two, or the fusion of two chromosomes into a one, or a reciprocal translocation: the exchange of two telomere-containing segments between two chromosomes. two consecutive dcj operations, excising and circularising a chromosomal segment followed by a re-linearisation of the circular intermediate and reintegration on the same chromosome, using two new cut-points, results in a block interchange: two segments of the genome appear to simply exchange their positions. in the case these two segments are consecutive, the two dcjs result in a transposition, the apparent movement of a segment from one place on a chromosome to another. the dcj operation is thus a very general framework, introduced by yancopoulos et al., as well as by lin et al. in a special case, and since been adopted by bergeron et al. and many others, sometimes under other names such as spring or "2-break rearrangement". if Π and Γ are two genomes on a set of n genes, the minimum number of dcj operations needed to transform Π into Γ is called the dcj distance and noted ddcj. this dcj distance is easily defined also for two all-duplicates genomes. for one all-duplicates genome Δ and one ordinary genome Π, the dcj distance between Π and Δ is ddcj = minΠ⊕Π ddcj. the reversal/translocation distance the reversal/translocation distance was introduced by hannenhalli and pevzner, and is equivalent to the dcj distance constrained to linear genomes. if Π is a linear genome, a linear dcj operation is a dcj operation on Π that results in a linear genome. this allows reversals, chromosome fusions, fussions, and reciprocal translocations. dcjs that create circular intermediates, temporary circular chromosomes, and thereby mimic block interchanges and transpositions, are not allowed. chromosome fusions and fussions are particular cases of translocations in this framework, justifying the appellation rt-distance. if Π and Γ are linear genomes, the rt distance between Π and Γ is the minimum number of linear dcj operations that transform Π into Γ, and is noted drt. computational problems the classical literature on genome rearrangements aims at reconstructing the evolutionary events and ancestral configurations that explain the differences between the organization of extant genomes. the focus has been on the genomic distance, median and halving problems. more recently the doubled distance and guided halving problems have also emerged as important. in each of the ensuing sections of this paper, these five problems are examined for a specific combination of distance d and kind of multichromosomal karyotype. distance. given two genomes Π, Γ, compute d. once the distance is calculated, an additional problem in the cases of dcj and rt is to reconstruct the rearrangement scenario of length d, i.e. the putative events that differentiate the genomes. double distance. given an all-duplicates genome Δ and an ordinary genome Π, compute d. this computation evaluates the evolutionary distance posterior to a wgd of the given genome Π, leading to an all-duplicates genome Δ, and locates the genes of the all-duplicates genome on chromosomes in one of the two ancestral copies of the ordinary genome. because the assignment of labels "1" or "2" to the two identical copies of a duplicated gene in Δ is arbitrary, the double distance problem is equivalent to finding such an assignment that minimises the distance between Δ and a genome Π ⊕ Π considered as ordinary genomes, where all the genes on any one chromosome in Π ⊕ Π are uniformly labeled "1" or "2". the double distance function is not symmetric because Δ is an all-duplicates genome and Π is an ordinary one, thus capturing the presumed asymmetric temporal and evolutionary relationship between the ancestor Π and the present-day genome Δ. median. given three genomes Π Π Π find a genome m which minimises d + d + d. the median problem estimates the common ancestor of two genomes, given a third one as an outgroup. this is meaningful even in the "unrooted" case, where it is not specified which of the three genomes is the outgroup, because of the symmetry of the sum to be minimised. halving. given an all-duplicates genome Δ, find an ordinary genome Π which minimises d, the double distance mentioned above. the goal of a halving analysis is to reconstruct the ancestor of an all-duplicates genome at the time of a wgd event. guided halving. given an all-duplicates genome Δ and an ordinary genome Π, find an ordinary genome m which minimises d + d. the guided halving problem is similar to the genome halving problem for Δ, but it takes into account the ordinary genome Π of an organism presumed to share a common ancestor with m, the reconstructed undoubled ancestor of Δ. a variant of the guided halving problem introduced in is to find an ordinary genome m that is a solution to genome halving, that is, minimises d, and which in addition minimises d. this helps choosing, among the numerous solutions to the genome halving problem, the one that is closest to the outgroup. we do not study this variant here, and it is open for all genomic distances. we will survey these five computational problems for the three distances that we have introduced, in the cases of multichromosomal genomes containing all linear chromosomes, all circular chromosomes, or permitting both. the latter are refered as mixed genomes. while many problems are open for multichromosomal genomes, there is a huge amount of research on these problems for unichromosomal genomes, whether circular or linear. they are not systematically particular cases of the multichromosomal problems, as the constraint of keeping only one chromosome along a rearrangement scenario can result in more difficult problems. more precisely, unichromosomal dcj problems reduce to rt multichromosomal ones. indeed, the rt operations always transform a unichromosomal genome into a unichromosomal one. as this paper contains very few results on the rt distance, practically the unichromosomal cases are often independent and not generalized here. results on unichromosomal genomes are summarised in table together with the results for the multichromosomal case we review or present here. a complete survey on these problems can be found in.  breakpoint distance, circular and mixed genomes in this section, d = dbp, and genomes are considered in their most general definition, that is, multichromosomal with both circular and linear chromosomes allowed. all the results also stand for circular genomes, but not always for linear genomes, which will be considered in a following section. as the nuclear genome of a eukaryotic species, a mixed karyotype is rarely observed, so probably unstable. nevertheless this case is of great theoretical interest, as it is the only combination of distance and karyotype where all five problems mentioned in the previous section prove to be polynomially solvable, including the median problem which is hard for almost every other variant. furthermore, the solutions in this context may suggest approaches for other variants of the problems, as well as providing a rapid bound for other distances, through the watterson et al. bound. distance and double distance the distance computation follows directly from the definition, and is easily achievable in linear time. the double distance computation is also easy: let Π be a genome and Δ be an all-duplicates genome. let a be the sum, for every adjacency xy in Π, of the number of adjacencies among x1y x1y x2y x2y in Δ. let e be the sum, for every telomere x in Π, of the number of telomeres among x and x in Δ. then we obtain indeed, it is a lower bound on the distance, because a and e are upper bounds on the number of common adjacencies and common telomeres, respectively, between Δ and any Π ⊕ Π. this lower bound is attained by constructing Π ⊕ Π in the following way: let xy be a possibly telomeric adjacency in Π; if x1y or x2y is an adjacency in Δ, choose x1y and x2y as adjacencies in Π ⊕ Π; if x1y or x2y is an adjacency in Δ, choose x1y and x2y as adjacencies in Π ⊕ Π; the two cases are either mutually exclusive if xy is not telomeric, or identical if xy is telomeric, so the assignment is made without ambiguity. for all adjacencies that have not been assigned, assign them arbitrarily. median the following result contrasts with the np-completeness proofs of almost all median problems in the literature. the problem is np-complete for unichromosomal genomes, that is, when the median genome m is required to be unichromosomal, whether the genomes are linear or circular, but the multichromosomal case happens to be easier. theorem there is a polynomial time algorithm for the breakpoint median problem for multichromosomal genomes. proof. let Π Π Π be three genomes on a gene set of size n. for any genome m on, let s = d + d + d be the median score of m. draw a graph g on the vertex set containing all extremities of genes in, and one supplementary vertex tx for every gene extremity x. for any pair of gene extremities x, y, draw an edge xy weighted by the number of genomes, among Π Π Π for which xy is an adjacency. then there is an edge between each pair of gene extremities, weighted by or now for any vertex x, draw an edge xtx weighted by half the number of genomes, among Π Π Π having x as a telomere. each edge xtx is then weighted by, or. finally, put an edge of weight between tx and ty for all pairs of gene extremities x, y. let m be a perfect matching in g. clearly, the edges joining gene extremities in m define the adjacencies of a genome, which we also call m. the relation between the weight of the perfect matching m and the median score of the genome m is easy to state: claim the weight w of the perfect matching m in g is 3n - s. indeed, for any genome Πi,, where ai = a is the number of common adjacencies between m and Πi, and ei = e is the number of common telomeres between m and Πi. if m and Πi have a common adjacency or a common telomere, this accounts for or, respectively, in the weight of the perfect matching m. so the weight of the matching m is, which yields d + d + d = 3n - w. conversely, any genome m can be extended to a perfect matching m in g such that s = 3n - w: construct the matching m by including the edges xy and txty for each adjacency xy and an edge xtx for each telomere x. claim implies that a maximum weight perfect matching m is a minimum score median genome. as the maximum weight perfect matching problem is polynomial, so is the breakpoint median problem.   □ if the three genomes in the instance are circular, then it is possible to constrain the result to also be circular by restricting the graph g to the extremities of the genes. then, in the same way, a perfect matching gives a circular solution to the median problem. this is not the case for linear genomes, since there is no way to guaranty that no chromosome in an instance is circular. note that a generalisation of this algorithm remains valid if the median of more than three genomes is to be computed. the phylogeny problems, both "big" and "small" versions, which also generalise the median problem for three genomes, remain open. the big problem is the search for a steiner tree in the space of genomes, minimising the sum of the distances on its branches, while in the small problem, presumably easier, the graph-theoretical structure of the tree, namely its vertex set and edge or branch set, are given, and only the genomes corresponding to the extra vertices need to be reconstructed. halving to our knowledge, the genome halving with breakpoint distance has not yet been studied. in this framework, it has an easy solution, using a combination of elements from the maximum weight perfect matching technique in the solution of the median problem presented above, and the double distance computation. let Δ be an all-duplicates genome on a gene set, and g be the graph on the vertex set containing all the extremities of the genes in, and one supplementary vertex tx for every gene extremity x. for any pair of gene extremities x, y, draw an edge in g weighted by zero, one or two according to the number of adjacencies in Δ among x1y x1y x2y and x2y now for any vertex x, draw an edge xtx weighted by half the number of telomeres among x and x in Δ. finally, put an edge of weight between txty for all pairs of gene extremities x, y. for a genome m on, define a perfect matching, also called m, by including edges xy and txty for each adjacency xy, and an edge xtx for each telomere x. let w be the weight of the matching m. claim for a genome m on, the perfect matching m thus constructed satisfies w = 2n - d. indeed, the score of the perfect matching m is, that is, 2n - d, according to the double distance formula. conversely, it is easy to see that any perfect matching on g defines a genome m such that w = 2n - d. this implies that the maximum weight perfect matching solves the genome halving problem in the breakpoint distance context. again, it is possible to solve the problem on only circular genomes by restricting the graph g to the gene extremities, dropping the tx supplementary vertices. guided halving as is the case for the median problem, this context provides the only polynomial result for the guided genome halving problem up to our knowledge. the solution combines elements of the three previous results, on the double distance, median and halving problems. let Δ be an all-duplicates genome on a gene set, and Π be an ordinary genome on. let g be the graph on the vertex set containing all the extremities of the genes in, and one supplementary vertex tx for every gene extremity x. for any pair of gene extremities x, y, there is an edge in g weighted by the number of adjacencies among x1y x1y x2y x2y in Δ, and xy in Π. now there is an edge xtx for any gene extremity x weighted by half the number of telomeres among x x in Δ and x in Π. so each edge between gene extremities has an integer weight in { 3}, and xtx edges may have weight, or. add 0-weight edges txty for all pairs x, y of gene extremities. for any genome m, let s = d + d. it is possible to construct a perfect matching m in g from genome m by choosing edges xy and txty for every adjacency xy in m. its weight is denoted w. claim for a genome m, the perfect matching thus constructed satisfies w = 3n - s. indeed, the weight of the perfect matching m is. according to the double distance formula, this yields w = 3n - s. conversely, if m is a perfect matching in g, its edges between gene extremities define the adjacencies of a genome m which satisfies s = 3n - w. this implies that the maximum weight perfect matching solves the guided genome halving problem in the breakpoint distance context. as is the case for the median problem, it is possible to generalise this statement for an arbitrary number of ordinary outgroup genomes. the phylogenetic problems are open. again, we can solve the problem on circular genomes by dropping the tx supplementary vertices in the graph g. breakpoint distance, linear case in this section, d = dbp and all genomes must be linear, as is most appropriate for modeling for the eukaryotic nuclear genome. in contrast to the model of the previous section, all the problems concerning at least three genomes are np-complete. distance and double distance the solutions to these problems are the same as in the previous section, where circularity was allowed. in the double distance computation, it is guaranteed that Π ⊕ Π is linear if Π is linear, because if x is a telomere in Π, then both x and x are telomeres in Π ⊕ Π. median whereas the median is polynomial in the circular and mixed cases, it changes complexity as soon as median genomes are required to be linear. this does not prevent the use of the polynomial algorithm described above as a lower bound, but all biologically relevant median problems seem in fact to be np-complete. theorem the breakpoint median problem for multichromosomal linear genomes is np-hard. proof. we use a reduction from the 2-chromosome breakpoint median, for which np-hardness is proved in lemma the 2-chromosome breakpoint median problem takes as input three unichromosomal linear genomes Π Π and Π on a set of genes, all having the same pair of telomeres. it asks for a linear genome m on with at most two chromosomes, which minimises its median score s = d + d + d. the following lemma states the difficulty of the breakpoint median problem compared to the 2-chromosome breakpoint median problem, and thus, together with lemma proves theorem lemma let Π Π Π be three unichromosomal linear genomes Π Π and Π all having the same pair of telomeres on the gene set = {...,n}, and k be a positive integer. there exists a genome m on with at most two linear chromosomes such that s ≤ k if and only if there exists a multichromosomal linear genome m' on with s ≤ k.: this direction is trivial: simply take m' = m.: let m' be a linear multichromosomal genome satisfying s ≤ k, that has as few chromosomes as possible. we will prove that m' has at most two chromosomes. suppose m' has at least three chromosomes. then it has at least six telomeres v...,v among them, it is possible to identify two telomeres, that belong to different chromosomes and are not telomeres in Π Π or Π because by hypothesis, they all have the same two telomeres. then the genome constructed from m' by adding the adjacency v1v has at most the same median score as m' and fewer chromosomes, contradicting the hypothesis on m'. so choosing m = m' gives a genome with at most two chromosomes such that s ≤ k.   □ we now need to prove the np-hardness of the 2-chromosome breakpoint median problem. we use a reduction from the hamiltonian cycle problem for directed graphs with vertex degree at most three, similar to the proof of bryant for the breakpoint median problem for unichromosomal circular genomes. lemma the 2-chromosome breakpoint median problem is np-hard. proof. given a directed graph with maximum degree deciding if it has a hamiltonian directed cycle is an np-complete problem. let thus g be such a digraph. we will construct an instance of the 2-chromosome breakpoint median problem from g first, let g be the directed graph with vertex set v = v ∪ {xe: e ∈ e} ∪ {p, q}, and arc set note that g has a hamiltonian cycle if and only if there is a cycle in g covering all vertices but p and q. given a subset x ⊆ e of the arcs of a graph g, let gx denote the graph with vertex set v and arc set x. construct three subsets a, b, c of arcs of g such that every arc of g belongs to exactly one of a, b, c, and a, b, c are either hamiltonian cycles of g or sets of vertex disjoint paths in g. the procedure is straightforward: for all vertex v of g which is a vertex of g put all incoming arcs in different subsets, and all outgoing arcs in different subsets. it can be done independently for every vertex because from the construction of g, no two vertices of g are neighbors. eventually put arc pq in any subset. now perform a series of modifications of g to obtain a graph with three hamiltonian cycles a, b, and c. along these modifications, we maintain a subset of arcs called supplementary arcs, noted s. before any transformation, s is empty. the goal is to maintain the property that there exists a cycle covering all vertices of g except p and q and not using supplementary arcs if and only if there is a hamiltonian cycle in g as already remarked, the property is true at the beginning. choose x ∈ {a, b, c} such that x is not a hamiltonian cycle in g. choose two vertices a and b such that adding the arc ab to g and x would either give a graph in which x is a hamiltonian cycle, or a set of disjoint paths with fewer components. then choose any vertex x of g different from a and b. perform the following transformation illustrated in figure 4: add two new vertices y and z. for each arc xw of g, replace it by the arc zw, and add zw to y ∈ {a, b, c} whenever xw ∈ y. add arcs xy, yz, xz, ay, yb to g. add xz, ay, yb to x. also add xz, ay, yb to s, and add xy, yz to all {a, b, c}\x. clearly, the property that there exists a cycle covering all vertices of g except p and q and not using supplementary arcs if and only if there is a hamiltonian cycle in g is still true after this transformation. repeat this process until a, b and c are all hamiltonian cycles in the resulting graph, which we call g'. the weight of an arc of g' is the number of hamiltonian cycles among a, b and c which contain this arc. note that g' has only weight and arcs. let v be an arbitrary vertex of g, different from p and q. let = v\{v} ∪ {v v2} be a set of genes. for every x ∈ {a, b, c}, construct a genome Πx on such that xhyt is an adjacency in genome x if xy is an arc of x in g' and x, y are different from v; if xv and vy are the arcs of x covering v, add the adjacencies and. this gives three linear unichromosomal genomes on with the same pair of telomeres, thus an instance of the 2-chromosome breakpoint median problem. for any genome m on, the weight of an adjacency xy is the number of genomes, among Πa, Πb and Πc, which contain this adjacency. adjacencies uhwt in m such that uw is an arc in s are called supplementary adjacencies. let λi be the number of arcs of weight i in the graph g', for each ≤ i ≤ for any genome m on, note s = d + d + d. the following is inspired by a result from used in. claim let n = |v |. a genome m with nm linear chromosomes on satisfies s ≥ 2n - + nm - λ where equality holds if and only if m contains all adjacencies of weight and no adjacency of weight indeed, for a genome m, denote by w the weight of the adjacency xy, and li = |xy adjacency of m: w = i|, for each ≤ i ≤ let t = if m has as a telomere, and t = otherwise, and t = if m has as a telomere, and t = otherwise. then we may write. as genome m has nm chromosomes, we have l + l + l + l = ||nm and || = n + so. as by construction no arc of g' has weight we may write s ≥ 2n - + nm - λ equality holds if and only if l = λ l = and, that is, if and only if m contains all adjacencies of weight at least and no adjacency of weight because l = implies that and are telomeres of m, thus. claim there is a linear genome m on with at most two chromosomes, with s = 2n - + nm - λ if and only if there is a hamiltonian cycle in g suppose there is a linear genome m on with at most two chromosomes, with s = 2n - + nm - λ this implies by claim that m contains all adjacencies of weight no adjacency of weight and that and are telomeres of m. from the construction of g', m cannot contain any supplementary adjacency, since the extremities of supplementary adjacencies all are also extremities of weight two adjacencies, which are all contained in m. note that in g', paths between vertices p and q to other vertices of the graph necessarily contain supplementary arcs. this yields that m has two chromosomes, one containing gene extremities from p and q, and the other containing the gene extremities from the other vertices, with telomeres and. let h ⊆ e contain the arcs xy such that xhyt is an adjacency in m, plus the arcs xv and vy for adjacencies of type and in m. h ∩ e yields a hamiltonian cycle in g suppose there is a hamiltonian cycle in g then there is a cycle h covering all vertices of g' except p and q. construct genome m on by adding adjacencies xhyt whenever xy is in h and x, y are different from v adjacencies and whenever xv or vy are arcs of h, all weight two adjacencies, and the adjacency ptqh. it is easy to check that m is a genome on, and by construction it contains all weight adjacencies and no weight adjacencies. this proves that it is np-complete to decide if a median genome reaches the lower bound of claim for its score, thus computing the minimum score median genome is np-hard.   □ a byproduct of this proof is the np-hardness of the 2-chromosome breakpoint median problem. the result implies np-completeness of the general case, where the genomes in the instance do not necessarily have the same pairs of telomeres. a consequence is that for any fixed k, it is also np-hard to compute a best linear median genome with at most k chromosomes. halving surprisingly, this problem has not been treated in the literature. we conjecture it has a polynomial solution, because the halving problem for all other rearrangement distances is polynomial. constructing a solution is beyond the scope of this paper, and the problem remains open. guided halving this problem is np-hard, as proved in, using the np-completeness result for the median proved just above in this section. dcj distance, general case in this section, d = ddcj. genomes can have several chromosomes, circular or linear. this is the most general context in which the dcj distance has been explicitly formulated. genomes rarely contain both circular and linear chromosomes; eukaryote nuclear genomes contain multiple linear chromosomes while prokaryotes generally contain one large circular chromosome, sometimes with additional plasmids. nevertheless, the simplicity of the computational framework where both genomes may contain both circular and linear chromosomes makes it attractive to mathematical study. note that the complexity of the median problem is not established by the work of caprara, who proved the unichromosomal result only. we show the np-hardness of the multichromosomal case here. alekseyev and pevzner mention that the complexity of the double distance problem in the context of circular genomes is open; we show here that it is np-hard as well. distance there is an easy linear solution, both for the distance and the scenario computation. we briefly recall the formula for computing the distance, because the underlying principle will be used in our proofs later on in this paper. the breakpoint graph of two genomes Π and Γ on a gene set, denoted by bp, is the graph whose vertex set is the set of extremities of the genes in, where there is an edge between two vertices x and y if xy is an adjacency in either Π or Γ. note that we do not invoke any ∘ symbols in the construction of the breakpoint graph. vertices in this graph have degree zero, one or two, so that the graph is a set of paths and cycles. it is also the line-graph of the adjacency graph, an alternate representation in. figure shows an example of a breakpoint graph. theorem shows how to obtain the distance directly from the graph. the formula is presented in with the cycles and odd paths of the adjacency graph. this corresponds to cycles and even paths of the breakpoint graph, as it is the line-graph of the adjacency graph. theorem for two genomes Π and Γ on a gene set of size n, let c be the number of cycles of the breakpoint graph bp, and p be the number of paths with an even number of edges. then note the similarity to the breakpoint distance formula in the background section on page the number of genes n is the same in both formulae, the parameter c is related to parameter a in the breakpoint formula in that each common adjacency is a cycle of the breakpoint graph, and parameter p is related to parameter e, as each shared telomere is an even path in the breakpoint graph. although these two measures of genomic distance were derived in different contexts and through different reasoning, their formulae show a remarkably similar form. they differ in that the dcj formula also counts non-trivial cycles and paths, but for distant genomes, both measures tend to give similar values. double distance the np-completeness proof for the double distance problem follows the principles of caprara's hardness proof for the median problem in the unichromosomal case. theorem the dcj double distance problem is np-hard for multichromosomal mixed or circular genomes. proof. the reduction is from the breakpoint graph decomposition problem. a graph g is bicoloured if all its edges are coloured either red or blue; it is balanced if it has only degree or degree vertices, every vertex is incident to the same number of red and blue edges, and there is no cycle formed by only red or only blue edges. given a balanced bicoloured graph g, the breakpoint graph decomposition problem is to find a partition of the edges of g into a maximum number of edge-disjoint cycles, each alternating between red and blue edges. caprara first proved the np-hardness of this problem, and berman and karpinski extended this by proving apx-hardness. let g be a balanced bicoloured graph on n vertices, defining an instance of the bgd problem. let w be the number of degree vertices of g, and w be the number of degree vertices of g. define the gene set as the vertex set of g. construct an all-duplicates genome Δ and a genome Π on in the following way, as illustrated in figure first, for each gene x of, let xtxh be an adjacency in Π. then, for every vertex x of g, let x1t, x1h, x2t and x2h, be the extremities of the duplicated gene x. if x has degree two in g, add the adjacency x1tx2h in Δ. then for each blue edge xy in g, choose among x1h and x2h an extremitiy that is not yet involved in an adjacency, and another among y1h and y2h. add an adjacency between the two chosen extremities in Δ. then for each red edge xy in g, choose among x1t and x2t an extremitiy that is not yet involved in an adjacency, and another among y1t and y2t. add an adjacency between the two chosen extremities in Δ. we then have an all-duplicates genome Δ, and a genome Π. note that Π is composed of n circular chromosomes, one for each gene, and that neither Π nor Δ have telomeres. claim the maximum number of edge-disjoint alternating cycles in g is equal to 2n - d - w. we first prove that the maximum number of edge-disjoint alternating cycles in g is at least 2n - d - w let Π ⊕ Π be the doubled genome such that d = d. as no genome has a telomere, by theorem d = 2n - c. therefore there are c edge-disjoint cycles in bg alternating between Π ⊕ Π-edges and Δ-edges. among them, w cycles are containing only two edges: if a vertex x of g has degree then Π ⊕ Π has the adjacency x1tx2h and x2tx1h because the other possibility systematically has one cycle less in bg. the Δ edges of all the other cycles are the edges of an alternating blue-red cycle in g. indeed, every blue edge defines an adjacency in Δ containing two gene heads, and every red edge defines an adjacency containing two gene tails. the Π ⊕ Π-edges all join one tail and one head, so two consecutive Δ-edges in a cycle of bg have different colours. this means there are at least 2n - d - w alternating cycles in g. conversely, if there are k edge-disjoint alternating cycles in g, then d ≤ 2n - k - w indeed, let c be any cycle of this partition. for every covered vertex x of degree in g, let e and f be two consecutive edges of c which are both incident to x. if e defines an adjacency in Δ which contains x2h and f defines an adjacency which contains x2t, choose x1hx1t and x2hx2t as adjacencies for Π ⊕ Π. if e defines an adjacency which contains x2h and f defines an adjacency which contains x1t, choose x1hx2t and x2hx1t as adjacencies for Π ⊕ Π. for vertices of degree always choose x1hx2t and x2hx1t as adjacencies for Π ⊕ Π. in this construction, each red-blue alternating cycle in g is a Π ⊕ Π-Δ alternating cycle in bp that has at least k cycles. and there are w additional length cycles at each degree vertex. so d ≤ 2n - k - w    □ median though effective exact algorithms and heuristics are available, we have: theorem the dcj median problem for multichromosomal genomes is np-hard, even for circular genomes. proof. we use a reduction from the breakpoint graph decomposition defined in the proof of theorem in a way very similar to part of caprara's proof for the unichromosomal case. let g be a balanced bicoloured graph on n vertices. define the gene set as a set containing one gene x for every degree vertex of g, and two genes x and y for every degree vertex of g. then construct the genomes Π Π Π in the following way, which is similar to the transformation in, as illustrated in figure for each degree vertex v of g, add the two adjacencies xtxh and ytyh to Π and the two adjacencies xtyh and ytxh to Π now fo every blue edge vw in g, add to Π an adjacency between heads of genes contructed from v and w. and for every red edge vu in g, add to Π an adjacency between tails of genes contructed from v and u. it is easy to see that Π Π and Π define genomes on the set of genes, and they have no telomeres. let w be the number of degree vertices of g, and w be the number of degree vertices of g. claim there exists a genome m on such that d + d + d ≤ w + 3w - k if and only if there exists at least k edge-disjoint alternating cycles in g.: suppose there are k edge-disjoint alternating cycles in g. we will construct a median genome m such that d + d + d = w + 2w - k. first, for each degree vertex v of g, let xtxh be in m. then, let v be a degree vertex in g, and vw be a blue edge incident to v. in an alternating cycle, edge vw is consecutive with a red edge, say uv. to vw is associated a constructed Π adjacency, say xhwh. then either the Π adjacency associated to uv contains the gene extremity xt, or it contains the extremity yt. in the first case, let xhxt and yhyt be in m, and in the second case, let xhyt and xty h be in m. the matching m defines the adjacencies of a circular genome on, that we also call m. there are w + 2w genes, so by theorem d + d + d = - + c + c). by construction, we have c + c = 2w + 3w and c = k, so d + d + d = w + 3w - k.: suppose m is a genome such that d + d + d ≤ w + 3w - k. suppose m is chosen such that d + d + d is minimum, and among all such genomes, choose m with a maximum number of edges parallel to Π1-edges or Π2-edges. a circular genome is said to be canonical if it only has adjacencies that belong to Π or Π we will prove that m is canonical. subclaim. m is canonical. suppose m is not canonical. suppose first that there is a degree vertex v in g, such that m does not contain the adjacency xtxh. suppose m contains adjacencies xta and xhb, where a and b are gene extremities or ∘ symbols if xt or xh is a telomere in m. then replace xta and xhb by xhxt and ab. by this operation, c and c both increase by at least and c decreases by at most so d + d + d decreases by one, contradicting the hypothesis. now suppose that there is a degree vertex in g, such that m does not contain any of the adjacencies xhxt, yhyt, xhyt, yhxt. say it contains adjacencies xha, xtb, y hc, ytd, where a, b, c, d may be null symbols if any of xh, xt, y h, yt is a telomere in m. then replace xha, xtb, yhc, ytd by xhxt, yhy t, and either ab, cd, or ac, bd, or ad, bc, according to the combination that creates the largest number of cycles in bp. suppose now that m contains only one among the adjacencies xhxt, yhy t, xhyt, yhxt, say xhxt, and m has adjacencies ytb and y hc. then replace edges ytb and y hc by yhyt and bc. all these operations decrease d + d + d or maintain it constant, while increasing the number of edges parallel to Π and Π contradicting the hypothesis. so the subclaim is proved. now, since m is canonical, there are c edge-disjoint alternating cycles in g, since an adjacency of m always joins a head and a tail, so the corresponding edge in g is adjacent to one red edge at one of its vertices and one blue edge at the other. by theorem c = - + d + d + c + c) and, by hypothesis, c ≥ -, that is, c ≥ k, which proves the claim.   □ halving this problem has a polynomial solution, as recently stated for unichromosomal genomes by and in the general case by. all these algorithms are simplified versions of the algorithm by el-mabrouk and sankoff, developed for the rt rearrangement distance, which allows reversals, translocations, fusions and fissions, but not the other dcj operations. guided halving theorem the dcj guided halving problem is np-complete for multichromosomal genomes. proof. again, we use a reduction of the breakpoint graph decomposition problem, as in the proofs of theorems and let g be a balanced bicoloured graph on n vertices. define the gene set as a set containing one gene x for every degree vertex of g, and two genes x and y for every degree vertex of g. from g, we define one genome Π and one all-duplicates genome Δ on as illustrated in figure for every degree vertex v of g, let x be the corresponding gene in and xt and xh its extremities. for every degree vertex v of g, let x and y be the two genes in, and xt and xh, y t and yh their extremities. for every blue edge uv in g, construct an adjacency in Π between the heads of the genes constructed from u and v, choosing arbitrarily between the heads of vertices x and y if u or v have degree in such a way that no two adjacencies share an extremity. for every red edge tv in g, construct an adjacency in Π between the tails of the genes constructed from t and v, again choosing arbitrarily between the tails of vertices x and y if t or v have degree this defines a genome Π on that has no telomere. now, define the genome Δ in the following way. for each degree vertex of g, Δ contains the adjacencies x1hx1t and x2hx2t defined by the extremities of the two copies of gene x. for each degree vertex in g, Δ contains the adjacencies x1hx1t, y2hy2t, x2hy1t, and x2ty1h defined by the extremities of the two copies of the two genes x and y. this defines an all-duplicates genome Δ on that has no telomere. let w be the number of degree vertices of g, and w be the number of degree vertices of g. claim. there exists a genome m such that d + d ≤ w + 3w - k if and only if there exists at least k edge-disjoint alternating cycles in g.: suppose there are k edge-disjoint alternating cycles in g. we will construct a genome m and a doubled genome m ⊕ m such that d + d ≤ w + 3w - k. first, for each degree vertex v of g, let xtxh be in m, and m ⊕ m be constructed so that x1tx1h and x2tx2h are in m ⊕ m. then, for every vertex v of degree of g, either the blue edge incident to xh is followed by the red edge incident to xt in one alternating cycle, or it is followed by the red edge incident to yt. in the first case, let xhxt and y hyt be in m, and x1hx1t, x2hx2t, y1hy1t, y2hy2t be in m ⊕m. in the second case, let xhyt and xtyh be in m, and x2hy1t, x1hy2t, x1ty2h, x2ty1h be in m ⊕ m. the matching m defines a genome without telomeres, and m ⊕ m is one of its doubled genomes. there are w + 2w genes, so by theorem d = w + 2w - c = w + 2w - k; and d = -. so d + d = w + 3w - k.: suppose m is a genome such that d + d ≤ w + 3w - k. suppose m is chosen such that d + d is minimum, and among all such genomes, choose m with a maximum number of edges of type xtxh for a degree vertex in g, or xhxt, yhyt, xhyt and xtyh for degree vertices of g. a genome is said to be canonical if it has no telomeres and has only edges of type xtxh for a degree vertex in g, or xhxt, yhyt, xhyt and xtyh for degree vertices of g. we will prove that m is canonical. subclaim. m is canonical. suppose m is not canonical. suppose first that there is a degree vertex v in g, such that m does not contain the edge xtxh. suppose m contains edges xtu and xhv, where u and v are gene extremities or ∘ symbols if xt or xh is a telomere in m. then replace xtu and xhv by xhxt and uv. by this operation, c decreases by at most one, while defining m ⊕ m as containing x1hx1t and x2hx2t makes c increase by at least this contradicts the hypothesis. now suppose that there is a degree vertex in g, such that m does not contain any of the edges xhxt, yhyt, xhyt, yhxt. say it contains edges xht, xtu, yhv, ytw, where t, u, v, w may be null symbols if any of xh, xt, yh, yt is a telomere in m. then replace xht, xtu, yhv, ytw by xh, xt, yhyt, tu, vw or xhyt, tw, xtyh, uv, depending on the cycles in c. suppose now that m contains only one among the edges xhxt, yhyt, xhyt, yhxt say xhxt, and m has edges ytu and yhv. then replace edges ytu and yhv by yhyt and uv. all these operations decrease d + d or maintain it constant, while increasing the number of edges of type xtxh for a degree vertex in g, or xhxt, yhyt, xhy t and xtyh for degree vertices of g, contradicting the hypothesis. at the end of this process, m is canonical, so the subclaim is proved. now, since m is canonical, there are c edge-disjoint alternating cycles in g, since an edge of m always joins a head and a tail, so that it is adjacent to one red and one blue edge. by theorem c = - + d + c), and by hypothesis, c ≥ - ), that is, c ≥ k, which proves the claim.   □ dcj distance, linear chromosomes in the original formulation of the dcj distance, it was shown that there is a solution where each excision of a circular intermediate could be followed directly by its reinsertion. thus the median and halving problems can be stated in terms of exclusively linear chromosomes in both the data genomes and the reconstructed ancestor. they all remain open. reversal/translocation distance hannenhalli and pevzner proposed a polynomial-time algorithm for calculating drt for two genomes Π and Γ, after solving the problem for unichromsomal genomes. this was reformulated in, minor corrections were added in and, and bergeron et al. simplified the formula and investigated the relations between drt and ddcj. a polynomial time genome halving algorithm was given in. though the constrained dcj distance in the previous section is arguably just as realistic, because of the long history of drt, effective heuristics for rt have been developed and applied for the double distance, median and guided halving problems, but their complexities remain open questions. note that gives an np-completeness result on a problem which slightly generalizes the reversal double-distance probem on unichromosomal genomes. discussion and  problem context: status of complexity questions for five problems related to ancestral genome reconstruction, for eight genomic distances in the unichromosomal and multichromosomal contexts. note that unichromosomal problems require that both input and output genomes be unichromosomal, so all problems involving doubled genomes are computationally defined in the circular case, when the doubled genome consists in a single circular chromosome composed of two successive occurences of the ordinary genome. other versions of the halving problem are less restrictive. p and np stand for polynomial and np-hard, respectively, and when followed by?, represent our conjectures. authors' contributions et, cz and ds have elaborated the definition and conjectures, proved the results and written the paper. 
although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances. the complexity of the median problem for unichromosomal genomes has been settled for both the breakpoint distance and the reversal distance. genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor to extant species. still other variants of these problems are np-complete, including the dcj double distance problem, previously mentioned as an open question. we settle here the complexity of several genome median and halving problems, including a surprising polynomial result for the breakpoint median and guided halving problems in genomes with circular and linear chromosomes, showing that the multichromosomal problem is actually easier than the unichromosomal problem.
 genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor to extant species. exploring complexity issues is a first step towards devising efficient algorithms. the complexity of the median problem for unichromosomal genomes has been settled for both the breakpoint distance and the reversal distance. although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.  we settle here the complexity of several genome median and halving problems, including a surprising polynomial result for the breakpoint median and guided halving problems in genomes with circular and linear chromosomes, showing that the multichromosomal problem is actually easier than the unichromosomal problem. still other variants of these problems are np-complete, including the dcj double distance problem, previously mentioned as an open question. we list the remaining open problems.  this theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes. 