Document Open Access Logo

Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard

Authors Anne Condon , Monir Hajiaghayi, Chris Thachuk

PDF
Thumbnail PDF

File

LIPIcs.DNA.27.9.pdf
  • Filesize: 1.02 MB
  • 21 pages

Document Identifiers

Author Details

Anne Condon
  • The University of British Columbia, Vancouver, Canada
Monir Hajiaghayi
  • The University of British Columbia, Vancouver, Canada
Chris Thachuk
  • The University of Washington, Seattle, WA, USA

Funding

  • Condon, Anne: Supported by an NSERC Discovery Grant.
  • Hajiaghayi, Monir: Supported by an NSERC Discovery Grant.
  • Thachuk, Chris: Supported by a Banting Fellowship, ERC AdG VERIWARE, NSF-CCF-1213127, and NSF-CCF-2106695.

Acknowledgements

We thank Erik Winfree for helpful discussions and proposing the problem and we also thank DNA 27 reviewers for their feedback.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DNA.27.9

Abstract

Given multiple nucleic acid strands, what is the minimum free energy (MFE) secondary structure that they can form? As interacting nucleic acid strands are the basis for DNA computing and molecular programming, e.g., in DNA self-assembly and DNA strand displacement systems, determining the MFE structure is an important step in the design and verification of these systems. Efficient dynamic programming algorithms are well known for predicting the MFE pseudoknot-free secondary structure of a single nucleic acid strand. In contrast, we prove that for a simple energy model, the problem of predicting the MFE pseudoknot-free secondary structure formed from multiple interacting nucleic acid strands is NP-hard and also APX-hard. The latter result implies that there does not exist a polynomial time approximation scheme for this problem, unless 𝖯 = NP, and it suggests that heuristic methods should be investigated.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Applied computing → Chemistry
Keywords
  • Nucleic Acid Secondary Structure Prediction
  • APX-Hardness
  • NP-Hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Tatsuya Akutsu. Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots,. Discrete Applied Mathematics, 104(1-3):45-62, August 2000. Google Scholar
  2. Mirela Andronescu, Zhi Chuan Zhang, and Anne Condon. Secondary structure prediction of interacting RNA molecules. Journal of Molecular Biology, 345(5):987-1001, February 2005. Google Scholar
  3. Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. SIAM Journal on Computing, 48(2):481-512, 2019. Google Scholar
  4. Robert M. Dirks, Justin S. Bois, Joseph M. Schaeffer, Erik Winfree, and Niles A. Pierce. Thermodynamic analysis of interacting nucleic acid strands. SIAM Rev., 49(1):65–88, 2007. URL: https://doi.org/10.1137/060651100.
  5. 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. Google Scholar
  6. Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, and Satoshi Murata. Toward reliable algorithmic self-assembly of DNA tiles: A fixed-width cellular automaton pattern. Nano Letters, 8(7):1791-1797, July 2008. Google Scholar
  7. Michael R Garey and David S Johnson. Computers and Intractability: A guide to NP-completeness, 1979. Google Scholar
  8. Dan S Hirschberg. Pattern matching algorithms, chapter Serial computations of Levenshtein distances, pages 123-142. Oxford university press, 1997. Google Scholar
  9. J. A. Jaeger, D. H. Turner, and M. Zuker. Predicting optimal and suboptimal secondary structure for RNA. Methods in Enzymology, 183:281-306, 1990. Google Scholar
  10. J. Justesen. A class of constructive asymptotically good algebraic codes. Information Theory, IEEE Transactions on, 18(5):652-656, 1972. Google Scholar
  11. Viggo Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37(1):27-35, 1991. Google Scholar
  12. Ronny Lorenz, Stephan H Bernhart, Christian Höner zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker. ViennaRNA package 2.0. Algorithms for Molecular Biology : AMB, 6:26, November 2011. Google Scholar
  13. R. B. Lyngsøand C. N. Pedersen. RNA pseudoknot prediction in energy-based models. Journal of Computational Biology, 7(3-4):409-427, 2000. Google Scholar
  14. Rune B. Lyngsø. Complexity of pseudoknot prediction in simple models. In Josep Diaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannellã, editors, Proceedings, Automata, Languages and Programming 31st Internationa l Colloquium, ICALP, volume 3142 of Lecture Notes in Computer Science, pages 919-931. Springer Berlin/Heidelberg, January 2004. URL: https://doi.org/10.1007/b99859.
  15. David H. Mathews and Douglas H. Turner. Prediction of RNA secondary structure by free energy minimization. Current Opinion in Structural Biology, 16(3):270-278, 2006. URL: https://doi.org/10.1016/j.sbi.2006.05.010.
  16. J. S. McCaskill. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers, 29(6-7):1105-1119, June 1990. Google Scholar
  17. R. Nussinov and A. B. Jacobson. Fast algorithm for predicting the secondary structure of single-stranded RNA. Proceedings of the National Academy of Sciences of the United States of America, 77(11):6309-6313, November 1980. Google Scholar
  18. R. Nussinov, G. Pieczenik, J. Griggs, and D. Kleitman. Algorithms for loop matchings. SIAM Journal on Applied Mathematics, 35(1):68-82, 1978. Google Scholar
  19. L.J. Schulman and D. Zuckerman. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory, 45(7):2552-2557, 1999. URL: https://doi.org/10.1109/18.796406.
  20. Bryan Wei, Mingjie Dai, and Peng Yin. Complex shapes self-assembled from single-stranded DNA tiles. Nature, 485(7400):623-626, 2012. Google Scholar
  21. S. Wuchty, W. Fontana, I. L. Hofacker, and P. Schuster. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, 49(2):145-165, February 1999. Google Scholar
  22. Joseph N. Zadeh, Brian R. Wolfe, and Niles A. Pierce. Nucleic acid sequence design via efficient ensemble defect optimization. Journal of Computational Chemistry, 32(3):439-452, 2011. URL: https://doi.org/10.1002/jcc.21633.
  23. M. Zuker and P. Stiegler. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research, 9(1):133-148, January 1981. Google Scholar
  24. Michael Zuker and David Sankoff. RNA secondary structures and their prediction. Bulletin of Mathematical Biology, 46(4):591-621, July 1984. URL: https://doi.org/10.1007/BF02459506.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact