Algorithmic hardness of the partition function for nucleic acid strands

Ahmed Shalaby; Damien Woods; Gwendal Ducloz

REVIEW 4 major objections 4 minor 38 references

Algorithmic hardness of the partition function for nucleic acid strands

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Computing the nucleic-acid partition function is $\#\mathrm{P}$-hard in two settings where it was open.

desk verdict Answers two open PF-hardness questions with a genuinely new reduction framework, but the #SSEL-to-PF bridge needs a real-number model and precision analysis. read the letter →

arxiv 2506.19756 v1 pith:5UPNAHDZ submitted 2025-06-24 cs.CC

Gwendal Ducloz , Ahmed Shalaby , Damien Woods This is my paper · ORCID

classification cs.CC MSC 68Q1768Q1592D20

keywords partitionfunctionminimumfreeenergysecondarystructurenucleicacidsDNA/RNAfoldingcomputationalcomplexity#P-hardnessmagnificationtrick

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that computing the partition function — the weighted sum over all secondary structures that governs equilibrium probabilities — is $\#\mathrm{P}$-hard in two settings where the question was open: systems with an unbounded number of strands, and a single strand when pseudoknots are allowed. The proof introduces a magnification trick that rescales all free energies by a factor and reads off, from the rescaled partition function, how many structures sit at each energy level. The same reductions tie together five thermodynamic problems — MFE, PF, their decision versions, and the counting problem $\#\mathrm{SSEL}$ — showing they have matching complexity in any energy model that admits magnification. If the argument is right, the partition function is not merely as hard as minimum-free-energy prediction; it is strictly harder unless the polynomial hierarchy collapses.

What carries the argument

The engine is the magnification trick: for a positive integer $j$, define the $j$-magnified energy model by multiplying every free energy by $j$, and call a partition-function oracle on it. The values returned satisfy $b_j = \sum_i \#\mathrm{SSEL}(g_i)(e^{-\beta g_i})^j$, so the first $N$ values form a Vandermonde system — a linear system whose rows are successive powers of the energy weights — whose unique solution is the vector of structure counts at the $N$ candidate energy levels. A second use of magnification with an enormous factor makes the minimum-free-energy structure dominate the sum, turning dPF into dMFE, while a base-$n!$ expansion of the magnified partition function turns PF into dPF. The counting-hardness results are carried by weakly parsimonious reductions: each solution of the source problem maps to a fixed, easily computed number of secondary structures, so the count of solutions is preserved.

What would settle it

Exhibit a family of BPM or BPS strand systems in which the matrix with entries $(e^{-\beta g_i})^j$ is so ill-conditioned that recovering the integer counts $\#\mathrm{SSEL}(g_i)$ from exact oracle values is provably impossible with polynomial precision; that would break the reduction from $\#\mathrm{SSEL}$ to PF even though $\#\mathrm{SSEL}$ itself may remain $\#\mathrm{P}$-hard.

Watch

Extended reading notes

Core claim

The central discovery is a reduction map in which MFE, dMFE, PF, dPF, and $\#\mathrm{SSEL}$ are mutually reducible by polynomial-time Turing reductions whenever the energy model supports magnification, together with two concrete hardness results. For a single strand with pseudoknots in the base-pair-stacking (BPS) model, the paper shows PF is $\#\mathrm{P}$-hard through a weakly parsimonious chain that starts from $\#3$-dimensional matching, passes through $\#4$-PARTITION, and reaches the problem of counting secondary structures with a given number of stacks. For an unbounded number of strands in the base-pair-matching (BPM) model, it proves the same by converting a known NP-hardness construction for multi-stranded MFE into a counting reduction. In both settings the hardness of PF is inherited from $\#\mathrm{SSEL}$, the problem of counting structures of a specified free energy, through the new reduction from $\#\mathrm{SSEL}$ to PF.

Load-bearing premise

The load-bearing premise is that a partition-function oracle returns exact numbers and that the structure counts can be recovered from the magnified values with only polynomial-precision linear algebra; if that recovery forces super-polynomial precision, the hardness conclusions do not follow from these reductions.

Editorial extensions

