Polyploids, genome halving and rearrangement phylogeny

Abstract

The basic rearrangement phylogeny methods require that the genomic content be the same in all the organisms being compared, and so are not applicable when one or more of the genomes being compared derive from ancestral whole genome doubling (WGD) events. In this thesis I developed algorithms for rearrangement phylogeny for sets of related genomes that include both descendants of WGD and unduplicated genomes. Furthermore I investigated the properties of these algorithms and validated them by applying them to real data. I defined varions possible local configurations of doubled and unduplicated genomes in a given phylogeny, each of which requires a different strategy for integrating genomic distance, halving and rearrangement median algorithms. The genome halving algorithm of El-Mabrouk and Sankoff efficiently reconstructs an ancestral pre-doubling genome from the chromosomal distribution of duplicate genes created by this event and remaining today in the descendant genome. However, this algorithm can produce many alternate optimal solutions. To reduce this non-uniqeness, hopefully to only one solution, I developed the guided genome halving algorithm. This rapidly and accurately constructs an optimal ancestor closest to one or more outgroups. As I refined this algorithm, I applied it to successively larger data sets, increasing in size over more than two orders of magnitude. Thus I constructed the ancestors of cereals, based on duplicate markers in maize and using rice and sorghum as outliers. I reconstructed genomes corresponding to the ancestral nodes of yeasts in the Saccharomyces complex, as well as the ancestor of poplar, based on grapevine and papaya as outgroups. I studied two cases involving two WGD descendants, one where the doubling precedes a speciation event and another where doubling occurs independently in both lineages initiated by a speciation event. I developed combinatorial algorithms permitting us to decide which of these options best explains the data. To take into account the massive loss of genes following ancestral genome doubling, I developed a method to incorporate the defective gene sets into consideration and evaluate the effects of these lost genes on the reconstruction of the ancestor.