Georgia Institute of Technology College of Sciences

Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of possible evolutionary events between the reconstructed genomes and the genomes of extant species. While these problems have been widely studied in past decades, their known algorithmic solutions are either not efficient or produce biologically inadequate results. These shortcomings have been recently addressed by restricting the problems solution space. We show that the restricted variants of genome median and halving problems are, in fact, closely related and have a neat topological interpretation in terms of embedded graphs and polygon gluings. Hence we establish a somewhat unexpected link between comparative genomics and topology, and further demonstrate its advantages for solving genome median and halving problems in some particular cases. As a by-product, we also determine the cardinality of the genome halving solution space.