Guided genome halving: provably optimal solutions provide good insights into the preduplication ancestral genome of Saccharomyces cerevisiae.
We present theoretical and practical advances on the Guided Genome Halving problem, a combinatorial optimisation problem which aims at proposing ancestral configurations of extant genomes when one of them has undergone a whole genome duplication. We provide a lower bound on the optimal solution, devise a heuristic algorithm based on subgraph identification, and apply it to yeast gene order data. On some instances, the computation of the bound yields a proof that the obtained solutions are optimal. We analyse a set of optimal solutions, compare them with a manually curated standard ancestor, showing that on yeast data, results coming from different methodologies are largely convergent: the optimal solutions are distant of at most one rearrangement from the reference.
Gavranović
Haris
H
Faculty of Natural Sciences, University of Sarajevo, Bosnia and Herzegovina.
Tannier
Eric
E
D000465:Algorithms; D019295:Computational Biology; D019143:Evolution, Molecular; D020440:Gene Duplication; D016681:Genome, Fungal; D008957:Models, Genetic; D012441:Saccharomyces cerevisiae / Q000235:genetics; D015003:Yeasts / Q000235:genetics