ExpertRNA: A New Framework for RNA Secondary Structure Prediction
ExpertRNA: A New Framework for RNA Secondary Structure Prediction
复制标题
DOI：
10.1287/ijoc.2022.1188
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Menghan Liu;E. Poppleton;Giulia Pedrielli;P. Šulc;D. Bertsekas
中科院分区：
文献类型：
--
作者：
Menghan Liu;E. Poppleton;Giulia Pedrielli;P. Šulc;D. Bertsekas
核糖核酸（RNA）是一种基本的生物分子，对所有生物体都是必不可少的，执行多种细胞任务。许多RNA分子的功能与其所采用的结构密切相关。因此，大量的努力致力于设计有效的算法来解决“折叠问题”-给定一个核苷酸序列，返回一个可能的碱基对列表，称为二级结构预测。早期的算法主要依赖于找到具有最小自由能的结构。然而，预测依赖于有效的简化自由能模型，该模型可能无法正确识别正确的结构作为自由能最低的结构。有鉴于此，新的数据驱动的方法，不仅考虑自由能，而且还使用机器学习技术来学习图案也进行了研究，最近被证明优于基于自由能的算法在几个实验数据集。在这项工作中，我们介绍了新的ExpertRNA算法，它提供了一个模块化的框架，可以很容易地将任意数量的奖励（自由能或非参数/数据驱动）和二级结构预测算法。我们认为ExpertRNA的这种能力有可能平衡最先进的折叠工具的不同优势和劣势。我们测试ExpertRNA的几个RNA序列结构数据集，我们比较性能的ExpertRNA对一个国家的最先进的折叠算法。我们发现，ExpertRNA产生，平均而言，更准确的预测nonpseudoknotted二级结构比使用的结构预测算法，从而验证了承诺的方法。ExpertRNA是一种受生物学问题启发的新算法。它适用于解决给定输入序列的RNA分子的二级结构预测问题。的计算贡献是由一个多分支，多专家推出算法的设计，使几个国家的最先进的方法作为基础的算法，并允许几个专家来评估产生的部分候选解决方案，从而避免假设的奖励被优化的RNA分子折叠时。我们的实现允许有效地利用并行计算资源，以及控制的大小的推出树的算法的进展。RNA的二级结构预测是生物学领域的一个重要问题，因为分子结构与其功能密切相关。虽然论文的贡献在于算法，但应用程序的重要性使ExpertRNA成为支持科学发现的计算效率算法的相关性的展示。
Ribonucleic acid (RNA) is a fundamental biological molecule that is essential to all living organisms, performing a versatile array of cellular tasks. The function of many RNA molecules is strongly related to the structure it adopts. As a result, great effort is being dedicated to the design of efficient algorithms that solve the “folding problem”—given a sequence of nucleotides, return a probable list of base pairs, referred to as the secondary structure prediction. Early algorithms largely rely on finding the structure with minimum free energy. However, the predictions rely on effective simplified free energy models that may not correctly identify the correct structure as the one with the lowest free energy. In light of this, new, data-driven approaches that not only consider free energy, but also use machine learning techniques to learn motifs are also investigated and recently been shown to outperform free energy–based algorithms on several experimental data sets. In this work, we introduce the new ExpertRNA algorithm that provides a modular framework that can easily incorporate an arbitrary number of rewards (free energy or nonparametric/data driven) and secondary structure prediction algorithms. We argue that this capability of ExpertRNA has the potential to balance out different strengths and weaknesses of state-of-the-art folding tools. We test ExpertRNA on several RNA sequence-structure data sets, and we compare the performance of ExpertRNA against a state-of-the-art folding algorithm. We find that ExpertRNA produces, on average, more accurate predictions of nonpseudoknotted secondary structures than the structure prediction algorithm used, thus validating the promise of the approach. Summary of Contribution: ExpertRNA is a new algorithm inspired by a biological problem. It is applied to solve the problem of secondary structure prediction for RNA molecules given an input sequence. The computational contribution is given by the design of a multibranch, multiexpert rollout algorithm that enables the use of several state-of-the-art approaches as base heuristics and allowing several experts to evaluate partial candidate solutions generated, thus avoiding assuming the reward being optimized by an RNA molecule when folding. Our implementation allows for the effective use of parallel computational resources as well as to control the size of the rollout tree as the algorithm progresses. The problem of RNA secondary structure prediction is of primary importance within the biology field because the molecule structure is strongly related to its functionality. Whereas the contribution of the paper is in the algorithm, the importance of the application makes ExpertRNA a showcase of the relevance of computationally efficient algorithms in supporting scientific discovery.