Medians at the corners, anti-medians at the center: the geometry of breakpoint medians for random signed multichromosomal genomes

Breakpoint medians provide insights into gene order across genomes and are crucial for ancestral reconstruction. Haghighi and Sankoff (2012) observed that most breakpoint medians of random genomes tend to cluster near the input genomes rather than being centrally located, while Larlee et al. (2016) noted that balancing the contributions from each input genome increases the overall breakpoint distance, leading to the formation of anti-medians.

The study investigates both these phenomena in the context of k independent uniform signed multichromosomal genomes with n genes. The key findings include the use of Poisson bounds to control the deviation of medians from the expected value of (k-1)n, and the observation that every median derives almost all its adjacencies from the input genomes, except for a small constant fraction.

Candidate genomes are created by sequentially adding adjacencies from the input genomes. The availability of fresh inputs depletes quadratically rather than linearly, making it challenging to combine contributions from multiple inputs. The research characterizes the achievable profiles, i.e., the limiting overlaps that a constructed genome can share with each input genome at the median scale.

The constructed genome takes all but a small fraction of its adjacencies from a single input genome, explaining the Haghighi-Sankoff phenomenon of seeking corner positions. This same characterization quantifies the trade-off between the cost of compromise and provides a game-theoretic explanation for the formation of anti-medians.

At the Pareto boundary, the total overlap is maximized when all contributions come from a single input, while the minimum overlap occurs at an equal compromise, where the excess over the median value has a closed-form expression. Numerical experiments demonstrate these effects at moderate genome sizes. In conclusion, this study offers a rigorous, quantitative account of the geometry of breakpoint medians and anti-medians in random signed genomes, elucidating why constructions at the median scale tend to favor a single input and the costs associated with achieving a balanced compromise.