Genome Halving Problem revisited The Genome Halving Problem is motivated by the whole genome duplication events in molecular evolution that double the gene content of a genome and result in a perfect duplicated genome that contains two identical copies of each chromosome. The genome then becomes a subject to rearrangements resulting in some rearranged duplicated genome. The Genome Halving Problem (first introduced and solved by Nadia ElMabrouk and David Sankoff) is to reconstruct the ancestral preduplicated genome from the rearranged duplicated genome. The ElMabroukSankoff algorithm is rather complex and in this paper we present a simpler algorithm that is based on a generalization of the notion of the breakpoint graph to the case of duplicated genomes. This generalization makes the ElMabroukSankoff result more transparent and promises to be useful in future studies of genome duplications.

Minimum Segmentation for Pangenomic Founder Reconstruction in Linear Time Given a threshold L and a set R  R_1, ..., R_m of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition 1,n into set P of disjoint segments such that each segment a,b in P has length at least L and the number d(a,b)R_ia,b : 1 u003c i u003c m of distinct substrings at segment a,b is minimized over a,b in P. The distinct substrings in the segments represent founder blocks that can be concatenated to form maxd(a,b) : a,b in P founder sequences representing the original R such that crossovers happen only at segment boundaries. We give an optimal O(mn) time algorithm to solve the problem, improving over earlier O(mn2). This improvement enables to exploit the algorithm on a pangenomic setting of input strings being aligned haplotype sequences of complete human chromosomes, with a goal of finding a representative set of references that can be indexed for read alignment and variant calling. We implemented the new algorithm and give some experimental evidence on the practicality of the approach on this pangenomic setting.