Tree-based Algorithms for Breakpoint Median and Near-Median Genomes

Abstract

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.

Medians at the corners, anti-medians at the center: the geometry of breakpoint medians for random signed multichromosomal genomes
P. H. da Silva, A. Jamshidpey, D. Sankoff
bioRxiv18 Oct 2026PreprintAll rights reservedFull textBioinformatics & computational biologybioRxiv
Counting approximate breakpoint medians of random genomes
Poly H. da Silva, Arash Jamshidpey, David Sankoff
arXiv29 Oct 2026PreprintCC BY-NC-ND 4.0Full textEvolutionary biologyarXiv
Near-Full-Length Hepatitis B Virus Genomes Isolated from Cerebrospinal Fluid of People Living with HIV and Cryptococcal Meningitis in Botswana
Basetsana K. S. Phakedi, Bonolo B. Phinius, Kesaobaka Molebatsi +16
Genes23 Sep 2026Peer-reviewedCC BYFull textGenetics & genomicsEurope PMC
Pre-binning correction of chimeric contigs reduces reference-discordant gene annotations in near-complete metagenome-assembled genomes
Y. Ding, J. Xiao, B. Zou +4
bioRxiv15 Oct 2026PreprintCC BYFull textBioinformatics & computational biologybioRxiv
Breakpoint Mapping and Disrupted Gene Identification in Azoospermic Patients With Chromosomal Balanced Translocation by Nanopore Sequencing.
Jian Zhang, Xiao-Lu Chen, Jia-Yan Chen +1
Journal of clinical laboratory analysis3 Nov 2026Peer-reviewedCC BY-NC-NDFull textGenetics & genomicsEurope PMCPMC

Cite

BibTeX RIS

BibTeX

@misc{silva2026treebased,
  title = {{Tree-based Algorithms for Breakpoint Median and Near-Median Genomes}},
  author = {Poly H. da Silva and Arash Jamshidpey and David Sankoff},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40667},
  eprint = {2610.40667},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40667},
}

RIS

TY  - UNPB
TI  - Tree-based Algorithms for Breakpoint Median and Near-Median Genomes
AU  - Poly H. da Silva
AU  - Arash Jamshidpey
AU  - David Sankoff
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.40667
UR  - https://arxiv.org/abs/2610.40667
AB  - 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.
ER  -

Abstract

Related

Cite