Breakpoint Medians and Anti-medians for Signed Genomes
摘要
The breakpoint distance is a fundamental measure for comparing gene orders and plays a central role in genome rearrangement phylogenetics. For more than two genomes, breakpoint medians are widely used to infer ancestral gene orders, yet their typical behavior is difficult to characterize due to the complex, non-geodesic geometry of genome space. A conjecture of Haghighi and Sankoff states that for random genomes, breakpoint medians tend to lie near one of the input genomes rather than constituting genuinely intermediate solutions. In this paper, we study breakpoint medians of independently and uniformly sampled signed multichromosomal genomes. We prove the Haghighi–Sankoff conjecture in this setting for the first time. We show that with high probability, any breakpoint median must remain close to a single input genome, rather than drawing adjacencies from multiple genomes. Our analysis relies on probabilistic bounds for usable adjacencies in random signed genomes and structural constraints of the signed multichromosomal model. We further provide a game-theoretic interpretation that explains why compromise strategies lead to increased total distance and the emergence of anti-medians.