Keywords:

Recent advances in sequencing technologies revealed the ubiquity of genome rearrangements between each and every one of us. These largescale mutations rearrange segments of chromosomes and have a profound impact on genetic variation, disease, and evolution. The study of the consequences of rearrangements along with their molecular mechanisms, however, is still in its infancy.

Given extant genomes, we are interested in tracing back the evolutionary rearrangement scenarios that transformed their least common ancestor into the genomes that we observe today. This not only helps to reveal evolutionary relationships between organisms, but also provides a window for the study of genome rearrangements themselves.

The central computational problem in this subfield of comparative genomics is that of finding optimal rearrangement scenarios transforming one genome into another. Historically all rearrangements were treated as being equally possible, and optimal scenarios were those that contained the minimum number of rearrangements. Recent advances in biology, however, allow us to devise much more sophisticated models. We present a short survey of the existing work on using biological constraints for genome rearrangements, and argue that a much more flexible approach is necessary to accompany the influx of newly available biological data.

In this work we propose an extremely general framework for genome rearrangements with biological constraints. Our main contribution is a polynomial time algorithm that, for an arbitrary cost function, finds a minimum cost scenario among those of minimum length. Along the way we establish a number of novel links between sorting genomes with double cut and join rearrangements, sorting graphs with 2-breaks or edge swaps, sorting permutations with mathematical transpositions, sorting strings with interchanges, and token swapping on graphs.

Keywords: weighted genome rearrangements, double cut and join, edge swap, minimum length transposition decomposition, minimum weight

Résumé

Un réarrangement génomique est une mutation qui modifie la structure des chromosomes voire même leur nombre dans un génome. Outre des fusions et des fissions de chromosomes, ces réarrangements comprennent des délétions, des insertions et des inversions de segments chromosomiques. Deux extrémités de chromosomes différents peuvent également être échangées au cours d'une translocation. L'ensemble de ces mutations constitue un scénario évolutif de réarrangements entre les espèces. Nous nous sommes intéressés à la reconstruction des scénarios de réarrangements entre espèces animales.

Notre projet associe des outils mathématiques et algorithmiques avec la compréhension biologique actuelle des réarrangements génomiques. D'un point de vue biologique, notre objectif est de lier génétique et épigénétique aux réarrangements dans les deux sens :

• nous développons une méthodologie pour étudier des caractéristiques génétiques et épigénétiques associées aux réarrangements,

• et inversement pour trouver des scénarios de réarrangements guidés par de telles caractéristiques génétiques et épigénétiques. (G, λ) the minimum ϕ-cost of an O-scenario for a labeled graph MCPS ϕ (G, λ) the minimum ϕ-cost of a parsimonious O-scenario for a labeled graph (H, λ H ) Chapter 1

Symbols

Introduction 1.1 Genome Rearrangements in an Evolutionary Setting

A rearrangement, also known as a structural variant, is a large-scale mutation that modifies the structure of the chromosomes or even their number in a genome. Take for example humans and our closest living relatives chimpanzees. We have 23 pairs of chromosomes, while chimps have 24. This difference is due to a fusion of two non-human ancestral primate chromosomes that resulted in human chromosome 2 [START_REF] De | Chromosome phylogenies of man, great apes, and old world monkeys[END_REF][START_REF] Timothy R Dreszer | Biased clustered substitutions in the human genome: the footprints of maledriven biased gene conversion[END_REF]. Studying this particular event can inform us about human evolution in multiple ways. Did this fusion lead to a speciation event that separated human and chimp lineages, or maybe those of archaic humans? Did it have a functional impact or trigger an advent of any phenotypic changes? If we were able to accurately date this fusion, could it be used for dating other events of human evolution? How exactly did it happen, why was it not lethal, and how did it spread within a population? Human and chimp lineages have each accumulated a number of other genomic rearrangements since their separation [START_REF] Kim | Reconstruction and evolutionary history of eutherian chromosomes[END_REF]. Besides chromosome fusion and fission these rearrangements include deletions, insertions and inversions of chromosomal segments. Two ends of different chromosomes might also get swapped during a translocation event. These mutations together constitute an evolutionary scenario between the species, and in this work we will be interested in reconstructing such scenarios between organisms.

Recent advances in sequencing technologies provide us with an unprecedented opportunity to study the mechanisms behind genome rearrangements [START_REF] Mani | Triggers for genomic rearrangements: insights into genomic, cellular and environmental influences[END_REF][START_REF] Kim | Mechanisms of germ line genome instability[END_REF], the ways they spread in populations [START_REF] Faria | Evolving inversions[END_REF], and their evolutionary significance [START_REF] Mérot | A roadmap for understanding the evolutionary significance of structural genomic variation[END_REF]. Methods for a systematic detection of genome rearrangements in populations and cancer cells are emerging [START_REF] Ho | Structural variation in the sequencing era[END_REF][START_REF] Soto | Identification of structural variation in chimpanzees using optical mapping and nanopore sequencing[END_REF], and more and more high-quality well-annotated genome assemblies are available for comparative research. Building upon these advances 13 recent studies started to unveil a role played in the evolutionary rearrangement scenarios by active chromatin, spatial proximity of loci in a genome, non-canonical DNA structures, and such chromatin features as topologically associating domains (TADs). Rearrangements between human and mouse have been shown to occur in active chromatin regions coming into 3D proximity in the nucleus [START_REF] Amélie S Véron | Close 3D proximity of evolutionary breakpoints argues for the notion of spatial synteny[END_REF][START_REF] Berthelot | The 3D organization of chromatin explains evolutionary fragile genomic regions[END_REF][START_REF] Krister | Large-scale mammalian genome rearrangements coincide with chromatin interactions[END_REF]. Gibbon rearrangements were shown to occur at TAD boundaries, with most TADs maintained as intact modules during and after a rearrangement [START_REF] Nathan H Lazar | Epigenetic maintenance of topological domains in the highly rearranged gibbon genome[END_REF]. A genome-wide depletion of deletions in active chromatin, and at TAD boundaries was observed across primate evolution [START_REF] Fudenberg | Chromatin features constrain structural variation across evolutionary timescales[END_REF], while deletions causing TAD fusions were shown to be rare and under negative selection in humans [START_REF] Huynh | TAD fusion score: discovery and ranking the contribution of deletions to genome structure[END_REF]. Transcriptional activity [START_REF] Henrike | Spatial chromosome folding and active transcription drive DNA fragility and formation of oncogenic MLL translocations[END_REF] and non-canonical DNA structures [START_REF] Georgakopoulos-Soares | Noncanonical secondary structures arising from non-B DNA motifs are determinants of mutagenesis[END_REF] were both linked to rearrangements in cancer, and the latter awaits further testing in an evolutionary setting.

Our project brings the mathematical and algorithmic tools from computer science together with the current biological understanding behind genome rearrangements. From a biological perspective, our goal is to link genetics/epigenetics to rearrangements in both directions:

• We will develop a method for studying genetic and epigenetic patterns associated with rearrangements in an evolutionary setting, and conversely

• for finding plausible evolutionary rearrangement scenarios informed by such genetic and epigenetic patterns.

Mathematical Models for Genome Rearrangements

There is a quarter century of mathematical and algorithmic work devoted to modeling rearrangements, and finding and sampling scenarios that could have transformed the gene order of one species into the gene order of another [START_REF] Fertin | Combinatorics of genome rearrangements[END_REF].

Inversions, also known as reversals, were first observed in fruit flies in 1921 by Sturtevant [START_REF] Sturtevant | A case of rearrangement of genes in drosophila[END_REF], and seem to be a suitable model for genome rearrangements in this species [START_REF] José M Ranz | Principles of genome evolution in the Drosophila melanogaster species group[END_REF]. In 1995 Hannenhalli and Pevzner [START_REF] Hannenhalli | Transforming men into mice (polynomial algorithm for genomic distance problem)[END_REF] came up with a rearrangement scenario between human and mouse genomes consisting of 131 reversals and translocations. The latter is a rearrangement that exchanges the ends of two linear chromosomes, and in an extreme case it can reproduce chromosome fusion and fission. Hannenhalli and Pevzner proved that for suitably represented genomes the minimum number of reversals [START_REF] Hannenhalli | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals[END_REF], or reversals and translocations [START_REF] Hannenhalli | Transforming men into mice (polynomial algorithm for genomic distance problem)[END_REF] required to transform one genome into another can be found in polynomial time. Mathematics behind their theory is quite complicated, see Bergeron [START_REF] Bergeron | A very elementary presentation of the Hannenhalli-Pevzner theory[END_REF] for a survey.

In 2005 Yancopoulos, Attie, and Friedberg [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF] proposed a mathematically drastically simpler rearrangement model called double cut and join (DCJ). A DCJ cuts 1.3. Weighted Genome Rearrangements chromosomes in one or two places, called breakpoints, and joins back the resulting chromosomal strands. In addition to inversions and translocations, this simple mathematical operation can reproduce such rearrangements as a circularization of a linear chromosome, and an excision of a circular chromosome out of a linear one. It is unclear if the latter types of rearrangements play any role in evolution, however circular DNA elements have been found in healthy human cells [START_REF] Devitt Møller | Circular DNA elements of chromosomal origin are common in healthy human somatic tissue[END_REF] and are abundant in cancer cells [START_REF] Turner | Extrachromosomal oncogene amplification drives tumour evolution and genetic heterogeneity[END_REF].

A distance is the minimum number of rearrangements required to transform one genome into another. Reversal, reversal/translocation and DCJ distances between genomes can be found in polynomial time [START_REF] Hannenhalli | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals[END_REF][START_REF] Hannenhalli | Transforming men into mice (polynomial algorithm for genomic distance problem)[END_REF][START_REF] Bergeron | A unifying view of genome rearrangements[END_REF], however most of the problems become NP-hard once more than two genomes are compared. These include the median problem, which is used for phylogenetic reconstruction, and asks for a genome minimizing the sum of the pairwise distances to a given set of genomes [START_REF] Caprara | The reversal median problem[END_REF][START_REF] Tannier | Multichromosomal median and halving problems under different genomic distances[END_REF].

Single cut or join (SCJ), an even simpler model for genome rearrangements was proposed by Feijão and Meidanis [START_REF] Feijão | SCJ: a breakpoint-like distance that simplifies several rearrangement problems[END_REF] in 2011. According to the authors, "this new distance measure may be of value as a speedily computable, first approximation to distances based on more realistic rearrangement models" [START_REF] Feijão | SCJ: a breakpoint-like distance that simplifies several rearrangement problems[END_REF]. This claim is supported with a proof that the median problem is polynomial time solvable for SCJ. New models for genome rearrangements are still being introduced. A rank distance for genomes modeled as matrices was introduced by Zanetti, Biller and Meidanis [START_REF] Paulo | Median approximations for genomes modeled as matrices[END_REF] in 2016. It relates to DCJ and is more sophisticated than SCJ while still allowing for interesting polynomial time results on the median problem as it was recently established by Chindelevitch, La and Meidanis [START_REF] Chindelevitch | A cubic algorithm for the generalized rank median of three genomes[END_REF].

Weighted Genome Rearrangements

Foundational models focused solely on the minimum length, or parsimonious, rearrangement scenarios transforming one genome into another [START_REF] Sankoff | Edit distance for genome comparison based on non-local operations[END_REF][START_REF] Hannenhalli | Transforming men into mice (polynomial algorithm for genomic distance problem)[END_REF][START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF]. However the true evolutionary scenario is likely to be non-parsimonious as discussed by Lin and Moret [START_REF] Lin | Estimating true evolutionary distances under the DCJ model[END_REF], and more recently by Biller, Guéguen, Knibbe, and Tannier [START_REF] Biller | Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation[END_REF] and Alexeev and Alekseyev [START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF]. In addition to this, both for reversals and DCJ the number of possible parsimonious scenarios was shown to grow exponentially with respect to the distance. These results were respectively established by Bergeron, Chauve, Hartman, and St-Onge [START_REF] Bergeron | On the properties of sequences of reversals that sort a signed permutation[END_REF], and Braga and Stoye [START_REF] Marília | Counting all DCJ sorting scenarios[END_REF]. This means that even if the true evolutionary scenario happened to be parsimonious, then one would still need some additional biological constraints on the rearrangement scenarios in order to select the ones that are more likely to resemble the true one.

To this end, the study of weighted genome rearrangements was pioneered by Blanchette, Kunisawa, and Sankoff [START_REF] Blanchette | Parametric genome rearrangement[END_REF] in 1996. They assigned different weights to a reversal, a transposition and an inverse transposition, where the former swaps two contiguous segments of a chromosome while the latter also inverts one of them. A greedy algorithm for minimizing the sum of the rearrangement weights in a scenario was proposed in [START_REF] Blanchette | Parametric genome rearrangement[END_REF]. The rationale behind this model is that different types of rearrangements might have different chances of appearing in the true evolutionary scenario. Hartmann, Wieseke, Sharan, Middendorf, and Bernt [START_REF] Hartmann | Genome rearrangement with ILP[END_REF] recently proposed a polynomial sized ILP for solving this problem with arbitrary weights. A variant of this problem where only transpositions and reversals are allowed, and a ratio of their weights satisfies w tr /w rev ≤ 1.5 was proved to be NP-hard by Oliveira, Brito, Dias, and Dias [START_REF] Rodrigues Oliveira | On the complexity of sorting by reversals and transpositions problems[END_REF].

Another approach deals with a notion of a preserved gene cluster, also known as a preserved common interval. It is a set of genes whose order might be shuffled but that remain clustered together in both genomes. This line of work is motivated by an observation that such conserved gene clusters sometimes contain functionally associated proteins [START_REF] Tamames | Conserved clusters of functionally related genes in two bacterial genomes[END_REF], and thus might be unlikely to get broken by a rearrangement in the true evolutionary scenario. See Hartmann, Middendorf, and Bernt [START_REF] Hartmann | Genome rearrangement analysis: Cut and join genome rearrangements and gene cluster preserving approaches[END_REF] for a recent survey of algorithmic work related to this constraint. The same authors in [START_REF] Hartmann | An exact algorithm for sorting by weighted preserving genome rearrangements[END_REF] provide an exact algorithm for finding a minimum weight preserving scenario, where different weights are assigned to inversions, transpositions, inverse transpositions, and tandem duplication random loss operations, that duplicate a segment of a chromosome and delete at random one copy of each duplicated gene. These four operations together constitute a model for genome rearrangements that is often used for studying the evolution of the metazoan mitochondrial genomes [START_REF] Bernt | Genetic aspects of mitochondrial genome evolution[END_REF].

Blanchette, Kunisawa, and Sankoff [START_REF] Blanchette | Parametric genome rearrangement[END_REF] also explored an idea of weighting each rearrangement based on its length, or the number of genes that it affects. This approach is based on the observed prevalence of short reversals in certain genomes [START_REF] Seoighe | Prevalence of small inversions in yeast gene order evolution[END_REF][START_REF] Darling | Dynamics of genome rearrangement in bacterial populations[END_REF]. See Galvao, Baudet, and Dias [START_REF] Galvao | Sorting circular permutations by super short reversals[END_REF] for a summary of the work on allowing only reversals of length at most 3. See Lintzmayer, Fertin and Dias [START_REF] Negri Lintzmayer | Sorting permutations and binary strings by length-weighted rearrangements[END_REF] for a summary of the work on weighting reversals and transpositions based on their lengths.

Baudet, Dias, and Dias [START_REF] Baudet | Sorting by weighted inversions considering length and symmetry[END_REF] proposed a model where reversals in bacterial genomes are weighted both based on their length and on the symmetry around the origin of replication. It was Ohlebusch, Abouelhoda, and Hockel [START_REF] Ohlebusch | A linear time algorithm for the inversion median problem in circular bacterial genomes[END_REF] that first used this symmetry to provide a polynomial time algorithm for a variant of the reversal median problem. Their work was motivated by an observation that most of the reversals in some circular bacterial genomes are either centered around the origin/terminus of replication or involve a single gene [START_REF] Eisen | Evidence for symmetric chromosomal inversions around the replication origin in bacteria[END_REF]. As far as we are aware, this was the first time when external biological information of any kind was used in order to constraint a rearrangement scenario.

Over the last few years more work along these lines emerged. Biller, Guéguen, Knibbe, and Tannier [START_REF] Biller | Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation[END_REF] pointed out that the number of nucleotides in the intergenic regions, or their lengths, could be used as a biological constraint for genome rearrangements. Bulteau, Fertin, Jean and Tannier aimed to minimize the sum of the lengths of insertions/deletions in the intergenic regions during a DCJ scenario [START_REF] Fertin | Algorithms for computing the double cut and join distance on both gene order and intergenic sizes[END_REF][START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF]. Similar ideas were later explored by Brito, Jean, Fertin, Oliveira, Dias, and Dias for reversals and transpositions of length at most 2 [START_REF] Andre R Oliveira | Super short operations on both gene order and intergenic sizes[END_REF], and for reversals and transposition [START_REF] Lima Brito | Sorting by genome rearrangements on both gene order and intergenic sizes[END_REF]. In the latter paper some possibilities for attributing different weights to reversals, transpositions and insertions/deletions were also explored.

Véron, Lemaitre, Gautier, Lacroix, and Sagot [START_REF] Amélie S Véron | Close 3D proximity of evolutionary breakpoints argues for the notion of spatial synteny[END_REF] suggested that the 3D structure of a genome is partially conserved between human and mouse. Physical proximity is already known to be one of the triggers for rearrangements in somatic cells [START_REF] Mani | Triggers for genomic rearrangements: insights into genomic, cellular and environmental influences[END_REF], and Swenson and Blanchette [START_REF] Krister | Large-scale mammalian genome rearrangements coincide with chromatin interactions[END_REF] used Hi-C data to support this hypothesis in an evolutionary setting. Based on these observations our team aimed to minimize the number of DCJ rearrangements breaking regions distant in the 3D space [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Simonaitis | Finding local genome rearrangements[END_REF][START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF][START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF].

Only a tiny fraction of these weighted genome rearrangement problems have polynomial time algorithms. These include finding a minimum length scenario for reversals of length at most 2 [START_REF] Galvao | Sorting circular permutations by super short reversals[END_REF][START_REF] Michael | Improved bounds on sorting by lengthweighted reversals[END_REF]. Also if reversal's weight is equal to its length, then a minimum weight reversal scenario for a binary string can be found in polynomial time as shown by Bender, Ge, He, Hu, Pinter, Skiena, and Swidan [START_REF] Michael | Improved bounds on sorting by lengthweighted reversals[END_REF]. In addition to this, Bérard, Bergeron, Chauve, and Paul [START_REF] Bérard | Perfect sorting by reversals is not always difficult[END_REF] introduced a specific family of gene clusters for which a minimum length preserving reversal scenario can be found in polynomial time. Other than that, all the weighted genome rearrangement problems with efficient algorithms of which we are aware are those that search for an optimal DCJ scenario among those that are of minimum length. These include a work on preserving DCJ by Bérard, Chateau, Chauve, Paul, and Tannier [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF], on insertions and deletions in the intergenic regions by Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF], and our own work on the physical locations of the intergenic regions [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF][START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF].

A General Framework for Cost Constrained DCJ

We have seen that a parsimony criterion alone cannot provide a small enough subset of plausible rearrangement scenarios. Models for weighting genome rearrangements based on a number of biological constraints were explored with a hope that they might help with this issue. As presented in the previous section, this led to an accumulation of algorithmic work, however these models mostly exploited the combinatorial properties of the gene orders and rearrangement operations, and not the external biological constraints, such as those concerning the 3D structure of a genome, or fragility of certain loci that might be due to transcriptional activity or non-canonical DNA structures. In addition to this, only a handful of exact polynomial time algorithms for finding a minimum weight rearrangement scenario can be found in the literature. However one line of work, that of weighted parsimonious DCJ scenarios, seemed promising to us and served as a starting point for our project.

In [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] and [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] two simple ways of assigning weights to DCJ rearrangements were introduced, while the weight of a DCJ scenario was defined to be the sum of the weights of its constituent rearrangements. In these papers genomes were supposed to be single-copy, meaning that they contain equal sets of genes, with a single occurrence of each gene. For both types of weights it was shown that finding a minimum weight scenario is NP-hard [START_REF] Fertin | Algorithms for computing the double cut and join distance on both gene order and intergenic sizes[END_REF][START_REF] Simonaitis | Finding local genome rearrangements[END_REF], while a minimum weight scenario among the parsimonious ones can be found in polynomial time [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF][START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF]. As in the previous models for weighting genome rearrangements, these algorithms exploited the combinatorial properties of the models themselves and could not be easily generalized to be used with more sophisticated ways to weight DCJs.

A catalyst for our project was the work on sorting permutations with cost constrained transpositions by Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF]. In the field of genome rearrangements a transposition is a rearrangement that swaps two adjacent regions of a chromosome, where a region can contain any number of genes. However in mathematics more broadly a transposition is a permutation that exchanges any two elements. It is the latter notion that we will use throughout this text. Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] allowed for an arbitrary cost function on transpositions and defined the cost of a transposition decomposition of a permutation to be the sum of the costs of its transpositions. Within this setting they showed that a minimum cost transposition decomposition among those of minimum length can be found in polynomial time regardless of the cost function. The ideas encountered in [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] encouraged us to aim for the following generalization of our work on weighting DCJs:

Project. A framework for cost constrained genome rearrangements under a DCJ model within which a minimum cost parsimonious scenario between two single-copy genomes could be found in polynomial time for an arbitrary cost function.

This means that our goal is not to come up with a particular mathematical model for cost constraining DCJs in a biologically meaningful way. But rather to provide guidelines for such a process, and ensure that no algorithmic work is needed if our guidelines are respected. The axes of our project became the following:

1. Efficiently explore the space of the parsimonious DCJ scenarios.

Augment a DCJ rearrangement with information concerning the intergenic

regions that it cuts and joins, and define an arbitrary cost function on these augmented DCJs.

3. Efficiently search for a minimum cost scenario among the parsimonious ones.

These tasks are respectively treated in Chapter 3, Chapter 4, and Chapter 5. Our framework generalizes all three models for cost constraining DCJs of which we are aware. These include previously mentioned work by our own team [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF], Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF], and Bérard, Chateau, Chauve, Paul, and Tannier [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF]. However, as we discuss in Chapter 4, the latter model on preserving DCJs needs to be slightly modified for it to fit into our framework.

An important feature of our framework is that it enables us to easily combine different models for cost constraining genome rearrangement. This means, for example, that we can assign a cost to a DCJ simultaneously based on the locations of its breakpoint regions in the 3D space, their lengths and the number of the gene clusters that this DCJ preserves.

Another feature is that even if a polynomial time algorithm for finding a minimum cost parsimonious scenario is ensured only for single-copy genomes, we still provide an exact algorithm for genomes with multiple copies of genes and unequal gene content.

Finally, the true evolutionary scenario might be non-parsimonious, thus a long term goal is to move away from a parsimony criterion. To this end, it might be possible to avoid exploring the space of all the DCJ scenarios, as was previously done by Fertin, Jean, and Tannier [START_REF] Fertin | Algorithms for computing the double cut and join distance on both gene order and intergenic sizes[END_REF] and our own team [START_REF] Simonaitis | Finding local genome rearrangements[END_REF]. Statistical tools could be used instead to estimate an upper bound l for the length of the true evolutionary scenario [START_REF] Biller | Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation[END_REF][START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF], and only the scenarios of length less than l could be explored. A number of our results are actually proved for non-parsimonious scenarios and provide a foundation for this future work.

In Chapter 2 we show that a DCJ can be interpreted as a graph transformation, which is a common approach in the field of genome rearrangements [START_REF] Fertin | Combinatorics of genome rearrangements[END_REF]. In the subsequent chapters we actually introduce a framework for cost constrained graph transformations, and not for cost constrained genome rearrangements. This general setting allows us to establish novel links between various sorting problems on permutations, strings, genomes and graphs. Work on sorting permutations [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF], strings [START_REF] Amir | String rearrangement metrics: A survey[END_REF] and genomes [START_REF] Hannenhalli | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals[END_REF] with various operations such as transpositions, interchanges and reversals relies heavily on graph theoretic techniques and data structures. In this work we show that a 2-break, a graph transformation that swaps endpoints of two edges as illustrated in Figure 7.1, generalizes a number of different sorting operations. These include sorting permutations with transpositions [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF], sorting strings with interchanges [START_REF] Amir | String rearrangement metrics: A survey[END_REF], sorting genomes with double cut and join (DCJ) rearrangements [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF], and token swapping on graphs [START_REF] Bonnet | Complexity of token swapping and its variants[END_REF]. All of these problems have cost-constrained variants, which serves as motivation for our choice to study cost constrained 2-breaks.

Sorting Graphs with 2-breaks

A 2-break is known under many different names across the literature: (double edge) swap, (degree-preserving) rewiring, switch, shuffle, flip, checkerboard swap, and is the simplest way to transform a graph without changing its degree sequence [START_REF] Bailey K Fosdick | Configuring random graph models with fixed degree sequences[END_REF]. Besides sorting, 2-breaks are used for modeling and analyzing various dynamic networks, notably peer-to-peer [START_REF] Feder | A local switch Markov chain on given degree graphs with application in connectivity of peerto-peer networks[END_REF] and lightwave networks [START_REF] Bienstock | A degree sequence problem related to network design[END_REF]. 2-breaks are also widely used for generating random graphs with an empirically relevant degree sequence [START_REF] Mark Ej Newman | Random graphs with arbitrary degree distributions and their applications[END_REF], and for studying the configuration model, which is a uniform distribution over graphs with a specific degree sequence. See [START_REF] Bailey K Fosdick | Configuring random graph models with fixed degree sequences[END_REF] for a recent survey of this line of work.

Outline

We start our work by introducing 2-breaks and a problem of finding a minimum length 2-break scenario transforming one graph into another in Section 2.2. We proceed by showing that 2-breaks generalize various transformations of permutations, strings, genomes and graphs in Section 2.7.

In Chapter 2 we introduce some theory concerning genomes and permutations. We show that a DCJ scenario for a pair of genomes and a transposition decomposition of a permutation can be both seen as 2-break scenarios for their breakpoint graphs. Such observations have already been made before, however by combining them together we establish a novel result. We show that a parsimonious DCJ scenario for a pair of single-copy co-tailed genomes (these are genomes that share the sets of genes adjacent to the ends of their linear chromosomes) can be interpreted as a minimum length transposition decomposition of a permutation and vice versa. We conclude this chapter with a short discussion of how this link might help us with various median problems.

In Chapter 3 we concentrate on a parsimonious 2-break scenario for a graph, and demonstrate that it can be partitioned into parsimonious 2-break scenarios for the very basic subgraphs of the graph, that we call circles. We then proceed by showing that a parsimonious 2-break scenario for a circle can be partitioned into scenarios for smaller circles. This leads to a dynamic programming algorithm for exploring the space of the parsimonious 2-break scenarios for a circle and, due to the previous observation, for any graph.

In Chapter 4 we introduce our framework for cost constraining 2-breaks that consists of four steps:

• Labeling vertices and edges of a graph.

• Allowing a 2-break to replace a pair of labeled edges with another pair of labeled edges.

• Allowing a label of an edge to be changed.

• Defining an arbitrary cost function ϕ on these new operations.

Within this setting we introduce the ϕ-Minimum Cost Parsimonious Scenario problem (ϕ-MCPS) for a labeled graph, and show that previous work on cost constrained DCJs [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF][START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF] and cost constrained transposition decompositions [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] can be interpreted as ϕ-MCPS problems.

In Chapter 5 we provide an exact algorithm for the ϕ-MCPS problem. Its worst case time complexity for a genome breakpoint graph of a pair of single-copy genomes with n genes is O(n 5 L 4 ), where L is the number of edge labels allowed in the chosen model for cost constraining 2-breaks. We conclude this chapter by arguing that despite its elevated time complexity our algorithm remains of practical importance for the study of genome rearrangements.

Chapter 2 Linking 2-breaks on Graphs, Rearrangements on Genomes, and Transpositions on Permutations

Introduction

We start this chapter with a presentation of the theory of sorting graphs with 2breaks. In Sections 2.3 and 2.4 we demonstrate that sorting genomes with double cut and join (DCJ) rearrangements and sorting permutations with transpositions can be both interpreted as sorting graphs with 2-breaks. Some links between these two problems have already been explored by the people working on the algebraic rearrangement theory [START_REF] Meidanis | An alternative algebraic formalism for genome rearrangements[END_REF][START_REF] Feijao | Extending the algebraic formalism for genome rearrangements to include linear chromosomes[END_REF], a recent survey of which is proposed by Bhatia, Feijão and Francis [START_REF] Bhatia | Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics[END_REF]. What is new here, is that we establish a bijection between the Minimum Length Transposition Decompositions (MLTDs) of a permutation and the parsimonious DCJ scenarios for a well chosen pair of genomes. This bijection facilitates an exchange of ideas between two well studied problems. For example, the work of Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] on sorting permutations with cost constrained transpositions informed our work in Chapter 5 on sorting graphs with cost constrained 2-breaks. In its turn, our work generalizes that on the cost constrained transpositions, as it will be briefly discussed in Section 2.7. On the other hand, as we explain in Section 2.6, the complexity of the Swap Median Permutation problem [START_REF] Yu | Multiple genome rearrangement by swaps and by element duplications[END_REF] remains unknown, while the DCJ Median problem is known to be NP-hard [START_REF] Tannier | Multichromosomal median and halving problems under different genomic distances[END_REF]. The work on the latter problem might inform us on how the former could be approached.

Transforming Graphs with 2-breaks

A 2-break Scenario for a Graph

In this section we introduce the problem of sorting a 2-edge-colored graph with 2breaks. This sorting problem is most often seen as transforming a source object (black edges) to the target one (gray edges), however here we will transform both black and gray edges into some intermediate set. This way to pose the problem does not change the length of a parsimonious 2-break scenario, however it will allow us to impose different cost constraints on black and gray edges in Chapter 4.

Definition 1 (2-edge-colored multigraph). Take a set V of vertices and two colors {black, gray}. An edge is an unordered pair of vertices. A colored edge is a pair of an edge and a color. A 2-edge-colored multigraph is an ordered pair (V, E), with E being a multiset of colored edges.

Definition 2 (Eulerian graph and alternating cycle). A 2-edge-colored multigraph is Eulerian if its every vertex has equal black and gray degrees. A cycle is alternating if it is Eulerian.

See Figure 2.1 a) for an example. All use of the word graph will be synonymous with Eulerian 2-edge-colored multigraph, and use of the word cycle will be synonymous with alternating cycle, unless specified otherwise.

Definition 3 (Terminal graph). A graph with equal multisets of black and gray edges is called terminal.

Definition 4 (2-break).

A 2-break transforms a pair of colored edges ({u, v}, col) and ({w, s}, col) into either ({u, w}, col) and ({v, s}, col), or ({u, s}, col) and ({v, w}, col).