If this is right

If an energy model is PF-polynomially magnifiable — meaning a polynomial-time PF algorithm exists for every magnified version — then MFE, dMFE, dPF, and $\#\mathrm{SSEL}$ are all in P as well.
In the unbounded-strand BPM setting and the single-strand pseudoknotted BPS setting, PF and dPF are $\#\mathrm{P}$-hard while dMFE is NP-complete; unless $\#\mathrm{P} \subseteq \mathrm{P}^{\mathrm{NP}}$, which collapses the polynomial hierarchy, the partition function is strictly harder than the MFE decision problem.
$\#\mathrm{SSEL}$ is $\#\mathrm{P}$-complete in both settings, and PF and $\#\mathrm{SSEL}$ are mutually reducible, so a polynomial-time algorithm for either would give one for the other.
There is no polynomial-time Turing reduction from $\#\mathrm{SSEL}$ to dMFE in the BPS model unless $\#\mathrm{P} \subseteq \mathrm{P}^{\mathrm{NP}}$, so the reduction map cannot be tightened in that direction.
The reduction map also gives an upper bound: all five problems lie in EXP, because enumerating all secondary structures is exponential in the number of bases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The load-bearing step in Section 3.2 (Algorithm 1) assumes exact PF oracle values and polynomial-size Gaussian elimination, with no conditioning or precision analysis; if recovering the integer counts $\#\mathrm{SSEL}(g_i)$ from those values requires super-polynomial precision in a standard Turing model, the reduction from $\#\mathrm{SSEL}$ to PF does not go through as written.
The magnification trick is a general recipe for weighted counting: any quantity of the form $\sum_i c_i w_i^j$ over a polynomial-size set of levels can be inverted from evaluations at $j=1,\dots,N$, so the technique may transfer to other Boltzmann-weighted counting problems.
If the full nearest-neighbour model were shown to be PF-polynomially magnifiable, Corollary 26 would immediately put MFE, dPF, and the density-of-states problem in P; the paper leaves that as an explicit open question.
The paper's open question of whether all magnification-based arrows can be replaced by direct reductions suggests a route for extending hardness results to energy models that do not admit magnification.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. The paper really does look like it answers both open questions about the partition function: PF is #P-hard for multiple strands in the BPM model and for a single pseudoknotted strand in the BPS model. And the reduction map among MFE, dMFE, PF, dPF, and #SSEL, built on the magnification trick, is a genuinely new framework that should transfer to other energy models. The core combinatorial reductions in Sections 4 and 5 are plausible, and the counting arguments are mostly explicit. That said, the bridge from #SSEL to PF, Theorem 22, has a real gap that touches both headline results.

The gap is exact real arithmetic. Algorithm 1 queries a PF oracle on a magnified model and assembles a Vandermonde system whose nodes are e^{-\beta g_i}. The proof says the largest entry of the matrix has size poly(n) and then runs Gaussian elimination. That silently assumes the oracle outputs exactly representable reals. In the standard binary Turing model, the query answers are generally transcendental, so they have no finite representation at all, and the bit-length bound is not justified. The stress-test note is right that the conditioning analysis is missing. The good news is the problem looks repairable: for these geometric node sets, finite precision with polynomially many bits (about n^2) should suffice to recover the integer counts, but that requires a stated computational model for real-valued oracle functions and a precision analysis. As written, the conclusion "PF is #P-hard" only follows if you accept that extra machinery.

The other soft spot is Theorem 37. The weak parsimony proof for the Condon, Hajiaghayi, and Thachuk reduction is sketched, not fully given: it refers to lemmas in the cited paper and then splits on distinguishable versus indistinguishable strands. The counting factor (2n)!^2(2m+n)! may be right, but the paper doesn't show enough detail to verify that no other overcounting occurs. For a conference paper this might pass with a pointer to the full proof; for a journal it needs more.

The appendix on candidate energy levels for the NN model, with the logarithmic precision assumption, is careful and honest. The assumption is clearly flagged as a physical approximation. I would like to see the paper again after the authors address the two issues above. In its current form, it deserves a serious referee, not a desk rejection, but the referee should be asked to check the real-number model and the parsimony count.

