La compréhension de la dynamique des réarrangements génomiques est une problématique importante en phylogénie.La phylogénie est l'étude de l'évolution des espèces. Un but majeur est d'établir les relations d'évolution au sein d'un groupe d'espèces, pour déterminer la topologie de l'arbre d'évolution formé par ce groupe et des ancêtres communs à certains sous-ensembles.Pour ce faire, il est naturellement très utile de disposer d'un moyen d'évaluer les distances évolutionnaires relatives entre des espèces, ou encore d'être capable d'inférer à un groupe d'espèces le génome d'un ancêtre commun à celles-ci.Ce travail de thèse, dans la lignée d'autres travaux, consiste à élaborer de tels moyens, ici dans des cas particuliers où les génomes possèdent des gènes en multiples copies, ce qui complique les choses.Plusieurs hypothèse explicatives de la présence de duplications ont été considérées, des formules de distance ainsi que des algorithmes de calcul de scénarios ont été élaborés, accompagnés de preuves de complexité. / Understanding the dynamics of genome rearrangements is a major issue of phylogenetics. Phylogenetics is the study of species evolution. A major goal of the field is to establish evolutionary relationships within groups of species, in order to infer the topology of an evolutionary tree formed by this group and common ancestors to some of these species. In this context, having means to evaluate relative evolutionary distances between species, or to infer common ancestor genomes to a group of species would be of great help.This work, in the vein of other studies from the past, aims at designing such means, here in the particular case where genomes present multiple occurrencies of genes, which makes things more complex. Several hypotheses accounting for the presence of duplications were considered. Distances formulae as well as scenario computing algorithms were established, along with their complexity proofs.

The advent of new technology enhance the speed and reduce the cost for sequencing biological data. Making biological sense of this genomic data is a big challenge to the algorithm design as well as the high performance computing society. There are many problems in Bioinformatics, such as how new functional genes arise, why genes are organized into chromosomes, how species are connected through the evolutionary tree of life, or why arrangements are subject to change. Phylogenetic analyses have become essential to research on the evolutionary tree of life. It can help us to track the history of species and the relationship between different genes or genomes through millions of years. One of the fundamentals for phylogenetic construction is the computation of distances between genomes. Since there are much more complicated combinatoric patterns in rearrangement events, the distance computation is still a hot topic as much belongs to mathematics as to biology. For the distance computation with input of two genomes containing unequal gene contents (with insertions/deletions and duplications) the problem is especially hard. In this thesis, we will discuss about our contributions to the distance estimation for unequal gene order data. The problem of finding the median of three genomes is the key process in building the most parsimonious phylogenetic trees from genome rearrangement data. For genomes with unequal contents, to the best of our knowledge, there is no algorithm that can help to find the median. In this thesis, we make our contributions to the median computation in two aspects. 1) Algorithm engineering aspect, we harness the power of streaming graph analytics methods to implement an exact DCJ median algorithm which run as fast as the heuristic algorithm and can help construct a better phylogenetic tree. 2) Algorithmic aspect, we theoretically formulate the problem of finding median with input of genomes having unequal gene content, which leads to the design and implementation of an efficient Lin-Kernighan heuristic based median algorithm. Inferring phylogenies (evolutionary history) of a set of given species is the ultimate goal when the distance and median model are chosen. For more than a decade, biologists and computer scientists have studied how to infer phylogenies by the measurement of genome rearrangement events using gene order data. While evolution is not an inherently parsimonious process, maximum parsimony (MP) phylogenetic analysis has been supported by widely applied to the phylogeny inference to study the evolutionary patterns of genome rearrangements. There are generally two problems with the MP phylogenetic arose by genome rearrangement: One is, given a set of modern genomes, how to compute the topologies of the according phylogenetic tree; Another is, given the topology of a model tree, how to infer the gene orders of the ancestor species. To assemble a MP phylogenetic tree constructor, there are multiple NP hard problems involved, unfortunately, they organized as one problem on top of other problems. Which means, to solve a NP hard problem, we need to solve multiple NP hard sub-problems. For phylogenetic tree construction with the input of unequal content genomes, there are three layers of NP hard problems. In this thesis, we will mainly discuss about our contributions to the design and implementation of the software package DCJUC (Phylogeny Inference using DCJ model to cope with Unequal Content Genomes), that can help to achieve both of these two goals. Aside from the biological problems, another issue we need to concern is about the use of the power of parallel computing to assist accelerating algorithms to handle huge data sets, such as the high resolution gene order data. For one thing, all of the method to tackle with phylogenetic problems are based on branch and bound algorithms, which are quite irregular and unfriendly to parallel computing. To parallelize these algorithms, we need to properly enhance the efficiency for localized memory access and load balance methods to make sure that each thread can put their potentials into full play. For the other, there is a revolution taking place in computing with the availability of commodity graphical processors such as Nvidia GPU and with many-core CPUs such as Cray-XMT, or Intel Xeon Phi Coprocessor with 60 cores. These architectures provide a new way for us to achieve high performance at much lower cost. However, code running on these machines are not so easily programmed, and scientific computing is hard to tune well on them. We try to explore the potentials of these architectures to help us accelerate branch and bound based phylogenetic algorithms.