We denote the former of these transformations by τ = {u, v}, {w, s} → {u, w}, {v, s} , col . Take a graph G containing the colored edges ({u, v}, col) and ({w, s}, col), and a graph G in which these edges were replaced with ({u, w}, col) and ({v, s}, col). We say that τ transforms G into G , and denote this transformation by G → G .

Maximum Alternating Edge-disjoint Cycle Decomposition

The problem of finding a parsimonious 2-break scenario for a graph is closely related to that of finding its Maximum Alternating Edge-disjoint Cycle Decomposition. See Figure 2.1 f)-g) for an example.

The Minimum Length of a 2-break Scenario

The problem of finding a parsimonious 2-break scenario has been treated in several unrelated settings using different terminologies. Bienstock and Günlük [START_REF] Bienstock | A degree sequence problem related to network design[END_REF] provide a thorough analysis of the problem. They demonstrate that finding a minimum length black-2-break scenario is NP-hard due to the NP-hardness of finding an MAECD of a graph. They also provide a 7/4-approximation algorithm for finding its length.

Lemma 1 (Adapted from Bienstock and Günlük [START_REF] Bienstock | A degree sequence problem related to network design[END_REF]). The minimum length of a 2-break scenario for a graph

G is d 2b (G) = e(G) -c(G)
, where e(G) is the number of colored edges in G divided by two. Now we show that there always exists a 2-break increasing the size of an MAECD by one. Take a non-terminal simple cycle S, its gray edge, and a pair of black edges incident to its endpoints. Denote them by ({u, w}, gray), ({u, v}, black), and ({w, s}, black). A 2-break {u, v}, {w, s} → {u, w}, {v, s} , black provides a non-simple graph, as it contains colored edges ({u, w}, gray) and ({u, w}, black) forming a cycle. See

Equivalent 2-break Scenarios

In Chapter 4 we introduce cost constraints on the individual 2-breaks and define the cost of a scenario to be the sum of the costs of its individual moves. In this setting two 2-break scenarios containing the same 2-breaks, but possibly performed in different orders, have the same cost. This motivates the following definition of an equivalence relation between the 2-break scenarios.

Definition 10 (Equivalent 2-break scenarios). Two 2-break scenarios are equivalent if their multisets of 2-breaks are equal.

In Chapter 3 we categorize the equivalence classes of the parsimonious 2-break scenarios.

Double Cut and Join Rearrangements are 2breaks

Genomes

In this section we present the theory of sorting genomes by double cut and join (DCJ) rearrangements. We introduce the breakpoint graph, a graphical representation of a pair of genomes, and proceed by establishing a bijection between the DCJ scenarios for a pair of genomes and the 2-break scenarios for their breakpoint graph.

A genome consists of chromosomes that are two stranded linear or circular DNA molecules. In the field of genome rearrangements a chromosome is usually modeled as a circular or linear order of directed genes separated by breakpoint regions, where the direction of a gene indicates the strand of a chromosome that it belongs to [START_REF] Fertin | Combinatorics of genome rearrangements[END_REF]. In Figure 2.3 a) the tail of an arrow represents the tail extremity, and the head of an arrow represents the head extremity of a gene. A genome can be represented by its adjacency set. An adjacency is either internal: an unordered pair of the gene extremities that are adjacent on a chromosome, or external: a single gene extremity adjacent to one of the two ends of a linear chromosome.

Denote the set of genes (or syntenic blocks) by V = {1, . . . , n}, and the sets of their head an tail extremities by

V h = {1 h , . . . , n h } and V t = {1 t , . . . , n t }.
In what follows we suppose that genomes share the same multiset of genes, however the proposed methods also apply for the genomes with different gene content when ghost adjacencies are introduced to account for the missing genes, as proposed by Yancopoulos and Friedberg [START_REF] Yancopoulos | Sorting genomes with insertions, deletions and duplications by DCJ[END_REF]. See Figure 2.3 for an example.

Double Cut and Join and the Adjacency Graph

We use double cut and join to model genome rearrangements. Definition 11 (Double cut and join (DCJ) [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF]). A DCJ transforms the adjacencies of a genome in one of the four following ways:

1. {a, b}, {c, d} → {a, c}, {b, d} , 2. {a, b}, {c} → {a, c}, {b} , 3. {a}, {b} → {a, b} , 4. {a, b} → {a}, {b} , with a, b, c, d ∈ V h ∪ V t .
Take a genome A containing the adjacencies {a, b} and {c, d}, and a genome A in which these adjacencies were replaced with {a, c} and {b, d}. We say that a DCJ {a, b}, {c, d} → {a, c}, {b, d} , A transforms A into A , and denote this transformation by A → A .

We will mostly be interested in the genomes containing a single copy of each gene. Such single copy genomes are uniquely represented by their sets of adjacencies, which is not the case for the genomes in general. All the work on DCJ of which we are aware operates on the adjacency sets and deals with the following notions of DCJ scenario and DCJ distance. A,B) is called edit distance in [START_REF] Shao | Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion[END_REF] and generalized DCJ distance in [START_REF] Shao | An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes[END_REF]. See Figure 2

.3 for an example of non-equal genomes with d aDCJ equal to 0.

A more sophisticated DCJ distance introduced in Definition 13 that takes the structure of the chromosomes into account remains to be studied in the future. The adjacency graph introduced by Bergeron, Mixtacki, and Stoye [START_REF] Bergeron | A unifying view of genome rearrangements[END_REF] has been widely used to represent a pair of genomes and study their DCJ scenarios. See Figure 2.4 for an example.

Definition 14 (Adjacency graph). The graph AG(A, B) of two genomes is the bipartite graph whose vertices are the adjacencies of A and B. There is an edge (respectively two edges) between the adjacencies if they share a gene extremity (respectively two gene extremities).

With the help of an adjacency graph the following results were established.

Lemma 2 (Bergeron,Mixtacki,and Stoye [15]). d aDCJ (A, B) for the single copy genomes is equal to n -(C + I/2), where n is the number of genes, C is the number of cycles of AG(A, B) and I is the number of odd length paths among the connected components of AG(A, B). Lemma 3 (Shao,and Lin [86]). Computing d aDCJ (A, B) for the non-single copy genomes is NP-hard. Denote by D the set of vertex-disjoint decompositions of AG(A, B) into cycles and paths. d aDCJ (A, B) = n -max D∈D (c D + o D /2), where c D is the number of cycles and o D is the number of odd length paths in a decomposition D.

These results can be seen as corollaries of Theorem 1 that we establish in what follows.

The Breakpoint Graph

The adjacency graph conveniently represents genomes, however we will only be interested in their adjacency sets. We find that in this setting the breakpoint graph [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF], being more concise, is much easier to work with. Here we use a variant of the breakpoint graph very similar to the one introduced by Alekseyev and Pevzner [START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF]. See AG(A, B) andG(A, B).

Definition 15 (Genome breakpoint graph). G(A, B) for two genomes A and B is a 2-edge-colored multigraph on vertices

V h ∪ V t ∪ {•}.

Observation 6. Every vertex of the adjacency graph AG(A, B) corresponds to an edge of the genome breakpoint graph G(A, B). This way, for every path in AG(A, B) there exists a corresponding path in G(A, B).

Using Lemma 2 we establish a following lemma.

3 h 2 t 1 h 1 t 3 t 2 h 4 h 4 t 3 h 2 t 1 h 1 t 3 t 2 h 4 h 4 t G(A,B)=G(C,B) G(A',B) d) 1 4 A 1 3 2 1 2 B 2 3 1 1 4 C 1 3 2 a) b) c) 2 h 2 t • 4 t 4 h 1 t 1 h • 1 t 1 h 2 h 2 t 3 h 4 t 4 h 3 t 2 h 2 t 1 h 1 t 3 h 1 h 2 h 2 t 1 t AG(A,B) e) 3 t Figure 2.3: Three genomes C = ({4 t }, {4 h , 1 t }, {1 h , 2 h }, {2 t , 3 h }, {3 t , 1 t }, {1 h }) , A = ({3 t , 1 t }, {1 h , 2 h }, {2 t , 3 h }), ({4 t }, {4 h , 1 t }, {1 h }) , and B = ({1 h , 2 h }, {2 t , 1 t }), ({3 t , 2 h }, {2 t , 1 h }, {1 t , 3 h })
are depicted in a)-c). C consists of a linear chromosome, A consists of a linear and a circular chromosome, while B consists of two circular chromosomes. The sets of adjacencies of C and A are the same, thus d aDCJ (A, C) = 0, while d gDCJ (A, C) = 1. Take a genome andG(A , B) are depicted in d). The vertex •, representing the ends of the linear chromosomes, is colored white. Extra colored edges are added for the missing genes (e.g. ({2 t , 2 h }, black) and ({4 h , 4 t }, gray)), called ghost adjacencies in [START_REF] Shao | Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion[END_REF]. The operation transforming A to A is an insertion of gene 2. It corresponds to the 2-break G(A, B) → G(A , B). In e) the adjacency graph AG(A, B) is depicted with diamonds indicating the ghost adjacencies.

A = {3 t , 2 h }, {2 t , 1 t }, {1 h , 2 h }, {2 t , 3 h } , {4 t }, {4 h , 1 t }, {1 h } . The breakpoint graphs G(A, B)
= ({1 t }, {1 h , 3 t }, {3 h }), ({4 h }, {4 t }), ({2 t , 5 h }, {5 t , 2 h }) and B = ({1 h , 2 t }, {2 h , 1 t }), ({3 t }, {3 h , 4 t }, {4 h }), ({5 h }, {5 t })
Both A and B contain a circular and 2 linear chromosomes. AG(A, B) contains two odd paths, an AA and a BB path. The odd path In what follows we establish that the equality d 2b (G(A, B)) = d aDCJ (A, B) stays valid for the non-single copy genomes. The breakpoint graph G(A, B) is defined in such a way, that for a DCJ A → A , the corresponding graph transformation

({1 t }, {2 h , 1 t }, {5 t , 2 h }, {5 t }) of AG(A, B), corresponds to the cycle (•, 1 t , 2 h , 5 t , •) of G(A, B). The AA path ({3 h }, {3 h , 4 h }, {4 h }) of AG(A, B) corresponds to the AA path (•, 3 h , 4 h , •) of G(A, B). The BB path ({3 t }, {3 t , 1 h }, {1 h , 2 t }, {2 t , 5 h }, {5 h }) of AG(A, B) corre- sponds to the BB path (•, 3 t , 1 h , 2 t , 5 h , •) of G(A, B).
G(A, B) → G(A ,

Unsigned DCJs

Due to experimental limitations the directions (also known as strandedness or signs) of the genes might remain unknown. In such a case a chromosome can still be modeled as a circular or linear order of unsigned genes. For example a signed genome A s = ({3 t , 1 t }, {1 h , 2 h }, {2 t , 3 h }), ({4 t }, {4 h , 1 t }, {1 h }) can be interpreted as an unsigned one A u = ({3, 1}, {1, 2}, {2, 3}), ({4}, {4, 1}, {1}) . The definitions of DCJ and the breakpoint graph remain valid for genomes containing unsigned genes, and so does Theorem 1. Chen [START_REF] Chen | On sorting unsigned permutations by double-cut-and-joins[END_REF] previously established this theorem for unsigned genomes using a slightly less general representation of a genome as a signed permutation.

Transpositions are 2-breaks

We start by introducing the basic notions of the theory of sorting permutations with transpositions. In the field of genome rearrangements a transposition is a rearrangement that swaps two adjacent regions of a chromosome, where a region can contain any number of genes. However in mathematics more broadly a transposition is a permutation that exchanges any two elements. It is the latter notion that we will use throughout this work. A permutation σ of V = {1, . . . , n} is a bijection σ : V → V . Denote the set of permutations of V by S n . The identity permutation, which maps every element onto itself, is denoted by id. The product of two permutations σ 1 and σ 2 is a permutation σ 1 σ 2 , such that σ 1 σ 2 (i) = σ 1 (σ 2 (i)) for any i ∈ V . Every permutation σ has an inverse σ -1 , such that σσ -1 = id. An orbit of a permutation σ on x ∈ V is the set {σ n (x)|n ∈ Z}. A permutation is a cycle if it has at most one orbit of size larger than 1. Denote the number of the disjoint orbits of a permutation σ by c(σ). Such a permutation can be written as a product of c(σ) disjoint cycles. A transposition is a cycle of length 2. Every permutation can be written as a product of transpositions, the minimum number of transpositions in such a product is denoted by d Cayley (σ, id). A sequence of transpositions (π 1 , . . . , π m ), for which π m . . . π 1 σ = id, with m = d Cayley (σ, id), is called a Minimum Length Transposition Decomposition (MLTD) of σ. The Cayley distance d Cayley (σ 1 , σ 2 ) between two permutations is defined to be d Cayley (σ -1 2 σ 1 , id).

Lemma 5 (Cayley [30]). For every permutation σ on n elements d Cayley (σ, id) = n -c(σ).

We proceed by introducing a graphical representation of permutations, similar to the breakpoint graph of the genomes, and by showing that there is a bijection between the parsimonious 2-break scenarios for that graph and the MLTDs of the permutations.

Definition 19 (Permutation breakpoint graph). For a pair of permutations

(σ 1 , σ 2 ) define a graph H(σ 1 , σ 2 ) on vertices V t = {1 t , . . . , n t } and V h = {1 h , . . . , n h } with black edges {(i h , σ 1 (i) t )|i ∈ V } and gray edges {(i h , σ 2 (i) t )|i ∈ V }.

Definition 20 (Positive circular graph).

A graph is circular if the black and gray degrees of its vertices are equal to 1, which means that all of its connected components are circles. A graph is positive if it is a bipartite graph on vertices V h = {1 h , . . . , n h } and V t = {1 t , . . . , n t }, with V h and V t being independent sets. Observation 7. H(σ 1 , σ 2 ) is a positive circular graph. See Figure 2.5 b) for an example with σ 1 = (123456) and σ 2 = id. Lemma 6. For a positive circular graph H there exist unique permutations σ 1 and

σ 2 such that H(σ 1 , σ 2 ) = H. If H is terminal, then σ 1 = σ 2 .
Proof. For every i ∈ {1, . . . , n} there exist unique k, l ∈ {1, . . . , n} such that H contains colored edges ({i h , k t }, black) and ({i h , l t }, gray). We define σ 1 (i) = k and σ 2 (i) = l to obtained the required permutations.

Definition 21 (Colored transposition).

A colored transposition is a pair of a transposition and a color col ∈ {black, gray}. A color indicates whether the transposition applies to σ 1 or σ 2 . [START_REF] Marília | Counting all DCJ sorting scenarios[END_REF]. Their product πσ can be expressed as a product of two disjoint cycles πσ = (1456) [START_REF] Bonnet | Complexity of token swapping and its variants[END_REF]. A graphical representation of a permutation as a functional digraph

D(σ) = (V, {(i, σ(i))|i ∈ V }) is depicted in a)
τ i transforms H(π(τ i-1 ) . . . π(τ 1 )σ, id) to H(π(τ i )π(τ i-1 ) . . . π(τ 1 )σ 1 , σ 2 ), thus H(σ, id) = H(π(τ l ) . . . π(τ 1 )σ, id).
Due to Lemma 6, π(τ l ) . . . π(τ 1 )σ = id, thus (π(τ 1 ), . . . , π(τ l )) is a transposition decomposition of σ. This establishes that l ≥ m, and thus m = l, which means that (τ (π 1 , black), . . . , τ (π m , black)) is a parsimonious black-2-break scenario for H(σ, id) and (π(τ 1 ), . . . , π(τ l )) is an MLTD of σ.

Lemma 8 can be easily generalized using the following definition of an MLTD of a pair of permutations.

Definition 25 (Shuffle).

A shuffle of two sequences ρ 1 and ρ 2 is a sequence that can be partitioned into the sub-sequences equal to ρ 1 and ρ 2 .

Example 1. (b 1 , b 2 , a 1 , b 3 , a 2 , a 3 , b 4 ) is shuffle of (a 1 , a 2 , a 3 ) and (b 1 , b 2 , b 3 , b 4 ).

Definition 26 (MLTD of permutations). Take two sequences of colored transpositions

T 1 = ((π 1 1 , black), . . . , (π 1 m 1 , black)) and T 2 = ((π 2 1 , gray), . . . , (π 2 m 2 , gray)), such that π 1 m 1 . . . π 1 1 σ 1 = π 2 m 2 . . . π 2 1 σ 2 and m 1 + m 2 = d Cayley (σ 1 , σ 2 ). An MLTD of σ 1 and σ 2 is a shuffle of T 1 and T 2 .
Essentially the same proof as that of Lemma 8, allows us to establish a bijection between the parsimonious 2-break scenarios for H(σ 1 , σ 2 ) and the MLTDs of σ 1 and σ 2 .

Theorem 2. Take an MLTD ((π 1 , col 1 ), . . . , (π m , col m )) of σ 1 and σ 2 . A sequence of 2-breaks (τ (π 1 , col 1 ), . . . , τ (π m , col m )) is a parsimonious scenario for H(σ 1 , σ 2 ). Take a parsimonious 2-break scenario (τ 1 , . . . , τ m ) for H(σ 1 , σ 2 ), with (col 1 , . . . , col m ) being the colors of these 2-breaks. A sequence ((π(τ 1 ), col 1 ), . . . , (π(t m ), col m )) is an MLTD of σ 1 and σ 2 .

A Parsimonious DCJ Scenario for Co-tailed

Single Copy Genomes is a Parsimonious 2break Scenario for a Circular Positive Graph

Positive Genomes

We want to establish a link between the DCJ scenarios for single copy genomes and the transposition decompositions of permutations. It is not an immediate task due to the differences between the genome and permutation breakpoint graphs.

• The breakpoint graph of the single copy genomes is not circular, as it contains a vertex • with the black and gray degrees greater than one.

• The genome breakpoint graph is not necessarily positive (see Definition 20).

In what follows we show how to overcome these two differences and interpret a parsimonious DCJ scenario as an MLTD and vice versa.

Definition 27 (Internal genome breakpoint graph). Take the genome breakpoint graph of two genomes A and B and remove from it the connected component containing • to obtain the internal genome breakpoint graph H(A, B).

Observation 10. The internal genome breakpoint graph of single copy genomes is circular.

Here we introduce positive genomes. The internal genome breakpoint graph of positive single copy genomes is a circular positive graph.

Definition 28 (Positive genome). An adjacency of a genome is positive, if it contains one head and one tail extremity. A genome is positive if all of its adjacencies are positive.

By the end of the section we will establish that a 2-break scenario for the internal genome breakpoint graph of two single copy genomes can be interpreted as a 2break scenario for the internal genome breakpoint graph of two positive single copy genomes.

Lemma 9. The vertices of a circular graph can be partitioned into two independent sets of equal size.

Proof. A circular graph is a vertex disjoint union of circles, thus it is enough to prove the statement for a circle C. C has an even number of vertices, take every second one of them. The obtained sub-set of vertices is an independent set of C. Its complement is also an independent set of C, thus establishing the result.

Definition 29 (Independent sets of a circular graph). The independent sets of a circular graph are the independent sets presented in Lemma 9.

Observation 11. The independent sets of a positive circular graph are {1 h , . . . , n h } and {1 t , . . . , n t }.

Lemma 10. For a circular graph there exists an isomorphic positive circular graph.

Proof. Take a circular graph G on 2n vertices. Denote its independent sets by

V 1 and V 2 . |V 1 | = |V 2 | = n, due to Lemma 9. Fix bijections f 1 : V 1 → V h and f 2 : V 2 → V t . Together they define a bijection f : V 1 ∪ V 2 → V h ∪ V t . To every colored edge ({u, v}, col) of G assign a colored edge ({f (u), f (v)}, col) to obtain a positive circular graph isomorphic to G.

Theorem 3. For single copy genomes A and B there exist positive single copy genomes A p and B p , such that the internal genome breakpoint graphs H(A, B) and

H(A p , B p ) are isomorphic.
Proof. H(A, B) is a circular graph, denote its number of vertices by 2n . Due to Lemma 10, there exists a circular positive graph H on vertices {1 h , . . . , n h } ∪ {1 t , . . . , n t } isomorphic to H(A, B). For every colored edge ({u, v}, black) (respectively ({u, v}, gray)) of H add an adjacency {u, v} to a genome A p (respectively B p ). The genomes A p and B p thus obtained are positive and H(A p , B p ) = H.

We conclude by establishing that a 2-break scenario for H(A, B) can be interpreted as a 2-break scenario for H(A p , B p ).

Definition 30 (Image of a 2-break). Take a function

f : V 1 → V 2 between two sets of vertices and a 2-break τ = {u, v}, {w, s} → {u, w}, {v, s} , col with vertices in V 1 . Denote {f (u), f (v)}, {f (w), f (s)} → {f (u), f (w)}, {f (v), f (s)} , col , a 2-break with vertices in V 2 , by f (τ ). Observation 12. Take two isomorphic graphs G 1 and G 2 , their isomorphism f and a 2-break scenario ρ = (τ 1 , . . . , τ m ) for G 1 . f (ρ) = (f (τ 1 ), . . . , f (τ m )) is a 2-break scenario for G 2 . If ρ is parsimonious, then so is f (ρ).

Co-tailed genomes

Here we introduce co-tailed genomes. A parsimonious 2-break scenario for their breakpoint graph is also a parsimonious 2-break scenario for their internal genome breakpoint graph and vice versa.

Definition 31 (Co-tailed genomes). Two genomes are co-tailed if their sets of external adjacencies are equal.

Definition 32 (Circular genome).

A genome is circular if all of its adjacencies are internal.

Observation 13. Two circular genomes are necessarily co-tailed. H(A,B)), which leads to Lemma 11.

The breakpoint graph G(A, B) of co-tailed genomes is a vertex disjoint union of H(A, B) and a terminal graph. This means that

d 2b (G(A, B)) = d 2b (

Lemma 11. Take co-tailed genomes A and B, and parsimonious 2-break scenarios ρ and ρ for G(A, B) and H(A, B). ρ and ρ are also parsimonious 2-break scenarios for H(A, B) and G(A, B

) respectively.

Synthesis

By now we are ready to put all the results from this section together. Take two cotailed single copy genomes A and B and their parsimonious DCJ scenario ∆. Due to Theorem 1, ∆ can be interpreted as a parsimonious 2-break scenario ρ = ρ(∆) for the breakpoint graph G(A, B). Due to Lemma 11, ρ is also a parsimonious 2-break scenario for the internal genome breakpoint graph H(A, B). Due to Theorem 3, there exist positive genomes A p and B p for which H(A, B) and H(A p , B p ) are isomorphic. Take their isomorphism f . Due to Observation 12, f (ρ) is a parsimonious 2-break scenario for H(A p , B p ). The latter is a positive circular graph by construction. Due to Lemma 6, there exist permutations σ 1 and σ 2 such that H(σ 1 , σ 2 ) = H(A p , B p ). And finally, due to Theorem 2, f (ρ) can be interpreted as a Minimum Length Transposition Decomposition of σ 1 and σ 2 . The implicated lemmas and theorems go both ways, thus ensuring that an MLTD of σ 1 and σ 2 can be interpreted as a parsimonious DCJ scenario for A and B. To this end, we obtain a stronger result. Every transposition on σ 1 or σ 2 can be interpreted as a 2break on H(σ 1 , σ 2 ), and every 2-break on H(σ 1 , σ 2 ) = H(A p , B p ) can be interpreted as a DCJ on A or B. Thus we obtain that every transposition decomposition of σ 1 and σ 2 can be interpreted as a DCJ scenario for A and B of the same length.

2 h 1 h 1 t 2 t 1 2 1 2 1 2 a) b)
Figure 2.6: Three single copy genomes are depicted in a). The three genomes are circular (see Definition 32), which also means that they are co-tailed (see Definition 31). Their 3-edge-colored internal genome breakpoint graph depicted in b) is not a bipartite graph as was always the case for the internal genome breakpoint graphs of two genomes.

The Median and Center Problems

The Swap and DCJ Median Problems

The genome breakpoint graph can be easily generalized for 3 genomes. In this case it is a 3-edge-colored multigraph. See Figure 2.6 for an example of the internal genome breakpoint graph of three co-tailed genomes. The internal genome breakpoint H(A, B, C) in the example is not bipartite. This means that the gene extremities no longer can be renamed to obtain three positive genomes with an isomorphic internal genome breakpoint graph. This also means that there are no permutations σ 1 , σ 2 and σ 3 with a breakpoint graph H(σ 1 , σ 2 , σ 3 ) isomorphic to H(A, B, C). This leads to a situation where the complexity of the Swap Median Permutation problem [START_REF] Yu | Multiple genome rearrangement by swaps and by element duplications[END_REF] remains unknown, even though the DCJ Median problem is known to be NP-hard [START_REF] Tannier | Multichromosomal median and halving problems under different genomic distances[END_REF].

Fix n ∈ N and denote by G n a set of all the genomes with genes {1, . . . , n}.

Problem 1 (The Swap Median Permutation problem (SMP), open [82]).

INPUT : X ⊆ S n , and r ∈ N.

OUTPUT : TRUE, if min σ M ∈Sn σ∈X d Cayley (σ M , σ) ≤ r. FALSE otherwise.
Observation 14. Popov [START_REF] Yu | Multiple genome rearrangement by swaps and by element duplications[END_REF] uses the term swap for what we call transposition.

Problem 2 (The DCJ Median problem for 3 circular genomes, NP-complete [START_REF] Tannier | Multichromosomal median and halving problems under different genomic distances[END_REF]).

INPUT : Three circular genomes A 1 , A 2 , A 3 , and r ∈ N.

OUTPUT : TRUE, if min

A M ∈Gn i∈{1,2,3} d aDCJ (A M , A i ) ≤ r. FALSE otherwise.
Not only is there no clear reduction from the DCJ Median problem for circular genomes to SMP, but also the reduction from the Breakpoint Graph Decomposition problem, a variant of the Maximum Alternating Edge-disjoint Cycle Decomposition (MAECD) problem, used to establish NP-hardness of a number of other median problems does not seem to apply to SMP.

A graph G is a balanced bicolored graph if the black and gray degrees of its vertices are equal to 1 or 2 and it does not contain a monochromatic cycle nor parallel edges. Caprara [START_REF] Caprara | Sorting permutations by reversals and Eulerian cycle decompositions[END_REF] demonstrated that the Breakpoint Graph Decomposition problem, consisting of finding an MAECD of a balanced bicolored graph, is NPhard. To prove the NP-hardness of the DCJ Median problem Tannier, Zhen and Sankoff [START_REF] Tannier | Multichromosomal median and halving problems under different genomic distances[END_REF] used a reduction from the Breakpoint Graph Decomposition problem similar to the one originally introduced by Caprara [START_REF] Caprara | The reversal median problem[END_REF] for the Inversion Median problem and later used by Feijão and Araujo [START_REF] Feijão | Fast ancestral gene order reconstruction of genomes with unequal gene content[END_REF] for the Intermediate Genome Median problem. In that reduction three genomes are associated to a balanced bicolored graph and some properties about the median are established. Two of the genomes and the obtained median are positive, but not the third genome, and there does not seem to be a simple way to modify that reduction so that it could work for SMP.

For now we pose the following question that would further our understanding of the links between sorting genomes by DCJs and sorting permutations by transpositions.

Problem 3 (open problem). Does a set of positive genomes admit a DCJ median that is positive?

If the answer to Problem 3 is yes, then the Swap Median Permutation problem is equivalent to the DCJ Median problem for positive genomes, which itself is equivalent to the DCJ Median problem for the co-tailed genomes for which the internal breakpoint graph is bipartite.

The Swap and DCJ Center Problems

The following problems illustrate the opposite situation, where our understanding of sorting with transpositions might inform us on sorting with DCJs.

Problem 4 (The Swap Center Permutation problem (SCP), NP-complete [START_REF] Yu | Multiple genome rearrangement by swaps and by element duplications[END_REF]).

INPUT : X ⊆ S n , and r ∈ N.

OUTPUT : TRUE, if min σ C ∈Sn max σ∈X d Cayley (σ C , σ) ≤ r. FALSE otherwise.
Problem 5 (The DCJ Closest Genome problem, open [START_REF] Felipe | On the computational complexity of closest genome problems[END_REF]).

INPUT : a set X of genomes, and r ∈ N.

OUTPUT : TRUE, if min

A C ∈Gn max A∈X d aDCJ (A C , A) ≤ r. FALSE otherwise.

Problem 6 (open problem). Does a set of positive genomes admit a DCJ closest genome that is positive?

If the answer to Problem 6 is yes, then SCP can be reduced to the DCJ Closest Genome problem, which would establish its NP-hardness.

The Rank Median Problem

In this section we briefly discuss a recent line of work on a variant of a median problem that is solvable in polynomial time and relates to the Swap Median Permutation problem.

A square real valued matrix M is orthogonal if M T M = M M T = I, where I is the identity matrix and M T is the transpose of M . A permutation matrix is a binary orthogonal matrix. Such a matrix has a single 1 in each column and each row. A permutation matrix P defines a permutation σ P , with σ P (i) = j if and only if P [i][j] = 1. Analogously a permutation σ defines a permutation matrix. The rank distance is defined for square real valued matrices M 1 and M 2 , with

d rk (M 1 , M 2 ) = rank(M 1 -M 2 ).
The following result relates rank distance for permutation matrices and Cayley distance for the corresponding permutations.

Lemma 12 (Zanetti, Biller, and Meidanis [START_REF] Paulo | Median approximations for genomes modeled as matrices[END_REF]). For permutation matrices P 1 and P 2 we have that

d rk (P 1 , P 2 ) = d Cayley (σ P 1 , σ P 2 ).
Denote the set of all n × n permutation matrices by P n . Problem 7 (The Permutation Rank Median problem for 3 permutation matrices, open [START_REF] Chindelevitch | A cubic algorithm for the generalized rank median of three genomes[END_REF]).

INPUT : permutation matrices P 1 , P 2 , P 3 ∈ P n , and r ∈ N.

OUTPUT : TRUE, if min

P M ∈P n i∈{1,2,3} d rk (P M , P i ) ≤ r. FALSE otherwise.
Due to Lemma 12, the Permutation Rank Median problem is equivalent to the Swap Median Permutation problem.

Problem 8 (The Rank Median problem).

INPUT : matrices M 1 , M 2 , M 3 ∈ R n×n , and r ∈ N. OUTPUT : TRUE, if min M M ∈R n×n i∈{1,2,3} d rk (M M , M i ) ≤ r. FALSE otherwise.
Chindelevitch, Zanetti, Pereira and Meidanis [START_REF] Chindelevitch | On the rank-distance median of 3 permutations[END_REF] established that the Rank Median problem is of polynomial time complexity for three orthogonal matrices. A Genomic matrix is defined to be a symmetric permutation matrix. Chindelevitch, La, and Meidanis [START_REF] Chindelevitch | A cubic algorithm for the generalized rank median of three genomes[END_REF] provided a cubic time algorithm for the Rank Median problem for three genomic matrices and showed that there always exists a rank median that is symmetric and orthogonal, but not necessarily binary.

