Busch Anke, Backofen Rolf
Albert-Ludwigs-University Freiburg, Institute of Computer Science, Chair of Bioinformatics Georges-Koehler-Allee 106, 79110 Freiburg, Germany.
Bioinformatics. 2006 Aug 1;22(15):1823-31. doi: 10.1093/bioinformatics/btl194. Epub 2006 May 18.
The structure of RNA molecules is often crucial for their function. Therefore, secondary structure prediction has gained much interest. Here, we consider the inverse RNA folding problem, which means designing RNA sequences that fold into a given structure.
We introduce a new algorithm for the inverse folding problem (INFO-RNA) that consists of two parts; a dynamic programming method for good initial sequences and a following improved stochastic local search that uses an effective neighbor selection method. During the initialization, we design a sequence that among all sequences adopts the given structure with the lowest possible energy. For the selection of neighbors during the search, we use a kind of look-ahead of one selection step applying an additional energy-based criterion. Afterwards, the pre-ordered neighbors are tested using the actual optimization criterion of minimizing the structure distance between the target structure and the mfe structure of the considered neighbor. We compared our algorithm to RNAinverse and RNA-SSD for artificial and biological test sets. Using INFO-RNA, we performed better than RNAinverse and in most cases, we gained better results than RNA-SSD, the probably best inverse RNA folding tool on the market.
RNA分子的结构通常对其功能至关重要。因此，二级结构预测备受关注。在此，我们考虑RNA反向折叠问题，即设计能折叠成给定结构的RNA序列。
我们引入了一种用于反向折叠问题的新算法（INFO-RNA），它由两部分组成；一种用于生成良好初始序列的动态规划方法以及随后使用有效邻居选择方法的改进随机局部搜索。在初始化过程中，我们设计一个在所有序列中采用给定结构且能量尽可能低的序列。在搜索过程中选择邻居时，我们使用一种通过应用基于能量的额外标准来提前一步进行前瞻的方法。之后，使用将目标结构与所考虑邻居的最小自由能结构之间的结构距离最小化的实际优化标准对预先排序的邻居进行测试。我们将我们的算法与用于人工和生物测试集的RNAinverse和RNA-SSD进行了比较。使用INFO-RNA，我们的表现优于RNAinverse，并且在大多数情况下，我们获得了比RNA-SSD更好的结果，RNA-SSD可能是市场上最好的反向RNA折叠工具。
