Duplications and genome rearrangements

Most genome rearrangements (e.g., reversals and translocations) can be represented as 2-breaks that break a genome at 2 points and glue the resulting fragments in a new order. Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While multi-break rearrangements were studied in depth for k = 2 breaks, the k-break distance problem for arbitrary k remains unsolved. In the first part of this dissertation we address several open issues and problems related to the multi-break rearrangements: (1) We prove a duality theorem for the multi-break distance problem between circular genomes and give a polynomial algorithm for computing this distance. (2) In 2003 Pevzner and Tesler [56] refuted the Random Breakage Model (RBM), that had been a de-facto theory of molecular evolution for more than three decades, and introduced a new Fragile Breakage Model (FBM). However, the rebuttal of RBM caused a controversy and led to a split among researchers studying genome evolution. In particular, since the mathematical theory used to refute RBM does not cover more complex rearrangement operations (like transpositions), the Pevzner-Tesler arguments do not apply for the case when transpositions are frequent. We contribute to the ongoing debates on “RBM vs. FBM” controversy by analyzing multi-break rearrangements and demonstrating that even if transpositions were a dominant force in mammalian evolution, the arguments in favor of FBM still stand. (3) We extend the above results to the more difficult case of linear genomes. In particular, we give lower bounds for the rearrangement distance between linear genomes and use these results to analyze comparative genomic architecture of mammalian genomes.;In the second part of this dissertation we study rearrangements in genomes with duplicated genes. In particular, we focus on the Genome Halving Problem motivated by the whole genome duplication events in molecular evolution, first formulated and solved by Nadia El-Mabrouk and David Sankoff. We propose a new approach to analysis of rearrangements in genomes with duplicated genes, based on a generalization of conventional breakpoint graph, that let us to obtain the following results: (1) We reformulate the problem of computing the rearrangement distance between genomes with duplicated genes as two graph-theoretical problems and demonstrate how to solve their particular variants appearing in the course of solving the Genome Halving Problem. For the Genome Halving Problem with 2-breaks (i.e., standard rearrangements) this leads to an alternative short solution. (2) We further study the Genome Halving Problem with 3-breaks that add trans-positions to the set of standard rearrangement operations considered by El-Mabrouk and Sankoff [24]. The El-Mabrouk–Sankoff analysis of the 2-Break Genome Halving Problem is already rather complex making it appears unlikely that there exists a similar result for the 3-Break Genome Halving. We prove the contrary by giving a polynomial algorithm and duality theorem for the 3-Break Genome Halving Problem. (3) We reveal that while the El-Mabrouk–Sankoff analysis of the Genome Halving Problem is correct in most cases, it does not hold in the case of unichromosomal circular genomes. This raises a problem of correcting the El-Mabrouk–Sankoff analysis and devising an algorithm that deals adequately with all genomes. We efficiently classify all genomes into two classes and show that while the El-Mabrouk–Sankoff theorem holds for the first class, it is incorrect for the second class. The crux of our analysis is a new combinatorial invariant defined on duplicated permutations. Using this invariant we were able to come up with a full proof of the Genome Halving theorem and a polynomial algorithm for the Genome Halving Problem (for unichromosomal circular genomes).