Sorting Permutations, Strings and Graphs

Introduction

In the previous sections we have established that the problem of sorting graphs with 2-breaks generalizes those of sorting genomes with DCJs and sorting permutations with transpositions. In this section, without entering too much into the details, we complement the picture by introducing the problems of sorting strings with interchanges and swapping tokens on graphs, together with their cost constrained variants. We also explain how the results on the cost constrained 2-breaks to be presented in this thesis generalize the known results for these seemingly unrelated sorting problems.

The Dutch National Flag Problem (DNF) [21]

Take a string x of n marbles that are either red, white or blue, and a string y with the red marbles going first, followed by the white ones, followed by the blue ones. Any two marbles in x can be interchanged. The Dutch National Flag problem asks for a minimum length interchange scenario transforming x to y. We define a 2-edge-colored graph H(x, y) on vertices {1, . . . , n} ∪ {R, W, B} with black edges {i, x[i]} and gray edges {i, y[i]}. H(x, y) is Eulerian and bipartite by construction. See Figure 2.7 b) for an example demonstrating that an interchange on x corresponds to a 2-break on H(x, y) preserving its bipartite structure. The minimum length of an interchange scenario transforming x to y is equal to d 2b (H(x, y)).

Bitner [21], represents x with a digraph D(x) on vertices {R, B, W } with directed edges (x[i], y[i])|i ∈ {1, . . . , n} . See Figure 2.
1 2 3 4 5 6 R W B 1 2 3 4 5 6 R W B R W B R W B a) b)
[i] = y[σ 1 (i)],
and so does σ 2 = (124365). The minimum cost of a transposition decomposition for both of these permutations is equal to 2, which is also the minimum number of interchanges required to transform x to y. Transpositions ( 24) and ( 35) of cost 1 transform σ 1 to id. Transpositions ( 16) and ( 34) of cost 1 transform σ 2 into σ 2 = (231) [START_REF] Hartmann | An exact algorithm for sorting by weighted preserving genome rearrangements[END_REF], which can be transformed to id with the help of three transpositions of cost 0.

MIN-cost-MLTD [41]

Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] fix an arbitrary cost function on the set of transpositions. They define the cost of a transposition decomposition to be the sum of the costs of its transpositions. The authors propose an O(n 4 )-time algorithm for the problem of finding a minimum cost decomposition among the Minimum Length Transposition Decompositions of a permutation (MIN-cost-MLTD) .

This work on the MIN-cost-MLTD problem influenced our research on cost constrained 2-breaks. The results that we will present in Chapter 5 allow us to generalize the work by Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] in a number of ways. First, we allow the cost of a transposition (ij) acting on a permutation σ to depend not only on i and j as in [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF], but also on σ -1 (i) and σ -1 (j), while keeping the same asymptotic complexity for solving the MIN-cost-MLTD problem. Second, a transposition decomposition in [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] can be seen as sorting a source permutation σ 1 into a target permutation id. Our work, on the other hand, can be interpreted as sorting two permutations σ 1 and σ 2 into some intermediate one, with the transpositions performed on σ 1 and σ 2 possibly having different costs.

MIN-cost-TD [41, 42]

Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] also investigate the problem of finding a minimum cost transposition decomposition of a permutation, the MIN-cost-TD problem. They prove that for an arbitrary cost function MIN-cost-MLTD is a 4-approximation of MIN-cost-TD. The work on the MIN-cost-TD problem [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF][START_REF] Farnoud | Computing similarity distances between rankings[END_REF] combined with our results on relating transposition decompositions and 2-break scenarios could in the future inform the search for a minimum cost 2-break scenario for a graph.

In [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] and [START_REF] Farnoud | Computing similarity distances between rankings[END_REF] it remained open whether the MIN-cost-TD problem is NPhard. We provide a polynomial time reduction from DNF to MIN-cost-TD. See Figure 2.7 for an example. Take an instance (x, y) of DNF and a permutation σ : {1, . . . , n} → {1, . . . , n} for which x[i] = y[σ(i)]. σ is not necessarily unique, and σ(i) fixes a position in y into which an element in position i in x must be moved. An interchange of the elements in the positions i and j in x corresponds to a transposition (σ(i)σ(j)) performed on σ. Make the cost of (ij) to be 0 if y[i] = y[j] and 1 otherwise. It can be shown that for this cost function, the cost of a minimum cost transposition decomposition of σ is equal to the minimum length of an interchange scenario transforming x into y. This establishes that MIN-cost-TD is NP-hard.

The Interchange Rearrangement Problem [4]

Take two strings x and y of length n with equal multisets of elements from a set S. Any two elements in x can be be interchanged. Costs are associated to interchanges and the goal is to transform x to y with a scenario minimizing the sum of the costs of its interchanges. Amir and Levy [START_REF] Amir | String rearrangement metrics: A survey[END_REF] propose a detailed survey of related Interchange Rearrangement problems. If each string has a unique occurrence of each element, then the problem is equivalent to the MIN-cost-TD problem. Amir, Hartman, Kapah, Levy, and Porat [START_REF] Amir | On the cost of interchange rearrangement in strings[END_REF] pose the w-Interchange Distance problem. Here the cost of an interchange of two elements at positions i and j is equal to |i -j| α with α ≥ 0. Among other results, the authors propose a linear time algorithm for α = 1 and show that the problem is NP-hard for α = 0. The Dutch National Flag problem is a particular case with the set S being equal to {R, W, B} and α = 0. Kapah, Landau, Levy, and Oz [START_REF] Kapah | Interchange rearrangement: The element-cost model[END_REF] study the Interchange Rearrangement Problem Under the Element-cost Model. Here the cost of an interchange depends on the elements that are being interchanged and not on their positions as in the w-Interchange Distance problem. The authors fix a non-negative function weight : S → R + on the elements in the set S. A symmetric function g on the pairs of elements is said to be general if for any three elements u, w, s it satisfies that weight(w) ≤ weight(s) if and only if g(u, w) ≤ g(u, s). The cost of an interchange of u and w is defined to be g(u, w). If each string x and y has a unique occurrence of each element, then a minimum cost interchange scenario for a general function can be found in linear time. The problem becomes NP-hard for general strings, however a 3-approximation algorithm is proposed in [START_REF] Kapah | Interchange rearrangement: The element-cost model[END_REF].

As in Section 2.7.2, we define a bipartite 2-edge-colored graph H(x, y) on vertices {1, . . . , n} ∪ S with black edges {i, x[i]} and gray edges {i, y[i]}. H(x, y) is Eulerian by construction. An interchange of elements in x results in a 2-break on H(x, y). Consider the Parsimonious Interchange Rearrangement problem, where we search for a minimum cost interchange scenario among the parsimonious ones.

If each string x and y has a unique occurrence of each element, and the interchange cost depends only on the positions of the elements being interchanged, then this problem is equivalent to MIN-cost-MLTD. Our results in Chapter 5 allow us to solve this problem for a cost function that depends both on the positions and the elements being interchanged. Our algorithm is polynomial for the strings that have unique occurrence of each element. The problem for general strings is NP-hard.

The Token Swapping Problem [100, 23, 101]

Take a connected 1-edge-colored simple graph on n vertices. Place unique tokens on its vertices and assign each token a unique destination vertex. Two tokens lying on adjacent vertices can be swapped. A token swap sequence is a sequence of token swaps that move all the tokens to their destination vertices. The Token Swapping problem [START_REF] Yamanaka | Swapping labeled tokens on graphs[END_REF] asks for the minimum length of a token swapping sequence. See Figure 2.8 for an illustration of the problem.

To a token t lying on a vertex u assign a token σ(t) whose destination vertex is u. Take two tokens t 1 and t 2 . A swap of the tokens lying on their destination vertices transforms σ into (t 1 t 2 )σ, and at the end of the scenario the identity permutation is obtained. This means that the Token Swapping problem is equivalent to the MIN-cost-TD problem where some transpositions are assigned infinite cost. The complexity of the Token Swapping problem remains unknown for trees. Yamanaka et al. [START_REF] Yamanaka | Swapping labeled tokens on graphs[END_REF] observed that there always exists a token swapping sequence of length O(n 2 ). This might be useful to prove Conjecture 1 from Farnoud, Milenkovic, Puleo, and Su [START_REF] Farnoud | Computing similarity distances between rankings[END_REF] that there always exists an O(n 2 ) length transposition decomposition of minimum cost.

The Colored Token Swapping Problem [23, 101]

Place colored tokens on the colored vertices of a connected 1-edge-colored simple graph. Two tokens lying on adjacent vertices can be swapped. A colored token swap sequence is a sequence of token swaps that moves the tokens to the vertices with corresponding colors. The Colored Token Swapping problem asks for the minimum length of a colored token swap sequence. For two colors, the Colored Token Swapping problem can be solved in polynomial time for general graphs and in linear time for trees. For three colors, the problem is NP-hard even for restricted families of graphs [START_REF] Yamanaka | Swapping colored tokens on graphs[END_REF].

Enumerate the vertices of a graph and take two sequences x and y, where x[i] is the color of the token on the vertex i and y[i] is the color of the vertex i. The Colored Token Swapping problem can be interpreted as the Interchange Rearrangement problem on x and y, where the interchanges of the elements at the positions corresponding to the adjacent vertices have cost equal to 1 and other interchanges have infinite cost.

Conclusion

We have established novel links between the problems of sorting genomes with DCJs, sorting permutations with transpositions and sorting graphs with 2-breaks. See Figure 2.9 for a summary.

These links allow us to interpret a DCJ in a parsimonious sorting scenario for genomes with n genes as a transposition acting on a permutation of n elements, and vice versa. However, this symmetry breaks once a non-parsimonious DCJ scenario is being considered. Feijão and Meidanis [START_REF] Feijao | Extending the algebraic formalism for genome rearrangements to include linear chromosomes[END_REF] showed that a genome with n genes can be interpreted as a permutation of 2n elements, and that a DCJ acting on a genome can be interpreted as a pair of transpositions acting on that permutation (see Figure 2.5 for an example). Their work allows us to interpret a non-parsimonious DCJ scenario as a transposition decomposition of a permutation, however the reverse problem of interpreting a transposition decomposition as a DCJ scenario is not addressed. Combination of these two lines of work might lead to a better understanding of the non-parsimonious 2-break and DCJ scenarios.

Such an understanding might allow for an exchange of ideas on sampling and estimation. For example, see a recent work by Irurozki, Calvo, and Lozano [START_REF] Irurozki | Sampling and learning Mallows and Generalized Mallows models under the Cayley distance[END_REF] on sampling permutations based on their Cayley distance to a given permutation, which might inform us on how to sample genomes based on their DCJ distance to a given genome.

Chapter 3 A Parsimonious 2-break Scenario for a Graph

Introduction

In this chapter we study in detail the structure of a parsimonious 2-break scenario. We show that a parsimonious 2-break scenario for a graph can be interpreted as a set of parsimonious 2-break scenarios for the circles corresponding to its simple cycles. In addition to that, a parsimonious 2-break scenario for a circle can be partitioned into parsimonious 2-break scenarios for its sub-circles, and this property allows for a dynamic programming algorithm exploring the space of the parsimonious 2-break scenarios for a circle. The main results of this chapter are the following:

1. A parsimonious 2-break scenario for a graph can be partitioned into parsimonious 2-break scenarios for the simple cycles in one of its Maximum Alternating Edge-disjoint Cycle Decompositions.

2. A parsimonious 2-break scenario for a simple cycle S can be interpreted as a parsimonious 2-break scenario for a circle arising from one of the Eulerian orientations of S.

3. A parsimonious 2-break scenario for a sub-circle of a circle C can be partitioned into parsimonious 2-break scenarios for smaller sub-circles of C.

4.

There is a bijection between the equivalence classes of the parsimonious 2break scenarios for a circle and the quadrangulations of a regular polygon.

There is also a bijection between the equivalence classes of the Minimum Length Transposition Decompositions of a cyclic permutation σ and the equivalence classes of the parsimonious 2-break scenarios for its permutation breakpoint graph H(σ, id).

51

Taken together these results enable us to efficiently search the space of parsimonious 2-break scenarios. We will build on them in Chapter 5 where we search for a minimum cost 2-break scenario among the parsimonious ones. We have published the initial versions of these results in [START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF][START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF].

A Parsimonious 2-break Scenario for a Graph is a Shuffle of the Parsimonious 2-break Scenarios for the Simple Cycles

In this section we show that a parsimonious 2-break scenario for a graph can be partitioned into parsimonious 2-break scenarios for its simple cycles. We do this with the help of the trajectory graph introduced by Shao, Lin, and Moret [START_REF] Shao | Sorting genomes with rearrangements and segmental duplications through trajectory graphs[END_REF]. The trajectory graph there is defined for a DCJ scenario, and Theorem 2 in [START_REF] Shao | Sorting genomes with rearrangements and segmental duplications through trajectory graphs[END_REF] establishes that the connected components of the trajectory graph of a parsimonious DCJ scenario are trees, and that these connected components correspond to the cycles of the adjacency graph. We redefine the trajectory graph of a 2-break scenario for a graph G, and show in Theorem 4 that the connected components of the trajectory graph of a parsimonious 2-break scenario for G are trees corresponding to a Maximum Alternating Edge-disjoint Cycle Decomposition of G.

Observation 15. A shuffle of the 2-break scenarios for the subgraphs in an Eulerian decomposition of a graph is a 2-break scenario for that graph. If the scenarios for the subgraphs are parsimonious, then the obtained scenario for the graph is also parsimonious.

In this subsection we establish a complementary result. Namely, that for a 2break scenario ρ on a graph there exists an Eulerian decomposition such that ρ is a shuffle of the 2-break scenarios for its subgraphs.

Definition 33 (Sink/source vertex and edge of a digraph). A vertex of a 2-edgecolored digraph is a source, if its black and gray indegrees are equal to 0. It is a sink, if its black and gray outdegrees are equal to 0. An edge of such a digraph is a source edge, if it is incident to a source vertex, while it is a sink edge if it is incident to a sink vertex. According to this definition an edge can be both a source and a sink at the same time.

Denote by ρ l the prefix of ρ of length l and by G l the graph obtained from G after ρ l is performed. Construct the trajectory graph D(G, ρ) in the following way. Start with an empty graph. For each colored edge ({u, v}, col) of G add two new vertices connected by a directed edge of color col labeled {u, v} to obtain D(G, ρ 0 ). See Figure 3.1 d) for an example. For the l-th 2-break in ρ ({u, v}, {w, s} → {u, w}, {v, s}, col), choose any two sink edges of D(G, ρ l-1 ) of color col labeled {u, v} and {w, s}, and merge their sink vertices. Proceed by adding two new edges of color col labeled {u, w} and {v, s} from the merged vertex to the newly added ones, thus obtaining D(G, ρ l ). Continue until D(G, ρ m ) is obtained, where m is the length of ρ. G m is terminal, thus the multisets of the labels of its sink black and gray edges are equal. This means that there exists a bijection between the sink vertices of D(G, ρ m ) incident to the edges of the same label but of different colors. Choose such a bijection at random and merge the pairs of the sink vertices of D(G, ρ m ) mapped by this bijection. Denote the obtained graph by D(G, ρ). See Figure 3.1 for an example of D(G, ρ). Shao, Lin, and Moret [START_REF] Shao | Sorting genomes with rearrangements and segmental duplications through trajectory graphs[END_REF] prove that the connected components of the trajectory graph for a parsimonious scenario are trees, and that they correspond to the cycles of the adjacency graph. The following theorem can be seen as a generalization of this result for the non-parsimonious scenarios. Proof. Denote by {C 1 , . . . , C k } the connected components of D(G, ρ). For i ∈ 1, k and l ∈ 0, m , denote by C i l a subgraph of D(G, ρ l ) consisting of its connected components containing the source vertices of C i . By construction, there exists a bijection between the sink edges of the graphs in {C Corollary 4. A parsimonious 2-break scenario for a graph having two connected components can be partitioned into two sub-sequences that are respectively parsimonious 2-break scenarios for these components.

3.1: An Eulerian 2-edge-colored multigraph G is depicted in a). A parsimo- nious 2-break scenario ρ = ({2, 3}, {4, 5} → {2, 5}, {3, 4}, gray), ({1, 2}, {5, 6} → {1, 6}, {2, 5}, black) transforms G into a terminal graph G 2 depicted in c). The prefix ρ 1 of ρ of length 1 transforms G into G 1 depicted in b). D(G, ρ 0 ), D(G, ρ 1

A Parsimonious 2-break Scenario for a Breakpoint Graph

Finding the size of an MAECD of a graph is NP-hard [START_REF] Bienstock | A degree sequence problem related to network design[END_REF]. However we are interested in a particular family of breakpoint graphs, corresponding to the genome breakpoint graphs, for which the size of an MAECD can be found in linear time and the space of all the possible MAECDs can be explored efficiently.

This subsection should sound familiar to the reader who is aware of the classical results concerning the parsimonious DCJ scenarios sorting the adjacency graph [START_REF] Marília | The solution space of sorting by DCJ[END_REF]. Lemma 14 basically reformulates the statement that odd paths and cycles of the adjacency graph are sorted on their own, while Observation 17 restates that an even length path can be recombined with another even length path or sorted on its own during a parsimonious DCJ scenario.

Definition 34 (Single/multiple vertex

∪ BB 1 , AA 2 ∪ BB 2 } and {C, AA 1 ∪ BB 2 , AA 2 ∪ BB 1 }.

A 2-break Scenario for a Simple Cycle is a 2-break Scenario for a Circle

Introduction

In Section 3.2 we have shown that a parsimonious 2-break scenario for a graph can be partitioned into parsimonious 2-break scenarios for the subgraphs in its Maximum Alternating Edge-disjoint Cycle Decomposition. Due to maximality, these subgraphs themselves have a MAECD of size equal to 1. A graph satisfying this property is a simple cycle, while a circle is a simple cycle with the black and gray degrees of every vertex equal to 1.

In this section we study simple cycles in detail and establish that a 2-break scenario of a simple cycle S corresponds to a 2-break scenario for a circle obtained from an Eulerian orientation of S. This relation will allow us to explore the space of the 2-break scenarios for a simple cycle by exploring the space of the 2-break scenarios for its circles.

The work presented in this section generalizes Proposition 6 from Braga and Stoye [START_REF] Marília | The solution space of sorting by DCJ[END_REF]. There it is stated that there are two options for a parsimonious DCJ scenario ∆ sorting the adjacency graph consisting of an AA and a BB path. Namely, either ∆ sorts the paths separately or corresponds to a DCJ scenario for an adjacency graph obtained by joining the paths into a cycle in one of the two possible ways. See Figure 3.3 for an illustration that these two ways of joining the paths into a cycle can be interpreted as two ways of splitting a simple cycle into a circle.

The Maximum Degree of a Simple Cycle is 2

A simple cycle might have some vertices with black and gray degrees higher than 1.

Here we establish that these degrees cannot be higher than 2.

Lemma 15. The black and gray degrees of a vertex of a simple cycle are at most equal to 2.

Proof. Take a simple cycle S and a vertex v of S. S is Eulerian by definition, thus the black and gray degrees of v are equal, denote them by d. Take an alternating Eulerian tour ∆ of S starting at v, and index the colored edges incident to v based on their order of appearance in ∆. If a loop ({v, v}, col) is present in S, then assign it two indices as in Figure 3.4. This way we obtain a sequence (col 1 , . . . , col 2d ), where col i is the color of the edge indexed with i.

If col 2i-1 = col 2i for 0 < i < d + 1, then a contiguous subsequence of ∆ starting from v with a colored edge indexed 2i -1 and finishing at v with a colored edge b 3 ) depict the circles obtained once its vertex • is split into two vertices • 1 and • 2 . These circles correspond to the cycles depicted in a 2 ) and a 3 ). Proposition 6 from Braga and Stoye [START_REF] Marília | The solution space of sorting by DCJ[END_REF] can be interpreted as stating that a parsimonious 2-break scenario for the simple cycle in b 1 ) corresponds to a parsimonious 2-break scenario for one of the two circles. In this section establish an analogous result for all the simple cycles and the 2-break scenarios that are not necessarily parsimonious.

1 t 1 h 2 t 2 h 3 h 4 h 1 t 1 h 2 t 2 h 4 t 3 t 3 h 3 t 4 t 4 h 1 t 1 h 2 t 2 h 3 h 4 h 1 t 1 h 2 t 2 h 4 t 3 t 3 h 3 t 4 t 4 h 1 t 1 h 2 t 2 h 3 h 4 h 1 t 1 h 2 t 2 h 4 t 3 t 3 h 3 t 4 t 4 h 1 t 2 h 2 t 1 h 3 h 4 t 3 t 4 h 1 t 2 h 2 t 1 h 3 h 4 t 3 t 4 h •1 •2 a 3 ) a 1 ) a 2 ) b 1 ) b 2 ) •1 •1 •2 •2 •2 •2 •1 •1 • 1 t 2 h 2 t 1 h 3 h 4 t 3 t 4 h •1 •2 b 3 )
indexed 2i composes an alternating cycle of S. By definition, the only alternating cycle of S is itself, thus 2i -1 = 1, 2i = 2d and d = 1.

Half of the colors in (col 1 , . . . , col 2d ) are black and the other half are gray. Suppose that d > 1, then we have already proven that col 2i-1 = col 2i for all 0 < i < d + 1. This means that there exists 0 < i < d -1 with col 2i = col 2i+1 . We know that col 2i-1 = col 2i and col 2i+1 = col 2i+2 . This means that the contiguous subsequence of ∆ starting from v with a colored edge indexed 2i -1 and finishing at v with a colored edge indexed 2i + 2 composes an alternating cycle. By definition, the only alternating cycle of S is itself, thus 2i -1 = 1, 2i + 2 = 2d and d = 2. In this case col 2i-1 = col 2i , for all i, however the contiguous subsequence of ∆ starting with the colored edge indexed by 1 and finishing with the colored edge indexed by 4 comprises an alternating cycle.

Splitting a Double Vertex of a Simple Cycle

Definition 38 (Single/double vertex). A vertex of a graph is double if its black and gray degrees are equal to 2, it is single if these degrees are equal to 1.

In the previous section we have established that all the vertices of a simple cycle are either single or double. In this section we replace a double vertex v with two single vertices v 1 and v 2 in a simple cycle S and its 2-break scenario ρ to obtain a 2-break scenario ρ for a simple cycle Ŝ with one less double vertex than S. Once repeated for every double vertex, this process will leave us with a 2-break scenario for a circle of S.

Take a double vertex v of a simple cycle S on vertices V . Replace v in V with vertices v 1 and v 2 to obtain a set of vertices V . Denote by M a function that transforms a graph on vertices V into a graph on vertices V by merging the vertices v 1 and v 2 into v. For a 2-break τ on vertices V , denote by M (τ ) a 2-break on vertices V obtained by replacing the occurrences of v 1 and v 2 with v. For a sequence of 2breaks ρ = ( τ1 , . . . , τm ) on vertices V , denote by M (ρ) = (M ( τ1 ), . . . , M ( τm )) a sequence of 2-breaks on vertices V . See Figure 3.5 for all the possible cases of S and Ŝ such that M ( Ŝ) = S. After inspecting the figure it should be clear that the following observation holds.

Observation 18. There exists a simple cycle Ŝ such that M ( Ŝ) = S and its vertices v 1 and v 2 are single. Suppose that Ŝ1 is not terminal. If S has a black loop incident to v, then take Ŝ2 = Ŝ1 . Otherwise Ŝ1 has 2 black edges incident to v 1 and v 2 , denote them by ({v 1 , u}, black) and ({v 2 , w}, black), with u and w possibly equal. Replace them with ({v 2 , u}, black) and ({v 1 , w}, black) to obtain a simple cycle Ŝ2 . By construction M ( Ŝ2 ) = S. Transform ρ1 by replacing all the occurrences of v 1 in the black 2-breaks of ρ1 with v 2 and vice versa. Denote the newly obtained sequence of 2-breaks by ρ2 . Denote the black edges in Ŝ1 incident to v by ({v 1 , u}, black) and ({v 2 , w}, black). Ŝ2 can be obtained from Ŝ1 by replacing these colored edges with ({v 2 , u}, black) and ({v 1 , w}, black). All the possible cases of S and Ŝ1 are depicted in Figure 3.6.

v v r u w u r v 1 v 2 u w v u w u w v 1 v 2 v v 1 v 2 v c) v 1 v 2 u w v 1 v 2 d) e) f) g) u w u v u w r s r s v 1 v 2 r s v 1 v 2 u w u w h) v u w r s q v u w
After inspecting the figure it should be clear that Ŝ2 is a terminal graph. Thus ρ2 is a 2-break scenario for Ŝ2 .

A 2-break Scenario for a Circle of a Simple Cycle

In this subsection we introduce the notion of a circle of a simple cycle S and show that a 2-break scenario for S corresponds to a 2-break scenario for one of its circles.

Take a simple cycle S on vertices V . All the vertices of S are either single or double due to Lemma 15. For every double vertex v in V , replace it with v 1 and v 2 to obtain a set of vertices V . Denote by M a function that transforms a graph on vertices V into a graph on vertices V by merging the pairs of vertices corresponding to the double vertices of S. For a 2-break τ on vertices V , denote by M (ρ) a 2-break on vertices V obtained by replacing the occurrences of v 1 and v 2 with v for every double vertex of S. For a sequence of 2-breaks ρ = ( τ1 , . . . , τm ) on vertices V , denote by M (ρ) = (M ( τ1 ), . . . , M ( τm )) a sequence of 2-breaks on vertices V .

v v u w v u v 1 v 2 u w v 1 v 2 u w v 1 v 2 a) b) c) u w v 1 v 2 u w v 1 v 2 v 1 v 2 u
Figure 3.6: Take a simple cycle S and a 2-break scenario ρ transforming S into a terminal graph S. There are three possibilities for a subgraph of S induced by the colored edges incident to a double vertex v of S. These are depicted at the top. At the bottom are the possibilities of such induced subgraphs of Ŝ, a graph that is transformed into S once its vertices v 1 and v 2 are merged into v. If Ŝ is not already terminal, then in order to obtain a terminal graph it is enough to swap the endpoints of its black edges incident to v 1 and v 2 . This means that if Ŝ1 in the proof of Lemma 17 is not terminal, then Ŝ2 , obtained by swapping its black edge, is terminal.

Definition 39 (Circle of a simple cycle). A circle C (see Definition 9) on vertices

V is a circle of a simple cycle S if M (C) = S.
By applying Lemma 17 for every double vertex of a simple cycle we establish the following theorem.

Theorem 5. Take a 2-break scenario ρ for a simple cycle S. There exists a circle C of S and its 2-break scenario ρ such that M (ρ) = ρ.

A Link Between the Eulerian Orientations of a Simple Cycle and its Circles

The motivation behind this subsection is to come up with a way to enumerate the circles of a simple cycle S. To this end, we introduce a notion of an Eulerian orientation of an undirected graph and show that an Eulerian orientation -→ S of a simple cycle S has a unique directed alternating Eulerian tour starting at a given vertex. We explain how to transform such a tour into a circle of S, and prove that all the circles of S (up to renaming of the double vertices) can be obtained this way.

Definition 40 (Eulerian orientation of a graph). An Eulerian orientation of an undirected 2-edge-colored graph G is an assignment of a direction to each colored edge of G satisfying that the black indegree (respectively outdegree) is equal to the gray outdegree (respectively indegree) for every vertex v.

See Figure 3.8 for an example of an Eulerian orientation of a simple cycle and a circle. We include the second one into ρ1 . ρ1 transforms Ŝ1 into a graph Ŝ1 that is not terminal, indicating that some of the choices should be modified. S contains a black loop incident to r, thus we choose Ŝ2 = Ŝ1 . In the black 2-breaks of ρ1 we swap the vertices v 1 and v 2 to obtain a 2-break scenario ρ2 for Ŝ2 depicted in c). Denote Ŝ2 by S and ρ2 by ρ . We proceed the same way in d) with a circle Ŝ 1 , that becomes S once the vertices v 1 and v 2 are merged into v. Once again we start by choosing ρ 1 , that does not lead to a terminal graph. To deal with this, we have to swap the black edges of Ŝ 1 incident to v 1 and v 2 and swap v 1 and v 2 in the black 2-breaks of ρ 1 to obtain Ŝ 2 and ρ 2 as depicted in e). u,w,v,r,r,v,u). The colored directed edges of the u-tour of -→ S incident to the second occurrence of v in the vertex sequence of the tour are ((v, u), black) and ((r, v), gray). Rename v to v 2 to obtain ((v 2 , u), black) and ((r, v 2 ), gray). Rename v to v 1 in the rest of the colored directed edges of the tour to obtain ((w, v 1 ), black) and ((v 1 , r), gray). Proceed by renaming r to obtain an Eulerian orientation of a circle of S depicted in d), that provides the u-circle (see Definition 41) of -→ S depicted in e) once its orientation is forgotten. The circles depicted in a) and e) are equivalent, as it suffice to rename the vertices v 1 and v 2 , and r 1 and r 2 in order to transform one circle into another.

v 2 v 1 a) d) r 1 r 2 v u w r 1 r 2 v u w r 1 r 2 v u w r 1 r 2 v u w r 1 r 2 v u w r 1 r 2 v u w r 1 r 2 u w v 2 v 1 r 1 r 2 u w v 2 v 1 r 1 r 2 u w v 2 v 1 r 1 r 2 u w v 2 v 1 r 1 r 2 u w v 2 v 1 r 1

Lemma 18. Take an Eulerian orientation

-→ S of a simple cycle S and its double vertex u. The black in and outdegrees of u in -→ S are equal to 1, and so are its gray in and outdegrees.

Proof. Either the black or the gray outdegree of u must be non-zero and without loss of generality we can suppose that this is the case for the black outdegree. Take a maximum length directed alternating path ∆ starting at u with a black edge. Due to the definition of an Eulerian orientation, this path finishes at u with a gray edge. ∆ is an Eulerian tour of S due to the simplicity of S. u is a double vertex, thus ∆ must have two incoming colored edges to u, and the first one of them must be black, while the second must be gray. This ensures that the black in and outdegrees of u are equal to 1, and so are its gray in and outdegrees. Definition 42 (Equivalent circles of a simple graph). For a simple graph S, a graph isomorphism g : V → V is S-preserving if it maps each single vertex of S to itself, and for each double vertex v of S one has either g(v 1 ) = v 1 and g(v 2 ) = v 2 , or g(v 1 ) = v 2 and g(v 2 ) = v 1 . Two circles of S are equivalent if there exists an S-preserving isomorphism between them.

A Parsimonious 2-break Scenario for a Circle

Introduction

