Counting approximate breakpoint medians of random genomes
Abstract
Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively. The breakpoint distance counts the adjacencies of one genome that are absent from the other, and a breakpoint median minimizes the total breakpoint distance to a given set of genomes. Deciding whether a permutation is a median often requires a minimization over the whole symmetric group, which makes the median set resistant to exact counting. We replace this global condition by a local one: a c-approximate median is a genome having at most c adjacencies absent from all the input genomes. For a fixed genome we introduce its approximate median inverse, the set of ordered k-tuples of genomes ad- mitting it as a c-approximate median, and we construct and count this set explicitly. For k genomes chosen uniformly and independently at random, this gives the probability that a given genome is a c-approximate median and the expected number of such approximate medians. The relaxation is not only technical: approximate medians and near-optimal genomes co- incide up to a shift of the tolerance that remains bounded in probability as the number of genes grows. Finally, we derive an explicit upper bound on the probability that a given genome is an exact median, and on the expected number of exact breakpoint medians.
Related
- Medians at the corners, anti-medians at the center: the geometry of breakpoint medians for random signed multichromosomal genomes
- Tree-based Algorithms for Breakpoint Median and Near-Median Genomes
- A hybrid approach combining a phylogenetic method and Approximate Bayesian Computation Random Forest for phylogenetic network inference: application to the rice domestication process in Asia
- Breakpoint Mapping and Disrupted Gene Identification in Azoospermic Patients With Chromosomal Balanced Translocation by Nanopore Sequencing.
- Active centromeres share a conserved array-architecture signature across great ape genomes
BibTeX
@misc{silva2026counting,
title = {{Counting approximate breakpoint medians of random genomes}},
author = {Poly H. da Silva and Arash Jamshidpey and David Sankoff},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40027},
eprint = {2610.40027},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40027},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Counting approximate breakpoint medians of random genomes
AU - Poly H. da Silva
AU - Arash Jamshidpey
AU - David Sankoff
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40027
UR - https://arxiv.org/abs/2610.40027
AB - Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively. The breakpoint distance counts the adjacencies of one genome that are absent from the other, and a breakpoint median minimizes the total breakpoint distance to a given set of genomes. Deciding whether a permutation is a median often requires a minimization over the whole symmetric group, which makes the median set resistant to exact counting. We replace this global condition by a local one: a c-approximate median is a genome having at most c adjacencies absent from all the input genomes. For a fixed genome we introduce its approximate median inverse, the set of ordered k-tuples of genomes ad- mitting it as a c-approximate median, and we construct and count this set explicitly. For k genomes chosen uniformly and independently at random, this gives the probability that a given genome is a c-approximate median and the expected number of such approximate medians. The relaxation is not only technical: approximate medians and near-optimal genomes co- incide up to a shift of the tolerance that remains bounded in probability as the number of genes grows. Finally, we derive an explicit upper bound on the probability that a given genome is an exact median, and on the expected number of exact breakpoint medians.
ER -