用改进遗传算法高效求解基因组重组装中的最长连续子序列问题
A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem
- 采用有偏随机键遗传算法，优化解的编码与评估效率
- 在多种测试数据上表现优于蚁群算法和CPLEX求解器
- 对大字符集输入仍有提升空间，适合生物信息学研究者参考
最长连续子序列（LRS）问题是生物信息学中一类组合优化难题，属于NP难问题，对基因组重组装具有重要意义。本文提出一种有偏随机键遗传算法（BRKGA）求解该问题，重点优化个体评估的计算效率，即灰度向量转为有效解的过程。为对比性能，还实现了最大最小蚁群算法，并使用整数线性规划求解器CPLEX求解所有实例。实验结果表明，所提BRKGA目前是求解LRS问题的最先进方法。然而，对于大字符集输入，仍存在改进空间。
原文摘要 · Abstract (English)
The longest run subsequence (LRS) problem is an NP-hard combinatorial optimization problem belonging to the class of subsequence problems from bioinformatics. In particular, the problem plays a role in genome reassembly. In this paper, we present a solution to the LRS problem using a Biased Random Key Genetic Algorithm (BRKGA). Our approach places particular focus on the computational efficiency of evaluating individuals, which involves converting vectors of gray values into valid solutions to the problem. For comparison purposes, a Max-Min Ant System is developed and implemented. This is in addition to the application of the integer linear programming solver CPLEX for solving all considered problem instances. The computation results show that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem. Nevertheless, the results also show that there is room for improvement, especially in the context of input strings based on large alphabet sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。