In Section 3.2 we have concisely represented a 2-break scenario with the help of the trajectory graph. Shao, Lin, and Moret [START_REF] Shao | Sorting genomes with rearrangements and segmental duplications through trajectory graphs[END_REF] demonstrated that the trajectory graph D(C, ρ) of a parsimonious 2-break scenario ρ for a circle C is a tree. Here we present the scenario graph S(C, ρ) that can be interpreted as a particular planar embedding of the trajectory graph, and show that it is a quadrangulation of a regular polygon. We use this enriched graphical tool to partition ρ into parsimonious 2-break scenarios for the sub-circles of C in Theorem 8. In Chapter 5 this partition will lead to a dynamic programming algorithm for finding a minimum cost scenario among the parsimonious ones.

We also establish a bijection between the equivalence classes of the parsimonious 2-break scenarios for a circle and the matched quadrangulations of a regular polygon. This work relates to that presented in Section 3 of Dulucq and Penaud [START_REF] Dulucq | Cordes, arbres et permutations[END_REF] and Section IV of Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF]. These papers discuss a bijection between the equivalence classes of the Minimum Length Transposition Decompositions of a cyclic permutation and a family of the spanning planar trees on a circle is established. In Subsection 3.6.4 we combine these results to establish a bijection between the equivalence classes of the MLTDs of a cyclic permutation σ and the equivalence classes of the parsimonious black-2-break scenarios for the permutation breakpoint graph H(σ, id).

The Scenario Graph of a Parsimonious 2-break Scenario for a Circle is Planar

In this subsection we introduce the scenario graph of a parsimonious 2-break scenario for a circle and prove that it is planar.

Definition 46 (Planar graph).

A graph is planar if it admits an embedding. An embedding divides the plane into regions, called faces. One of them is unbounded or infinite, while the rest are bounded. Theorem 7. Take a parsimonious 2-break scenario ρ for a circle C. The scenario graph S(C, ρ) is planar and all the bounded faces of its embedding Σ S(C,ρ) are quadrilaterals. In addition to that, there exists a bijection between the 2-breaks in ρ and the bounded faces of Σ S(C,ρ) , that associates to a 2-break in ρ the face bounded by its edges. [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] and C [START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] are depicted in d) and e). The first 2-break τ in ρ transforms C [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] into a union of two vertex-disjoint circles C 1 and C 5 as depicted in f). ρ can be partitioned into 2-break scenarios ρ [START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] and ρ [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] for the sub-circles C [START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] and C [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] Proof. The proof is by induction on the number of vertices in C. C has an even number of vertices by construction. If C has two vertices, then ρ is empty, its scenario graph has a single edge and no bounded faces. Suppose that the statement is true for every circle having at most 2k -2 ≥ 2 vertices and take a circle C with 2k vertices and its parsimonious 2-break scenario ρ.

Due to Corollary 2, the first 2-break {u, v}, {w, s} → {u, w}, {v, s} , col of ρ transforms C into a union of two vertex disjoint circles. Denote them by C 1 and C 2 . Due to Corollary 4, the rest of ρ can be partitioned into ρ 1 and ρ 2 , that are 2-break scenarios for C 1 and C 2 respectively. The edges of Σ S(C,ρ) can be obtained by adding the edges {u, v} and {w, s} to the union of the edges of S(C 1 , ρ 1 ) and S(C 2 , ρ 2 ). Σ S(C 1 ,ρ 1 ) and Σ S(C 2 ,ρ 2 ) satisfy the inductive hypothesis, thus their edges do not cross. {u, v} and {w, s} do not cross the other edges and together with {u, w} and {v, s} bound the only face of Σ S(C,ρ) not belonging to Σ S(C 1 ,ρ 1 ) or Σ S(C 2 ,ρ 2 ) . See Figure 3.10 for an illustration of the links between the scenario and the trajectory graphs.

Partitioning a Parsimonious 2-break Scenario for a Circle into the Scenarios for its Sub-circles

In this section we introduce a notion of a sub-circle of a circle and demonstrate that a parsimonious 2-break scenario for a circle can be partitioned into parsimonious 2-break scenarios for its sub-circles.

Definition 47 (Sub-circle). Take an odd length path in a circle. If the edges incident to its endpoints are black (respectively gray), then join its endpoints with a gray (respectively black) edge to obtain a circle. The added colored edge is the colored outer edge of the sub-circle.

Fix a circular straight-line embedding Σ C of a circle C on n vertices. Number them 1, n while respecting their clockwise order on Σ C and ensuring that the colored edge going clockwise from n to 1 is gray. For i, j ∈ 1, n with i and j of different parity, define C[i, j] to be the sub-circle of C consisting of the path going clockwise from i to j in Σ C and the colored outer edge. By construction, it is ({i, j}, gray) if i is odd and ({i, j}, black) otherwise. Denote this color by col {i,j} , and the opposite color by col {i,j} .

Lemma 19. Take a parsimonious 2-break scenario ρ for a circle C and an edge {i, j} of its scenario graph. ρ can be partitioned into parsimonious 2-break scenarios for C[i, j] and C[j, i].

Proof. The proof is by induction of the number of vertices in C. See Due to Theorem 7, the scenario graph of ρ inherits from Σ C a circular straightline embedding in which all the bounded faces are quadrilaterals. The edges of τ and the edge {i, j} all belong to the scenario graph of ρ. This means that i and j belong either to C 1 or C 2 , without loss of generality we can suppose that it is C 2 . This also means that all the vertices of τ belong either to C[i, j] or C [j, i]. Without loss of generality we can suppose that it is C[j, i].

The inductive hypothesis holds for the triplet (C 2 , ρ 2 , {i, j}), providing us with a partition of ρ 2 into two parsimonious 2-break scenarios for the sub-circles of (C 2 , λ 2 ) having ({i, j}, black) and ({i, j}, gray) as the colored outer edges. By construction, one of these labeled sub-circles is C[i, j]. Denote the other one by C 5 , and denote the parsimonious 2-break scenarios obtained for them by ρ [i,j] and ρ 5 respectively. By now we have established that ρ is a shuffle of τ , ρ 1 , ρ [i,j] , and ρ 5 . Remove ρ [i,j] and τ from ρ to obtain a shuffle of ρ 1 and ρ 5 , that we denote by ρ. Due to Observation 15, ρ is a parsimonious 2-break scenario for the union of the vertexdisjoint circles C 1 and C 5 , which is also the graph obtained from C[j, i] after τ is performed. Finally, by deleting only ρ [i,j] from ρ, we obtain a shuffle of τ and ρ, that is a parsimonious 2-break scenario for C[j, i], that together with ρ [i,j] satisfies the statement.

Definition 48 (Matched scenario for a sub-circle). A parsimonious 2-break scenario for a sub-circle C[i, j] is matched, if its scenario matching includes the edge {i, j}.

It is non-matched otherwise. Theorem 8. Take a matched parsimonious 2-break scenario ρ for C[i, j] with i+3 ≤ j. ρ can be partitioned into a 2-break τ = {i, k}, {l, j} → {i, j}, {k, l} , col {i,j} with i < k < l < j, a parsimonious [START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF]

-break scenario for C[k, l] and matched parsimonious 2-break scenarios for C[i, k] and C[l, j].

Proof. The scenario graph S(C, ρ) inherits its embedding Σ S(C,ρ) from Σ C . An edge {i, j} is incident to a single bounded face of the embedding Σ S(C,ρ) , thus due to Theorem 7 there exists a single 2-break τ in ρ with {i, j} among its edges. τ introduces a colored edge ({i, j}, col {i,j} ), since ρ is matched. This means that there exist i < k < l < j such that τ = {i, k}, {l, j} → {i, j}, {k, l} , col {i,j} . The scenario graph of ρ contains the edges {i, j}, {i, k}, {k, l}, {l, j} of τ . Applying Lemma 19 for {i, k}, {k, l} and {l, j}, we obtain parsimonious 2-break scenarios ρ 1 , ρ 2 , and ρ 3 for the sub-circles C[i, k], C[k, l] and C[l, j] that together with τ partition ρ. All we have to prove now is that ρ 1 and ρ 3 are matched.

If k = i + 1, then C[i, k] has two vertices and ρ 1 is matched by definition. Thus we can suppose that i + 3 ≤ k, which means that ({i, k}, col {i,j} ) is not present in C[i, j]. τ replaces this colored edge, thus due to Observation 1 ρ also contains a 2-break introducing this edge. Due to Theorem 7 there are only two 2-breaks in ρ with {i, k} among their edges. Due to the same theorem ρ 1 contains a 2-break with {i, k} among its edges. By construction τ is not in ρ 1 , thus we can conclude that ρ 1 contains a 2-break introducing ({i, k}, col {i,j} ), which means that ρ 1 is matched. The same analysis applies to ρ 3 .

Analogous arguments to those presented in proof of Theorem 8 allow us to prove the following. Theorem 9. Take a non-matched parsimonious 2-break scenario ρ for C[i, j] with i + 3 ≤ j. ρ contains a 2-break τ = {i, j}, {k, l} → {i, k}, {l, j} , col {i,j} with i < k < l < j, and ρ can be partitioned into τ , parsimonious 2-break scenarios for

C[i, k] and C[l, j], and a parsimonious matched 2-break scenario for C[k, l].

These two theorems allow us to partition a parsimonious 2-break scenario for a sub-circle of C into parsimonious 2-break scenarios for smaller sub-circles of C.

A Bijection Between the Equivalence Classes of the Parsimonious 2-break Scenarios for a

Circle and its Matched Quadrangulations

Introduction

In Theorem 7 we have established that the scenario graph of a parsimonious 2-break scenario for a circle is a quadrangulation of a regular polygon. We define 2-break scenarios to be equivalent if their multisets of 2-breaks are equal and establish a bijection between the equivalence classes of the parsimonious 2-break scenarios for a circle and the matched quadrangulations of a regular polygon. Proof. The proof is by induction on the number of vertices in a circle C. If it has two vertices, then its parsimonious 2-break scenario is empty and the statement is true. Suppose that the statement is true for every circle with at most 2k -2 ≥ 2 vertices and take a circle C on 2k vertices together with its parsimonious 2-break scenarios ρ 1 and ρ 2 .

The Scenario Graphs and Matchings of Equivalent Scenarios are Equal

First suppose that ρ 1 and ρ 2 are equivalent. This means that they contain exactly the same 2-breaks but possibly in different order. By definition, the edges of Σ S(C,ρ 1 ) are the edges of the 2-breaks in ρ 1 , and these are exactly the same as the edges of the 2-breaks in ρ 2 , meaning that Σ S(C,ρ 1 ) = Σ S(C,ρ 2 ) . Due to Lemma 20, the terminal graphs provided by ρ 1 and ρ 2 are equal. This means that their scenario matchings are also equal. Now suppose that the scenario graphs and the scenario matchings of ρ 1 and ρ 2 are equal. Take the first 2-break τ 1 of ρ 1 . Without loss of generality we can suppose that τ 1 does not replace ({1, n}, gray). In this case there exists i < j and a color col, such that τ 1 = {i, i + 1}, {j, j + 1} → {i, j + 1}, {i + 1, j} , col . As ({i, i + 1}, col) is an edge of C, there is a single bounded face of Σ S(C,ρ 1 ) incident to {i, i + 1}. Due to Theorem 7, τ 1 is the single 2-break in ρ 1 with {i, i + 1} among its edges. This means that {i, i + 1} is not in the scenario matching of ρ 1 and thus neither in that of ρ 2 .

Due to Theorem 7, there exists a face in Σ S(C,ρ 1 ) bounded by the edges of τ 1 . Σ S(C,ρ 1 ) = Σ S(C,ρ 2 ) , thus the latter contains the same face that we denote by f . Due to Theorem 7, ρ 2 contains a 2-break τ 2 with the edges of τ 2 bounding f , and τ 2 being the single 2-break in ρ 2 with {i, i + 1} among its edges. {i, i + 1} is not present in the scenario matching of ρ 2 , and the colored edge ({i, i + 1}, col) is present in C, thus τ 2 must replace this colored edge, meaning that τ 2 = τ 1 , denote them by τ .

Due to Lemma 21, τ can be moved to the beginning of ρ 2 to obtain an equivalent parsimonious 2-break scenario ρ 3 . Due to Corollary 2, τ transforms C into a union of vertex disjoint circles, denote them by C 1 and C 2 . Due to Corollary 4, the rest of ρ 1 (respectively ρ 3 ) can be partitioned into two sub-sequences ρ 1 1 and ρ 1 2 (respectively ρ 3 1 and ρ 3 2 ) that are parsimonious 2-break scenarios for C 1 and C 2 . The scenario graphs and matchings of ρ 1 1 and ρ 3 1 are equal, and so are those of ρ 1 2 and ρ 3 2 . Thus ρ 1 1 and ρ 3 1 are equivalent, due to the induction hypothesis, and so are ρ 1 2 and ρ 3 2 . This allows us to conclude that ρ 1 and ρ 3 are equivalent, and thus are ρ 1 and ρ 2 .

Corollary 6. Due to Observation 19, the scenario matchings of two parsimonious black-2-break scenarios are equal by construction, thus they are equivalent if and only

if their scenario graphs are equal. Proof. The proof is by induction on the number of vertices in C. If C has 2 vertices, then the empty scenario satisfies the statement. Suppose that the statement is true for every circle having at most 2k -2 ≥ 2 vertices and take a circle on 2k vertices.

A Matched Quadrangulation

Due to Theorem 7 and Theorem 1, Σ S has k -1 bounded face. On the other hand, Σ S has k edges of the form {i, i + 1} that are black in C, and such an edge is incident to at most one bounded face of Σ S . This way we obtain that Σ S contains a pair of edges that are black in C incident to the same bounded face f . Denote these black edges by ({i, i + 1}, black) and ({j, j + 1}, black) with i < j.

All the edges in Σ S , except {i, i + 1} and {j, j + 1}, are incident to an even number of vertices of C[i + 1, j], which itself has an even number of vertices. Thus either both {i, i + 1} and {j, j + 1} are in M, or both are not in M.

Denote the subgraphs of Σ S induced by the vertices of C[i+1, j] and C[j +1, i] by Σ S 1 and Σ S 2 respectively. Denote by M 1 (respectively M 2 ) a subset of M consisting of the edges with both ends in

C[i + 1, j] (respectively C[j + 1, i]).
Suppose that {i, i + 1} and {j, j + 1} are not in M. In this case M 1 and M 2 partition M and are the matchings of Σ S 1 and Σ S 2 . Due to the induction hypothesis, there exist parsimonious 2-break scenarios ρ 1 and ρ 2 for C[i + 1, j] and C[j + 1, i] satisfying the statement of the theorem. A 2-break {i, i + 1}, {j, j + 1} → {i, j +1}, {i+1, j} , black followed by ρ 1 and ρ 2 is a parsimonious 2-break scenario for C satisfying the statement of the theorem.

Suppose that {i, i + 1} and {j, j + 1} are in M. In this case the vertices i + 1 and j are not incident to any edges in M 1 and the vertices j + 1 and i are not incident to any edges in M 2 . Add {i + 1, j} to M 1 and {j + 1, i} to M 2 to obtain the matchings M 1 of Σ S 1 and M 2 of Σ S 2 . Due to the induction hypothesis, there exist parsimonious 2-break scenarios ρ 1 and ρ 2 for C[i + 1, j] and C[j + 1, i], satisfying the statement of the theorem. ρ 1 and ρ 2 followed by a 2-break {i, j + 1}, {i + 1, j} → {i, i + 1}, {j, j + 1} , gray is a parsimonious 2-break scenario for C satisfying the statement of the theorem.

Corollary 7. Take a quadrangulation of a regular polygon Σ S and its matching M g containing the edges that are gray in C. There exists a parsimonious black-2-break scenario ρ for which Σ S(C,ρ) = Σ S and M(C, ρ) = M g .

A Bijection Between the Equivalence Classes of the Parsimonious 2-break Scenarios and the Equivalence Classes of the MLTDs

In Section 2.4 we have established a bijection between the parsimonious black-2break scenarios for the permutation breakpoint graph H(σ, id) and the MLTDs of σ. Here we use some classical results concerning the equivalence classes of the MLTDs of a cyclic permutation σ to establish a bijection between them and the equivalence classes of the parsimonious black-2-break scenarios for H(σ, id). Using Lemma 22 we obtain a function F that assigns an equivalence class of the MLTDs to an equivalence class of the parsimonious black-2-break scenarios. The way that we assign a parsimonious black-2-break scenario for H(σ, id) to a given MLTD of σ in Lemma 8 relies on the order of transpositions in the MLTD, thus it is not immediately clear if F is a bijection. To prove this, we have to use the machinery introduced by Dulucq and Penaud [START_REF] Dulucq | Cordes, arbres et permutations[END_REF] and later used by Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF].

Definition 52 (Equivalent transposition decompositions).

Definition 53 (The graph of an MLTD). For a permutation σ ∈ S n and its MLTD T define a 1-edge-colored graph T (T ) = (V, E), with V = {1, . . . , n} and E = {{i, j}|(i, j) ∈ T }).

Definition 54 (Planar graph on a circle). Embed vertices {1, . . . , n} on a circle while respecting their order. If a straight line drawing of a graph T on these vertices is an embedding, then T is a planar graph on a circle. See Figure 3.12 d) and e) for an example of a planar spanning tree on a circle.

Theorem 12 (Dulucq and Penaud [38], Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF]). Take an MLTD T of a cyclic permutation σ ∈ S n . T (T ) is a planar spanning tree on a circle. Now, take a planar spanning tree T on a circle. There exists an MLTD T of σ satisfying T (T ) = T . There are 1 2n+1 3n n planar spanning trees on a circle with n + 1 vertices, thus this is also the number of the equivalence classes of the MLTDs of a cyclic permutation of n + 1 elements.

A sequence with values 1 2n+1 3n n is called the Fuss-Catalan sequence. As Catalan numbers count the number of triangulations of a regular polygon, so the Fuss-Catalan numbers count the number of quadrangulations of a regular polygon.

Lemma 23 (Baryshnikov [8]). The number of quadrangulations of a regular polygon on 2n + 2 vertices is equal to 1 2n+1 3n n .

Corollary 6 and Corollary 7 allow us to conclude with a following lemma.

Lemma 24. The number of equivalence classes of the black-2-break scenarios for a circle on 2n vertices is equal to the number of quadrangulations of a regular polygon on 2n vertices.

Due to Theorem 12, Lemma 23 and Lemma 24, there is an equal number of the equivalence classes of MLTDs of a cyclic permeation σ and the equivalence classes of the parsimonious black-2-break scenarios for the permutation breakpoint graph H(σ, id). Apostolakis in Section 3.3 of [START_REF] Apostolakis | Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections[END_REF] presents a bijection between the quadrangulations, that he calls quadrangular dissections, and the planar spanning trees on a circle, that he calls non-crossing trees. The construction provided in [START_REF] Apostolakis | Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections[END_REF] and presented in Figure 3.12 establishes that F is indeed a bijection between these equivalence classes.

Conclusion

We have shown that a parsimonious 2-break scenario for a graph can be partitioned into parsimonious 2-break scenarios for the circles of its simple cycles. Theorem 8 allows us to partition a parsimonious 2-break scenario for a circle into parsimonious 2-break scenarios for its sub-circles. In Chapter 5 this will lead to a dynamic programming algorithm for exploring the space of the parsimonious 2-break scenarios for a circle. Taken together these results allow us to explore the space of the parsimonious 2-break scenarios for any graph. Figure 3.12: A black-2-break scenario ρ for the permutation breakpoint graph H((12345), id) is depicted in a), while its scenario graph is presented in b). Using Lemma 8, ρ provides us with a Minimum Length Transposition Decomposition T = (( 45), ( 23), ( 15), ( 13)) of (12345). (( 23), ( 45), ( 15), [START_REF] Bergeron | A very elementary presentation of the Hannenhalli-Pevzner theory[END_REF]) is an equivalent MLTD to T . Graphically the transpositions of T can be interpreted as the diagonals of the bounded faces of the scenario graph joining the tail vertices, as depicted in c). These diagonals correspond to a planar spanning tree on a circle T (T ) given in d). T , another planar spanning tree on a circle, is depicted in e). We provide in i) a quadrangulation of a regular polygon corresponding to an equivalence class E of the parsimonious black-2-break scenarios for H((12345), id), for which F (E) is the equivalence class of the MLTDs of σ corresponding to T . T partitions a circle into 5 regions and each region corresponds to an arc of the circle. To each arc/region assign a head vertex as depicted in f). Add a gray edge between the head vertices if their corresponding regions are separated by an edge of T . The obtained graph κ(T ) is called the complement of T in [START_REF] Apostolakis | Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections[END_REF]. Each edge of T intersects exactly one edge of κ(T ) and vice versa, the pairs of the intersecting edges correspond to the diagonals of the quadrilaterals depicted in h) and i).

and that we could incorporate the edge label changes proposed by Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF].

In a seemingly different line of work Farnoud and Milenkovic [41] allowed for an arbitrary positive real valued cost function on transpositions and defined the cost of a transposition decomposition of a permutation to be the sum of the costs of its transpositions. The authors proposed an O(n 4 )-time algorithm for finding a minimum cost decomposition among the Minimum Length Transposition Decompositions of a permutation σ ∈ S n .

These three lines of work converged into a framework for cost constrained 2breaks outlined in Section 4.2 and first presented by us in [START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF]. The rest of the chapter consists of novel but rather technical work aimed to better understand the structure of the minimum cost scenarios.

An O-scenario

In this section we augment a graph with labels on both vertices and edges, and introduce an O-scenario transforming one labeled graph into another. The labeled edges can be modified either via an O-change, that changes the label of a single edge, or via an O-break, that is a 2-break acting not only on the connectivity of the edges but also on their labels. The labels of the vertices stay fixed throughout an O-scenario, however they are used to define which O-changes and O-breaks are allowed to transform a labeled graph. Take alphabets of vertex and edge labels Σ V and Σ E . We will use letters {u, v, w, s, r} to denote vertices, {a, b, c, d} to denote vertex labels and {x, y, z, t, q} to denote edge labels. We start by introducing a set of valid operations O.

Definition 55 (Valid operations O). A valid set of operations O is a subset of tuples

• ({a, b}, x); ({a, b}, y); col (called edge-label change), and

•

({a, b}, x), ({c, d}, y) ; ({a, c}, z), ({b, d}, t) ; col (called 2-break on labels)

for a, b, c, d ∈ Σ V , x, y, z, t ∈ Σ E , and col ∈ {gray,black}.

Having O defined on the labels of the vertices and not on the graph vertices themselves allows us to use it for any labeled graph. An O-break ({u, v}, x), ({w, s}, y) → ({u, w}, z), ({v, s}, t) , col can also be denoted by a pair of a 2-break τ = {u, v}, {w, s} → {u, w}, {v, s} , col , and a labeling χ of its colored edges. We will allow ourselves to write (τ, χ) = ({u, v}, x), ({w, s}, y) → ({u, w}, z), ({v, s}, t) , col for these different notations. In what follows, the scenario graph and the scenario matching (see Definition 43 and Definition 44) of a parsimonious O-scenario for a circle will mean the scenario graph and the scenario matching of its underlying 2-break scenario.

Definition 56 (Labeled graph). A labeled graph is a pair of a graph G = (V, E) and its labeling

λ = (λ V , λ E ) with λ V : V → Σ V and λ E : E → Σ E .

The ϕ-cost of an O-scenario

Optimization Problems

For an arbitrary cost function ϕ on a set of valid operations O we introduce a couple of families of optimization problems for the O-scenarios.

Definition 62 (The ϕ-cost of an O-scenario). Take a cost function ϕ : O → R + . The ϕ-cost ϕ(ρ) of an O-scenario ρ is the sum of the ϕ-costs of its constituent operations.

Definition 63 (The MCS ϕ -cost of a labeled graph). The MCS ϕ -cost of a labeled graph (G, λ), denoted by MCS ϕ (G, λ), is the minimum ϕ-cost of an O-scenario for (G, λ), if such an O-scenario exists, and ∞ otherwise. A ϕ-MCS O-scenario is an O-scenario with ϕ-cost equal to MCS ϕ (G, λ). Definition 64 (The MCPS ϕ -cost of a labeled graph). The MCPS ϕ -cost of a labeled graph (G, λ), denoted by MCPS ϕ (G, λ), is the minimum ϕ-cost of a parsimonious O-scenario for (G, λ), if such an O-scenario exists, and ∞ otherwise. A ϕ-MCPS O-scenario is a parsimonious O-scenario with ϕ-cost equal to MCPS ϕ (G, λ). Problem 9 (ϕ-Minimum Cost Scenario or ϕ-MCS). INPUT : A labeled graph (G, λ). OUTPUT : MCS ϕ (G, λ).

Problem 10 (Minimum Cost Scenario or MCS).

INPUT :A pair (O, ϕ) and a labeled graph (G, λ). OUTPUT : MCS ϕ (G, λ).

Problem 11 (ϕ-Minimum Cost Parsimonious Scenario or ϕ-MCPS).

INPUT : A labeled graph (G, λ). OUTPUT : MCPS ϕ (G, λ).

Problem 12 (Minimum Cost Parsimonious Scenario or MCPS).

INPUT :A pair (O, ϕ) and a labeled graph (G, λ). OUTPUT : MCPS ϕ (G, λ).

As we outline in the following subsection, some particular cases of ϕ-MCPS and ϕ-MCS have already been addressed in the literature. The MCS problem is more pertinent for the study of genome rearrangements, as the real evolutionary scenarios might be non-parsimonious, however it is also much more difficult to approach than the MCPS problem. Not only have we shown MCS to be NP-complete even for fairly simple cost functions, but there is a general lack of tools for working with non-parsimonious 2-break scenarios. This is why we first treat MCPS, which also serves as an upper bound for MCS. The results established in Chapter 3 concerning the parsimonious 2-break scenarios will lead to a polynomial time algorithm for the MCPS problem for a labeled circle and a labeled breakpoint graph in Chapter 5.

ϕ-MCPS and ϕ-MCS in the Literature

Minimum Local Parsimonious Scenario

In [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] we supposed the adjacencies of a genome A to be partitioned into spatial regions represented by different colors. We then developed a polynomial time algorithm for finding a parsimonious DCJ scenario minimizing the number of rearrangements whose breakpoints appear in different regions. The problem, as stated in [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF], differs slightly from ϕ-MCPS, since in that study we do not have colors for the adjacencies of genome B. We can bridge this gap as follows.

There is a single vertex label a, while edge labels Σ E = Σ c ∪{t} are the colors representing the different spatial regions of a genome plus an additional terminal label t. O contains 2-breaks on labels ({a, a}, x), ({a, a}, y); ({a, a}, x), ({a, a}, y); black for x, y ∈ Σ c , and edge-label changes ({a, a}, x); ({a, a}, t); black for x ∈ Σ c . The ϕ c -cost of a 2-break on labels in O is 0 if the labels of the edge are equal and 1 otherwise. The ϕ c -cost of an edge-label change is 0.

In [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] we presented an O(n 3 ) time algorithm for the ϕ c -MCPS problem on a labeled circle with the gray edges labeled with t, while in [START_REF] Simonaitis | Finding local genome rearrangements[END_REF] we established that the ϕ c -MCS problem is NP-hard. In the same paper we proposed an algorithm for the ϕ c -MCS problem on a breakpoint graph that is exponential in the number of colors and not in the number of vertices. In [START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF] we used the same O and an arbitrary symmetric function Φ : Σ 2 E → R + , for which we defined ϕ f ({a, a}, x), ({a, a}, y); ({a, a}, x), ({a, a}, y); black = Φ(x, y). This drastically enhanced the model introduced in [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] as now a rearrangement whose breakpoints appear in the same region could have non-zero cost. In [START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF] we described an O(n 4 ) time algorithm solving ϕ f -MCPS on a labeled circle on n vertices.

Sorting by wDCJs and Indels in Intergenes

Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] introduced a problem where genome adjacencies are labeled with their genetic length (number of nucleotides). A wDCJ is a DCJ that preserves the sum of the genetic lengths of the adjacencies and an indel δ increases or decreases the genetic length of an adjacency by δ. The cost of a wDCJ is 0 and the cost of an indel δ is |δ|. A scenario of wDCJs and indels for (G, λ) is said to be valid if its wDCJ-length is d 2b (G). The paper treats a problem of finding a minimum cost scenario among the valid ones and presents an O(n log n) algorithm for co-tailed single-copy genomes with n genes.

Translating this into our formalism yields the following ϕ-MCPS problem. Edge labels are the natural numbers and there is a single vertex label that we denote by a. O contains 2-breaks on labels ({a, a}, w 1 ), ({a, a}, w 2 ); ({a, a}, w 3 ), ({a, a}, w 4 ); col with w i ∈ N satisfying w 1 + w 2 = w 3 + w 4 . O also contains edge-label changes ({a, a}, w 1 ); ({a, a}, w 2 ); col with w i ∈ N.

For this O we have that d Ob (G, λ) = d 2b (G) for any labeled graph (G, λ), since G can be first transformed into a terminal graph using any parsimonious O-scenario and then its labels can be adjusted. The ϕ l -cost of a 2-break on labels is 0 and the ϕ l -cost of an edge-label change ({a, a}, w 1 ); ({a, a}, w 2 ); black is |w 1 -w 2 |.

For ϕ l -MCPS Bulteau, Fertin, and Tannier presented an O(r log r) time algorithm on a labeled circle with r vertices. Combining this algorithm with our results from Section 5.5 provides a polynomial time algorithm for ϕ l -MCPS on a labeled breakpoint graph, while the ILP defined in Section 5.2 solves ϕ l -MCPS on any labeled graph.

wDCJ-dist

Fertin, Jean, and Tannier [START_REF] Fertin | Algorithms for computing the double cut and join distance on both gene order and intergenic sizes[END_REF] treated a problem wDCJ-dist where wDCJs without indels are allowed, and the sums of the genetic lengths of the adjacencies of two genomes are equal.

In this case we keep the same Σ E , Σ V and O as in Example 4.3.2 except that the edge-label changes are excluded from O. A labeled graph is said to be balanced if the sums of the labels of black and gray edges are equal. wDCJ-dist is the problem of finding d Ob (G, λ) for a balanced labeled circular graph. The authors showed that wDCJ-dist is strongly NP-complete. However, they also proved that d Ob (G, λ) = d 2b (G) for a balanced labeled circular graph whose connected components are balanced labeled circles.

Rearrangement Scenarios that Preserve Common Intervals

