A Rapid Exact Solution for the Guided Genome Halving Problem

\subsubsection*Background Genome rearrangements are large-scale evolutionary events that shuffle genomic architectures. Since genome rearrangements are rare, the number of events between two genomes is used in phylogenomic studies to measure the evolutionary distance between them. Such measurement is often based on the maximum parsimony assumption, implying that the evolutionary distance can be estimated as the minimum number of rearrangements between genomes. The maximum parsimony assumption enables addressing the ancestral genome reconstruction problem, which asks for reconstructing of ancestral genomes from the given extant genomes, by minimizing the total distance between genomes along the branches of the phylogenetic tree. The basic case of this problem with just three given genomes is known as the genome median problem (GMP), which asks for a single ancestral genome (\emphmedian genome ) at the minimum total distance from the given genomes. \emphWhole genome duplication (WGD) represents yet another type of dramatic evolutionary events, which simultaneously duplicate each chromosome of a genome. WGDs are known to have happened in the evolution of plants~\citeguyot2004ancestral. An analog of the GMP in presence of a WGD is known as the guided genome halving problem (GGHP). This problem is posed for input genomes A and B, where all genes in B are present in a single copy (\emphordinary genome ), while all genes in A are present in two copies (\emphduplicated genome ). The GGHP asks for an ordinary ancestral genome R that minimizes the total evolutionary distance between genomes A and $2R$ (genome resulted from the WGD of R) and between B and R. \vspace-0.5em \subsubsection*Methods A major tool for analysis of genome rearrangements is the breakpoint graph, which encodes gene adjacencies in different genomes by edges of different colors. A median genome corresponds to a certain optimal perfect matching in the breakpoint graph of the given genomes. While the GMP is NP-hard \citetannier2009multichromosomal, one of the prominent exact and practical solutions to the GMP is based on decomposition of the breakpoint graph intoadequate subgraphs ~\citexu2009fast, i.e., induced subgraphs where any optimal matching can be extended to an optimal matching in the whole graph. To handle genomes with duplicated genes, one has to generalize the notion of the breakpoint graph to the contracted breakpoint graph of the given genomes A and B. In the present study, we extend the adequate subgraph approach to the GGHP. \vspace-0.5em \subsubsection*Results We extended the notion of adequate subgraphs to contracted breakpoint graphs and identified all simple adequate subgraphs of order $2$ and $4$ (shown in Fig. \reffig:adequate_gghp ). This enables us to design an efficient divide-and-conquer algorithm for the GGHP. Our algorithm searches for adequate subgraphs in the given contracted breakpoint graph and combines optimal matchings in these subgraphs into an optimal matching (representing a solution to the GGHP) in the whole graph. \vspace-0.5em \subsubsection*Conclusion Our present study provides an exact fast algorithm for the GGHP. In future research, we plan to extend the notion of adequate subgraphs to other ancestral reconstruction problems with duplicated genomes, such as the guided genome aliquoting problem. \vspace-1em