Referee Report

4 major / 4 minor

Summary. The paper proves #P-hardness of computing the partition function (PF) for two nucleic acid secondary-structure settings: (i) a single strand with pseudoknots under the base-pair stacking (BPS) model, and (ii) an unbounded number of strands with unpseudoknotted structures under the base-pair matching (BPM) model. The proofs combine #P-completeness of the counting problems #SSEL, #BPS, and #MULTI-PKF-SSP with a general reduction map among MFE, dMFE, PF, dPF, and #SSEL. The authors introduce an 'energy magnification trick' and a class of 'PF-polynomially magnifiable' energy models, and they show that all five problems are mutually related by polynomial-time Turing reductions when such magnification is available. The paper answers two open questions from the literature if the central reduction from #SSEL to PF is valid in the intended computational model.

Significance. If the results hold, they resolve two well-known open problems and show that the partition function is strictly harder than the decision version of MFE in these settings unless the polynomial hierarchy collapses. The magnification trick is an elegant and potentially transferable idea, and the combinatorial reductions for #BPS and #MULTI-PKF-SSP appear plausible and are worked out in unusual detail. The paper also offers a clean conceptual organization of five thermodynamic problems and gives concrete open questions about the NN model. However, the main hardness results for PF depend on one reduction step whose computational model is not specified and whose precision analysis is missing, so the significance is conditional on that step being repaired.

major comments (4)

[Section 3.2, Theorem 22 and Algorithm 1] The reduction from #SSEL to PF assumes that the PF oracle returns exact real values b_j = PF(s,T,M_j) and that the resulting Vandermonde system can be solved exactly by Gaussian elimination. The paper never specifies the computational model for PF: it is not stated whether PF is a function in the standard binary Turing model, a BSS/real-RAM function, or an oracle returning exact reals. In the standard model, the outputs b_j are in general irrational (already for BPM, e^{-βg_i} = e^{βi} is transcendental by the Lindemann-Weierstrass theorem), so they have no finite binary representation and the algorithm's step 'solve the system' is not well defined on a Turing machine. This is load-bearing because Theorems 33 and 38 conclude PF is #P-hard solely by composing #SSEL hardness with Theorem 22.
[Section 3.2, proof of Theorem 22, bit-size bound] The time analysis states that 'the largest entry of A has size log((e^{-βg_N})^N) = N log(e^{-βg_N}) = poly(n)' and similarly for b, but this silently assumes that the entries e^{-βg_i} and the exact sums b_j are representable in poly(n) bits. They are not finite strings in the standard model. Even if the oracle returns approximations, the Vandermonde matrix with nodes e^{-βg_i} can be extremely ill-conditioned when energy levels are close (e.g., in the NN model with logarithmic precision, δ can be n^{-O(1)}), so no precision analysis is given to show that poly(n) bits of oracle accuracy suffice to recover the integer counts #SSEL(g_i). Without such an analysis, the claimed polynomial-time Turing reduction is incomplete.
[Theorems 33 and 38] Because both headline PF-hardness theorems invoke Theorem 22 without any alternative argument, the main results do not follow from the text as written. To make the claims rigorous, the authors must either (a) define PF as an exact real computation problem and prove hardness in that model with a corresponding notion of reduction, or (b) provide a precise finite-precision analysis showing that a standard PF oracle (e.g., one returning fixed-precision rational approximations) is sufficient to recover the counts in polynomial time. This is not merely a presentation issue; it changes the meaning of the quantifiers in the hardness statements.
[Section 3.5, Definition 25] The definition of PF-polynomially magnifiable energy model and the claim that an algorithm for PF under M_j gives an oracle for the reduction are reasonable, but the reduction map in Figure 2 and Theorem 22 require that the magnified model M_j be a valid input to the same PF problem. The paper does not specify how an energy model is encoded as input, nor how the magnification factor j is represented. For BPM and BPS this is benign, but for the NN model the energy function includes temperature-dependent terms and logarithmic loop energies, so it is not immediate that M_j is a legitimate instance of the same decision/function problem. The authors should clarify the input encoding and, if necessary, restrict the magnification claim accordingly.

