A Unified Dynamic Programming Framework for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed
Authors:
- 10 September 2020
- journal article
- research article
- Published by American Chemical Society (ACS) in ACS Synthetic Biology
- Vol. 9 (10) , 2665-2678
Abstract
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–120× ) using vectorization and caching. With these performance enhancements, equilibrium analysis of substantial test tube ensembles can be performed in ≤ 1 min on a single computational core (e.g., partition function and equilibrium concentration for all complex species of up to six strands formed from two strand species of 300 nt each, or for all complex species of up to two strands formed from 80 strand species of 100 nt each). A new sampling algorithm simultaneously samples multiple structures from the complex ensemble to yield speedups of an order of magnitude or more as the number of structures increases above ≈103. These advances are available within the NUPACK 4.0 code base (www.nupack.org) which can be flexibly scripted using the all-new NUPACK Python module.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-1317694)
- Division of Chemistry (CHE-1643606)
- University of Oxford
- Office of Cyberinfrastructure (NSF-OAC-1835414)
- Balliol College, University of Oxford
- National Institutes of Health (T32 GM007616)
- Beckman Institute, Caltech
This publication has 33 references indexed in Scilit:
- Thermodynamic properties of DNA sequences: characteristic values for the human genomeBioinformatics, 2005
- The Thermodynamics of DNA Structural MotifsAnnual Review of Biophysics, 2004
- Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structureProceedings of the National Academy of Sciences, 2004
- Mfold web server for nucleic acid folding and hybridization predictionNucleic Acids Research, 2003
- Thermodynamic parameters for DNA sequences with dangling endsNucleic Acids Research, 2000
- Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structureJournal of Molecular Biology, 1999
- Thermodynamic Parameters for an Expanded Nearest-Neighbor Model for Formation of RNA Duplexes with Watson−Crick Base PairsBiochemistry, 1998
- A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamicsProceedings of the National Academy of Sciences, 1998
- [11] Predicting thermodynamic properties of RNA1995
- Estimation of Secondary Structure in Ribonucleic AcidsNature, 1971