Another biological constraint that has been studied for genome rearrangements is that of conserved gene clusters, or preserved common intervals [START_REF] Heber | Algorithms for finding gene clusters[END_REF][START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF][START_REF] Hartmann | An exact algorithm for sorting by weighted preserving genome rearrangements[END_REF]]. An interval or gene cluster of a genome is a set of consecutive genes on one of its chromosomes. Gene clusters shared between genomes, also known as common intervals, were observed to contain functionally associated proteins [START_REF] Tamames | Conserved clusters of functionally related genes in two bacterial genomes[END_REF]. This moti-vated a search for rearrangement scenarios that preserve common intervals. Bérard, Chateau, Chauve, Paul, and Tannier [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF] studied the problem of finding such a preserving DCJ scenario of the minimum length. In this subsection we introduce the F-perfect DCJ problem treated in [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF], and explain why it cannot be immediately interpreted as a ϕ-MCPS problem. We then propose a modification of F-perfect DCJ that resolves this conflict. At this point our goal is to demonstrate the versatility of our method, thus further studies should be undertaken to see how these variants of F-perfect DCJ compare to each other. Take a subset of genes I. An adjacency is a border adjacency of I if exactly one of its gene extremities is an extremity of a gene in I. An interval of a genome, by definition, has zero or two border adjacencies. Take a genome with at most two border adjacencies of I. A DCJ transforming this genome preserves I if the resulting genome also contains at most two border adjacencies of I. According to this definition a preserving DCJ might excise a circular chromosome out of an interval I thus leading to a situation where I is no longer a single interval in the obtained genome. Two sets overlap if their intersection is non-empty and properly included in both of the sets. A family F of sets is nested, if no two sets in F overlap. Take two single-copy genomes A and B having n genes together with a family F of common intervals. A DCJ scenario transforming A into B is F-perfect if its DCJs preserve the intervals in F. The authors in [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF] pose the F-perfect DCJ problem of finding a minimum length F-perfect DCJ scenario. They not only establish that the F-perfect DCJ problem is NP-hard in general, but also show that it can be solved in O(n 2 ) time for a nested F. In this case the minimum length of a F-perfect DCJ scenario is actually equal to d aDCJ (A, B). Take a DCJ δ = {a, b}, {c, d} → {a, c}, {b, d} and an interval I of a genome A. If the number of border adjacencies among {a, b}, {c, d} and {a, c}, {b, d} is equal, then δ is preserving. However if these numbers are not equal, then from δ and I alone we cannot decide whether it is preserving or not, as this now depends on A too. As a workaround we define a DCJ to strongly preserve a subset of genes if the resulting genome preserves the number of border adjacencies. Now no information on A is necessary to decide whether a DCJ is strongly preserving for I or not. Define a common interval for two genomes to be strongly common if its number of border adjacencies in both genomes is equal. If the genomes contain only linear chromosomes, which is the case for most of eukaryotic genomes, then their common interval is necessarily strongly common as it contains exactly two border adjacencies in both genomes. Take a family F of strongly common intervals of A and B. A DCJ scenario is strongly F-perfect if its DCJs are strongly preserving for the intervals in F. We pose the strictly F-perfect DCJ problem of finding a minimum length strongly F-perfect DCJ scenario transforming A into B.

Take two single-copy genomes A and B with genes {1, . . . , n} and a family F of their strongly common intervals. Take a single edge label t and vertex labels Σ V = {1 t , . . . , n t } ∪ {1 h , . . . , n h }. Construct O containing every 2-break on labels ({a, b}, t), ({c, d}, t); ({a, c}, t), ({b, d}, t); black with a, b, c, d ∈ E V . Its ϕ p -cost is 0 if the number of border adjacencies in {a, b}, {c, d} and {a, c}, {b, d} is equal for every strongly common interval in F, it is 1 otherwise. Label the colored edges of the genome breakpoint graph G(A, B) with t and its vertices with themselves to obtain a labeled graph (G(A, B), λ). MCPS ϕp (G(A, B), λ) provides us with the minimum number of non-strongly preserving DCJs in a DCJ scenario of length d aDCJ (A, B).

Using the algorithm presented in Chapter 5 we can compute it in O(n 4 ) time.

This approach allows for a great flexibility as we can choose arbitrary costs for 2-breaks on labels. For example, define breaking costs for the intervals in F and define the cost of a 2-break on labels to be the sum of the breaking costs of all the intervals that it breaks. A ϕ-MCPS problem thus defined allows us to find a DCJ scenario of length d aDCJ (A, B) that best preserves a family of common intervals in O(n 4 ) time.

Cost Constrained Transposition Decompositions of a Permutation

Farnoud and Milenkovic [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF] fixed an arbitrary cost function ϕ on transpositions and defined the cost of a transposition decomposition of a permutation to be the sum of the costs of its transpositions. They proposed an O(n 4 ) time algorithm for the problem of finding a minimum cost decomposition among the Minimum Length Transposition Decompositions of a permutation σ ∈ S n , the MINcost-MLTD problem. The MIN-cost-TD problem was also discussed. Farnoud and Milenkovic showed that for an arbitrary cost function MIN-cost-MLTD is a 4-approximation of MIN-cost-TD. In addition to that, Farnoud, Milenkovic, Puleo, and Su [START_REF] Farnoud | Computing similarity distances between rankings[END_REF] conjectured that there exists a MIN-cost-TD of length O(n 2 ).

There is a single edge label x, while vertex labels are Σ V = V t ∪ V h , with V t = {1 t , . . . , n t } and V h = {1 h , . . . , n h }. O consists of the 2-breaks on labels of the form (({u h , v t }, x), ({w h , s t }, x); ({u h , s t }, x), ({w h , v t }, x); black , where every edge is incident to a tail and a head vertex. The ϕ t -cost of such a 2-break on labels is equal to ϕ(v, s).

Due to Lemma 8, an instance of the MIN-cost-MLTD problem for a permutation σ can be interpreted as an instance of the ϕ t -MCPS problem for its permutation breakpoint graph H(σ, id) with every edge labeled x and every vertex labeled with itself. Analogously an instance of the MIN-cost-TD problem can be interpreted as an instance of the ϕ t -MCS problem. This way the work on MIN-cost-TD [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF][START_REF] Farnoud | Computing similarity distances between rankings[END_REF] can guide further work on ϕ-MCS, and our results on ϕ-MCPS can be used to generalize those on MIN-cost-MLTD.

Token Swapping and Interchange Rearrangement Problem

We invite the reader to revisit Section 2.7 for more examples of the problems that can be interpreted as ϕ-MCPS or ϕ-MCS.

Change-first O-scenario

In order to solve the MCPS problem we have to search the space of the parsimonious O-scenarios. An O-scenario, as defined in Section 4.2, might contain any number of O-changes, thus the search space might be prohibitively large.

Among the problems discussed in Subsection 4.3.2 only Sorting by wDCJs and Indels in Intergenes [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] (or ϕ l -MCPS in our notation) allowed for Ochanges. The authors established that there exists an MCPS ϕ l scenario consisting of a sequence of O-breaks followed by a sequence of O-changes. This observation drastically reduced the search space. Along the same lines, we introduce a notion of a change-first O-scenario. It is an O-scenario that starts with some O-changes on the labeled edges of a labeled graph and then proceeds with O-breaks without any more O-changes. We would like to explore the space of the change-first Oscenarios and not that of all the O-scenarios. To this end we introduce a notion of a complete pair (O, ϕ), and show that in this setting for every labeled graph there exists a change-first MCPS ϕ O-scenario. In the following section we demonstrate that every pair (O, ϕ) can be transformed into a complete one in polynomial time, which allows us to concentrate solely on the change-first O-scenarios in Chapter 5.

Definition 65 (Complete (O,ϕ)). A pair (O, ϕ) is complete if the following properties hold.

1. If O contains a pair of edge-label changes γ 0 = ({a, b}, x 0 ); ({a, b}, x 1 ); col and γ 1 = ({a, b}, x 1 ); ({a, b}, x 2 ); col , then O also contains an edge-label change γ 2 = ({a, b}, x 0 ); ({a, b}, x 2 ); col , and ϕ(γ 2 ) ≤ ϕ(γ 0 ) + ϕ(γ 1 ).

If

O contains π 0 = ({a, b}, x), ({c, d}, y) ; ({a, c}, z), ({b, d}, t) ; col , γ 0 = ({a, c}, z); ({a, c}, z ); col and γ 1 = ({b, d}, t); ({b, d}, t ); col , then O also contains π 1 = ({a, b}, x), ({c, d}, y) ; ({a, c}, z ), ({b, d}, t ) ; col , for which ϕ(π 1 ) ≤ ϕ(π 0 ) + ϕ(γ 0 ) + ϕ(γ 1 ). In this figure we provide an example of a pair (O, ϕ) and its completion (O c , ϕ c ). For this we use a single vertex label a and edge labels {x, y, z, t, q, qt, xyz, xyztq}. The figure itself depicts 1-edge-colored directed multigraphs W black {a,a} and W gray {a,a} introduced in Lemma 26 whose directed edges define the edge-label changes in O as follows. An edge-label change γ 1 = ({a, a}, x); ({a, a}, y); black is in O, as a directed edge (x, y) is in W black {a,a} , and γ 2 = ({a, a}, x); ({a, a}, q); black is not in O, as W black {a,a}

Definition 66 (Change-first O-scenario). An O-scenario for a labeled graph (G, λ) is change-first if it is a sequence of O-
does not contain a directed edge (x, q). O contains the 2-breaks on labels involving a single edge label. For example a 2-break on labels π 1 = ({a, a}, x), ({a, a}, x) ; ({a, a}, x), ({a, a}, x) ; black is in O, as it involves a single edge label x, and π 2 = ({a, a}, x), ({a, a}, x) ; ({a, a}, y), ({a, a}, q) ; black is not in O, as it involves 3 existing edge labels. We define the ϕ-cost of an edgelabel change in O to be equal to 1 and the ϕ-cost of a 2-break on labels to be equal to the length of the involved edge label. For example ϕ(π 1 ) = 1, as the length of x is 1. We provide a short description of the completion (O c , ϕ c ) of (O, ϕ) introduced in Section 4.5. An edge-label change γ 2 belongs to O c , as there is a directed path from x to q in W black {a,a} . The minimum length of such a path is 2, thus ϕ c (γ 2 ) = 2. A 2-break on labels π 2 is in O c , as π 1 is in O, and γ 1 and γ 2 are in O c , furthermore

ϕ c (π 2 ) is equal to ϕ(π 1 ) + ϕ c (γ 1 ) + ϕ c (γ 2 ) = 4.
of an O-scenario ρ. Lemma 25 will be used in the following chapter when solving the ϕ-MCPS problem for a circle.

Lemma 25. Take a complete pair (O,ϕ) and an O-scenario ρ for a labeled circle (C,λ).

There exists a change-first O-scenario ρ satisfying the following properties:

• ϕ(ρ) ≤ ϕ(ρ),
• The underlying 2-break scenarios of ρ and ρ are equal,

• If ρ does not contain an O-change modifying the label of some colored edge, then neither does ρ.

Proof. Take (τ, χ) = ({u, v}, x), ({w, s}, y) → ({u, w}, z), ({v, s}, t) , col , the first O-break in ρ. Denote by ρ {u,w} the subsequence of ρ consisting of the O-changes applying to a colored edge ({u, w}, col). Keep only those O-changes in ρ {u,w} that x q q x q q q q x y q ({5, 6}, black, x), ({1, 2}, x), ({5, 6}, x) → ({1, 6}, x), ({2, 5}, x) , black , ({2, 3}, gray, t) → ({2, 3}, gray, q), ({2, 5}, black, x) → ({2, 5}, black, xyz), ({2, 5}, black, xyz) → ({2, 5}, black, q), ({2, 3}, q), ({4, 5}, q) → ({2, 5}, q), ({3, 4}, q) , gray , ({1, 6}, gray, z) → ({1, 6}, gray, x) . A possible change-first O c -scenario obtained from ρ in Lemma 25 is ρ = ({5, 6}, black, y) → ({5, 6}, black, x), ({2, 3}, gray, t) → ({2, 3}, gray, q), ({1, 6}, gray, z) → ({1, 6}, gray, x) , ({1, 2}, x), ({5, 6}, x) → ({1, 6}, x), ({2, 5}, q) , black , ({2, 3}, q), ({4, 5}, q) → ({2, 5}, q), ({3, 4}, q) , gray . It is not unique, as the O c -changes in the beginning of the change-first scenario can be performed in any order. follow (τ, χ) but precede the following O-break replacing ({u, w}, col). If ρ {u,w} is not empty, then denote by z the label provided by the last O-change in ρ {u,w} , otherwise denote z = z. Due to Corollary 2 in Section 2.2, every prefix of ρ transforms (C, λ) into a union of vertex disjoint circles, and, by definition, a circle contains at most one copy of every colored edge. This means that all the O-changes in ρ {u,w} apply to the same colored edge. Analogously, construct the subsequence ρ {v,s} of the O-changes in ρ transforming the label of ({v, s}, col) from t to t . Due to the completeness of (O, ϕ), ({u, v}, x), ({w, s}, y) → ({u, w}, z ), ({v, s}, t ) , col is an O-break. Transform ρ by deleting ρ {u,w} and ρ {v,s} , and replacing (τ, χ) with ({u, v}, x), ({w, s}, y) → ({u, w}, z ), ({v, s}, t ) , col , to obtain an O-scenario of smaller or equal ϕ-cost. The underlying 2-break scenario of ρ remains unchanged. Proceed with the rest of O-breaks in ρ. Now take a labeled edge ({u, v}, col, x) of (C, λ). As above, construct a subse-quence ρ {u,v} containing the O-changes in ρ transforming the label of ({u, v}, col) from x to x . If ρ {u,v} is not empty, then transform ρ by adding ({u, v}, col, x) → ({u, v}, col, x ) to its beginning and deleting ρ {u,w} to obtain an O-scenario of lower or equal ϕ-cost. The underlying 2-break scenario of ρ remains unchanged. Proceed with the rest of labeled edges of (C, λ) to obtain a change-first O-scenario.

Completion of (O, ϕ)

In this section we transform a pair (O, ϕ) into a complete pair (O c , ϕ c ), while ensuring that MCPS ϕ and MCPS ϕc costs for every labeled graph are equal.

Lemma 26. The completion (O

c ,ϕ c ) of (O,ϕ) can be constructed in O(|E V | 2 |Σ E | 3 + |Σ E | 2 |O|) time, which is O(|Σ E | 6 |E V | 4 )
(|E V | 2 |Σ 3 E | + |Σ E | 2 |O|) is O(|Σ E | 6 |E V | 4 ). Lemma 27. MCPS ϕ (G, λ) = MCPS ϕc (G, λ) for a labeled graph (G, λ). Proof. MCPS ϕc (G, λ) ≤ MCPS ϕ (G, λ) as every O-scenario for (G, λ) is also an O c - scenario for (G, λ). This means that if MCPS ϕc (G, λ) = ∞, then MCPS ϕ (G, λ) is also ∞. Suppose

Conclusion

We have introduced a framework for cost constraining 2-breaks and demonstrated that it generalizes previous work on cost constrained DCJ rearrangements and cost constrained transpositions.

We have shown that when dealing with the Minimum Cost Parsimonious Scenario problem it is enough to explore the space of the change-first O-scenarios. These are the O-scenarios in which the O-changes precede the O-breaks. However for this to work we first need to construct the completion (O c , ϕ c ), which, as presented in Lemma 26, is a time consuming task. In practice this might prompt us tably this is a case for the problems introduced in Section 4.3.2, namely Sorting by wDCJs and Indels in Intergenes [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] and Minimum Local Parsimonious Scenario [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF]. For these problems O(n log(n)) and O(n 3 ) time algorithms exist for a labeled circle on n vertices. In Section 5.5 we explain how such a preexisting O(n t ) time algorithm with t ≥ 1 for ϕ-MCPS on a labeled circle can be used as a subroutine to obtain an O(n t+1 ) time algorithm for ϕ-MCPS on a labeled breakpoint graph.

MCPS for a Graph

Introduction

Here we build on Theorem 4 stating that a parsimonious 2-break scenario for a graph can be partitioned into parsimonious 2-break scenarios for the subgraphs in its Maximum Alternating Edge-disjoint Cycle Decomposition. We adjust its proof to show that the same holds for a labeled graph and its parsimonious Oscenario. This allows us to prove that the MCPS ϕ -cost of a labeled graph is equal to the minimum of the MCPS ϕ -costs of its labeled MAECDs. We proceed by proposing a straightforward ILP for computing the MCPS ϕ -cost of a labeled graph once the MCPS ϕ -costs of its labeled simple cycles are known.

The MCPS ϕ -cost of a Labeled Graph is Equal to the

Minimum MCPS ϕ -cost of its labeled MAECD

• {H 1 , . . . , H k } is an ED of G.
• Every element in H is a labeled subgraph of (G, λ).

• For every labeled edge its multiplicity in (G, λ) is equal to the sum of multiplicities in {(H 1 , λ H 1 ), . . . , (H k , λ H 1 )}.

The MCPS ϕ -cost of H is equal to the sum of the MCPS ϕ -costs of its labeled subgraphs.

Observation 21. Take a labeled Eulerian decomposition of a labeled graph (G, λ) and a set of O-scenarios for its labeled subgraphs. A shuffle (see Definition 25 in Section 3.2) of these O-scenarios is an O-scenario for (G, λ). If the O-scenarios for the subgraphs are parsimonious, then the obtained O-scenario for (G, λ) is also parsimonious.

Lemma 28. Take a parsimonious O-scenario ρ for a labeled graph (G, λ). There exists a labeled MAECD of (G, λ), such that ρ is a shuffle of the parsimonious O-scenarios for its labeled subgraphs.

Proof. The proof is, up to minor modifications, analogous to the proof of Theorem 4. These modifications are the following. The labels of the directed 2-edge-colored edge-labeled trajectory graph D((G, λ), ρ) are of the form ({u, v}, x) for a pair of vertices {u, v} of G and an edge label x. If the l-th operation of ρ is an O-change ({u, v}, col, x) → ({u, v}, col, y), then D((G, λ), ρ l ) is obtained from D((G, λ), ρ l-1 ) by choosing a sink edge of D((G, λ), ρ l-1 ) of color col labeled ({u, v}, x), and adding an edge of color col labeled ({u, v}, y) between its sink vertex and the newly added one. This transformation does not modify the number of the connected components of D((G, λ), ρ l-1 ). Non-source and non-sink vertices of a connected component of D((G, λ), ρ) correspond to a subsequence of ρ that is a parsimonious O-scenario for a labeled subgraph of (G, λ). These labeled subgraphs corresponding to the connected components of D((G, λ), ρ) form a labeled MAECD of (G, λ). Corollary 9. A parsimonious O-scenario for a labeled graph having two connected components can be partitioned into two sub-sequences that are parsimonious Oscenarios for these components.

Theorem 13. The MCPS ϕ -cost of a labeled graph is equal to the minimum MCPS ϕcost of its labeled MAECD.

Proof. For a labeled graph (G, λ), take its minimum MCPS ϕ -cost labeled MAECD H = {(H 1 , λ H 1 ), . . . , (H k , λ H k )}. If the MCPS ϕ -cost of H is not equal to ∞, then there exist parsimonious O-scenarios for its labeled subgraphs of the ϕ-costs equal to the MCPS ϕ -costs of those labeled subgraphs. Due to Observation 21, by performing these parsimonious O-scenarios one after another we obtain a parsimonious O-scenario ρ for (G, λ). Its ϕ-cost is equal to the MCPS ϕ -cost of the labeled MAECD under question, establishing that MCPS ϕ (G, λ) is less than or equal to the minimum MCPS ϕ -cost of a labeled MAECD of (G, λ).

If MCPS ϕ (G, λ) = ∞, then take an MCPS ϕ O-scenario for (G, λ). Due to Lemma 28, there exists a labeled MAECD of (G, λ), such that ρ is a shuffle of the parsimonious O-scenarios for its labeled subgraphs. The ϕ-cost of ρ is equal to the sum of the ϕ-costs of those parsimonious O-scenarios, establishing that MCPS ϕ (G, λ) is greater than or equal to the MCPS ϕ -cost of a labeled MAECD of (G, λ). They are not isomorphic, as a labeled circle in b) contains a vertex incident to colored edges labeled y and t, while such a vertex does not exist in a labeled circle in f).

In c) and g) possible Eulerian orientations of these labeled circles are depicted. Once pairs of vertices {v 1 , v 2 } and {r 1 , r 2 } are merged into v and r, these Eulerian orientations of labeled circles become Eulerian orientations of (S, λ) depicted in d) and h). The vertex sequences of their u-tours (u, w, v, r, r, v, u) and (u, v, r, r, v, w, u).

The labeled u-circles obtained from these u-tours following the process detailed in Section 3.4.5 are presented in e) and i). The labeled circles presented in b) and e) are isomorphic, while the ones presented in f) and i) are even equal.

See Figure 5.1 for an example of a labeled circle, a labeled Eulerian orientation and its labeled u-circle. Theorem 14. Take a vertex u of a labeled simple cycle (S, λ). MCPS ϕ (S, λ) is equal to the minimum of the MCPS ϕ -costs of the labeled u-circles of (S, λ).

Proof. Take a labeled u-circle of (S, λ) and its O-scenario ρ. For every double vertex v in S, replace the occurrences of v 1 and v 2 in ρ with v to obtain an O-scenario ρ for (S, λ). The ϕ-costs of ρ and ρ are equal as the labels of v 1 , v 2 and v are equal by construction. This means that MCPS ϕ (S, λ) is less than or equal to the minimum MCPS-cost of a labeled u-circle of (S, λ).

In Theorem 5 to a 2-break scenario for a simple cycle we assigned a 2-break scenario for its circle. We illustrate in Figure 5.2 an analogous process that to an The ϕ-costs of ρ and ρ1 are equal as v 1 , v 2 , and v have equal labels. In d) an Eulerian orientation of (S, λ) is depicted. Its labeled v-circle, the circle obtained from the Eulerian tour starting from v with a black directed edge, is ( Ŝ1 , λ1 ). Transform ( Ŝ1 , λ1 ) by replacing the labeled edges ({v 1 , u}, black, t) and ({v 2 , w}, black, y) with ({v 2 , u}, black, t) and ({v 1 , w}, black, y) to obtain a simple labeled cycle ( Ŝ2 , λ2 ) presented in d). In the black 2-breaks of ρ1 replace the occurrences of v 1 with v 2 , and those of v 2 with v 1 , to obtain an O-scenario ρ2 for ( Ŝ2 , λ2 ) with ϕ-cost equal to that of ρ. In e) an Eulerian orientation of (S, λ) is depicted whose labeled v-circle is ( Ŝ2 , λ2 ).

O-scenario ρ for (S, λ) assigns a labeled circle (C, λ) of (S, λ) and its O-scenario ρ of the same ϕ-cost as ρ. Choose a labeled Eulerian orientation ( -→ C , λ) of (C, λ). For every double vertex v in S, merge the vertices v 1 and v 2 in ( -→ C , λ) to obtain a labeled Eulerian orientation ( -→ S , λ) of (S, λ). From Figure 5.1 it should be clear that the labeled u-circle of ( -→ S , λ) and (C, λ) are isomorphic. Finally, due to Lemma 29, MCPS-costs of isomorphic labeled graphs are equal. This means that ϕ(ρ) is greater than or equal to MCPS-cost of the labeled u-circle of ( -→ S , λ).

ϕ-MCPS for a Circle

Introduction

Here we build on Theorem 8 stating that a 2-break scenario for a sub-circle of a circle C can be partitioned into 2-break scenarios for smaller sub-circles of C. We adjust its proof to show that it stays valid for a parsimonious O-scenario on a labeled circle. This partitioning of a parsimonious O-scenario allows for a dynamic programming algorithm for MCPS presented in Subsection 5.4.5.

A Circular Straight Line Embedding of a Circle

Fix a circular straight-line embedding Σ C of a labeled circle (C, λ) on n vertices. As in Subsection 3.5.3, number the vertices with 1, n while respecting their clockwise order on Σ C and ensuring that the colored edge going clockwise from n to 1 is gray. For i, j ∈ 1, n with i and j of different parity, define C[i, j] to be the sub-circle of C consisting of the path going clockwise from i to j in Σ C and its colored outer edge (see Definition 47) Suppose that the statement is true for any circle with at most 2k -2 ≥ 2 vertices and take a circle C on 2k vertices. See Figure 3.9 for an illustration of the proof that follows. Take the first O-break (τ ,χ) in ρ. Being change-first, ρ contains at most two O-changes acting on the colored edges replaced by (τ ,χ), denote them by µ. Denote by ρ the subsequence of ρ obtained once µ and (τ ,χ) are deleted. Denote by (C , λ ) the labeled graph that is obtained from (C,λ) after µ and (τ ,χ) are performed. ρ is a parsimonious O-scenario for (C , λ ). Due to Corollary 2, it has two connected components that are both circles, denote them by (C 1 , λ 1 ) and (C 2 , λ 2 ). Due to Corollary 9, ρ can be partitioned into ρ 1 and ρ 2 , that are parsimonious O-scenarios, change-first by construction, for (C 1 , λ 1 ) and (C 2 , λ 2 ) respectively. Due to Theorem 7, the scenario graph of ρ inherits from Σ C a circular straightline embedding in which all the bounded faces are quadrilaterals. The edges of τ and the edge {i, j} all belong to the scenario graph of ρ. This means that both i and j either belong to C 1 or C 2 , without loss of generality we can suppose that it is C 2 . This also means that all the vertices of τ belong either to C[i, j] or C[j, i].

Without loss of generality we can suppose that it is C[j, i].

The inductive hypothesis holds for a triplet (C 2 , λ 2 ), ρ 2 , {i, j} , providing us with a label x, and a partition of ρ 2 into two parsimonious outer-change-free scenarios for the x-labeled sub-circles of (C 2 , λ 2 ). By construction, one of these labeled sub-circles is (C[i, j], λ x ). Denote the other one by (C 5 , λ 5 ) and denote the parsimonious outer-change-free O-scenarios obtained for them by ρ [i,j] and ρ 5 respectively.

By now we know that ρ is a shuffle of µ, (τ ,χ), ρ 1 , ρ [i,j] , and ρ 5 . Remove ρ [i,j] , µ and (τ ,χ) from ρ to obtain a shuffle of ρ 1 and ρ 5 , that we denote by ρ. Due to Observation 21, ρ is a parsimonious O-scenario for the union of the vertexdisjoint circles (C 1 , λ 1 ) and (C 5 , λ 5 ), which is also the labeled graph obtained from (C[j, i], λ x ) after µ and (τ, χ) are performed. Finally, by deleting only ρ [i,j] from ρ, we obtain a shuffle of µ, (τ, χ) and ρ, that is a parsimonious O-scenario for (C[j, i], λ x ), that does not contain any O-changes acting on its colored outer edge, and together with ρ [i,j] satisfies the statement. {i, j}, {k, l} , col {i,j} with i < k < l < j. This means that ρ contains an O-break (τ, χ) with a labeling χ of τ edges. ρ is change-first, thus it does not contain an O-change modifying the labeled edge ({i, j}, col {i,j} , χ({i, j})) introduced by (τ, χ). ρ is outer-change-free, thus it also does not contain an O-change modifying its labeled outer edge ({i, j}, col {i,j} , x). Due to Theorem 7, τ is a single 2-break in ρ u with {i, j} among its edges. This means that ρ does not contain an O-break replacing labeled edge ({i, j}, col {i,j} , χ({i, j})) or ({i, j}, col {i,j} , x). Thus ρ transforms (C[i, j], λ x ) into a terminal graph containing labeled edges ({i, j}, col {i,j} , χ({i, j})) and ({i, j}, col {i,j} , x), which means that χ({i, j}) = x.

Apply Lemma 30 for {i, k}, {k, l} and {l, j} to obtain edge labels z, t, y and parsimonious outer-change-free O-scenarios ρ 1 , ρ 2 , and ρ 3 for sub-circles (C[i, k], λ z ), (C[k, l], λ y ) and (C[l, j], λ t ), that together with (τ, χ) partition ρ. χ({i, k}) = z, χ({k, l}) = y and χ({l, j}) = t, since ρ is change-first. All we have to prove now is that ρ 1 and ρ 3 are matched. [START_REF] Apostolakis | Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections[END_REF][START_REF] Bérard | Perfect sorting by reversals is not always difficult[END_REF].

If k = i + 1, then ρ 1 is an O-scenario for a labeled circle on two vertices and is matched by definition. Suppose that i ≤ k + 3, meaning that a colored edge ({i, k}, col {i,j} ) is not present in C. ρ u contains a 2-break replacing it, thus due to Observation 1, it must also contain a 2-break introducing it. ρ u is a parsimonious 2-break scenario, thus due to Theorem 7, it contains only two 2-breaks with {i, k} among their edges. Due to the same theorem, the underlying 2-break scenario of ρ 1 contains a single 2-break with {i, k} among its edges. That 2-break is not τ , which means that it introduces ({i, k}, col {i,j} ), and thus ρ 1 is indeed a matched O-scenario. The same analysis applies to ρ 3 .

The proof of the following theorem for non-matched O-scenarios is analogous to that of Theorem 15.

Theorem 16. Take a parsimonious non-matched outer-change-free change-first Oscenario ρ for (C[i, j], λ x ) with i + 3 ≤ j. There exists an O-break (τ, χ) = ({i, j}, x), ({k, l}, y) → ({i, k}, z), ({l, j}, t) , col {i,j} with i < k < l < j, such that ρ can be partitioned into (τ, χ) and parsimonious outer-change-free change-first O-scenarios for (C[i, k], λ z ), (C[k, l], λ y ), and (C[l, j], λ t ) with the O-scenario for (C[k, l], λ y ) being matched.

Minimal Weight Polygon Quadrangulation

Our algorithm to be presented in Subsection 5.4.5 can be seen as a generalization of that for the Minimal Weight Polygon Quadrangulation problem (MWPQ) presented by Massarwi, Sosin, and Elber in Section 3.1.2 of [START_REF] Massarwi | Untrimming: Precise conversion of trimmed-surfaces to tensor-product surfaces[END_REF]. There arbitrary positive weights are assigned to the quadrilaterals in a polygon, and the authors ask for a quadrangulation minimizing the sum of the weights of its quadrilaterals.

A quadrangulation Q of a sub-circle C[i, j] contains a quadrilateral f incident to the edge {i, j}. Suppose that its vertices are i < k < l < j. See Figure 5.5 for an example. The weight of Q is equal to the sum of the weights of

Q restricted to C[i, k], Q restricted to C[k, l], Q restricted to C[l, j]
and the weight of f . This partition allows for an O(n 4 ) time dynamic programming algorithm for MWPQ, which is very similar to an O(n 3 ) time dynamic programming algorithm for the Minimal Weight Triangulation problem on a simple polygon presented by Klincsek [START_REF] Gt Klincsek | Minimal triangulations of polygonal domains[END_REF]. Computing ϕ m and ϕ u Now we show how to compute ϕ m and ϕ u for a labeled sub-circle of (C, λ) using ϕ m and ϕ u values for its smaller labeled sub-circles. We have demonstrated in Theorem 15 that a matched outer-change-free change-first O-scenario for (C[i, j], λ x ) contains an O-break introducing a colored edge ({i, j}, x, col {i,j} ). This O-break has the following form.

Definition 75 (matched O-break for a labeled sub-circle). An O-break (τ, χ) is matched for (C[i, j], λ x ), if τ = {i, k}, {l, j} → {i, j}, {k, l} , col {i,j} for i < k < l < j with i ≡ l mod 2 and k ≡ j mod 2, and χ({i, j}) = x.