minor comments (4)

[Section 3.3, proof of Theorem 23] In the final paragraph of the proof, the statement 'dMFE(s,T,B,k) ⇔ dPF(s,T,B',k')' uses the letter B where the energy model M is meant; this is a typographical error that should be corrected.
[Abstract and Introduction] The abstract and introduction contain small wording and formatting issues, e.g., 'Condon Hajiaghayi, and Thachuk' lacks commas, 'nearest nieghbour' is misspelled, and the phrase 'giving theorists the vibe' is informal for a journal or LIPIcs proceedings paper.
[Section A.2.2, Lemma 43] The proof sketch of Lemma 43 is quite dense and refers to Algorithm 3 and Figure 4 without a full correctness argument relating the recursion equations to the NN energy model; a more detailed explanation of why the sumset operations correctly compute occupied energy levels would help readers who are not already familiar with the Dirks et al. recursion.
[Section 5.2, Lemma 40] The counting argument in Lemma 40 (the number of isolated flanks and the application of Lemma 17 from Condon et al.) is terse and relies on external lemmas from a cited paper; the text would benefit from a short explanation of why the recursive application terminates and how the contradiction is reached.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: PF hardness follows from external #SSEL completeness plus a genuine Vandermonde inversion, not from self-reference.

full rationale

The claimed #P-hardness of PF rests on two independent legs. First, #SSEL is shown #P-complete through weakly parsimonious reductions from #3DM to #4-PARTITION to #BPS/#MULTI-PKF-SSP, all grounded in external results (Bosboom et al., Condon et al., Lyngsø). Second, Theorem 22 gives #SSEL ≤_T PF by evaluating PF at N magnified energy models and inverting a Vandermonde system whose nodes are the distinct values e^{-βg_i}; the unknowns #SSEL(g_i) are recovered by linear algebra, not by definition. The target quantity is not an input to itself, and no fitted parameter is renamed as a prediction. Theorems 33 and 38 simply combine these independent facts. The only self-citations, such as Shalaby and Woods [27], are motivational or support positive results in the reduction map discussion; they are not load-bearing for the hardness theorems. The concern about exact real-valued PF oracles and precision of Vandermonde inversion is a computational-model rigor issue, not circularity: it does not exhibit a step where a derived claim is equivalent to its input by construction. No circular step is therefore identified, and the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters and no new physical entities. Its central claims rest on polynomial computability of energy level sets, on an exact real-arithmetic oracle model for PF, and on the weak parsimony of two prior reductions. The magnification trick is a proof technique rather than an invented entity.

assumptions (4)

domain assumption Candidate energy level sets G^M_s of polynomial size are computable in polynomial time (Note 13 and Lemma 42).
Used in every reduction to enumerate energy levels; for the NN model this relies on the logarithmic precision assumption for loop free energies.
domain assumption The PF and dPF oracles return exact real values, and the Vandermonde system in Theorem 22 can be solved exactly in polynomial time with polynomial bit complexity.
Unstated in the paper but necessary for the #SSEL to PF and PF to dPF reductions to be polynomial-time Turing reductions in a standard model.
standard math #3DM is #P-hard in the bounded-degree distinct-triples form used in Lemmas 31 and Theorem 37.
The paper cites reference [3] for this fact, which is a nonstandard citation; the fact itself is classical.
domain assumption The reduction of Condon et al. from 3DM(3) to MULTI-PKF-SSP is weakly parsimonious as claimed in Theorem 37.
The paper asserts this without fully proving it and explicitly omits many details of the prior reduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Algorithmic hardness of the partition function for nucleic acid strands." pith.science (2026). https://pith.science/paper/5UPNAHDZ

@misc{pith2026250619756,
  author       = {Pith},
  title        = {Pith review of: Algorithmic hardness of the partition function for nucleic acid strands},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5UPNAHDZ}},
  note         = {Machine review of arXiv:2506.19756}
}

read the original abstract

