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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Breakpoint Medians and Anti-medians for Signed Genomes

  • Poly H. da Silva,
  • Arash Jamshidpey,
  • David Sankoff

摘要

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.