Practical aliquoting of flowering plant genomes

We pose the problem of dissecting an ancient polyploid genome into its constituent subgenomes despite fragmentation and noise caused by genome rearrangements and fractionation of multi-copy genes. We formulate this in terms of decomposition into "defective" k-partite graphs, distinguished by location within the genome. We devise and implement a clustering heuristic for solving realistic instances of the problem. An unusual focus of our method is the focus on prioritizing gene density or lack of gaps in the assembly of fragments into larger regions, rather than maximizing the number of genes. We validate the method against the grape genome in which the ancient core eudicot triplication is readily detectible and is already well known. We then analyze the tomato genome, whose proposed status as a descendant of a more recent Solanum hexaploid is controversial, and confirm this proposal. The solution reveals unexpected information about the evolution of the tomato.