To understand and engineer biological and artificial nucleic acid systems, algorithms are employed for prediction of secondary structures at thermodynamic equilibrium. Dynamic programming algorithms are used to compute the most favoured, or Minimum Free Energy (MFE), structure, and the Partition Function (PF), a tool for assigning a probability to any structure. However, in some situations, such as when there are large numbers of strands, or pseudoknoted systems, NP-hardness results show that such algorithms are unlikely, but only for MFE. Curiously, algorithmic hardness results were not shown for PF, leaving two open questions on the complexity of PF for multiple strands and single strands with pseudoknots. The challenge is that while the MFE problem cares only about one, or a few structures, PF is a summation over the entire secondary structure space, giving theorists the vibe that computing PF should not only be as hard as MFE, but should be even harder. We answer both questions. First, we show that computing PF is #P-hard for systems with an unbounded number of strands, answering a question of Condon Hajiaghayi, and Thachuk [DNA27]. Second, for even a single strand, but allowing pseudoknots, we find that PF is #P-hard. Our proof relies on a novel magnification trick that leads to a tightly-woven set of reductions between five key thermodynamic problems: MFE, PF, their decision versions, and #SSEL that counts structures of a given energy. Our reductions show these five problems are fundamentally related for any energy model amenable to magnification. That general classification clarifies the mathematical landscape of nucleic acid energy models and yields several open questions.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 34 canonical work pages

[1]

Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

Tatsuya Akutsu. Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics , 104(1-3):45--62, 2000

work page 2000
[2]

Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

2009
[3]

Demaine, Martin L

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky. Path puzzles: Discrete tomography with a path constraint is hard. Graphs and Combinatorics , 36:251--267, 2020. URL: https://link.springer.com/article/10.1007/s00373-019-02092-5, https://doi.org/10.1007/s00373-019-02092-5 doi:10.1007/s00373-019-02092-5

work page doi:10.1007/s00373-019-02092-5 2020
[4]

An o (n 5) algorithm for mfe prediction of kissing hairpins and 4-chains in nucleic acids

Ho-Lin Chen, Anne Condon, and Hosna Jabbari. An o (n 5) algorithm for mfe prediction of kissing hairpins and 4-chains in nucleic acids. Journal of Computational Biology , 16(6):803--815, 2009

work page 2009
[5]

Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX -hard

Anne Condon, Monir Hajiaghayi, and Chris Thachuk. Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX -hard. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

work page 2021
[6]

Hofacker, and Peter F

Jan Cupal, Ivo L. Hofacker, and Peter F. Stadler. Dynamic programming algorithm for the density of states of rna secondary structures. In Reinhard Hofstädt, Thomas Lengauer, Markus Löffler, and Dirk Schomburg, editors, Computer Science and Biology'96 (German Conference on Bioinformatics) , pages 184--186, Leipzig, Germany, 1996. University of Leipzig

work page 1996
[7]

Domain-based nucleic-acid minimum free energy: Algorithmic hardness and parameterized bounds

Erik D Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods. Domain-based nucleic-acid minimum free energy: Algorithmic hardness and parameterized bounds. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30)(2024) , pages 2--1. Schloss Dagstuhl--Leibniz-Zentr...

work page 2024
[8]

Thermodynamic analysis of interacting nucleic acid strands

Robert M Dirks, Justin S Bois, Joseph M Schaeffer, Erik Winfree, and Niles A Pierce. Thermodynamic analysis of interacting nucleic acid strands. SIAM review , 49(1):65--88, 2007

2007

Show all 38 references

[9]

A partition function algorithm for nucleic acid secondary structure including pseudoknots

Robert M Dirks and Niles A Pierce. A partition function algorithm for nucleic acid secondary structure including pseudoknots. Journal of computational chemistry , 24(13):1664--1677, 2003

2003
[10]

An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots

Robert M Dirks and Niles A Pierce. An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots. Journal of computational chemistry , 25(10):1295--1304, 2004

2004
[11]

A unified dynamic programming framework for the analysis of interacting nucleic acid strands: enhanced models, scalability, and speed