In the following lemma we iterate through the space of the matched O-breaks for (C[i, j], λ x ) to compute ϕ m [i, j, x]. Lemma 32. For i, j ∈ 1, n with j ≥ i + 3 of different parity and an edge label x we have:

ϕ m [i, j, x] = min (τ,χ)∈M ϕ m [i, k, z] + ϕ m [l, j, t] + ϕ[k, l, y] + ϕ(τ, χ) , where M is a set of matched O-breaks for (C[i, j], λ x ).
[i, j, x] ≥ ϕ(τ, χ) + ϕ m [i, k, z] + ϕ m [l, j, t] + ϕ[k, l, y].
Now we show that the opposite inequality holds. Take a matched O-break

(τ, χ) = ({i, k}, z), ({l, j}, t) → ({i, j}, x), ({k, l}, y) , col {i,j} . If ϕ m [i, k, z] + ϕ m [l, j, t] + ϕ[k, l, y] + ϕ(τ, χ) = ∞,
[i, j, x] ≤ ϕ(τ, χ) + ϕ m [i, k, z] + ϕ m [l, j, t] + ϕ[k, l, y].
Analogously, we introduce non-matched O-breaks and use Theorem 16 to establish Lemma 33.

Definition 76 (non-matched O-break for a labeled sub-circle). An O-break (τ, χ) is matched for (C[i, j], λ x ), if {i, j}, {k, l} → {i, k}, {l, j} , col {i,j} for i < k < l < j with i ≡ l mod 2 and k ≡ j mod 2, and χ({i, j}) = x. Lemma 33. For i, j ∈ 1, n with j ≥ i + 3 of different parity and an edge label x we have:

ϕ u [i, j, x] = min (τ,χ)∈M ϕ[i, k, z] + ϕ[l, j, t] + ϕ m [k, l, y] + ϕ(τ, χ) ,
where M is a set of non-matched O-breaks for (C[i, j], λ x ).

Computing MCPS ϕ (C,λ)

Finally we use values ϕ m [1, n, y] and ϕ u [1, n, y]

(C, λ) ≥ ϕ[1, n, x ] + W gray {a,b} (x, x ) ≥ min y∈Σ E ϕ[1, n, y] + W gray {a,b} (x, y)
If the proposed expression is equal to ∞, then there is nothing more to prove. Otherwise, take an edge label x together with a parsimonious outer-change-free O-scenario ρ for (C[1, n], λ x ) realizing the minimum of the expression. Add an O-change ({1, n}, gray, x) → ({1, n}, gray, x ) to the beginning of ρ to obtain a parsimonious O-scenario for (C, λ). This way we obtain MCPS ϕ (C, λ) ≤ ϕ[1, n, x ] + W gray {a,b} (x, x ) = min y∈Σ E ϕ[1, n, y] + W gray {a,b} (x, y) . . Its four labeled Eulerian orientations are given in b1), b2), c1) and c2). By inverting the directions of the labeled edges of the labeled Eulerian orientation in b1) we obtain that in b2). Their labeled 1-circles are isomorphic, and that of b1) is depicted in b3). The same is true for the figures in c1), c2) and c3). Due to reasons explained in Theorem 14, every labeled circle of this labeled simple cycle is isomorphic to either a labeled circle in b3) or that in c3).

• b1) b2) b3) c1) c2) c3) x x x x x x x x x x x x x x t
+ p 3 + Q t ) time, which is O(n t+1 + n 3 ).
Proof. Take a labeled breakpoint graph (G, λ). It has P + Q colored edges parti-tioned between AA paths, BB paths and circle subgraphs of G that can be easily identified in O(P +Q) time. Due to Theorem 14, MCPS ϕ (S, λ S ) is equal to the minimum of the MCPS ϕ -costs of at most two non-isomorphic labeled circles containing O(P ) edges. This means that the p 2 edges of B(G) can be weighted in O(p 2 f (P )) time. A minimum weight perfect matching of B(G) can be found in O(p 3 ) time using the Hungarian algorithm as it has 2p vertices. The MCPS ϕ -costs of the circle subgraphs of G can be computed in O(cf (Q)) time. Combining these results we obtain an O(p 2 f (P ) + p 3 + cf (Q)) time algorithm for ϕ-MCPS on (G, λ). Now suppose that f (r) = O(r t ) for some constant t ≥ 1. This means that ϕ-MCPS for a labeled circle with r edges can be computed in k 2 r t steps for some constant k. Let

p i=0 p j=0 k(a i + b j ) t = k p i=0 p j=0 t l=0 t l a l i b t-l j = k t l=0 t l p i=0 p j=0 a l i b t-l j = k p j=0 p i=0 b t j + k p i=0 p j=0 a t i + k t-1 l=1 t l p i=0 a l i p j=0 b t-l j = kp p j=0 b t j + kp p i=0 a t i + k t-1 l=1 t l p i=0 a l i p j=0 b t-l j ≤ kp( p j=0 b j ) t + kp( p i=0 a i ) t + k t-1 l=1 t l ( p i=0 a i ) l ( p j=0 b j ) t-l ≤ k(pP t B + pP t A ) + pk t-1 l=1 t l P t-l B P l A = kp(P B + P A ) t = kpP t
Thus B(G) edges can be weighted in O(pP t ) time. This provides us with an O(pP t + p 3 + Q t ) time algorithm for computing the MCPS ϕ -cost of a labeled breakpoint graph. p, P and Q are O(n), thus the worst case time complexity is O(n t+1 + n 3 ).

Time Complexity

We have treated the MCPS problem by proposing a polynomial time dynamic programming algorithm solving it for a labeled circle and an ILP solving it for any labeled graph. The O(n 4 L 4 ) time complexity of our algorithm for a labeled circle, where n is the number of vertices and L is the number of edge labels, might seem prohibitively high. However this worst case time complexity can be avoided in practice, at least when dealing with the biological data related to genome rearrangements.

To begin with, n remains quite low in the genome breakpoint graphs of interest. In our study [START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF] n did not exceed 250 even for the species as distant as human and chicken, while for human and gibbon, a pair of species of a particular interest for the study of genome rearrangements [START_REF] Nathan H Lazar | Epigenetic maintenance of topological domains in the highly rearranged gibbon genome[END_REF], n was found to be 80 or less. An initial version of our algorithm, where L = 1 and only black 2-breaks are allowed, took seconds to finish for the genome breakpoint graph of human and gibbon and minutes for that of human and chicken. This indicates that for low L values our algorithm stays feasible for any pair (O, ϕ).

An O-break includes 4 vertices and 4 edge labels, thus the total number B of the O-breaks that might appear in a parsimonious O-scenario for a labeled circle is O(n 4 L 4 ). In our algorithm we check every O-break exactly once, thus its time complexity can be brought down to O(n 4 + B). This can be done with the help of an appropriately chosen data structure for O, where for every quadrilateral we can query the O-breaks with the edges bounding that quadrilateral. Take for example the set of valid operations O used in Minimum Local Parsimonious Scenario [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] and introduced in Subsection 4.3.2. Here O(B) is actually O(n 6 ), as every O-break in a parsimonious O-scenario includes only two edge labels that must be already present among the n edge labels of (C, λ).

Finally, once a particular pair (O, ϕ) is chosen, our algorithm can be used as a blueprint to devise a more efficient algorithm specifically tailored for this pair. For example the ϕ-costs of some O-breaks might be too high for them to appear in a ϕ-MCPS O-scenario, or the vertex and edge labels of a sub-circle C[i, j] might impose constraints on the possible labels of its outer colored edge, so we do not have to check L different options.

Chapter 6 Conclusion

We have established novel links between various permutation, string, genome and graph sorting problems, that ultimately led to our framework for cost constrained 2-break scenarios. Even if it is beyond the scope of this study to fully explore the implications of these links, we have briefly mentioned some open optimization problems that might benefit from our observations. These include Swap Median Permutation, DCJ Closest Genome, Token Swapping on trees, and a conjecture stating that there always exists an O(n 2 ) length transposition decomposition of minimum cost [START_REF] Farnoud | Computing similarity distances between rankings[END_REF]. We have not even touched upon questions related to counting, sampling and estimating, that also hold a number of important open problems. For example, the problem of counting the parsimonious DCJ scenarios transforming one single copy genome into another is conjectured to be #P-complete [START_REF] Miklós | Sampling and counting genome rearrangement scenarios[END_REF]. Finally, we believe that further investigation might reveal important connections between the study of genome rearrangements, rank aggregation [START_REF] Bachmaier | On the hardness of maximum rank aggregation problems[END_REF], and permutation codes [START_REF] Yang | Theoretical bounds and constructions of codes in the generalized Cayley metric[END_REF] that are not yet fully appreciated.

We have furthered our understanding of parsimonious DCJ scenarios by revealing novel links between parsimonious 2-break scenarios, Minimum Length Transposition Decompositions and quadrangulations of regular polygons. We have defined two scenarios to be equivalent if they consist of the same rearrangements, and described the equivalence classes for this relation. There are (n + 1) (n-1) [START_REF] Ouangraoua | Combinatorial structure of genome rearrangements scenarios[END_REF] parsimonious black-2-break scenarios for a circle on 2n + 2 vertices, while the number of their equivalence classes is only [START_REF] Amir | String rearrangement metrics: A survey[END_REF] ) n . This drastic reduction in the search space was instrumental in our work on cost constrained parsimonious scenarios. The true evolutionary scenario, however, is likely to be non-parsimonious [START_REF] Biller | Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation[END_REF][START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF]. This prompts us to relax the parsimony criterion and the first step in this direction could be a description of the equivalence classes of the 2-break scenarios that are almost parsimonious.

1 2n+1 3n n ≈ 1 n 3/2 ( 27
We have introduced a framework for cost constrained DCJs, and demonstrated that within it a particular optimization problem can be efficiently solved. Through-113 out this work we have searched to minimize the sum of rearrangement costs, however, our algorithms can be easily modified to maximize their product. If the labels of the intergenes were somehow linked with the probabilities for the rearrangements to occur, then our work could be used to find the most likely parsimonious rearrangement scenarios.

We have shown that a Minimum Cost Parsimonious Scenario can be solved in polynomial time for an arbitrary cost function. The next step is to move from arbitrary to biologically relevant costs. Defining the latter term would require a separate project, however for now we say that these are the cost functions for which an MCPS scenario resembles the true evolutionary one. In [START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF] we briefly discussed an idea for testing this relevance with the help of what we call sure 2-breaks. These are 2-breaks that appear in every parsimonious 2-break scenario for a graph. Take a circle subgraph on four vertices in a genome breakpoint graph G. Every parsimonious 2-break scenario for G necessarily contains either the black or the gray 2-break sorting this circle. This means that if the true evolutionary scenario is close to being parsimonious, then it is likely to contain one of these 2-breaks, that we call sure. A biologically relevant cost function then would be expected to have low value for at least one of these sure 2-breaks, however statistical tests that would accompany this idea are yet to be developed. In [START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF] we have shown that a parsimonious 2-break scenario for human and gibbon has ~30 sure 2-breaks that comprise ~25% of its length. By comparing multiple pairs of species we could accumulate a larger set of sure 2-breaks for which various cost functions could be tested.

As far as we are aware, every previous model for cost constrained genome rearrangements was symmetric. By this we mean that for every rearrangement scenario between genomes A and B, there exist scenarios transforming A into B, and B into A of the same cost. Such a model does not provide any information regarding the branch of a phylogenetic tree on which rearrangements occurred. Our models, on the other hand, can be non-symmetric. In this case it might happen that the black sure 2-break has significantly lower cost than the gray one for the same circle subgraph of the genome breakpoint graph. If the true evolutionary scenario is close to being parsimonious and the cost function is biologically relevant, then this indicates that a particular rearrangement happened on the lineage leading to genome A. In addition to this, in our work a DCJ scenario transforms genomes A and B into some genome C. For the true evolutionary scenario this C would be the least common ancestor of A and B. If a biologically relevant cost function ϕ is available, then the genome C thus obtained for a ϕ-MCPS scenario might inform us about the properties of the least common ancestor of A and B. If we were able to enumerate or uniformly sample the ϕ-MCPS scenarios, then we could ask various questions concerning the gene order of the least common ancestor and the properties of its intergenic regions.

Chapter 7

Résumé

Les Réarrangements Génomiques Dans le Contexte Évolutif

Un réarrangement génomique est une mutation qui modifie la structure des chromosomes voire même leur nombre dans un génome. Prenez par exemple les humains et les chimpanzés. Nous avons 23 paires de chromosomes, alors que les chimpanzés en ont 24. Cette différence est due à une fusion de deux chromosomes ancestraux qui a donné naissance au chromosome 2 chez l'homme [START_REF] Timothy R Dreszer | Biased clustered substitutions in the human genome: the footprints of maledriven biased gene conversion[END_REF]. Les lignées humains et chimpanzés ont chacune accumulé un certain nombre d'autres réarrangements depuis leur séparation [START_REF] Kim | Reconstruction and evolutionary history of eutherian chromosomes[END_REF].

Outre des fusions et des fissions de chromosomes, ces réarrangements comprennent des délétions, des insertions et des inversions de segments chromosomiques. Deux extrémités de chromosomes différents peuvent également être échangées au cours d'une translocation. L'ensemble de ces mutations constitue un scénario évolutif de réarrangements entre les espèces. Nous nous sommes intéressés à la reconstruction des scénarios de réarrangements entre espèces animales.

Les progrès récents dans les technologies de séquençage nous fournissent une occasion sans précédent pour étudier les mécanismes moléculaires de réarrangements génomiques [START_REF] Mani | Triggers for genomic rearrangements: insights into genomic, cellular and environmental influences[END_REF][START_REF] Kim | Mechanisms of germ line genome instability[END_REF], la façon dont ils se propagent dans les populations [START_REF] Faria | Evolving inversions[END_REF], et leur importance pour l'évolution [START_REF] Mérot | A roadmap for understanding the evolutionary significance of structural genomic variation[END_REF]. Des méthodes de détection systématique de réarrangements génomiques dans le génome humain émergent [START_REF] Ho | Structural variation in the sequencing era[END_REF] et nous informent de leur apparition en chacun de nous. Des études récentes s'appuient sur ces avancées pour dévoiler le rôle joué dans les scénarios évolutifs par:

• les domaines de chromatine transcriptionnellement actifs [START_REF] Fudenberg | Chromatin features constrain structural variation across evolutionary timescales[END_REF][START_REF] Henrike | Spatial chromosome folding and active transcription drive DNA fragility and formation of oncogenic MLL translocations[END_REF],

• la proximité spatiale entre loci dans un génome [START_REF] Amélie S Véron | Close 3D proximity of evolutionary breakpoints argues for the notion of spatial synteny[END_REF][START_REF] Berthelot | The 3D organization of chromatin explains evolutionary fragile genomic regions[END_REF][START_REF] Krister | Large-scale mammalian genome rearrangements coincide with chromatin interactions[END_REF], 115

• les limites des domaines d'association topologique [START_REF] Nathan H Lazar | Epigenetic maintenance of topological domains in the highly rearranged gibbon genome[END_REF][START_REF] Fudenberg | Chromatin features constrain structural variation across evolutionary timescales[END_REF][START_REF] Huynh | TAD fusion score: discovery and ranking the contribution of deletions to genome structure[END_REF],

• les structures d'ADN non canoniques [START_REF] Georgakopoulos-Soares | Noncanonical secondary structures arising from non-B DNA motifs are determinants of mutagenesis[END_REF].

Notre projet associe des outils mathématiques et algorithmiques avec la compréhension biologique actuelle des réarrangements génomiques. D'un point de vue biologique, notre objectif est de lier génétique et épigénétique aux réarrangements dans les deux sens :

• nous développons une méthodologie pour étudier des caractéristiques génétiques et épigénétiques associées aux réarrangements, et inversement

• pour trouver des scénarios de réarrangements guidés par de telles caractéristiques génétiques et épigénétiques.

Des Modèles Mathématiques de Réarrangements Pondérés

Les études mathématiques et algorithmiques des scénarios de réarrangements génomiques ont commencé il y a un quart de siècle et ont conduit à un grand nombre de problèmes combinatoires [START_REF] Fertin | Combinatorics of genome rearrangements[END_REF]. Le problème central dans ce domaine est celui de trouver un scénario optimal transformant un génome en un autre.

Les réarrangements ont généralement été traités comme étant tout aussi probables, ou ayant des poids égaux. Dans ce cas, un scénario est optimal s'il est de longueur minimale. Nous présentons dans la Section 1.3 un aperçu des modèles dans lesquels des poids différents ont été attribués aux réarrangements en fonction de certaines contraintes biologiques, dans le but de trouver des scénarios de réarrangement qui ressemblent mieux au véritable scénario évolutif. Cependant, dans la plupart des cas, ces contraintes supplémentaires entraînent des problèmes difficiles. Des algorithmes polynomiaux sont connus seulement pour quelques-uns d'entre eux:

• Un scénario le plus court composé d'inversions affectant au plus deux gènes peut être trouvé en temps polynomial, comme le montrent Galvao, Baudet, et Dias [START_REF] Galvao | Sorting circular permutations by super short reversals[END_REF] et Bender, Ge, He, Hu, Pinter, Skiena, et Swidan [START_REF] Michael | Improved bounds on sorting by lengthweighted reversals[END_REF].

• Si le poids d'inversion est égal au nombre de gènes qu'il affecte, alors un scénario de poids minimum composé d'inversions peut être trouvé en temps polynomial pour deux chaînes binaires [START_REF] Michael | Improved bounds on sorting by lengthweighted reversals[END_REF].

• Un scénario parfait de longueur minimale composé d'inversions peut être trouvé en temps polynomial pour une certaine famille d'intervalles communs, comme le montre Bérard, Bergeron, Chauve, et Paul [START_REF] Bérard | Perfect sorting by reversals is not always difficult[END_REF].

À notre connaissance, il existe d'autres algorithmes polynomiaux pour les problèmes de réarrangements pondérés : ce sont ceux qui s'appuient sur un modèle de réarrangements appelés double cut and join. Le double cut and join (DCJ) a été introduit en 2005 par Yancopoulos, Attie et Friedberg [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF], et est mathématiquement beaucoup plus simple que les modèles précédents basés sur les inversions ou les inversions et les translocations. Le double cut and join modélise un réarrangement en coupant des chromosomes en un ou deux endroits et en rejoignant les brins chromosomiques. En plus des inversions et des translocations, cette opération simple peut reproduire d'autres réarrangements comme une circularisation d'un chromosome linéaire et une excision d'un chromosome circulaire. On ne sait pas si ces derniers types de réarrangements ont un rôle dans l'évolution, mais des éléments d'ADN circulaires ont été trouvés dans des cellules humaines à l'état normal [START_REF] Devitt Møller | Circular DNA elements of chromosomal origin are common in healthy human somatic tissue[END_REF] et sont abondantes dans des cellules cancéreuses [START_REF] Turner | Extrachromosomal oncogene amplification drives tumour evolution and genetic heterogeneity[END_REF]. Il existe quelques algorithmes efficaces pour les problèmes de double cut and join pondérés :

• Un scénario parfait de longueur minimale de double cut and join peut être trouvé en temps polynomial pour une certaine famille d'intervalles communs, comme le montrent Bérard, Chateau, Chauve, Paul, and Tannier [START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF].

• Un scénario de poids minimum peut être trouvé en temps polynomial parmi les scénarios de longueur minimale pour les double cut and join pondérés en fonction des insertions et des suppressions dans les régions intergéniques, comme le montrent Bulteau, Fertin et Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF].

• Un scénario de poids minimum peut être trouvé en temps polynomial parmi les scénarios de longueur minimale pour les double cut and join pondérés en fonction d'emplacements spatiaux des régions intergéniques, comme nous l'avons montré dans nos travaux précédents [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Simonaitis | A general framework for genome rearrangement with biological constraints[END_REF][START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF],

Nous soulignons dans la Section 1.4 que les données biologiques qui sont disponibles aujourd'hui nécessitent des modèles de réarrangements pondérés qui sont beaucoup plus flexibles que ceux qui ont été étudiés auparavant.

Un Cadre Général pour les Double Cut and Join Pondérés

La principale contribution de cette thèse est la suivante :

Projet. Nous présentons un cadre sur le modèle de réarrangements double cut and join avec des poids arbitraires. Dans ce cadre un scénario de poids minimum peut être trouvé en temps polynomial parmi les scénarios de longueur minimale pour deux génomes à contenu génétique identique et sans doublons.

Cela signifie que notre objectif n'est pas de proposer un modèle particulier de pondération de double cut and join d'une manière biologiquement significative, mais plutôt de guider ce processus et de garantir qu'aucun travail algorithmique n'est nécessaire si nos directives sont respectées.

Les axes principaux de notre projet sont les suivants:

1. Une méthode pour explorer efficacement l'espace des scénarios double cut and join de longueur minimale.

2. Une méthode pour enrichir un réarrangement avec des informations concernant les régions intergéniques qu'il coupe et rejoint, et un poids arbitraire.

3. Un algorithme efficace pour trouver un scénario de poids minimum parmi les scénarios de longueur minimale.

Ces tâches sont traitées respectivement aux Chapitre 3, Chapitre 4, et Chapitre 5. Notre cadre généralise les trois modèles de double cut and join pondérés précedemment évoqués [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF][START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF].

Aperçu

Au Chapitre 2, nous montrons qu'un double cut and join peut être interprété comme une transformation de graphe. Dans ce qui suit nous introduisons en fait un cadre de transformations pondérées des graphes et non de réarrangements pondérées génomiques.

Un 2-break est une transformation de graphe échangeant les extrémités de deux arêtes comme illustré en Figure 7.1. Nous montrons en Section 2.7 qu'un 2-break généralise un certain nombre d'opérations de tri. Celles-ci incluent le tri des permutations avec transpositions [START_REF] Farnoud | Sorting of permutations by costconstrained transpositions[END_REF], le tri des chaînes avec échanges [START_REF] Amir | String rearrangement metrics: A survey[END_REF], le tri des génomes avec double cut and join [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF], et l'échange des jetons sur les graphes [START_REF] Bonnet | Complexity of token swapping and its variants[END_REF]. Des variantes pondérées pour tous ces problèmes ont été étudiées dans la littérature. Cela a motivé notre choix d'étudier les 2-breaks pondérés et pas seulement le cas particulier du double cut and join. Au Chapitre 3, nous examinons un scénario de 2-breaks de longueur minimale pour un graphe et démontrons qu'il peut être partitionné en scénarios de 2-breaks de longueur minimale pour des cycles. Nous procédons ensuite en montrant qu'un scénario de 2-breaks de longueur minimale pour un cycle peut être partitionné en scénarios pour des cycles qui sont plus petits. Cela conduit à un algorithme de programmation dynamique qui explore l'espace des scénarios de 2-breaks de longueur minimale pour un cycle. Au Chapitre 5, nous fournissons un algorithme exact pour trouver un scénario de poids minimum parmi les scénarios de 2-breaks de longueur minimale. En l'utilisant, nous pouvons trouver, en temps O(n 5 L 4 ), un scénario de poids minimum parmi les scénarios de réarrangements pondérés de longueur minimale pour deux génomes à contenu génétique identique et sans doublons. Ici n est le nombre de gènes et L est le nombre d'états différents auxquels une région intergénique est autorisée à accéder. Le problème devient NP-difficile si les génomes ne satisfont pas à ces critères. Dans ce cas, nous utilisons l'optimisation linéaire en nombres entiers pour résoudre le problème de manière exacte. Nous concluons le chapitre par une discussion concernant la complexité polynomial de notre algorithme. Nous montrons qu'en pratique n est assez petit, comme on l'a déjà discuté dans [START_REF] Simonaitis | Weighted minimumlength rearrangement scenarios[END_REF].

Le vrai scénario évolutif pourrait être d'une longueur non minimale. Il serait donc intéressant d'explorer l'espace de tous les scénarios, et pas seulement ceux de longueur minimale. Cependant on sait que c'est NP-difficile de trouver un scénario de réarrangements pondérés de poids minimum, même pour les modèles très simples de pondération, comme le montrent Fertin, Jean, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] et nos travaux [START_REF] Simonaitis | Finding local genome rearrangements[END_REF].

Nous estimons qu'il n'est pas nécessaire d'explorer l'espace de tous les scénarios possibles. D'abord, des outils statistiques pourraient être utilisés pour estimer une borne supérieure l pour la longueur du véritable scénario évolutif, comme discuté par Biller, Guéguen, Knibbe, et Tannier [START_REF] Biller | Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation[END_REF] et Alexeev et Alekseyev [START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF]. Ensuite, seuls les scénarios de longueur inférieure à l pourraient être explorés. Un certain nombre de nos résultats sont en fait prouvés pour les scénarios qui ne sont pas nécessairement de longueur minimale. Ces résultats fournissent donc une base pour les travaux futurs. Au Chapitre 6 nous discutons comment la pertinence d'un modèle de réarrangements pondérés pourrait être testée en utilisant des données biologiques. Pour conclure, nous expliquons comment notre cadre pourrait être utile pour les études phylogénétiques.

Figure 1 . 1 :

 11 Figure 1.1: A 2-break transforms a pair of edges {u, v} and {w, s} of a multigraph into either {u, w} and {v, s}, or {u, s} and {v, w}. The term 2-break was first proposed by Alekseyev and Pevzner [1].

Figure 2 . 1 :

 21 Figure 2.1: An example of an Eulerian 2-edge-colored multigraph G is presented in a). a) to e) depicts a parsimonious 2-break scenario transforming G into a terminal graph presented in e). The first two 2-breaks of the scenario are {8, 9}, {8, 9} → {8, 8}, {9, 9} , black and {5, 9}, {6, 7} → {5, 6}, {7, 9} , gray . Two different Maximum Alternating Edge-disjoint Cycle Decompositions of G exist, they are depicted in f) and g). All the graphs depicted in g) are simple cycles. The one in the middle of g) is also a circle.

Figure 2 .Corollary 1 .Figure 2 . 2 :

 2122 Figure 2.2: A simple cycle is depicted in a) with vertices u and w singled out. b)-d) depicts four possible 2-breaks that each yield a graph with an MAECD size equal to 2.

Definition 12 .

 12 A DCJ scenario is a sequence of DCJs transforming two genomes A and B into two genomes with equal sets of adjacencies. Denote by d aDCJ (A, B) the minimum length of such a scenario for genomes A and B. Observation 3. d aDCJ (

Definition 13 .Observation 4 .

 134 A genome DCJ scenario is a sequence of DCJs transforming two genomes A and B into two equal genomes. Denote by d gDCJ (A, B) the minimum length of such a scenario for genomes A and B. For any pair of genomes we have d aDCJ (A, B) ≤ d gDCJ (A, B), while d aDCJ (A, B) = d gDCJ (A, B) if A and B are single copy genomes. See Figure 2.3 for an example of genomes with unequal values of d aDCJ and d gDCJ .

Figure 2 .

 2 4 and Figure 2.3 for examples.

1

 1

Figure 2 . 4 :

 24 Figure 2.4: The adjacency and breakpoint graphs AG(A, B) and G(A, B) of the single copy genomes are depicted, with A= ({1 t }, {1 h , 3 t }, {3 h }), ({4 h }, {4 t }),

Lemma 4 .

 4 For single copy genomes we have d aDCJ (A, B) = d 2b (G(A, B)). Proof. Denote by C the number of cycles, and by I the number of odd paths among the connected components of AG(A, B). There are C circles among the connected components of G(A, B). There are also I subgraphs of G(A, B) that are circles containing the vertex •. The rest of the simple cycles in G(A, B) contain a pair of an AA and a BB path, and G(A, B) contains n -I/2 AA and BB paths in total, thus c(G(A, B)) = C + I + n -I/2. By summing up the degrees of the vertices and dividing them by two we obtain that e(G) = 2n, thus d 2b (G(A, B)) = e(G(A, B)) -c(G(A, B)) = n -C -I/2 due to Lemma 1. Due to Lemma 2, d aDCJ (A, B) = n -C -I/2, and thus d 2b (G(A, B)) = d aDCJ (A, B).

  7 a) for an example. He proves that the minimum length of an interchange scenario transforming x to y is equal to n -c(D(x)), where c(D(x)) is the size of a maximum edge disjoint decomposition of D(x)'s edges into directed cycles. Computing c(D(x)) is NP-hard and so is the DNF problem.

Figure 2 . 7 :

 27 Figure 2.7: First we illustrate how an interchange of two elements in a string can be interpreted as a 2-break on a properly defined graph. Take strings x = R, W, B, R, R, B and y = R, R, R, W, B, B. Interchange the second and the fourth elements of x to obtain x = R, R, B, W, R, B. One can observe in a) that a transformation D(x) → D(x ) resembles a 2-break. A transformation H(x, y) → H(x , y) is a 2-break that preserves the bipartite structure of a graph as shown in b). Two interchanges are enough to transform x into y. We proceed with an illustration of a polynomial reduction from DNF to MIN-cost-TD mentioned in Section 2.7.4. Make the cost of a transposition (ij) to be 0 if y[i] = y[j] and 1 otherwise. Permutation σ 1 = (24)(35), satisfies x[i] = y[σ 1 (i)], and so does σ 2 = (124365). The minimum cost of a transposition decomposition for both of these permutations is equal to 2, which is also the minimum number of interchanges required to transform x to y. Transpositions (24) and (35) of cost 1 transform σ 1 to id. Transpositions (16) and (34) of cost 1 transform σ 2 into σ 2 = (231)[START_REF] Hartmann | An exact algorithm for sorting by weighted preserving genome rearrangements[END_REF], which can be transformed to id with the help of three transpositions of cost 0.

Figure 2 . 8 :

 28 Figure 2.8: On the left we have an instance of the Token Swapping problem where the tokens 1, 2, 3, 4, 5 are placed on the vertices 3, 5, 2, 1, 4.To this instance we assign a permutation σ 1 = (13254). A swap of the tokens lying on the vertices 4 and 5 provide us with a permutation σ 2 = (1324), which is equal to (45)σ 1 . A further swap of the tokens lying on the vertices 2 and 3, provide us with a permutation σ 3 = (124), which is equal to (23)σ 2 . This instance of the Token Swapping can be interpreted as the problem of decomposing (13254) into a product of transpositions from the subset {(12), (23), (34), (35), (45)}. A possible decomposition is (45)(23)(12)(23)(34)(23) = (13254).

Theorem 4 .

 4 Take a 2-break scenario ρ of length m for a graph G. D(G, ρ) has a number of connected components k greater than or equal to e(G) -m. Further, there exists an Eulerian decomposition H of G of size k, such that ρ is a shuffle of the 2-break scenarios for its subgraphs. If ρ is parsimonious, then H is an MAECD of G.

  H i . D(G, ρ 0 ) has 2e(G) connected components. The l-th 2-break of ρ merges two vertices of D(G, ρ l-1 ). This reduces its number of connected components by at most one. D(G, ρ) is obtained from D(G, ρ m ) after merging e(G) pairs of vertices. This reduces its number of connected components by at most e(G) and establishes that

