Alekseyev and Avdeyev Published in Algorithms for Computational Biology

May 28, 2019

Dr Max Alekseyev, a professor with the Computational Biology Institute (CBI) and the Department of Epidemiology and Biostatistics, and Pavel Avdeyev, a graduate research assistant with the CBI and PhD student in the Department of Mathematics, published an article, "A Uniform Theory of Adequate Subgraphs for the Genome Median, Halving, and Aliquoting Problems," in Algorithms for Computational Biology on April 13th, 2019. 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 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. Generalization of WGDs to whole genome multiplication events leads to the genome aliquoting problem. In this study, the authors generalize the adequate subgraphs approach previously proposed for the genome median problem to the genome halving and aliquoting problems. The study lays a theoretical foundation for practical algorithms for the reconstruction of pre-duplicated ancestral genomes.