染色体重排——包括DNA倒位、易位、融合和断裂——会重新配置基因顺序并影响基因表达，从而推动植物和其他真核生物的遗传多样性和适应性进化。准确重建这些进化轨迹对于阐明物种形成和环境适应的机制至关重要。具体而言，准确重建染色体重排路径有助于识别关键的分化事件，例如多倍体中基因组融合的顺序。这还有助于解码基因顺序变化对调控网络的影响，例如染色体倒位如何改变顺式调控元件之间的相互作用。最终，这种方法为作物遗传改良提供了理论框架，例如通过追踪祖先染色体结构来确定与驯化特征相关的基因。基于比较基因组学和遗传学原理的端粒中心模型（Wang, 2015）强调了端粒在保护真核生物染色体完整性方面的作用，并有助于重建其数亿年的进化轨迹（Wang, 2025, Nature Protocols）。该模型已成功应用于多种植物科的染色体进化重建。例如，Zhuang（2019）的研究专注于栽培花生的基因组分析，通过全基因组测序、组装和分析系统地解决了关于这种多倍体作物起源和进化的关键问题，从而为遗传改良提供了核心基因组资源。
然而，精确重建染色体进化轨迹仍然是一个巨大的挑战。经典方法——如细胞遗传学分析和比较基因组学——提供了宝贵的见解，但往往缺乏解决复杂进化历史所需的分辨率和计算效率（Kille, Bryce等人，2022）。尽管高通量测序产生了指数级的基因组数据增长，但这些数据集的庞大体积和复杂性需要更复杂的分析工具来重建染色体进化轨迹。当前的计算方法存在固有的局限性。例如，穷举搜索策略仅适用于小规模的基因组片段，并且在处理大规模数据集时面临计算难题。虽然启发式算法在计算上高效，但它们往往缺乏生物学合理性，并倾向于收敛于局部最优解。此外，传统意义上的蒙特卡洛树搜索（MCTS）在基因组学中的应用经常未能结合关键的染色体结构特征（例如端粒介导的融合或断裂），导致重建结果偏离合理的进化模式（Salse, 2009; Sun, 2022）。因此，现有方法难以同时满足效率、生物学合理性和稳定性这三个核心要求，凸显了该领域的一个关键缺口。这一缺口凸显了迫切需要新的分析框架，这些框架必须既稳健又高效，并能够将基因组数据与先进的数学模型相结合，以实现更高保真度的染色体进化轨迹重建。
本研究旨在通过染色体片段索引、独立的启发式算法和混合启发式-蒙特卡洛树搜索（MCTS）策略来解决染色体重排历史重建问题。在方法上，根据倒位模式对染色体片段进行编码，并开发了具有生物学意义的倒位规则。启发式算法将DNA片段的方向和相关倒位事件纳入蒙特卡洛树搜索框架中，以优化重排路径。所提出的CIPE-MCTS混合算法结合了两种关键机制：指数衰减函数和奖励-惩罚系统。它将端粒中心模型（TCM）的生物学原理与数学引导的双重收益评估函数深度整合在一起，从而实现了计算效率、生物学合理性和解决方案稳定性的协同优化。该框架的核心目标是通过实现准确的或接近准确的进化路径重建，为生物学分析提供可靠的计算支持。这些方法创新为解释染色体进化建立了新的范式，并为未来的比较基因组学研究提供了有价值的工具。
本研究解决的问题是确定将一种染色体序列转换为另一种染色体序列所需的最小重排操作序列（例如倒位、易位）。这类似于序列空间中两个节点之间的最短路径问题。哈密顿路径问题是计算机科学中正式确定的经典NP难题。通过归约证明，染色体重排的最优路径问题也被确立为NP难题。根据NP难度的定义，如果从一个NP难题存在多项式时间的归约到目标问题，那么目标问题也是NP难题。由于NP问题可以归约为哈密顿路径问题，而哈密顿路径问题又可以多项式时间归约为染色体重排最优路径问题，因此染色体重排路径优化完全符合NP难题的定义。
对于涉及少量重排的情况，采用穷举搜索方法遍历整个解空间以确定最优解。尽管计算成本较高，但这种方法保证了全局最优性。对于更大规模的问题，引入了蒙特卡洛树搜索（MCTS）算法。通过在解空间中进行随机采样和树搜索，MCTS能够在合理的时间内识别出近似最优解。这种方法在探索和利用之间取得了平衡。此外，还提出了一种基于问题特定结构和规则的启发式搜索算法，能够快速识别接近最优解的解。这种启发式搜索方法显著提高了计算效率，同时保持了解决方案的质量，从而增强了其在实际应用中的可行性。
本文介绍了CIPE-MCTS算法，它将经典启发式搜索与蒙特卡洛树搜索范式紧密结合。启发式算法的概念最初由Herbert A. Simon和Allen Newell（Newell等人，1958）提出，指的是一类放弃保证全局最优性，而是在可接受的计算限制内识别“满意”解的搜索和优化方法。这类算法利用经验规则、直觉或领域特定知识来缩减搜索空间，从而规避了穷举枚举中的组合爆炸问题。蒙特卡洛树搜索（MCTS）的算法框架最初由法国学者Rémi Coulom（2006）明确提出并命名。同年，匈牙利研究人员Kocsis和Szepesvári（2006）引入了树的上置信界（UCB）算法，为MCTS提供了严格的理论基础和核心的探索-利用策略。Schadd、Winands和van den Herik（2008, 2012）通过引入最大边界值和快速反向传播，改进了单玩家MCTS（SP-MCTS），显著增加了单智能体谜题中的搜索深度。Cazenave（2011）提出了嵌套蒙特卡洛搜索，它在MCTS中添加了多层嵌套结构，首次在16×16 SameGame游戏中达到了人类专家的水平。Silver和Veness（2010）提出了POMCP算法，通过根采样和基于UCB的选择将MCTS扩展到部分可观测马尔可夫决策过程（POMDP），实现了大规模POMDP中的在线规划。Pepels等人（2012）将遗传算法进化出的启发式方法嵌入MCTS，在Ms. Pac-Man竞赛中获得了第二名，实证验证了启发式增强MCTS的有效性。Song等人（2019）使用MCTS研究了非抓取多目标重排，并通过展开网络训练探索了效率改进。Bai等人（2022）提出了一种用于非抓取多目标重排的层次化策略，其中高级策略采用了通过模仿和强化学习训练的政策网络引导的MCTS算法。
总之，本研究提出了一个数学问题，即推断和重建进化轨迹，并寻求计算解决方案，这是一个极具挑战性的NP难题。最终，提出了一种创新方法，将数学染色体重建模型与CIPE-MCTS框架深度结合。该方法在图论和群论框架内形式化重建操作，并结合了由启发式评估函数、衰减函数和动态哈希表引导的蒙特卡洛树搜索，从而实现了全局优化和计算效率。它在重建准确性和运行时间方面优于穷举搜索和独立的启发式算法，提供了一个可扩展且数学上严谨的工具，用于理解染色体重建。