Figure

  Figure 3.1: An Eulerian 2-edge-colored multigraph G is depicted in a). A parsimonious 2-break scenario ρ = ({2, 3}, {4, 5} → {2, 5}, {3, 4}, gray), ({1, 2}, {5, 6} →

  ), and D(G, ρ 2 ) are depicted in d), e), and f) respectively. All the edges of D(G, ρ 0 ) are both source edges and sink edges. The sink edges of D(G, ρ i ) correspond to the edges of G i , while the source edges of D(G, ρ i ) correspond to the edges of G. Two possibilities for D(G, ρ) are presented in g) and h), depending on which vertices are chosen to be merged. Denote the larger connected component of D(G, ρ) in h) by C 1 . H 1 0 , H 1 1 and H 1 2 are depicted in i), j) and k) respectively. k ≥ e(G) -m. If ρ is parsimonious, then m = e(G) -c(G) using Lemma 1 and thus k ≥ c(G). Due to the maximality of c(G), G can be partitioned into at most c(G) edge-disjoint Eulerian subgraphs. Due to the result obtained in the previous paragraph, we obtain that k = c(G) and H = {H 1 , . . . , H k } is an MAECD of G.

Observation 17 .

 17 A simple non-circle subgraph of G is a union of an AA and a BB path. See Figure 3.2 for an example. Denote by B(G) a complete bipartite graph having the AA and the BB paths of G as vertices. Due to Lemma 13 and Observation 17 we obtain the following result. Lemma 14. A Maximum Alternating Edge-disjoint Cycle Decomposition of a breakpoint graph G can be identified with a perfect matching of B(G) plus the set of the circle subgraphs of G.

Figure 3 . 2 :

 32 Figure 3.2: An example of a breakpoint graph is depicted that contains a single circle subgraph denoted by C. It also contains two AA paths AA 1 and AA 2 , and two BB paths BB 1 and BB 2 . This breakpoint graph has only two possible MAECDs that are {C, AA 1 ∪ BB 1 , AA 2 ∪ BB 2 } and {C, AA 1 ∪ BB 2 , AA 2 ∪ BB 1 }.

Figure 3 . 3 :

 33 Figure 3.3: In a 1 ) the adjacency graph AG(A, B) is depicted consisting of an AA and a BB path. The two ways to join these paths into a cycle are depicted in a 2 ) and a 3 ). In b 1 ) a subgraph of the breakpoint graph G(A, B) is depicted. It is a simple cycle obtained by eliminating the colored edges ({•, •}, black) and ({•, •}, gray). b 2 ) andb3 ) depict the circles obtained once its vertex • is split into two vertices • 1 and • 2 . These circles correspond to the cycles depicted in a 2 ) and a 3 ). Proposition 6 from Braga and Stoye[START_REF] Marília | The solution space of sorting by DCJ[END_REF] can be interpreted as stating that a parsimonious 2-break scenario for the simple cycle in b 1 ) corresponds to a parsimonious 2-break scenario for one of the two circles. In this section establish an analogous result for all the simple cycles and the 2-break scenarios that are not necessarily parsimonious.

Figure 3 . 4 :

 34 Figure 3.4: This is an illustration for Lemma 15. It depicts an Eulerian tour ∆ starting at the central vertex with black and gray degrees equal to 4. Dashed arrows here represent the portions of the tour that do not visit v. For this example the sequence of the colors used in the proof is {black, black, gray, gray, black, black, gray, gray}. In this case col 2i-1 = col 2i , for all i, however the contiguous subsequence of ∆ starting with the colored edge indexed by 1 and finishing with the colored edge indexed by 4 comprises an alternating cycle.

Figure 3 . 5 :Lemma 16 .Lemma 17 .

 351617 Figure 3.5: An example of a simple cycle S is depicted in a). A subgraph of S induced by the colored edges incident to its double vertex v is presented in b). In total, there are 6 possibilities for such an induced subgraph, modulo an inversion of the colors of the edges. These induced subgraphs are depicted at the top parts of the figures c)-h). At the bottom of the figures c)-h) are depicted the possibilities, modulo an exchange of the names of the vertices v 1 and v 2 , of such induced subgraphs of Ŝ, that are transformed into S once their vertices v 1 and v 2 are merged into v. Lemma 16. Take a simple cycle S with a double vertex v and a simple cycle Ŝ satisfying M ( Ŝ) = S. For a 2-break τ transforming S into some S , there exists a 2-break τ transforming Ŝ into some Ŝ , satisfying M ( Ŝ ) = S and M (τ ) = τ .

Figure 3 . 7 :

 37 Figure 3.7:A simple cycle S with double vertices r and v is depicted in a) together with a 2-break scenario ρ of length 2 transforming S into a terminal graph S. A graph Ŝ1 , that becomes S once the vertices r 1 and r 2 are merged into r, is depicted in b) together with a sequence of 2-breaks ρ1 satisfying M (ρ 1 ) = ρ. For the first 2-break τ 1 in ρ ({r, v}, {u, w} → {r, w}, {u, v}, gray) we have two options for τ1 satisfying M ( τ1 ) = τ 1 : ({r 1 , v}, {u, w} → {r 1 , w}, {u, v}, gray) and ({r 2 , v}, {u, w} → {r 2 , w}, {u, v}, gray). We include the second one into ρ1 . For the second 2-break τ 2 ({r, r}, {v, w} → {r, v}, {r, w}, black) of ρ we also have two options for τ2 satisfying M ( τ2 ) = τ 2 : ({r 1 , r 2 }, {v, w} → {r 1 , w}, {r 2 , v}, black) and ({r 1 , r 2 }, {v, w} → {r 1 , v}, {r 2 , w}, black). We include the second one into ρ1 . ρ1 transforms Ŝ1 into a graph Ŝ1 that is not terminal, indicating that some of the choices should be modified. S contains a black loop incident to r, thus we choose Ŝ2 = Ŝ1 . In the black 2-breaks of ρ1 we swap the vertices v 1 and v 2 to obtain a 2-break scenario ρ2 for Ŝ2 depicted in c). Denote Ŝ2 by S and ρ2 by ρ . We proceed the same way in d) with a circle Ŝ 1 , that becomes S once the vertices v 1 and v 2 are merged into v. Once again we start by choosing ρ 1 , that does not lead to a terminal graph. To deal with this, we have to swap the black edges of Ŝ 1 incident to v 1 and v 2 and swap v 1 and v 2 in the black 2-breaks of ρ 1 to obtain Ŝ 2 and ρ 2 as depicted in e).

Figure 3 . 8 :

 38 Figure 3.8: A circle C of a simple cycle S from Figure 3.7 is presented in a). In b) one of its two Eulerian orientations is depicted. Merge its vertices v 1 and v 2 into v and its vertices r 1 and r 2 into r to obtain an Eulerian orientation -→ S in c). The u-tour of -→ S is the directed alternating Eulerian tour of -→ S starting from u. Its vertex sequence is (u, w, v, r, r, v, u). The colored directed edges of the u-tour of -→ S incident to the second occurrence of v in the vertex sequence of the tour are ((v, u), black) and ((r, v), gray). Rename v to v 2 to obtain ((v 2 , u), black) and ((r, v 2 ), gray). Rename v to v 1 in the rest of the colored directed edges of the tour to obtain ((w, v 1 ), black) and ((v 1 , r), gray). Proceed by renaming r to obtain an Eulerian orientation of a circle of S depicted in d), that provides the u-circle (see Definition 41) of -→ S depicted in e) once its orientation is forgotten. The circles depicted in a) and e) are equivalent, as it suffice to rename the vertices v 1 and v 2 , and r 1 and r 2 in order to transform one circle into another.

Corollary 5

 5 (u-tour of -→ S ). For a single vertex u of a simple cycle S there exists a unique directed alternating Eulerian tour of -→ S starting from u. For a double vertex u of S, there exists a unique directed alternating Eulerian tour of -→ S starting with a black edge from u. We call this tour the u-tour of -→ S . Definition 41 (the u-circle of -→ S and a u-circle of S). For every double vertex v of S perform the following. Rename v with v 2 in the colored directed edges of the u-tour of -→ S incident to the second occurrence of v in the vertex sequence of that tour. Rename the rest of the occurrences of v in the colored directed edges of the u-tour of -→ S with v 1 , thus obtaining a set of the colored directed edges of an Eulerian orientation -→ C of a circle C of S. C is the u-circle of -→ S and a u-circle of S. See Figure 3.8 for an example of the u-circle of -→ S . We define two circles of S to be equivalent if they are equal up to switching the names of the pairs of vertices corresponding to the double vertices of S.

Theorem 6 .

 6 Take a vertex u of a simple cycle S. For a circle C of S there exists a u-circle of S equivalent to C. Proof. Choose an Eulerian orientation -→ C of a circle C. For every double vertex v in S, merge the vertices v 1 and v 2 in -→ C to obtain an Eulerian orientation -→ S of S. From Figure 3.8 it should be clear that the u-circle of -→ S and C are equivalent.

Definition 43 (Observation 19 .Definition 45 (

 431945 Scenario graph). For a circle C and its parsimonious 2-break scenario ρ, define a 1-edge-colored graph S(C, ρ) on the vertices of C. If C has two vertices, then S(C, ρ) contains a single edge incident to them. Otherwise, the edges of S(C, ρ) are the edges of the 2-breaks in ρ.See Figure3.9 a) and b) for an example.Definition 44 (Scenario matching). A parsimonious 2-break scenario ρ for a circle C transforms it into a terminal graph that has equal sets of black and gray edges. Delete its gray edges to obtain a perfect matching of the scenario graph S(C, ρ), that we denote by M(C, ρ). The scenario matching of a parsimonious black-2-break scenario for a circle consists of the edges that are gray in the circle. Circular straight-line drawing of a scenario graph). A circular straight-line drawing of a graph is a drawing on a plane with the vertices of the graph arranged on a circle and the edges drawn as straight lines. If the edges in the drawing do not cross, then the drawing is an embedding.Fix a circular straight-line embedding Σ C of a circle C. The scenario graph S(C, ρ) for a parsimonious 2-break scenario ρ for C also inherits a circular straight-line drawing Σ S(C,ρ) from Σ C . See Figure 3.9 for an example of a scenario graph, scenario matching, and their circular straight-line embeddings. In what follows we will suppose that a circle C comes together with a circular straight-line embedding Σ C .

Figure 3

 3 Figure 3.9: A circular straight-line embedding Σ C of a circle C is depicted in a) on the left. This embedding divides the plane into two faces. f u is unbounded, while f b is bounded. The rest of a) depicts a parsimonious 2-break scenario ρ = {1, 2}, {7, 8} → {1, 8}, {2, 7} , black , {4, 5}, {6, 7} → {4, 7}, {5, 6} , gray , {1, 10}, {8, 9} → {1, 8}, {9, 10} , gray , {3, 4}, {2, 7} → {2, 3}, {4, 7} , black for C. The circular straight-line embedding Σ S(C,ρ) of a scenario graph S(C, ρ) inherited from Σ C is depicted in b). The edges of the scenario graph that are in the scenario matching M(C, ρ) appear dashed in b). The first 2-break τ in ρ transforms C into a union of two circles C 1 and C 2 of C depicted in c). According to the notation to be presented in Subsection 3.5.3, C 1 and C 2 are the sub-circles C[START_REF] Baryshnikov | On stokes sets[END_REF][START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF] and C[START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] of C. What follows is an example for Lemma 19 and Lemma 30 with i = 4 and j = 7. The sub-circles C[START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] and C[START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] are depicted in d) and e). The first 2-break τ in ρ transforms C[START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] into a union of two vertex-disjoint circles C 1 and C 5 as depicted in f). ρ can be partitioned into 2-break scenarios ρ[START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] and ρ[START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF] for the sub-circles C[START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] and C[START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF][START_REF] Amir | String rearrangement metrics: A survey[END_REF], with ρ[START_REF] Amir | String rearrangement metrics: A survey[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] = {4, 5}, {6, 7} → {4, 7}, {5, 6} , gray ,

  Figure 3.9 for an example. If C has two vertices, then the scenario graph of ρ contains a single 1

Figure 3 . 10 :

 310 Figure 3.10: An embedding of a trajectory graph D(C, ρ) for a circle C and its parsimonious 2-break scenario ρ from Figure 3.9 is depicted in a). b) presents another embedding of D(C, ρ), where it is drawn over the embedding Σ S(C,ρ) of the scenario graph from Figure3.9. To each edge and face of Σ S(C,ρ) assign a vertex as depicted in c), and join two vertices if they correspond to a face incident to an edge. The ternary tree thus obtained is, up to minor modifications, equal to D(C, ρ) once the edge labels, colors and orientations are forgotten.

Definition 51 (Theorem 11 .

 5111 Matched quadrangulation of Σ C ). Take a circular straight-line embedding Σ C of a circle C and forget the colors of its colored edges to obtain a regular polygon. If C has two vertices, then keep a single edge joining them to obtain an embedding Σ S . Otherwise, add straight-line edges to obtain an embedding Σ S with all the inner faces being quadrilaterals. We call this embedding a quadrangulation of a regular polygon. A pair of Σ S and its perfect matching M is a matched quadrangulation of Σ C . See Figure3.11 for an example of a matched quadrangulation and an example for Theorem 11. Take a circle C and its matched quadrangulation (Σ S , M). There exists a parsimonious 2-break scenario ρ for which Σ S(C,ρ) = Σ S and M(C, ρ) = M.

Figure 3 .

 3 Figure 3.11: A matched quadrangulation (Σ S , M) of a circular straight-line embedding of a circle is depicted in a) with the matched edges indicated in dashed lines. Following the process described in Theorem 11, we obtain a parsimonious 2-break scenario ρ with the scenario graph and matching of ρ being equal to Σ S and M. ρ is depicted in b)-f). To begin with, Σ S contains a face bounded by the edges {1, 2}, {2, 7}, {7, 8} and {8, 1}, with ({1, 2}, black) and ({7, 8}, black) being the colored edges of C. {1, 2} and {7, 8} do not belong to M, thus we start ρ with a 2-break {1, 2}, {2, 7} → {1, 7}, {2, 8} , black that leaves us with two subcircles C[START_REF] Baryshnikov | On stokes sets[END_REF][START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF] and C[START_REF] Alexeev | Estimation of the true evolutionary distance under the fragile breakage model[END_REF][START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF], for which we proceed with the same process. Σ S contains a face bounded by the edges {1, 8}, {8, 9}, {9, 10} and {10, 1}, with ({9, 10}, black) and ({1, 8}, black) being the colored edges of C[START_REF] Baryshnikov | On stokes sets[END_REF][START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF]. {9, 10} and {1, 8} belong to M, thus we proceed with a 2-break {10, 1}, {8, 9} → {9, 10}, {1, 8} , gray .

  Take a colored edge ({u, v}, col) and its label x provided by λ, we denote this labeled edge by({u, v}, col, x).Definition 57 (O-change). If a set of valid operationsO contains an edge-label change ({a, b}, x); ({a, b}, y); col and (G, λ) contains a labeled edge ({u, v}, col, x), with vertices (u, v) labeled (a, b), then the label of this edge can be changed into y. We denote such a transformation of (G, λ) by ({u, v}, col, x) → ({u, v}, col, y), and call it an O-change.Definition 58 (O-break). If a set of valid operations O contains a 2-break on labels ({a, b}, x), ({c, d}, y) ; ({a, c}, z), ({b, d}, t) ; col and (G, λ) contains labeled edges ({u, v}, col, x) and ({w, s}, col, y), with vertices (u, v, w, s) labeled (a, b, c, d) respectively, then a 2-break {u, v}, {w, s} → {u, w}, {v, s} , col can be performed on G, with the labels of the new colored edges ({u, w}, col) and ({v, s}, col) being z and t. We call such a transformation of a labeled graph (G, λ) an O-break and denote it ({u, v}, x), ({w, s}, y) → ({u, w}, z), ({v, s}, t) , col . Definition 59 (O-scenario and its 2-break-length). An O-scenario for (G, λ) is a sequence of O-changes and O-breaks transforming it into (G, λ), with G being a terminal graph and its multisets of black and gray labeled edges being equal. The number of O-breaks in an O-scenario is its 2-break-length. See Figure 4.2 for an example of an O-scenario. An O-scenario does not necessarily exist for a given (G, λ), however if it exists, then the inequality d Ob (G, λ) ≥ d 2b (G) holds, where d Ob (G, λ) denotes the minimum 2-break-length of an O-scenario, and d 2b (G) is the minimum length of a 2-break scenario for G. Definition 60 (Parsimonious O-scenario). An O-scenario for (G, λ) is parsimonious, if its 2-break-length is exactly d 2b (G). According to this definition a parsimonious O-scenario can contain any number of O-breaks.

Definition 61 (

 61 Underlying 2-break scenario of an O-scenario). Take an O-scenario ρ for a labeled graph (G, λ) and omit the O-changes to obtain a sequence of O-breaks (τ 1 , χ 1 ), . . . , (τ m , χ m ) . The sequence of 2-breaks (τ 1 , . . . , τ m ) is a 2-break scenario for G, we call it the underlying 2-break scenario of ρ.

  changes with at most one O-change per labeled edge of (G, λ), followed by a sequence of O-breaks. See Figure 4.2 for an example of an O-scenario and an illustration of Lemma 25 in which we provide a canonical O-scenario ρ preserving some of the core properties

Figure 4

 4 Figure 4.1:In this figure we provide an example of a pair (O, ϕ) and its completion (O c , ϕ c ). For this we use a single vertex label a and edge labels {x, y, z, t, q, qt, xyz, xyztq}. The figure itself depicts 1-edge-colored directed multigraphs W black {a,a} and W gray {a,a} introduced in Lemma 26 whose directed edges define the edge-label changes in O as follows. An edge-label change γ 1 = ({a, a}, x); ({a, a}, y); black is in O, as a directed edge (x, y)

Figure 4 . 2 :

 42 Figure 4.2: We provide an example of an O c -scenario for a labeled circle using a set of valid operations O c introduced in Figure 4.1. ρ = ({5, 6}, black, y) →

Corollary 8 .

 8 Take a complete pair (O, ϕ) and a labeled circle (C, λ). Either there exists a change-first ϕ-MCPS O-scenario for (C, λ), or MCPS ϕ (C, λ) = ∞.

Definition 67 (

 67 Completion of (O, ϕ)). Construct the completion (O c ,ϕ c ) of (O,ϕ) as follows. To begin with, for every sequence of edge-label changes from O of the form ({a, b}, x 0 ); ({a, b}, x 1 ); col , ({a, b}, x 1 ); ({a, b}, x 2 ); col , . . . , ({a, b}, x m-1 ); ({a, b}, x m ); col add an edge-label change ({a, b}, x 0 ); ({a, b}, x m ); col to O c . A number of different sequences might result in the same edge-label change in O c , define its ϕ c -cost to be the minimum sum of the ϕ-costs of the edge-label changes in such a sequence. For every 2-break on labels ({a, b}, x), ({c, d}, y) ; ({a, c}, z), ({b, d}, t) ; col in O, and a pair of edge-label changes ({a, c}, z); ({a, c}, z ); col and ({b, d}, t); ({b, d}, t ); col in O c , add a 2-break on labels ({a, b}, x), ({c, d}, y) ; ({a, c}, z ), ({b, d}, t ) ; col to O c . A number of different combinations of a 2-break on labels in O and edge-label changes in O c might result in the same 2-break on labels in O c , define its ϕ c -cost as the minimum sum of the ϕ-cost of a 2-break on labels and the ϕ c -costs of the edge-label changes invoking it. Observation 20. (O c , ϕ c ) is complete by construction. See Figure 4.1 for an example of the completion of (O, ϕ) and an illustration for Lemma 26.

  that a parsimonious O c -scenario ρ for (G, λ) exists. By construction, every O c -break in ρ can be replaced with an O-break followed by a pair of O c -changes, and every O c -change can be replaced by a sequence of O-changes to obtain an O-scenario with ϕ-cost equal to ϕ c -cost of ρ. Corollary 8 and Lemma 27 ensure that for every labeled graph there exists a change-first O c -scenario of ϕ c -cost equal the MCPS ϕ -cost of that labeled graph.

Figure 5 . 1 :

 51 Figure 5.1: A labeled simple cycle (S, λ) is depicted in a) with vertex labels represented using different colors. In b) and f) two labeled circles of (S, λ) are presented. They are not isomorphic, as a labeled circle in b) contains a vertex incident to colored edges labeled y and t, while such a vertex does not exist in a labeled circle in f). In c) and g) possible Eulerian orientations of these labeled circles are depicted. Once pairs of vertices {v 1 , v 2 } and {r 1 , r 2 } are merged into v and r, these Eulerian orientations of labeled circles become Eulerian orientations of (S, λ) depicted in d) and h). The vertex sequences of their u-tours (u, w, v, r, r, v, u) and (u, v, r, r, v, w, u). The labeled u-circles obtained from these u-tours following the process detailed in Section 3.4.5 are presented in e) and i). The labeled circles presented in b) and e) are isomorphic, while the ones presented in f) and i) are even equal.

Figure 5 . 2 :

 52 Figure 5.2: In a) an O-scenario ρ for a labeled simple cycle (S, λ) containing a double vertex v is depicted. Vertex colors in the figure represent their labels. ρ is not change-first, as it starts with two O-breaks and finishes with a single O-change. b) depicts a labeled simple cycle ( Ŝ1 , λ1 ) and a sequence ρ1 of two O-breaks and an O-change. (S, λ) can be obtained from ( Ŝ1 , λ1 ) by merging the vertices v 1 and v 2 into v. ρ can be obtained from ρ1 by replacing the occurrences of v 1 and v 2 with v.The ϕ-costs of ρ and ρ1 are equal as v 1 , v 2 , and v have equal labels. In d) an Eulerian orientation of (S, λ) is depicted. Its labeled v-circle, the circle obtained from the Eulerian tour starting from v with a black directed edge, is ( Ŝ1 , λ1 ). Transform ( Ŝ1 , λ1 ) by replacing the labeled edges ({v 1 , u}, black, t) and ({v 2 , w}, black, y) with ({v 2 , u}, black, t) and ({v 1 , w}, black, y) to obtain a simple labeled cycle ( Ŝ2 , λ2 ) presented in d). In the black 2-breaks of ρ1 replace the occurrences of v 1 with v 2 , and those of v 2 with v 1 , to obtain an O-scenario ρ2 for ( Ŝ2 , λ2 ) with ϕ-cost equal to that of ρ. In e) an Eulerian orientation of (S, λ) is depicted whose labeled v-circle is ( Ŝ2 , λ2 ).

5. 4 . 3 Figure 5 . 3 :Lemma 30 .

 435330 Figure 5.3: A parsimonious change-first O-scenario ρ = ({1, 2}, gray, z) → ({1, 2}, gray, x), ({1, 2}, black, y) → ({1, 2}, black, x) for a labeled circle (C, λ) having 2 vertices is depicted in a). The underlying 2-break scenario of ρ is empty, as ρ does not contain any O-breaks. The scenario graph and the scenario matching of ρ coincide and are depicted in dashed in b). The labeled subcircles (C[2, 1], λ x ) and (C[1, 2], λ x ) of C are depicted in c). ρ can be partitioned into ρ 1 = ({1, 2}, gray, z) → ({1, 2}, gray, x) and r 2 = ({1, 2}, black, y) → ({1, 2}, black, x) , that are parsimonious change-first outer-change-free scenarios for (C[2, 1], λ x ) and (C[1, 2], λ x ) respectively.

Definition 74 (Theorem 15 .

 7415 Matched scenario for a sub-circle). A parsimonious O-scenario for a sub-circle C[i, j] is matched, if its scenario matching includes an edge {i, j}. It is non-matched otherwise. Take ρ, a parsimonious matched outer-change-free change-first Oscenario for (C[i, j], λ x ) with i + 3 ≤ j. ρ can be partitioned into an O-break (τ, χ) = ({i, k}, z), ({l, j}, t) → ({i, j}, x), ({k, l}, y) , col {i,j} with i < k < l < j, and parsimonious outer-change-free change-first O-scenarios for (C[i, k], λ z ), (C[k, l], λ y ), and (C[l, j], λ t ) with the O-scenarios for (C[i, k], λ z ) and (C[l, j], λ t ) being matched. Proof. Denote the underlying 2-break scenario of ρ by ρ u . See Figure 5.4 for an example of ρ u . Due to Theorem 8, ρ u contains a 2-break τ = {i, k}, {l, j} →

Figure 5 . 4 :

 54 Figure 5.4: A circular straight-line embedding Σ C of a circle C is depicted in a), while b) presents its sub-circle C[2, 11]. In c) the scenario graph and the matching of an underlying parsimonious 2-break scenario ρ u for C[2, 11] is depicted, with ρ = {7, 8}, {9, 10} → {7, 10}, {8, 9} , black , {6, 7}, {10, 11} →

Figure 5 . 5 :

 55 Figure 5.5: A quadrangulation Q of C[START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF][START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF] is depicted in a). It contains a quadrilater f incident to edge {1, 12} that is depicted in b). When restricted to the sub-circles C[START_REF] Alekseyev | Breakpoint graphs and ancestral genome reconstructions[END_REF][START_REF] Bachmaier | On the hardness of maximum rank aggregation problems[END_REF], C[START_REF] Bachmaier | On the hardness of maximum rank aggregation problems[END_REF][START_REF] Baudet | Sorting by weighted inversions considering length and symmetry[END_REF] and C[START_REF] Baudet | Sorting by weighted inversions considering length and symmetry[END_REF][START_REF] Bérard | Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes[END_REF], Q provides quadrangulations depicted in c), d) and e).

ϕ u [n, 1 ,

 1 y] = ∞ and ϕ m [n, 1, y] = W gray {a,b} (x, y), with a and b being the labels of n and 1.

Proof.

  First we show that ϕ m [i, j, x] is greater than or equal to the proposed expression. If ϕ m [i, j, x] = ∞, then this inequality is trivially true. Otherwise, due to Lemma 25, there exists a parsimonious change-first outer-change-free matched O-scenario ρ for (C[i, j], λ x ) with ϕ-cost equal to ϕ m [i, j, x]. Due to Theorem 15, it can be partitioned into a matched O-break (τ, χ) = ({i, k}, z), ({l, j}, t) → ({i, j}, x), ({k, l}, y) , col {i,j} and parsimonious outer-change-free O-scenarios ρ 1 , ρ 2 and ρ 3 for the sub-circles (C[i, k], λ z ), (C[k, l], λ y ) and (C[l, j], λ t ), with ρ 1 and ρ 3 being matched. This establishes an inequality ϕ m

  then this inequality is trivially true. Otherwise take parsimonious outer-change-free O-scenarios ρ 1 , ρ 2 , andρ 3 of ϕ-costs ϕ m [i, k, z], ϕ[k, l, y],and ϕ m [l, j, t], for the labeled sub-circles (C[i, k], λ z ), (C[k, l], λ y ), and (C[l, j], λ t ) respectively, with ρ 1 and ρ 3 being matched O-scenarios. The sequence obtained by performing ρ 1 and ρ 3 , followed by (τ, χ) and ρ 2 is a parsimonious matched outer-change-free O-scenario for (C[i, j], λ x ). Thus establishing ϕ m

Figure 5 . 6 :

 56 Figure 5.6: A labeled simple cycle of a labeled breakpoint graph is depicted in a). Its four labeled Eulerian orientations are given in b1), b2), c1) and c2). By inverting the directions of the labeled edges of the labeled Eulerian orientation in b1) we obtain that in b2). Their labeled 1-circles are isomorphic, and that of b1) is depicted in b3). The same is true for the figures in c1), c2) and c3). Due to reasons explained in Theorem 14, every labeled circle of this labeled simple cycle is isomorphic to either a labeled circle in b3) or that in c3).

