HBM：基于双向蒙特卡洛树和混合贪心策略的序列反转求解方法

HBM: A Sequence Reversal Solving Method Based on Bidirectional Monte Carlo Tree and Hybrid Greedy Strategy

摘要: 基因序列重排是计算生物学中的经典组合优化问题，目标是以最少的子串反转操作将给定序列转化为目标序列，其在解析基因组进化机制方面具有重要意义。然而，该问题具有NP难特性，求解极具挑战。为提高求解效率与质量，本文提出一种基于双向蒙特卡洛树与混合贪心策略的序列反转求解模型(HBM)。该模型首先通过预处理去除已匹配的前后缀，压缩问题规模；进而采用分层递进求解框架，依次利用双向广度优先搜索获取初始路径，在未获解时启用混合贪心策略，融合五种启发式指标动态选择局部操作，最终通过双向蒙特卡洛树搜索平衡探索与利用，以获取高质量解。在特定DNA序列数据集上的实验表明，HBM在反转路径长度、时间–质量性价比及解质量稳定性方面均优于现有方法。

Abstract: Gene sequence rearrangement is a classic combinatorial optimization problem in computational biology, which aims to transform a given sequence into a target sequence with the minimum number of substring reversal operations and plays a crucial role in deciphering the mechanisms of genome evolution. However, this problem is characterized by NP-hardness, making its solution extremely challenging. To improve the efficiency and quality of the solution, this paper proposes a sequence reversal solving model (HBM) based on a bidirectional Monte Carlo tree and a hybrid greedy strategy. The model first compresses the problem scale by preprocessing to remove matched prefixes and suffixes; then adopts a hierarchical progressive solving framework, sequentially using bidirectional breadth-first search to obtain an initial path, activating a hybrid greedy strategy when no solution is obtained, integrating five heuristic metrics to dynamically select local operations, and finally balancing exploration and exploitation through bidirectional Monte Carlo tree search to acquire high-quality solutions. Experiments on a specific DNA sequence dataset show that HBM outperforms existing methods in terms of reversal path length, time-quality cost-effectiveness, and solution quality stability.