Laboratoire de Recherche en Informatique, Université Paris-Sud XI, bât. 490, 91405 Orsay cedex, France.
Bioinformatics. 2010 Jun 15;26(12):i278-86. doi: 10.1093/bioinformatics/btq218.
Thermodynamics-based dynamic programming RNA secondary structure algorithms have been of immense importance in molecular biology, where applications range from the detection of novel selenoproteins using expressed sequence tag (EST) data, to the determination of microRNA genes and their targets. Dynamic programming algorithms have been developed to compute the minimum free energy secondary structure and partition function of a given RNA sequence, the minimum free-energy and partition function for the hybridization of two RNA molecules, etc. However, the applicability of dynamic programming methods depends on disallowing certain types of interactions (pseudoknots, zig-zags, etc.), as their inclusion renders structure prediction an nondeterministic polynomial time (NP)-complete problem. Nevertheless, such interactions have been observed in X-ray structures.
A non-Boltzmannian Monte Carlo algorithm was designed by Wang and Landau to estimate the density of states for complex systems, such as the Ising model, that exhibit a phase transition. In this article, we apply the Wang-Landau (WL) method to compute the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. Our method is shown to be much faster than existent software, such as RNAsubopt. From density of states, we compute the partition function over all secondary structures and over all pseudoknot-free hybridizations. The advantage of the WL method is that by adding a function to evaluate the free energy of arbitrary pseudoknotted structures and of arbitrary hybridizations, we can estimate thermodynamic parameters for situations known to be NP-complete. This extension to pseudoknots will be made in the sequel to this article; in contrast, the current article describes the WL algorithm applied to pseudoknot-free secondary structures and hybridizations.
The WL RNA hybridization web server is under construction at http://bioinformatics.bc.edu/clotelab/.
基于热力学的动态规划 RNA 二级结构算法在分子生物学中具有重要意义，其应用范围从使用表达序列标签 (EST) 数据检测新型硒蛋白，到确定 microRNA 基因及其靶标。已经开发了动态规划算法来计算给定 RNA 序列的最小自由能二级结构和配分函数、两个 RNA 分子杂交的最小自由能和配分函数等。然而，动态规划方法的适用性取决于不允许某些类型的相互作用（假结、Zig-Zag 等），因为它们的包含使得结构预测成为非确定性多项式时间（NP）完全问题。然而，在 X 射线结构中已经观察到了这种相互作用。
Wang 和 Landau 设计了一种非玻尔兹曼蒙特卡罗算法来估计具有相变的复杂系统（如伊辛模型）的态密度。在本文中，我们应用 Wang-Landau (WL) 方法来计算给定 RNA 序列的二级结构和两个 RNA 序列杂交的态密度。我们的方法比现有的软件（如 RNAsubopt）快得多。从态密度，我们计算所有二级结构和所有无假结杂交的配分函数。WL 方法的优点是，通过添加一个函数来评估任意假结结构和任意杂交的自由能，我们可以估计已知 NP 完全的情况下的热力学参数。这个对假结的扩展将在本文的后续部分进行；相比之下，本文描述了 WL 算法应用于无假结的二级结构和杂交。
WL RNA 杂交网络服务器正在建设中，网址是 http://bioinformatics.bc.edu/clotelab/。
