Linearization of Ancestral Genomes with Duplicated Genes

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 base 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 preduplicated ancestral genomes, referred to as the genome halving problem. Reconstruction of the preduplicated or median genomes consisting of linear chromosomes for given linear genomes is known to be intractable. There exist efficient methods for solving a relaxed version of this problem, where the preduplicated or median genomes are allowed to have circular chromosomes.