Breakpoint median genomes are key candidates for ancestral reconstruction and for studying the diversity of parsimonious rearrangement solutions. Even for linear unichromosomal genomes represented as unsigned permutations, the breakpoint median problem is NP‑hard and medians are typically non‑unique, making the exploration of their diversity essential.
We introduce a tree‑based algorithmic framework. The method builds a rooted labeled tree whose leaves encode candidate median genomes that satisfy local adjacency constraints derived from the input genomes. We prove that the reduced search space still contains all breakpoint medians while being dramatically smaller than the full permutation space.
Experimental evaluation on three‑genome instances shows that the approach can compute exact medians and, at the same time, quickly generate many near‑optimal near‑median genomes. Early sampling of leaves often yields high‑quality near‑medians with minimal computational effort.
We also propose constrained sampling procedures aimed at balanced near‑medians—candidates whose breakpoint distances to the input genomes are more evenly distributed. Such balanced solutions are particularly relevant for ancestral reconstruction because they reflect the input genomes more uniformly.
Overall, the framework offers a unified solution 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 hide the diversity or balance of the median set, our method can enumerate all medians, produce near‑medians early, and deliberately explore structurally distinct candidates under the breakpoint distance.
Review: The tree‑based constrained search dramatically reduces computational complexity and opens new avenues for systematic study of breakpoint medians, especially in applications requiring a diverse set of ancestral candidates.