Mark E Fornace, Nicholas J Porubsky, and Niles A Pierce. A unified dynamic programming framework for the analysis of interacting nucleic acid strands: enhanced models, scalability, and speed. ACS Synthetic Biology , 9(10):2665--2678, 2020

2020
[12]

Computers and intractability

Michael R Garey and David S Johnson. Computers and intractability. A Guide to the , 1979

1979
[13]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., USA, 1979

1979
[14]

A complexity dichotomy for partition functions with mixed signs, 2009

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs, 2009. URL: https://arxiv.org/abs/0804.1932, https://arxiv.org/abs/0804.1932 arXiv:0804.1932

2009 arXiv
[15]

Knotty: efficient and accurate prediction of complex RNA pseudoknot structures

Hosna Jabbari, Ian Wark, Carlo Montemagno, and Sebastian Will. Knotty: efficient and accurate prediction of complex RNA pseudoknot structures. Bioinformatics , 34(22):3849--3856, 2018

2018
[16]

Intramolecular reaction in polycondensations

Homer Jacobson and Walter H Stockmayer. Intramolecular reaction in polycondensations. i. the theory of linear systems. The Journal of chemical physics , 18(12):1600--1606, 1950

1950
[17]

ViennaRNA package 2.0

Ronny Lorenz, Stephan H Bernhart, Christian H \"o ner zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker. ViennaRNA package 2.0. Algorithms for molecular biology , 6:1--14, 2011

2011
[18]

Thermodynamics of RNA structures by W ang-- L andau sampling

Feng Lou and Peter Clote. Thermodynamics of RNA structures by W ang-- L andau sampling. Bioinformatics , 26(12):i278--i286, 2010

2010
[19]

RNA pseudoknot prediction in energy-based models

Rune B Lyngs and Christian NS Pedersen. RNA pseudoknot prediction in energy-based models. Journal of computational biology , 7(3-4):409--427, 2000

2000
[20]

Complexity of pseudoknot prediction in simple models

Rune Lyngsø. Complexity of pseudoknot prediction in simple models. volume 3142, pages 919--931, 07 2004. https://doi.org/10.1007/978-3-540-27836-8_77 doi:10.1007/978-3-540-27836-8_77

2004 doi
[21]

Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure

David H Mathews, Jeffrey Sabina, Michael Zuker, and Douglas H Turner. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. Journal of molecular biology , 288(5):911--940, 1999

1999
[22]

The equilibrium partition function and base pair binding probabilities for RNA secondary structure

John S McCaskill. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers: Original Research on Biomolecules , 29(6-7):1105--1119, 1990

1990
[23]

Fast algorithm for predicting the secondary structure of single-stranded RNA

Ruth Nussinov and Ann B Jacobson. Fast algorithm for predicting the secondary structure of single-stranded RNA . Proceedings of the National Academy of Sciences , 77(11):6309--6313, 1980

1980
[24]

Algorithms for loop matchings

Ruth Nussinov, George Pieczenik, Jerrold R Griggs, and Daniel J Kleitman. Algorithms for loop matchings. SIAM Journal on Applied mathematics , 35(1):68--82, 1978

1978
[25]

A dynamic programming algorithm for RNA structure prediction including pseudoknots

Elena Rivas and Sean R Eddy. A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of molecular biology , 285(5):2053--2068, 1999

1999
[26]

The thermodynamics of DNA structural motifs

John SantaLucia Jr and Donald Hicks. The thermodynamics of DNA structural motifs. Annu. Rev. Biophys. Biomol. Struct. , 33:415--440, 2004

2004
[27]

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands, 2024

Ahmed Shalaby and Damien Woods. An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands, 2024. ICALP 2025, accepted. URL: https://arxiv.org/abs/2407.09676

2024 arXiv
[28]

Estimation of secondary structure in ribonucleic acids

Ignacio Tinoco, Olke C Uhlenbeck, and Mark D Levine. Estimation of secondary structure in ribonucleic acids. Nature , 230(5293):362--367, 1971

1971
[29]

S. Toda. On the computational power of pp and (+)p. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science , SFCS '89, page 514–519, USA, 1989. IEEE Computer Society. https://doi.org/10.1109/SFCS.1989.63527 doi:10.1109/SFCS.1989.63527

