Evolutionary ancestor inference via genome rearrangement.

摘要

Inferring ancestral gene orders in a phylgenomic tree is an important topic in comparative genomics. In this thesis, three different approaches have been used to infer ancestors, first, using common intervals in a model-free approach and extending it to using common clusters and neighbourhood parameter; second, using double cut and join operation (DCJ); third, using breakpoint distance. A statistically fair comparison between the performance of DCJ and breakpoint criteria ends the thesis.;Noticing the drawback that the concept of common intervals suffers from, we introduce the concept of generalized adjacency to find common clusters using a neighborhood parameter that turns out to be closely related to the bandwidth parameter of a graph. Our focus will be on how this parameter affects the characteristics of clusters: how numerous they are, how large they are, how rearranged they are and to what extent they are preserved from ancestor to descendant in a phylogenetic tree. Again, we use dynamic programming optimization to determine the presence of individual edges at the ancestral nodes of the phylogeny.;The DCJ (double cut and join) operation introduced by Yancopoulos et al. in 2005 is the most inclusive operation to date as it can generate all the movement rearrangements. One year later, Bergeron et al. restated the DCJ model and produced a simplified (linear) algorithm, which is now the most general existing algorithm to transform one genome into another using genome rearrangements events. Motivated by both, the most inclusive operation, DCJ, and its most general algorithm, we study the small phylogeny problem in the space of multichromosomal genomes under the DCJ metric. This is similar to the existing MGR (multiple genome rearrangements) approach, but it allows, in addition to inversion and reciprocal translocation, operations of transposition and block interchange.;Thanks to Tannier et al., the first polynomial solution to the median problem has been found in only one context, namely the case of breakpoint distance on multichromosomal genoms where chromosomes are unconstrained as to linearity or circularity. This motivated us to study the small phylogeny problem using breakpoint median as a third approach, that is different both biologically and computationally from the common intervals and DCJ approaches, and then to compare statistically the performance of both criteria, breakpoint and DCJ.;Away from any assumptions or considerations, probabilistic or combinatorial, about specific processes involved in rearranging genomes, we present a new phylogenetic reconstruction method based solely on common intervals. The objective function to be optimized is simply the sum over the tree branches of the symmetric difference between the two sets of intervals associated with the genomes at the two ends of the branch. To achieve this goal, we use dynamic programming optimization to determine the presence of common intervals at the ancestral nodes of the phylogeny.;Keywords: phylogenetic tree, genome rearrangment, inversion, reciprocal translocation, transposition, block interchange, common intervals, generalized adjacency, neighborhood parameter, graph bandwidth, multiple genome rearrangement (MGR), double cut and join (DCJ), breakpoint (BP), excess explanatory rate.