Transfer Matrix and Tensor Approaches to Nucleic Acid Secondary Structure Thermodynamics
Nucleic acid secondary structure thermodynamic models have great utility for the analysis and design of nucleic acid structures, devices, and systems, yet their complexity and piecemeal development over decades pose challenges to further innovation. Employing different functional forms for each loop type within a structure, existing nearest neighbor (NN) models necessitate numerous loop-specific dynamic programming recursions in order to calculate physical quantities of interest. Here, we derive and implement a new class of models based on transfer matrices, yielding a single functional form for the free energy of all loop types (as the trace of a matrix product) and a single dynamic programming recursion for calculating physical quantities of interest. This new class of models has additional attractive properties: 1) incorporating a subensemble of states describing proximal interactions within each loop, 2) approximating logarithmic entropic scaling for all closed loops, 3) offering the opportunity to model correlations between the subensembles of neighboring loops by generalizing transfer matrices to tensors, and 4) providing a basis for systematically adjusting the number of model parameters to enhance accuracy as new empirical data become available for parameter regression. We use literature experimental data to regress parameters for representative new transfer matrix models, observing accuracy as good as or better than that of existing NN models, yet using dramatically fewer parameters (e.g., dozens vs hundreds or thousands). For complex ensembles containing an arbitrary number of interacting nucleic acid strands totaling N nucleotides, the new single recursion leads to exact dynamic programs for calculating diverse physical quantities (including the partition function, equilibrium base-pairing probabilities, minimum free energy and suboptimal proxy structures, Boltzmann-sampled secondary structures, and gradient of the partition function) with O(N3) time complexity. The simplicity of the new partition function dynamic program enables overflow-safe partition function calculations using renormalization to achieve scalability for large complexes (e.g., 50,000 nt) as well as formulation using a global matrix multiplication primitive that facilitates GPU acceleration, yielding speedups of an order of magnitude relative to NN partition function algorithms for large complexes. The new class of transfer matrix and tensor models provides an elegant framework for future efforts to advance the accuracy, speed, and scope of computational nucleic acid analysis and design.