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

Abstract

Purpose. Breakpoint medians summarize gene order across genomes and are central to ancestral reconstruction. Haghighi and Sankoff (2012) found most breakpoint medians of random genomes near the inputs rather than at balanced positions, while Larlee et al. (2016) observed that balancing adjacency contributions increases the total breakpoint distance, producing anti-medians. We study both phenomena for k independent uniform signed multichromosomal genomes on n genes. Major findings. Poisson bounds control the median-value deviation from (k-1)n, and every median inherits all but O[P](1) of its adjacencies from the inputs. We build candidate genomes by drawing adjacencies from the inputs one at a time. The supply from a fresh input depletes quadratically rather than linearly, making large contributions from multiple inputs harder to combine. We characterize the attainable profiles, the limiting overlaps such a construction can share with each input. At the median scale the constructed genome takes all but o[P](n) of its adjacencies from one input, explaining the Haghighi--Sankoff corner-seeking phenomenon. The same characterization quantifies the cost of compromise and provides a game-theoretic explanation of anti-medians. On the Pareto boundary the total overlap is maximal when it all comes from one input and uniquely minimal at equal compromise, where the excess over the median value has a closed form. Numerical experiments illustrate these effects at moderate genome sizes. Conclusions. These results provide a rigorous, quantitative account of breakpoint median and anti-median geometry in random signed genomes, showing why attainable median-scale constructions favor a single input and what balanced compromise costs.