A Unified Dynamic Programming Framework for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed
A Unified Dynamic Programming Framework for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed
复制标题
DOI：
10.1021/acssynbio.9b00523
复制
发表时间：
2020-10-16
影响因子：
4.7
通讯作者：
Pierce, Niles A.
中科院分区：
文献类型：
--
作者：
Fornace, Mark E.;Porubsky, Nicholas J.;Pierce, Niles A.
NUPACK软件套件中的动态规划算法能够分析包含任意数量相互作用链物种的复杂和试管集成的核酸序列，服务于分子编程，核酸纳米技术，合成生物学和整个生命科学研究人员的需求。在这里，为了增强底层物理模型，确保大规模计算的可扩展性，并在计算复杂和试管集成的不同物理量时实现显着的加速，我们引入了一个统一的动态规划框架，它结合了三个成分：(1)指定子问题之间依赖关系并包含结构系综和自由能模型细节的递归；(2)定义每个子问题数学形式的评估代数；(3)通过子问题依赖图指定计算轨迹的操作顺序。使用新的递归来增强物理模型，这些递归操作在复杂的系综上，包括同轴和摆动堆叠子系综。递归进行一般编码，然后使用特定数量的评估代数和操作顺序编译，以生成每个物理量的可执行文件：配分函数、平衡碱基配对概率、MFE能量和代理结构、次优代理结构和玻尔兹曼抽样结构。对于大型复合体（例如，30,000 nt），使用溢出安全评估代数实现配分函数计算的可扩展性，以及使用无回溯操作顺序实现平衡基对概率的可扩展性。一个新的块操作顺序，处理试管集合中复杂物种的亚复杂块，使用矢量化和缓存可以显着加速（例如20-120倍）。有了这些性能的增强，大量试管整体的平衡分析可以在
Dynamic programming algorithms within the NUPACK software suite enable analysis of nucleic acid sequences over complex and test tube ensembles containing arbitrary numbers of interacting strand species, serving the needs of researchers in molecular programming, nucleic acid nanotechnology, synthetic biology, and across the life sciences. Here, to enhance the underlying physical model, ensure scalability for large calculations, and achieve dramatic speedups when calculating diverse physical quantities over complex and test tube ensembles, we introduce a unified dynamic programming framework that combines three ingredients: (1) recursions that specify the dependencies between subproblems and incorporate the details of the structural ensemble and the free energy model, (2) evaluation algebras that define the mathematical form of each subproblem, (3) operation orders that specify the computational trajectory through the dependency graph of subproblems. The physical model is enhanced using new recursions that operate over the complex ensemble including coaxial and dangle stacking subensembles. The recursions are coded generically and then compiled with a quantity-specific evaluation algebra and operation order to generate an executable for each physical quantity: partition function, equilibrium base-pairing probabilities, MFE energy and proxy structure, suboptimal proxy structures, and Boltzmann sampled structures. For large complexes (e.g., 30 000 nt), scalability is achieved for partition function calculations using an overflow-safe evaluation algebra, and for equilibrium base-pairing probabilities using a backtrack-free operation order. A new blockwise operation order that treats subcomplex blocks for the complex species in a test tube ensemble enables dramatic speedups (e.g., 20-120X ) using vectorization and caching. With these performance enhancements, equilibrium analysis of substantial test tube ensembles can be performed in