Metraipolis › archive › dc_033a34cb1912
Counting approximate breakpoint medians of random genomes — arXiv:2610.40027
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.40027
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:47:50.311Z
- SHA-256 of the archived text
988d364d2a6bde0b8ef6012956e367086269568389687f5eed736623e99d4fae- Stable URL of this page
https://metraipolis.com/documento/dc_033a34cb1912
How to cite
Counting approximate breakpoint medians of random genomes — arXiv:2610.40027 — arXiv (en), https://arxiv.org/abs/2610.40027 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_033a34cb1912 (Metraipolis archive dc_033a34cb1912, sha256 988d364d2a6bde0b8ef6012956e367086269568389687f5eed736623e99d4fae)
BibTeX
@misc{dc033a34cb1912,
title = {Counting approximate breakpoint medians of random genomes — arXiv:2610.40027},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.40027},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_033a34cb1912; sha256 988d364d2a6bde0b8ef6012956e367086269568389687f5eed736623e99d4fae},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40027. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Computational Engineering, Finance, and Science (cs.CE) ; Data Structures and Algorithms (cs.DS); Populations and Evolution (q-bio.PE). Pagina del lavoro: https://arxiv.org/abs/2610.40027 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-01T02:17:58.614Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).