Dimitrieva Slavica, Bucher Philipp
Swiss Institute of Bioinformatics and Swiss Institute for Experimental Cancer Research, Swiss Federal Institute of Technology, Lausanne, 1015, Switzerland.
J Bioinform Comput Biol. 2012 Apr;10(2):1241007. doi: 10.1142/S0219720012410077.
Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n(3)). Recently, it has been claimed that RNA folding can be achieved in average time O(n(2)) using a sparsification technique. A proof of quadratic time complexity was based on the assumption that computational RNA folding obeys the "polymer-zeta property". Several variants of sparse RNA folding algorithms were later developed. Here, we present our own version, which is readily applicable to existing RNA folding programs, as it is extremely simple and does not require any new data structure. We applied it to the widely used Vienna RNAfold program, to create sibRNAfold, the first public sparsified version of a standard RNA folding program. To gain a better understanding of the time complexity of sparsified RNA folding in general, we carried out a thorough run time analysis with synthetic random sequences, both in the context of energy minimization and base pairing maximization. Contrary to previous claims, the asymptotic time complexity of a sparsified RNA folding algorithm using standard energy parameters remains O(n(3)) under a wide variety of conditions. Consistent with our run-time analysis, we found that RNA folding does not obey the "polymer-zeta property" as claimed previously. Yet, a basic version of a sparsified RNA folding algorithm provides 15- to 50-fold speed gain. Surprisingly, the same sparsification technique has a different effect when applied to base pairing optimization. There, its asymptotic running time complexity appears to be either quadratic or cubic depending on the base composition. The code used in this work is available at: .
常用的RNA折叠程序在伪结排除约束下计算序列的最小自由能结构。它们基于运行时间为O(n(3))的祖克算法。最近，有人声称使用一种稀疏化技术可以在平均时间O(n(2))内实现RNA折叠。二次时间复杂度的证明基于计算RNA折叠遵循“聚合物-ζ属性”这一假设。后来又开发了几种稀疏RNA折叠算法的变体。在此，我们展示我们自己的版本，它非常简单，不需要任何新的数据结构，因此很容易应用于现有的RNA折叠程序。我们将其应用于广泛使用的维也纳RNAfold程序，创建了sibRNAfold，这是标准RNA折叠程序的首个公开稀疏版本。为了更全面地理解一般情况下稀疏RNA折叠的时间复杂度，我们在能量最小化和碱基配对最大化的背景下，对合成随机序列进行了全面的运行时间分析。与之前的说法相反，在各种条件下，使用标准能量参数的稀疏RNA折叠算法的渐近时间复杂度仍然是O(n(3))。与我们的运行时间分析一致，我们发现RNA折叠并不像之前所声称的那样遵循“聚合物-ζ属性”。然而，稀疏RNA折叠算法的一个基本版本能提供15到50倍的速度提升。令人惊讶的是，同样的稀疏化技术应用于碱基配对优化时会产生不同的效果。在那里，其渐近运行时间复杂度根据碱基组成似乎要么是二次的，要么是三次的。这项工作中使用的代码可在以下网址获取： 。
