Metraipolis › archive › dc_edbc6c2939a2

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-03T05:45:17.126Z
SHA-256 of the archived text
074495ef341a842a812a64e2a6a09ec7aa4c0edd54ee6716f04f06ba52e9481d
Stable URL of this page
https://metraipolis.com/documento/dc_edbc6c2939a2

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_edbc6c2939a2 (Metraipolis archive dc_edbc6c2939a2, sha256 074495ef341a842a812a64e2a6a09ec7aa4c0edd54ee6716f04f06ba52e9481d)
BibTeX
@misc{dcedbc6c2939a2,
  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_edbc6c2939a2; sha256 074495ef341a842a812a64e2a6a09ec7aa4c0edd54ee6716f04f06ba52e9481d},
  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-03T05:32:17.014Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).