Mathematical Models of Ancestral Genome Reconstruction
Open AccessComparative genomics is a field of biological research, where the genomic sequences of different species are compared to each other to understand their genomic similarities and dissimilarities, and reveal their evolutionary history. The emergence of many newly sequenced genomes allows us to address various evolutionary questions from a mathematical modeling standpoint. One of the key computational problems in comparative genomics is the reconstruction of genomes of ancestral species based on genomes of extant species. Since most dramatic changes in genomic architectures are caused by genome rearrangements, this problem is often posed as a minimization of the number of genome rearrangements between extant and ancestral genomes. The basic case of three given genomes is known as the genome median problem. Whole genome duplications (WGDs) represent yet another type of dramatic evolutionary events and inspire the reconstruction of pre-duplicated ancestral genomes, referred to as the genome halving problem. We consider these problems under the Double-Cut-and-Join (DCJ) model representing most common genome rearrangements (reversals, translocations, fissions, and fusions) as operations on genome graphs.In the current work, we first study the implicit appearance of transpositions (i.e., more complex genome rearrangements, represented as pairs of DCJs) in rearrangement scenarios. Second, we demonstrate that the genome median and halving problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. Third, we propose polynomial-size integer linear programming (ILP) formulations for the aforementioned problems. The obtained ILP formulations provide a novel practical approach to ancestral genome reconstruction. Fourth, since in our model the ancestral genomes are allowed to have circular chromosomes even if the given genomes consist of linear chromosomes only, we propose a method for ``linearizing'' ancestral genomes. And last but not least, we consider the even more general problem of ancestral genome reconstruction for multiple given genomes, for which we present MGRA2 - an extension of the algorithmic toolbox initially introduced for ancestral reconstruction of genomes with uniform gene content.This manuscript is based on a number of papers [9, 12–18, 37] that resulted from the author’s research during his Ph.D. at the Department of Mathematics and the Computational Biology Institute at The George Washington University.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.