GTheorem 18 .

 18 has O(n) AA and BB paths forming O(n 2 ) simple non-circle subgraphs each containing O(n) edges. If the MCPS ϕ -cost of a labeled circle with r edges can be computed in O(r t ) time for some constant t ≥ 1, then B(G) edges can be weighted in O(n t+2 ) time. The minimum weight perfect matching of B(G) can be found in O(n 3 ) time using the Hungarian algorithm, which leads to an O(n t+2 ) time algorithm for the ϕ-MCPS problem on a labeled breakpoint graph. In what follows we use amortized analysis to show that its time complexity is actually O(n t+1 + n 3 ). Denote by p and c the number of AA paths and circle subgraphs in a breakpoint graph G. By construction, G has an equal number of AA and BB paths. Denote by P the number of colored edges of G that belong to an AA or a BB path. Denote by Q the number of its colored edges that belong to a circle subgraph. For some function f and an O(f (r)) time algorithm for ϕ-MCPS on a labeled circle with r colored edges, there exists an O(p 2 f (P ) + p 3 + cf (Q)) time algorithm for ϕ-MCPS on a labeled breakpoint graph. If f (r) = O(r t ) for some constant t ≥ 1, then the MCPS ϕ -cost of a labeled breakpoint graph can be computed in O(pP t

Figure 7 . 1 :

 71 Figure 7.1: Un 2-break transforme une paire d'arêtes {u, v} et {w, s} en {u, w} et {v, s}, ou {u, s} et {v, w}.

  Definition 5 (Vertices, edges and color of a 2-break). The vertices and edges of a 2-break τ = {u, v}, {w, s} → {u, w}, {v, s} , col , are respectively u, v, w, s and {u, v}, {w, s}, {u, w}, {v, s} . Its color is col. We say that τ replaces colored edges ({u, v}, col) and ({w, s}, col) and introduces colored edges ({u, w}, col) and ({v, s}, col). If a 2-break scenario ρ for G contains a 2-break replacing a colored edge ({i, j}, col), then either it is already present in G or ρ contains a 2-break introducing this labeled edge.

	Observation 1. Definition 7 (Black-2-break scenario and its minimum length d b2b (G)). A black-2-
	break scenario is a 2-break scenario consisting entirely of black 2-breaks. Denote the
	minimum length of a black-2-break scenario for a graph G by d b2b (G).
	Definition 6 (2-break scenario for a graph and its minimum length d 2b (G)). A 2-
	break scenario for a graph is a sequence of 2-breaks transforming it into a terminal
	graph. Denote the minimum length of a 2-break scenario for G by d 2b (G).

then it is an AA (respectively BB) path of AG(A, B). Definition 17 (AA/BB paths of G(A, B)). Take a connected non Eulerian sub- graph H of G(A, B) in which the black and gray degrees of every vertex different from • are equal to 1. If the black and gray degrees of • are respectively equal to

	For every internal adja-
	cency {a, b} ∈ A (respectively B) there is a colored edge ({a, b}, black) (respectively
	({a, b}, gray)) in G(A, B), and for every external adjacency {a} ∈ A (respectively B)
	there is a colored edge ({a, •}, black) (respectively ({a, •}, gray)) in G(A, B). There
	is also a number of loops ({•, •}, black) and ({•, •}, gray) in G(A, B) ensuring that
	the black and gray degrees of • are equal to 2n.
	Observation 5. The genome breakpoint graph is Eulerian.
	Definition 16 (AA/BB paths of AG(A, B)). Take a connected component of the
	adjacency graph AG(A, B) that is an even length path. If it starts in A (respectively
	B), 2
	and 0, then H is an AA path of G(A, B). If these degrees are respectively equal to
	0 and 2, then H is a BB path of G(A, B).
	See Figure 2.4 for an example of AA and BB paths of

  B) is a black 2-break. In addition to that, for a black 2-break G(A, B) → G there exists a genome A such that the transformation A → A is a DCJ and G(A , B) = G . For genomes A and B one has d aDCJ (A, B) = d 2b (G(A, B)).

		G(A , B). If col is gray, then δ(τ ) can be performed on B to obtain a genome B
		such that G(A, B) = G(A, B ). This means that ∆(ρ) transforms A and B into
		genomes Ā and B, such that G( Ā, B) is a terminal graph. This implies that the sets
		of adjacencies of Ā and B are equal, and thus ∆(ρ) is a DCJ scenario for A and B.
		Now take a DCJ δ transforming A into some genome A . If δ is among the
		first three types in Definition 11, then τ (δ) can be performed on G(A, B) to obtain
		G(A , B). The only non trivial case is if δ = {a, b} → {a}, {b} , A for some ex-
		tremities a and b. In this case τ (δ) = {a, b}, {•, •} → {a, •}, {b, •} , black . In
		order for τ (δ) to be a 2-break for G(A, B), it must contain a self loop ({•, •}, black).
		However such a loop is present, since A contains an internal adjacency {a, b}, thus
		it contains at most 2n -2 external adjacencies and the black degree of • in G(A, B)
		is 2n by construction. This means that a 2-break τ (δ) can be performed on G(A, B)
		to obtain G(A , B). An analogous observation stays valid for a DCJ δ transforming
		genome B. This means that ρ(∆) transforms G(A, B) into a graph G(C, C) for
		some genome C, and this graph is terminal by construction. Thus ρ(∆) is a 2-break
		scenario for G(A, B).
		Corollary 3.
	Definition 18 (DCJ of a 2-break and 2-break of a DCJ). Take a DCJ δ transforming
	adjacencies of either genome A or B. The four DCJ types presented in Definition 11
	correspond to the four following 2-breaks in the same order:
	1.	{a, b}, {c, d} → {a, c}, {b, d} , col ,
	2.	{a, b}, {c, •} → {a, c}, {b, •} , col ,
	3.	{a, •}, {b, •} → {a, b}, {•, •} , col ,
	4.	{a, b}, {•, •} → {a, •}, {b, •} , col ,
	with col = black if δ transforms A and col = gray if δ transforms B. This correspon-
	dence is used to define the notions of the DCJ of a 2-break and the 2-break of a DCJ.
	For example, we say that {a, b}, {•, •} → {a, •}, {b, •} , black is a 2-break τ (δ)
	of a DCJ δ = {a, b} → {a}, {b} , A , and that {a}, {b} → {a, b} , B is
	a DCJ δ(τ ) of a 2-break τ = {a, •}, {b, •} → {a, b}, {•, •} , gray .
	Theorem 1. Take a DCJ scenario ∆ = (δ 1 , . . . , δ m ) for genomes A and B. ρ(∆) =
	(τ (δ 1 ), . . . , τ (δ m )) is a 2-break scenario for G(A, B). Take a 2-break scenario ρ =
	(τ 1 , . . . , τ m ) for G(A, B). ∆(ρ) = (δ(τ 1 ), . . . , δ(τ m )) is a DCJ scenario for A and B.
	Proof. Take a 2-break τ of color col transforming G(A, B) to G(A, B) . If col is
	black, then δ(τ ) can be performed on A to obtain a genome A such that G(A, B) =

1 h 3 h )(2 t 4 t ). See Section 2.8 for a quick explanation. Definition 22 (2-break τ (π, col) of a colored transposition). Take a transposition π = (ij), a color col and a graph H(σ 1 , σ 2 ). Denote the unique edges of color col in H(σ 1 , σ 2 ) incident to vertices i t and j t by ({k

  for D(σ) and D(πσ). The permutation breakpoint graphs H(σ, id) and H(πσ, id) depicted in b) differ by a 2break {1 h , 2 t }, {3 h , 4 t } → {1 h , 4 t }, {3 h , 2 t } , black . Two positive genomes (see Definition 28) A and A are depicted in c). The DCJ transforming one into another is a circular excision. A positive genome B is depicted in d). H(σ, id) in b) is an internal genome breakpoint graph (see Definition 27) of A and B, while H(πσ, id) in b) is that of A and B. A graph H that can be obtained from H(A, B) via a non preserving 2-break (see Definition 23) {1 h , 2 t }, {3 h , 4 t } → {1 h , 3 h }, {2 t , 4 t } is presented in e). This 2-break does not belong to any parsimonious 2-break scenario for H(A, B). On a side note, in [46] a genome A gets assigned permutations π chr = (1 t 2 t 3 t 4 t 5 t 6 t )(6 h 5 h 4 h 3 h 2 h 1 h ) and π adj = (1 h 2 t )(2 h 3 t )(3 h 4 t )(4 h 5 t )(5 h 6 t )(6 h 1 t ), while the DCJ transforming A into A is interpreted as a pair of transpositions (h , i t }, col) and ({l h, j t }, col). The 2-break τ (π, col) is {k h , i t }, {l h , j t } → {k h , j t }, {l h , i t } , col . (π, col) transforms H(σ 1 , σ 2 ) into H(πσ 1 , σ 2 ) if col is black and H(σ 1 , πσ 2 ) otherwise. Take a preserving 2-break τ for H(σ 1 , σ 2 ). τ transforms H(σ 1 , σ 2 ) into H(π(τ )σ 1 , σ 2 ) if it is black, into H(σ 1 , π(τ )σ 2 ) otherwise.Proof. Take a Minimum Length Transposition Decomposition (π 1 , . . . , π m ) of σ. Due to Observation 8, a 2-break τ (π i , black) transforms H(π i-1 . . . π 1 σ, id) to H(π i π i-1 . . . π 1 σ, id), and thus ρ = (τ (π 1 , black), . . . , τ (π m , black)) transforms H(σ, id) to H(π m . . . π 1 σ, id) = H(id, id), which is a terminal graph. This means that ρ is a black-2-break scenario for H(σ, id) and establishes that m ≥ l.

	Observation 9. Lemma 7. All the 2-breaks in a parsimonious 2-break scenario for a positive circular
	graph are preserving.
	Proof. It is enough to show that the first 2-break τ of a parsimonious 2-break sce-
	nario for a positive circular graph is preserving. τ replaces two colored edges of the
	same circle and transforms it into a union of vertex disjoint circles due to Corollary 2.
	Figure 2.5 b) and e) illustrate that the obtained circular graph is positive.
	Lemma 8. Take an MLTD (π 1 , . . . , π m ) of σ. (τ (π 1 , black), . . . , τ (π m , black)) is a
	parsimonious black-2-break scenario for H(σ, id). Take a parsimonious black-2-break
	scenario (τ 1 , . . . , τ l ) for H(σ, id). (π(τ 1 ), . . . , π(t l )) is an MLTD of σ.
	Now take a parsimonious black-2-break scenario (τ 1 , . . . , τ
	Observation 8. A 2-break τ Definition 23 (Preserving 2-break). A 2-break for a positive circular graph is pre-
	serving, if it transforms it into another positive circular graph.
	Definition 24 (Transposition π(τ ) of a preserving 2-break τ ). Exactly two vertices
	of a preserving 2-break τ are in V t , denote them by i t and j t . The transposition π(τ )
	is (ij).

l ) transforming H(σ, id) into a terminal graph H(σ, id). Due to Lemma 7, all the 2-breaks in the scenario are preserving. Due to Observation 9,

  ). A vertex is single if its black and gray degrees are equal to 1 and it is multiple if these degrees are larger. Definition 35 (Breakpoint graph). A graph is a breakpoint graph if it has at most one multiple vertex. If such a vertex exists, denote it by •. Definition 36 (Simple and circle subgraphs). A subgraph is a simple subgraph if it is a simple cycle and a circle subgraph if it a circle (see Definition 9). A subgraph is a simple non-circle subgraph if it is a simple cycle that is not a circle. Proof. Take a circle subgraph C of a breakpoint graph G and its MAECD H. If C does not include the multiple vertex •, then it is a connected component of G that is a simple cycle and thus appears in all the MAECDs of G. Suppose that C does include the multiple vertex •. Take the black edge of C incident to •. This colored edge belongs to some Eulerian simple cycle H in H. Take an Eulerian tour ∆ of H starting from • with this colored edge. All the vertices of G except • are single, this means that ∆ finishes at • with a gray edge. H being a simple cycle means that H = C, and thus C ∈ H. We define AA and BB paths of a breakpoint graph as in Definition 16. Definition 37 (AA/BB path of a breakpoint graph). Take a connected non Eulerian sub-graph H of G in which the black and gray degrees of every vertex different from • are equal to 1. If the black and gray degrees of • are respectively equal to 2 and 0, then H is an AA path of G. If these degrees are respectively equal to 0 and 2, then H is a BB path of G.

	Observation 16. The genome breakpoint graph (see Definition 15) is a breakpoint
	graph.
	See Figure 3.2 for an example of a breakpoint graph.
	Lemma 13. A circle subgraph of a breakpoint graph belongs to its every MAECD.

  We include the second one into ρ1 . For the second 2-break τ 2 ({r, r}, {v, w} → {r, v}, {r, w}, black) of ρ we also have two options for τ2 satisfying M ( τ2 ) = τ 2 : ({r 1 , r 2 }, {v, w} → {r 1 , w}, {r 2 , v}, black) and ({r 1 , r 2 }, {v, w} → {r 1 , v}, {r 2 , w}, black).

1

, v}, {u, w} → {r 1 , w}, {u, v}, gray) and ({r 2 , v}, {u, w} → {r 2 , w}, {u, v}, gray).

  Definition 50 (Edge count of a 2-break scenario). Take a pair of vertices {u, v}, a color col and a 2-break τ . If τ replaces one colored edge (respectively two colored edges) ({u, v}, col), then its ({u, v}, col)-count is -1 (respectively -2). If τ introduces one colored edge (respectively two colored edges) ({u, v}, col), then its ({u, v}, col)-Take a graph G, a 2-break scenario ρ transforming G into a terminal graph G, and two vertices {u, v} together with a color col. To the number of colored edges ({u, v}, col) in G add the ({u, v}, col)-count of ρ to obtain the number of colored edges ({u, v}, col) in G. This quantity stays the same for an equivalent 2-break scenario, meaning that it also transforms G into a terminal graph G.

	count is 1 (respectively 2). ({u, v}, col)-count of a 2-break scenario is the sum of the
	({u, v}, col)-counts of its 2-breaks.
	Lemma 20. Equivalent 2-break scenarios for a graph transform it into equal termi-
	nal graphs.
	Proof.
	Definition 49 (Equivalent 2-break scenarios). Two 2-break scenarios are equivalent
	if their multisets of 2-breaks are equal.

Lemma 21. Take a parsimonious 2-break scenario ρ for a circle C and a 2-break τ in ρ replacing two colored edges of C. The sequence of 2-breaks with τ performed first and followed by the rest of ρ is a parsimonious 2-break scenario for C.

Proof. Without loss of generality we can suppose that τ does not replace the colored edge ({1, n}, gray). In this case there exists i + 3 ≤ j and a color col, such that τ = {i, i + 1}, {j, j + 1} → {i, j + 1}, {i + 1, j} , col . Due to Theorem 7, there exists a face in the embedding of the scenario graph Σ S(C,ρ) bounded by the edges of τ . Applying Lemma 19 twice we obtain that ρ can be partitioned into parsimonious 2-break scenarios for C[j + 1, i], C[i + 1, j] and τ . Due to Corollary 4, ρ without τ is a is a parsimonious 2-break scenario for the union of C[j + 1, i] and C[i + 1, j], that is a graph obtained from C after τ is performed. This means that moving τ to the beginning of ρ we obtain a parsimonious 2-break scenario for C. Theorem 10. The scenario graphs and matchings of two parsimonious 2-break scenarios for a circle are equal if and only if these scenarios are equivalent.

  Take a 2-break τ in a parsimonious black-2-break scenario ρ for H(σ, id). Due to Lemma 8, τ is a preserving 2-break and thus of the form {u h , v t }, {w h , s t } → {u h , s t }, {w h , v t } , black for some u, v, w, s ∈ {1, . . . , n}. The bijection in Lemma 8 works by transforming τ into its transposition π(τ ) = (vs). The multisets of 2-breaks of two equivalent black-2-break scenarios are equal, this means that the multisets of transpositions of the MLTDs obtained for them in Lemma 8 are also equal.

	Two transposition de-
	compositions of a permutation are equivalent if their multisets of transpositions are
	equal.
	Lemma 22. Take two equivalent parsimonious black-2-break scenarios for H(σ, id).
	The MLTDs obtained for them in Lemma 8 are also equivalent.
	Proof.

  in the worst case.Proof. For a color col ∈ {black,gray} and a pair of vertex labels {a, b}, define an edge-weighted 1-edge-colored directed multigraph W col {a,b} with a vertex set Σ E . For an edge-label change ({a, b}, x); ({a, b}, y); col in O, add a directed edge (x, y) in W col {a,b} of weight ϕ ({a, b}, x); ({a, b}, y); col . For a pair of edge labels {x, y}, an edge-label change ({a, b}, x); ({a, b}, y); col is in O c if and only if a path from x to y exists in W col {a,b} . Further, its ϕ-cost is equal to the minimum weight of such a path. Johnson's algorithm [63] can be used to find the minimum weight paths between all the pairs of vertices in W col {a,b} in O(|Σ E | 3 ) time. This operation has to be repeated for the |E V | 2 pairs of vertex labels and two different colors, thus ϕ c -costs of the edge-label changes in O c can be computed in O(|E V | 2 |Σ E | 3 ) time. Take a 2-break on labels ({a, b}, x), ({c, d}, y) ; ({a, c}, z), ({b, d}, t) ; col in O and a pair of edge labels {z , t }. If edge-label changes ({a, c}, z); ({a, c}, z ); col and ({b, d}, t); ({b, d}, t ); col are in O c , then it also contains a 2-break on labels ({a, b}, x), ({c, d}, y) ; ({a, c}, z ), ({b, d}, t ) ; col . One can iterate through 2breaks on labels in O and the pairs of edge labels in O(|O||Σ E | 2 ) time. If one can check in constant time whether an edge-label change is present in O c , then the 2breaks on labels in O c and their ϕ c -costs can also be obtained in O(|O||Σ E | 2 ) time. The size of O is O(|Σ V | 4 |Σ E | 4 ) in the worst case, which means that O

Definition 68 (

 68 Labeled subgraph). (H, λ H ) is a labeled subgraph of a labeled graph (G, λ), if H is a subgraph of G and λ H coincides with λ on the vertices and the colored edges of H. Definition 69 (Labeled Eulerian decomposition (ED) and its MCPS ϕ -cost). H = {(H 1 , λ H 1 ), . . . , (H k , λ H k )} is a labeled Eulerian decomposition of a labeled graph (G, λ), if the following properties hold:

  which is ({i, j}, gray) if i is odd, and ({i, j}, black) otherwise. Denote the color of this edge by col {i,j} , and the opposite color by col {i,j} .Definition 72 (x-labeled sub-circle). (C[i, j], λ) is a labeled sub-circle of (C, λ), if the labels of all the colored edges of C[i, j] except ({i, j}, col {i,j} ) and the labels of its vertices coincide with the labels given by λ. If the label of the colored outer edge ({i, j}, col {i,j} ) of C[i, j] is x, then (C[i, j], λ) is the x-labeled sub-circle of (C, λ), we denote it by (C[i, j], λ x ).

  to compute MCPS ϕ (C, λ). Denote the labels of the vertices 1 and n, by a and b, and denote the label of the colored edge ({1, n}, gray) by x. MCPS ϕ (C, λ) for a labeled circle is equal to:

	Lemma 34. min min y∈Σ E	ϕ

m [1, n, y] + W gray {a,b} (x, y) , min y∈Σ E ϕ u [1, n, y] + W gray {a,b} (x, y) Lemma 35. Denote the labels of the vertices 1 and n, by a and b, and denote the label of the colored edge ({1, n}, gray) by x. MCPS ϕ (C, λ) for a labeled circle is equal to min y∈Σ E ϕ[1, n, y] + W gray {a,b} (x, y) Proof. We first show that MCPS ϕ (C, λ) is larger than or equal to the proposed expression. If MCPS ϕ (C, λ) = ∞, then this inequality is trivially true. Otherwise due to Corollary 8 and the completeness of (O, ϕ) there exists a change-first ϕ-MCPS O-scenario ρ for (C, λ). Such a ρ contains at most one O-change that modifies a labeled edge ({n, 1}, gray, x). If such an O-change does not exist, then ρ is outer-change-free and MCPS ϕ (C, λ) is larger than or equal to ϕ[1, n, x]. If such an O-change exists, then denote it by µ and denote the label it provides by x . ρ with µ removed is a parsimonious outer-change-free O-scenario for (C[1, n], λ x ).

This means that MCPS ϕ

  (d 1 , . . . , d c ) denote the numbers of colored edges in the circle subgraphs of G. By definition c i=0 d i = Q. The MCPS ϕ -cost of these c circles can be computed in c Q t steps. Let (a 1 , . . . , a p ) and (b 1 , . . . , b p ) denote the numbers of the colored edges in the AA and the BB paths. Denote p i=0 a i by P A and p j=0 b j by P B . By definition P = P A + P B . As explained above, the MCPS ϕcost of a union of an AA path and a BB path having a and b colored edges can be computed in at most k(a + b) t steps by computing the MCPS ϕ -costs of at most two labeled circles with a + b colored edges. The MCPS ϕ -cost of every pair of an AA and a BB path can be computed in a number of steps bounded by:

	i=0	k 2 d t i ≤ 2 4

La principale contribution de cette thèse est la suivante. Nous présentons un cadre sur le modèle de réarrangements double cut and join avec des poids arbitraires. Dans ce cadre un scénario de poids minimum peut être trouvé en temps polynomial parmi les scénarios de longueur minimale pour deux génomes à contenu génétique identique et sans doublons.En plus de cela, nous établissons un certain nombre de nouvelles correspondances entre les divers problèmes de tri. Ces problèmes incluent le tri des génomes avec des réarrangements dits double cut and join, le tri des graphes avec 2-breaks ou edge swaps, le tri des permutations avec des transpositions, le tri des chaînes avec des échanges et l'échange de jetons sur les graphes.Mots clés: scénario évolutif de réarrangements, double cut and join, réarrangements génomiques pondérés, décomposition de la permutation en transpositions, quadrangulation de poids minimum.

Chapter 4

Cost Constrained 2-break Scenarios

Introduction

In this chapter we present our model for assigning costs to 2-break scenarios and introduce the problem of finding a minimum cost scenario among those of minimum length, the ϕ-Minimum Cost Parsimonious Scenario problem, that will be treated in Chapter 5.

In [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] we proposed a method to cost constrain DCJs based on the spatial proximity of the intergenic regions, as it is one of the biological triggers for genome rearrangements [START_REF] Mani | Triggers for genomic rearrangements: insights into genomic, cellular and environmental influences[END_REF]. We labeled edges of the genome breakpoint graph with the spatial positions of the corresponding genome adjacencies, and allowed a 2-break to transform two edges labeled x and y into 2 new edges with the same labels. Within this model the cost of a 2-break is 0 if the labels are equal and 1 otherwise. We posed the Minimum Local Parsimonious Scenario problem (MLPS) of finding a parsimonious 2-break scenario minimizing the sum of the costs of its 2-breaks.

Around the same time Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] proposed a method to cost constrain DCJs based on the lengths of the intergenic regions. Here once again edges of the breakpoint graph were labeled, however an additional operation, that of changing an edge label, was allowed. The Sorting by wDCJs and Indels in Intergenes problem (presented in Subsection 4.3.2), asked for an optimal 2-break scenario among the parsimonious ones. Bulteau, Fertin, and Tannier [START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF] proposed a polynomial time algorithm solving this problem for a circle.

In [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF] we also started our work on MLPS by providing a polynomial time algorithm solving it for a circle. We then proceeded by showing how this algorithm can be used as a sub-routine to solve MLPS for the genome breakpoint graph. We soon realized that our method could be extended beyond the breakpoint graphs, Chapter 5

Minimum Cost Parsimonious Scenario

Introduction

In this chapter we treat the MCPS problem. The central result is a polynomial time dynamic programming algorithm for MCPS on a labeled circle for a complete pair (O, ϕ). The MCPS problem is NP-hard in general due to the NP-hardness of finding a Maximum Alternating Edge-disjoint Cycle Decomposition of a graph [START_REF] Bienstock | A degree sequence problem related to network design[END_REF], nevertheless we demonstrate that our algorithm for a labeled circle can be used as a subroutine to solve MCPS for any labeled graph. This results in a proof that MCPS remains polynomial time solvable for a labeled breakpoint graph.

We build on the work presented in Chapter 3. The Labeled Eulerian decomposition, the labeled trajectory graph, the labeled circle of a simple cycle, and the labeled sub-circle are natural generalizations of the structures previously used to study parsimonious 2-break scenarios. We show that the proofs from Chapter 3 can be adapted to this labeled setting and prove the following. First we show that the MCPS ϕ -cost of a labeled graph is equal to the minimum of the MCPS ϕ -costs of its labeled Maximum Alternating Edge-disjoint Cycle Decompositions. We proceed by establishing that the MCPS ϕ -cost of a labeled simple cycle is equal to the minimum of the MCPS ϕ -costs of its labeled circles. Finally we show that a parsimonious Oscenario for a circle can be partitioned into parsimonious O-scenarios for its labeled sub-circles, which leads to a dynamic programming algorithm for MCPS. Its worst case time complexity is O(n 4 L 4 ), where n is the number of vertices in a circle and L is the number of edge labels used in O.

Our algorithm is general in that it works with an arbitrary cost function. If a particular cost function ϕ is chosen, then its combinatorial properties might be exploited to come up with a faster algorithm for a particular ϕ-MCPS problem. No-

An ILP for ϕ-MCPS

In the following sections we will show how to compute the MCPS ϕ -costs of labeled simple cycles of a labeled graph. Once these costs are known, Theorem 13 leads to a straightforward ILP computing the MCPS ϕ -cost of (G, λ).

Denote by S a set of the simple cycles of G. For every simple cycle S in S assign a variable x S , with x S equal to 1 if S belongs to a cycle packing and 0 otherwise. Denote by E a set of the colored edges present in G and by mult(G, e) the multiplicity of a colored edge e in G. Start by computing the size of an MAECD of G by packing as many simple cycles in G as possible.

Maximize S∈S x S Subject to S:e∈S x S mult(S, e) ≤ mult(G, e) for e ∈ E, and x S ∈ {0, 1} for S ∈ S.

Now denote by S λ a set of the labeled simple cycles that are labeled subgraphs of (G, λ), by E λ a set of the labeled edges present in (G, λ), by mult λ ((G, λ), e) the multiplicity of a labeled edge e in (G, λ), and by c(G) the size of an MAECD of G. The following ILP computes MCPS ϕ (G, λ).

Subject to (S,λ S ):e∈S λ x (S,λ S ) mult λ ((S, λ S ), e) ≤ mult λ ((G, λ), e) for e ∈ E λ , (S,λ S )∈S λ x (S,λ S ) = c(G) and x (S,λ S ) ∈ {0, 1} for (S, λ S ) ∈ S λ .

ϕ-MCPS for Isomorphic Labeled Graphs

In this subsection we introduce a notion of isomorphic labeled graphs and establish in Lemma 29 that their MCPS ϕ -costs are equal. It will be used in the following section where we show that for a labeled circle of a labeled simple cycle there exists an isomorphic labeled u-circle. Similarly, in Theorem 6 we have shown that for a circle of a simple cycle there exists an equivalent u-circle.

Definition 70 (Isomorphism of labeled graphs). Two labeled graphs (G 1 , λ 1 ) and (G 2 , λ 2 ) on vertices V are isomorphic if there exists a function g : V → V for which the following properties hold:

• For every vertex v the labels of v in (G 1 , λ 1 ) and g(v) in (G 2 , λ 2 ) are equal.

• For every colored edge ({u, v}, col) the multisets of edge labels of ({u, v}, col) in (G 1 , λ 1 ) and of ({g(u),

Such a function g is an isomorphism of (G 1 , λ 1 ) and (G 2 , λ 2 ).

See Figure 5.1 for an example of isomorphic and non-isomorphic labeled circles.

Lemma 29. The MCPS ϕ -costs of two isomorphic labeled graphs are equal.

Proof. Take a pair of isomorphic labeled graphs (G 1 , λ 1 ) and (G 2 , λ 2 ) together with their isomorphism g and a labeled edge ({u, v}, col, x) of (G 1 , λ 1 ). By definition (G 2 , λ 2 ) contains a labeled edge ({g(u), g(v)}, col, x) and vertex labels of u and g(u), and v and g(v) are equal. This means that the ϕ-costs of O-changes ({u, v}, col, x) → ({u, v}, col, y) and ({g(u), g(v)}, col, x) → ({g(u), g(v)}, col, y) are also equal. In addition to that they transform (G 1 , λ 1 ) and (G 2 , λ 2 ) into isomorphic labeled graphs with g being their isomorphism. An analogous result can be established for an Ochange transforming (G 1 , λ 1 ). Taken together these observations show that to a ϕ-MCPS O-scenario for (G 1 , λ 1 ) we can assign an O-scenario for (G 2 , λ 2 ) of equal ϕ-cost. We can do the same for a ϕ-MCPS O-scenario for (G 2 , λ 2 ) which finishes the proof.

ϕ-MCPS for a Simple Cycle

Here we build on Theorem 6 in Section 3.4.5 stating that a 2-break scenario for a simple cycle can be interpreted as a 2-break scenario for its u-circle. We adjust its proof to show that the MCPS ϕ -cost of a labeled simple cycle is equal to the minimum of the MCPS ϕ -costs of its labeled u-circles.

We start by introducing the notion of a labeled circle of a simple cycle. Take a simple cycle S on vertices V . As defined in Section 3.4, a vertex of S is double if its black and gray degrees are equal to two, it is single otherwise. V is a set of vertices in which every double vertex v in S replaced with new vertices v 1 and v 2 . M is a function V → V satisfying M (v) = v for a single vertex of S, and M (v 1 ) = M (v 2 ) = v for a double vertex of S.

Definition 71 (Labeled circle of a simple cycle). A labeled circle (C, λ) is a labeled circle of a simple labeled cycle (S, λ) if the following properties hold:

• C is a circle of S.

• The labels given by λ and λ coincide on the single vertices of S.

• For every double vertex v of S, the labels of v 1 and v 2 given by λ are equal to the label of v given by λ.

• Take a labeled edge ({M (u), M (v)}, col, x) for every labeled edge ({u, v}, col, x) of (C, λ). A multiset of labeled edges thus obtained is equal to the labeled edges of (S, λ).

A Dynamic Programming Algorithm for ϕ-MCPS for a Circle Introduction and Notations

We use Theorem 15 and Theorem 16 to express the minimum ϕ-cost of a parsimonious outer-change-free matched (or non-matched) O-scenario for a labeled subcircle as a sum of these costs for smaller labeled sub-circles. Once these costs are obtained for (C[1, n], λ x ) for every edge label x, we combine them to obtain the minimum ϕ-cost of a parsimonious O-scenario for (C, λ).

Take a complete (O, ϕ) and an embedding Σ C of a labeled circle (C, λ) on n vertices as in Subsection 5.4.2. Denote by ϕ m [i, j, x] (respectively ϕ u [i, j, x]) the minimum ϕ-cost of a parsimonious outer-change-free matched (respectively non-

). Take a labeled edge ({i, i + 1}, col, x) present in (C, λ) and an edge label y with a and b being the labels of i and i + 1. Define W col {a,b} (x, x) = 0. If an edge-label change ({a, b}, x); ({a, b}, y); col is in O, then denote ϕ ({a, b}, x); ({a, b}, y); col by W col {a,b} (x, y), otherwise, define W col {a,b} (x, y) = ∞. Do the same for a labeled edge ({n, 1}, gray, x) in (C, λ).

Initializing ϕ m and ϕ u

We start by initializing ϕ u and ϕ m for the labeled sub-circles of (C, λ) on two vertices. Lemma 31. Take a labeled edge ({i, i + 1}, col, x) of (C, λ) and an edge label y.

{a,b} (x, y), with a and b being the labels of i and i + 1. Corollary 10. Take a labeled edge ({n, 1}, gray, x) of (C, λ) and an edge label y.

Proof. C[i, i

The MCPS

ϕ-MCPS for a Breakpoint Graph

In this section we show that the ϕ-MCPS problem for a labeled breakpoint graph can be solved using an algorithm for ϕ-MCPS on a labeled circle as a subroutine. The latter might be either the general dynamic programming algorithm from the previous section, or an algorithm with a lower time complexity specifically tailored for a particular cost function as in [START_REF] Krister M Swenson | Models and algorithms for genome rearrangement with positional constraints[END_REF][START_REF] Bulteau | Genome rearrangements with indels in intergenes restrict the scenario space[END_REF].

A breakpoint graph, as defined in Section 3.3, is a graph with at most one vertex of black and gray degrees larger than 1. Denote this vertex by •. An AA path (respectively a BB path) of a breakpoint graph is an alternating tour of odd length starting from • with a black edge (respectively gray edge). A simple subgraph of a breakpoint graph is either a circle or a union of an AA and a BB path. Denote by B(G) a complete bipartite graph having the AA and the BB paths of G as vertices. Lemma 14 states that a Maximum Alternating Edge-disjoint Cycle Decomposition of a breakpoint graph G can be identified with a perfect matching of B(G) plus the circle subgraphs of G.

Take a pair (O, ϕ) and a labeled breakpoint graph (G, λ) on n vertices. Upon inspection of Figure 5.6 it should be clear that a labeled simple subgraph (S, λ S ) of (G, λ) has at most four labeled Eulerian orientations and two non-isomorphic labeled circles. Due to Theorem 14, MCPS ϕ (S, λ S ) is equal to the minimum of the MCPS ϕ -costs of these labeled circles. Use an algorithm for ϕ-MCPS on a labeled circle to compute the MCPS ϕ -costs of all the simple labeled subgraphs of (G, λ). Weight the edges of B(G) with the MCPS ϕ -costs of the corresponding simple labeled subgraphs. Due to Lemma 14 and Theorem 13, MCPS ϕ (G, λ) is equal to the sum of the MCPS ϕ -costs of the labeled circle subgraphs of (G, λ) plus the minimum weight of a perfect matching of B(G).