Optimal path reconstruction of plant chromosome evolution.

DNA rearrangements contribute to the formation of new chromosomes, which are often the foundation of speciation. Deciphering the order of DNA rearrangements facilitates the reconstruction of evolutionary trajectories from extant to ancestral chromosomes, a task that is computationally NP-hard. Here, a mathematically rigorous chromosome-rearrangement model is integrated with the "Chromosomal Inversion Path Exploration via Monte-Carlo Tree Search (CIPE-MCTS)" framework in a deeply coupled manner. This integration yields a robust analytical framework that ensures both global optimality and computational efficiency, thereby enabling the precise reconstruction of complex chromosomal evolutionary trajectories. The framework rigorously characterizes elementary rearrangement operations-inversion, translocation, fusion, and fission-within a strict graph-theoretic and group-theoretic formalism. On this basis, MCTS is introduced, guided by a domain-specific heuristic evaluation function that integrates a decay function and a dynamic hash table. The Upper Confidence Bound for Trees (UCT) serves as the node-selection criterion, while an extensible sampling strategy enables rapid convergence toward near-optimal solutions within the vast state space. Comprehensive benchmark tests demonstrate that, under identical hardware constraints, this method achieves significantly higher reconstruction accuracy than exhaustive global search, while its overall running time is markedly shorter than that of a single heuristic algorithm, thereby achieving simultaneous improvements in both accuracy and efficiency. This study introduces, for the first time, a scalable, reproducible, and mathematically guaranteed tool for accurate analysis of complex plant genomes, offering a novel quantitative perspective for elucidating the chromosomal basis of plant diversification and adaptive evolution.