RNA逆折叠问题的线性时间求解算法——针对无孤立碱基对或堆叠结构的高效设计策略

本研究针对RNA逆折叠（Inverse Folding）问题的计算复杂性挑战，通过引入模m-可分离性（modulo m-separability）概念，开发了一种线性时间算法。研究团队证明对于最小螺旋长度≥3碱基对（hmin≥3）的目标结构，该问题可在O(n)时间内解决，且算法可均匀生成满足GC含量控制的序列。这一突破性成果为RNA设计领域提供了高效解决方案，对合成生物学和药物开发具有重要意义。

　　

在合成生物学和药物开发领域，RNA分子的精准设计一直是一个核心挑战。RNA逆折叠问题即根据目标二级结构寻找能够唯一折叠成该结构的序列，这一问题的计算复杂性长期困扰着研究人员。尽管早期研究揭示了该问题在一般情况下的NP难解性，但实践中仍缺乏高效可靠的解决方案。

发表在《Algorithms for Molecular Biology》的这项研究通过创新性地引入模m-可分离性概念，为这一难题带来了突破性进展。研究团队证明，对于不含孤立碱基对或孤立堆叠（即所有螺旋包含3⁺个碱基对）的目标结构，逆折叠问题可在线性时间内解决。

研究团队首先建立了可分离性与设计性之间的理论联系，证明任何可分离结构都是可设计的。通过深入分析，他们发现当目标结构的最小螺旋长度h_min≥3时，必然存在2-可分离着色方案。基于这一关键发现，团队开发了固定参数 tractable（FPT）算法，能够在O(n·m·2^m)时间内求解模m-可分离性问题。

在技术方法层面，研究主要采用了以下关键技术：

1. 1.
   树着色框架：将RNA二级结构表示为树模型，通过着色方案确保设计序列的唯一折叠性
2. 2.
   动态规划算法：基于模m-可分离性概念开发高效求解算法
3. 3.
   均匀采样技术：结合拒绝策略实现设计序列的均匀随机生成
4. 4.
   Turner能量模型验证：使用ViennaRNA软件包评估设计序列在真实能量模型下的表现

研究结果方面，论文通过多个重要发现系统验证了所提方法的有效性和实用性：

可分离性与设计性的关系

研究发现可分离性是设计性的充分条件，但非必要条件。存在可设计但不可分离的结构实例，同时证明了在h_min≥3条件下二者等价。

计算复杂性分析

研究团队证明了即使限制h_min=2，可分离性判定仍是NP难问题。这一发现凸显了模m-可分离性方法在特定条件下的优越性。

模m-可分离性的算法实现

通过固定参数tractable算法，研究实现了模m-可分离性对应问题的有效求解。当m=2时，算法可在线性时间内处理h_min≥3的所有可设计实例。

实际应用验证

实验结果表明，分离序列在Turner能量模型下显著优于兼容序列，成功设计比例从10%提升至35%。放松模型进一步将成功率提高至43%，展现出良好的实用价值。

GC含量控制

通过多维Boltzmann采样技术，研究实现了设计序列GC含量的精确控制，为实际应用提供了重要工具。

研究结论部分强调，该工作不仅解决了RNA逆折叠问题的理论挑战，更为实际应用提供了高效可靠的解决方案。模m-可分离性概念的引入为RNA设计领域开辟了新方向，线性时间算法的实现使得大规模RNA设计成为可能。特别是在最小螺旋长度h_min≥3的条件下，研究建立了可设计性、2-可分离性和避免m_3•/m₅ motif三者之间的等价关系，为后续研究奠定了坚实基础。

这项研究的重要意义在于，它将RNA逆折叠问题的求解从理论上的棘手状态转变为实际可操作的线性时间问题，为合成生物学、药物设计和基因治疗等领域的RNA分子设计提供了强有力的工具支持。同时，研究所建立的模m-可分离性框架有望扩展到更复杂的能量模型和设计场景，推动整个RNA设计领域向更高效、更可靠的方向发展。