Senter Evan, Dotu Ivan, Clote Peter
Department of Biology, Boston College, Chestnut Hill, MA, 02467, USA.
J Math Biol. 2015 Jan;70(1-2):173-96. doi: 10.1007/s00285-014-0760-4. Epub 2014 Feb 12.
RNA folding pathways play an important role in various biological processes, such as (i) the hok/sok (host-killing/suppression of killing) system in E. coli to check for sufficient plasmid copy number, (ii) the conformational switch in spliced leader (SL) RNA from Leptomonas collosoma, which controls trans splicing of a portion of the '5 exon, and (iii) riboswitches--portions of the 5' untranslated region of messenger RNA that regulate genes by allostery. Since RNA folding pathways are determined by the energy landscape, we describe a novel algorithm, FFTbor2D, which computes the 2D projection of the energy landscape for a given RNA sequence. Given two metastable secondary structures A, B for a given RNA sequence, FFTbor2D computes the Boltzmann probability p(x, y) = Z(x,y)/Z that a secondary structure has base pair distance x from A and distance y from B. Using polynomial interpolationwith the fast Fourier transform,we compute p(x, y) in O(n(5)) time and O(n(2)) space, which is an improvement over an earlier method, which runs in O(n(7)) time and O(n(4)) space. FFTbor2D has potential applications in synthetic biology, where one might wish to design bistable switches having target metastable structures A, B with favorable pathway kinetics. By inverting the transition probability matrix determined from FFTbor2D output, we show that L. collosoma spliced leader RNA has larger mean first passage time from A to B on the 2D energy landscape, than 97.145% of 20,000 sequences, each having metastable structures A, B. Source code and binaries are freely available for download at http://bioinformatics.bc.edu/clotelab/FFTbor2D. The program FFTbor2D is implemented in C++, with optional OpenMP parallelization primitives.
RNA折叠途径在各种生物学过程中发挥着重要作用，例如：（i）大肠杆菌中的hok/sok（宿主杀伤/杀伤抑制）系统，用于检查质粒拷贝数是否充足；（ii）来自粗短锥虫的剪接前导（SL）RNA中的构象转换，它控制一部分5'外显子的反式剪接；（iii）核糖开关——信使RNA 5'非翻译区的一部分，通过变构调节基因。由于RNA折叠途径由能量景观决定，我们描述了一种新颖的算法FFTbor2D，它可以计算给定RNA序列的能量景观的二维投影。对于给定RNA序列的两个亚稳态二级结构A和B，FFTbor2D计算二级结构与A的碱基对距离为x且与B的距离为y时的玻尔兹曼概率p(x, y) = Z(x,y)/Z。通过使用快速傅里叶变换进行多项式插值，我们在O(n(5))时间和O(n(2))空间内计算p(x, y)，这比早期方法有所改进，早期方法的运行时间为O(n(7))且空间为O(n(4))。FFTbor2D在合成生物学中有潜在应用，在合成生物学中，人们可能希望设计具有目标亚稳态结构A和B且具有良好途径动力学的双稳态开关。通过反转由FFTbor2D输出确定的转移概率矩阵，我们表明，在二维能量景观上，粗短锥虫剪接前导RNA从A到B的平均首次通过时间比20,000个序列中的97.145%都要长，每个序列都具有亚稳态结构A和B。源代码和二进制文件可在http://bioinformatics.bc.edu/clotelab/FFTbor2D免费下载。程序FFTbor2D用C++实现，并带有可选的OpenMP并行化原语。