1989
[30]

Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing , 8(3):410--421, 1979. https://doi.org/10.1137/0208032 doi:10.1137/0208032

1979 doi
[31]

Lindemann–weierstrass theorem

Wikipedia. Lindemann–weierstrass theorem. [Online; accessed 11-April-2025]. URL: https://en.wikipedia.org/wiki/Lindemann-Weierstrass_theorem

2025
[32]

Wikipedia. Sumset. [Online; accessed 18-June-2025]. URL: https://en.wikipedia.org/wiki/Sumset

2025
[33]

Complete suboptimal folding of RNA and the stability of secondary structures

Stefan Wuchty, Walter Fontana, Ivo L Hofacker, and Peter Schuster. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers: Original Research on Biomolecules , 49(2):145--165, 1999

1999
[34]

A case of mathematical eponymy: the V andermonde determinant

Bernard Ycart. A case of mathematical eponymy: the V andermonde determinant. Revue d'histoire des math \'e matiques , 2011. URL: https://api.semanticscholar.org/CorpusID:118023769

2011
[35]

Zadeh, Christopher D

John N. Zadeh, Christopher D. Steenberg, Justin S. Bois, Blake R. Wolfe, Matthew B. Pierce, Abbas R. Khan, Raymond M. Dirks, and Niles A. Pierce. NUPACK : Analysis and design of nucleic acid systems. Journal of Computational Chemistry , 32(1):170--173, 2011

2011
[36]

Mfold web server for nucleic acid folding and hybridization prediction

Michael Zuker. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic acids research , 31(13):3406--3415, 2003

2003
[37]

RNA secondary structures and their prediction

Michael Zuker and David Sankoff. RNA secondary structures and their prediction. Bulletin of mathematical biology , 46:591--621, 1984

1984
[38]

Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information

Michael Zuker and Patrick Stiegler. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic acids research , 9(1):133--148, 1981

1981

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

Tatsuya Akutsu. Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics , 104(1-3):45--62, 2000

work page 2000

[2] [2]

Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

2009

[3] [3]

Demaine, Martin L

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky. Path puzzles: Discrete tomography with a path constraint is hard. Graphs and Combinatorics , 36:251--267, 2020. URL: https://link.springer.com/article/10.1007/s00373-019-02092-5, https://doi.org/10.1007/s00373-019-02092-5 doi:10.1007/s00373-019-02092-5

work page doi:10.1007/s00373-019-02092-5 2020

[4] [4]

An o (n 5) algorithm for mfe prediction of kissing hairpins and 4-chains in nucleic acids

Ho-Lin Chen, Anne Condon, and Hosna Jabbari. An o (n 5) algorithm for mfe prediction of kissing hairpins and 4-chains in nucleic acids. Journal of Computational Biology , 16(6):803--815, 2009

work page 2009

[5] [5]

Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX -hard

Anne Condon, Monir Hajiaghayi, and Chris Thachuk. Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX -hard. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

work page 2021

[6] [6]

Hofacker, and Peter F

Jan Cupal, Ivo L. Hofacker, and Peter F. Stadler. Dynamic programming algorithm for the density of states of rna secondary structures. In Reinhard Hofstädt, Thomas Lengauer, Markus Löffler, and Dirk Schomburg, editors, Computer Science and Biology'96 (German Conference on Bioinformatics) , pages 184--186, Leipzig, Germany, 1996. University of Leipzig

work page 1996

[7] [7]

Domain-based nucleic-acid minimum free energy: Algorithmic hardness and parameterized bounds

Erik D Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods. Domain-based nucleic-acid minimum free energy: Algorithmic hardness and parameterized bounds. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30)(2024) , pages 2--1. Schloss Dagstuhl--Leibniz-Zentr...

work page 2024

[8] [8]

Thermodynamic analysis of interacting nucleic acid strands

Robert M Dirks, Justin S Bois, Joseph M Schaeffer, Erik Winfree, and Niles A Pierce. Thermodynamic analysis of interacting nucleic acid strands. SIAM review , 49(1):65--88, 2007

2007