Metraipolis › archive › dc_22fcdf02a3f2

Tree-based Algorithms for Breakpoint Median and Near-Median Genomes — arXiv:2610.40667

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.40667
License (as archived): CC0-1.0
Archived: 2026-11-02T08:00:42.290Z
SHA-256 of the archived text: a22eaed1f6a046c2ecc2ae807112b8c082f159afb02e6b755fddca72f52fe707
Stable URL of this page: https://metraipolis.com/documento/dc_22fcdf02a3f2

How to cite

Tree-based Algorithms for Breakpoint Median and Near-Median Genomes — arXiv:2610.40667 — arXiv (en), https://arxiv.org/abs/2610.40667 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_22fcdf02a3f2 (Metraipolis archive dc_22fcdf02a3f2, sha256 a22eaed1f6a046c2ecc2ae807112b8c082f159afb02e6b755fddca72f52fe707)

BibTeX

@misc{dc22fcdf02a3f2,
  title = {Tree-based Algorithms for Breakpoint Median and Near-Median Genomes — arXiv:2610.40667},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40667},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_22fcdf02a3f2; sha256 a22eaed1f6a046c2ecc2ae807112b8c082f159afb02e6b755fddca72f52fe707},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40667. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Median genomes serve as candidates for ancestral reconstruction and help study the diversity of parsimonious rearrangement solutions. However, the breakpoint median problem is NP-hard for unichromosomal genomes, and medians are non-unique, making their diversity important to study. In this paper, we develop tree-based algorithms for studying breakpoint medians of linear unichromosomal genomes represented as unsigned permutations. The algorithms construct rooted labeled trees whose leaves encode candidate median genomes satisfying local adjacency constraints derived from the inputs. We show that the resulting reduced search spaces contain all breakpoint medians while being much smaller than the full permutation space. We investigate these reduced spaces experimentally for three-genome instances. Our method finds exact medians and many near-optimal approximations, while early sampling of leaves often produces near-medians quickly. We also introduce constrained sampling procedures for targeting balanced near-medians, whose distances to the input genomes are more evenly distributed and hence are particularly relevant for ancestral reconstruction. The resulting framework provides a unified method for exact enumeration, efficient sampling, and targeted exploration of median and near-median genomes. In contrast to Traveling Salesman Problem-based approaches, which typically return a single solution and do not reveal the diversity or balance of the median set, our method can enumerate all medians, sample near-medians early, and target structurally distinct candidates under the breakpoint distance.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Genomics (q-bio.GN) ; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.40667 — 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-02T07:42:45.756Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).