In the course of evolution, genomes diverge from their ancestors either via global mutations and by rearrangement of their chromosomal segments, or through local mutations within their genes. In this thesis (Chapters: 2, 3 and 4) we analyze the evolution of genomes based on different rearrangement operations including: in Chapter 2 both restricted and unrestricted double-cut-and-join (DCJ) operations, in Chapter 3 both internal and general reversal and translocation (IRT and HP, respectively) operations, and in Chapter 4 translocation, weighted reversal (WR) and maximum length reversal (MLR) operations. Based on the rearrangement operation chosen we can model the evolution of genomes as a discrete or continuous-time Markov chain process on the space of signed genomes. For each model of evolution, we study the stochastic process by investigating the time up to which the difference between the number of operations along the evolutionary trajectory and the edit distance of the genome from its ancestor is negligible, as soon as these two values starts diverging drastically from one another we say the process escapes from parsimony. One of the major parameters in the known edit distance formulas between any two genomes (such as reversal, DCJ, IRT, HP and translocation) is the number of cycles in their breakpoint graph. For DCJ, IRT and HP models by adopting the method elaborated by Berestycki and Durret, we estimate the number of cycles in the breakpoint graph of the genome at time t and its ancestor by the number of tree components of the random graph constructed from the model of evolution at time t, which is an Erdös-Rényi. We also proved that for each of the DCJ, IRT and HP models of evolution, the process on a genome of size n is bound to its parsimonious estimate up to t ≈ n/2 steps. Since the random graph constructed from the models of evolution for the translocation, WR and MLR processes are not Erdös-Rényi, the proofs of their parsimony- bound require more advanced mathematical tools, however our simulation shows for the translocation, two types of WR, and MLR (except for reversals with very short maximum length) models, the escape from parsimony do not occur before n/2 steps, where n is the number of genes in the genome. A basic result in this field is due to Berestycki and Durrett, from 2006, who found that a random transposition (pairwise exchange of the elements in the corresponding permutation of the genome) evolves along its parsimonious path of evolution up to n/2 steps, where n is the number of the genes. Although, this transposition model is applicable solely for evolution of a unichromosomal ancestor which remains unichromosomal at each step t of the process; however for the DCJ, IRT, HP and translocation models the genomes are multichromosomal which increases the difficulty of the problem at hand. The models studied in Chapters 2 - 4 are all based on signed permutation representations of genomes, where each "gene" occurs exactly once, with either positive or negative polarity. The same genes occur in all the genomes being considered. There is no distinction between the same gene in two different genomes. In Chapter 5 we generalize our representation to genes that may have several copies of a gene, which differ only by a few point mutations. This leads to problems of identifying copies in two genomes that are primary orthologs, under the assumptions of differentials in point mutation rate. We provide algorithms, software and test examples.

La compréhension de la dynamique des réarrangements génomiques est importante en phylogénie. La phylogénie est l'étude de l'évolution des espèces. Un but majeur est d'établir les relations d'évolution au sein d'un groupe d'espèces, pour déterminer la topologie de l'arbre d'évolution formé par ce groupe et des ancêtres communs à certains sous-ensembles. Pour ce faire, il est naturellement très utile de disposer d'un moyen d'évaluer les distances évolutionnaires relatives entre des espèces, ou encore d'être capable d'inférer à un groupe d'espèces le génome d'un ancêtre commun à celles-ci. Ce travail de thèse, dans la lignée d'autres travaux, consiste à élaborer de tels moyens, ici dans des cas particuliers où les génomes possèdent des gènes en multiples copies, ce qui complique les choses. Plusieurs hypotèses explicatives de la présence de duplications ont été considérées, des formules de distance ainsi que des algorithmes de calcul de scénarios ont été élaborés, accompagnés de preuves de complexité.