Premium
An algorithm for computing nucleic acid base‐pairing probabilities including pseudoknots
Author(s) -
Dirks Robert M.,
Pierce Niles A.
Publication year - 2004
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.20057
Subject(s) - recursion (computer science) , algorithm , backtracking , nucleic acid , computer science , partition (number theory) , permutation (music) , partition function (quantum field theory) , mathematics , combinatorics , chemistry , physics , biochemistry , quantum mechanics , acoustics
Given a nucleic acid sequence, a recent algorithm allows the calculation of the partition function over secondary structure space including a class of physically relevant pseudoknots. Here, we present a method for computing base‐pairing probabilities starting from the output of this partition function algorithm. The approach relies on the calculation of recursion probabilities that are computed by backtracking through the partition function algorithm, applying a particular transformation at each step. This transformation is applicable to any partition function algorithm that follows the same basic dynamic programming paradigm. Base‐pairing probabilities are useful for analyzing the equilibrium ensemble properties of natural and engineered nucleic acids, as demonstrated for a human telomerase RNA and a synthetic DNA nanostructure. © 2004 Wiley Periodicals, Inc. J Comput Chem 25: 1295–1304, 2004