Document Open Access Logo

Programming Biomolecules That Fold Greedily During Transcription

Authors Cody Geary, Pierre-Etienne Meunier, Nicolas Schabanel, Shinnosuke Seki

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.43.pdf
  • Filesize: 4.04 MB
  • 14 pages

Document Identifiers

Author Details

Cody Geary
Pierre-Etienne Meunier
Nicolas Schabanel
Shinnosuke Seki

Cite As Get BibTex

Cody Geary, Pierre-Etienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Programming Biomolecules That Fold Greedily During Transcription. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.43

Abstract

We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which a molecule begins to fold before awaiting the end of its production. This model is inspired by a recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA. 

An important challenge of this model, also encountered in experiments, is to get a single sequence to fold into different shapes, depending on the surrounding molecules. Another big challenge is that not all parts of the sequence are meaningful for all possible inputs. Hence, to prevent them from interfering with subsequent operations in the Oritatami folding pathway we must structure the unused portions of the sequence depending on the context in which it folds.

Next, we introduce general design techniques to solve these challenges and program molecules. Our main result in this direction is an algorithm that is time linear in the sequence length that finds a rule for folding the sequence deterministically into a prescribed set of shapes, dependent on its local environment. This shows that the corresponding problem is fixed-parameter tractable, although we also prove it NP-complete in the number of possible environments.

Subject Classification

Keywords
  • natural computing
  • self-assembly
  • molecular folding

Metrics

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

References

  1. O. Aichholzer, D. Bremner, E. D. Demaine, H. Meijer, V. Sacristán, and M. Soss. Long proteins with unique optimal foldings in the H-P model. Computational Geometry, 25(1-2):139-159, 2003. Google Scholar
  2. J. Atkins and W. E. Hart. On the intractability of protein folding with a finite alphabet of amino acids. Algorithmica, 25(2-3):279-294, 1999. Google Scholar
  3. Bonnie Berger and Tom Leighton. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology, 5(1):27-40, 1998. Google Scholar
  4. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow. Two hands are better than one (up to constant factors). In STACS: Proceedings of the Thirtieth International Symposium on Theoretical Aspects of Computer Science, pages 172-184, 2013. URL: http://arxiv.org/abs/1201.1650.
  5. Ho-Lin Chen and David Doty. Parallelism and time in hierarchical self-assembly. In SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1163-1182. SIAM, 2012. Google Scholar
  6. Matthew Cook, Yunhui Fu, and Robert T. Schweller. Temperature 1 self-assembly: Deterministic assembly in 3D and probabilistic assembly in 2D. In SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2011. Arxiv preprint: URL: http://arxiv.org/abs/0912.0027.
  7. Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitriou, Antonio Piccolboni, and Mihalis Yannakakis. On the complexity of protein folding. Journal of computational biology, 5(3):423-465, 1998. Google Scholar
  8. R. Das and D. Baker. Automated de novo prediction of native-like RNA tertiary structures. PNAS, 104:14664-14669, 2007. Google Scholar
  9. K.A. Dill. Theory for the folding and stability of globular proteins. Biochemistry, 24(6):1501-1509, 1985. Google Scholar
  10. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The tile assembly model is intrinsically universal. In FOCS 2012, pages 439-446, October 2012. Google Scholar
  11. Constantine Glen Evans. Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. PhD thesis, California Institute of Technology, 2014. Google Scholar
  12. Kirsten L. Frieda and Steven M. Block. Direct observation of cotranscriptional folding in an adenine riboswitch. Science, 338(6105):397-400, 2012. Google Scholar
  13. Kenichi Fujibayashi, David Yu Zhang, Erik Winfree, and Satoshi Murata. Error suppression mechanisms for dna tile self-assembly and their simulation. Natural Computing: an international journal, 8(3):589-612, 2009. URL: http://dx.doi.org/10.1007/s11047-008-9093-9.
  14. Cody Geary, Paul W. K. Rothemund, and Ebbe S. Andersen. A single-stranded architecture for cotranscriptional folding of RNA nanostructures. Science, 345:799-804, 2014. Google Scholar
  15. Boyle J, Robillard G, and Kim S. Sequential folding of transfer RNA. a nuclear magnetic resonance study of successively longer tRNA fragments with a common 5' end. J Mol Biol, 139:601-625, 1980. Google Scholar
  16. Hosna Jabbari and Anne Condon. A fast and robust iterative algorithm for prediction of rna pseudoknotted secondary structures. BMC bioinformatics, 15(1):147, 2014. Google Scholar
  17. D. H. Mathews, M. D. Disney, J. L. Childs, S. J. Schroeder, M. Zuker, and D. H. Turner. Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. PNAS, 101:7287-7292, May 2004. URL: http://dx.doi.org/10.1073/pnas.0401799101.
  18. D.H. Mathews. Revolutions in rna secondary structure prediction. Journal of molecular biology, 359(3):526-32, 2006. URL: http://dx.doi.org/10.1016/j.jmb.2006.01.067.
  19. Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014. Google Scholar
  20. M. Paterson and T. Przytycka. On the complexity of string folding. In F. Meyer and B. Monien, editors, ICALP 1996, volume 1099 of LNCS, pages 658-669. Springer Berlin Heidelberg, 1996. Google Scholar
  21. M. Popenda, M. Szachniuk, M. Antczak, K.J. Purzycka, P. Lukasiak, N. Bartol, J. Blazewicz, and R.W. Adamiak. Automated 3D structure composition for large RNAs. Nucleic Acids Research, 40(14):e112, 2012. URL: http://dx.doi.org/doi:10.1093/nar/gks339.
  22. Elena Rivas. The four ingredients of single-sequence rna secondary structure prediction. a unifying perspective. RNA Biol, 10(7):1185-1196, Jul 2013. 23695796[pmid]. URL: http://dx.doi.org/10.4161/rna.24971.
  23. Paul W. K. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297-302, March 2006. URL: http://dx.doi.org/10.1038/nature04586.
  24. Nadrian C. Seeman. Nucleic-acid junctions and lattices. Journal of Theoretical Biology, 99:237-247, 1982. Google Scholar
  25. R. Unger and J. Moult. Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications. Bulletin of Mathematical Biology, 55(6):1183-1198, 1993. Google Scholar
  26. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, Caltech, June 1998. Google Scholar
  27. Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin. Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Proceedings of ITCS 2013: Innovations in Theoretical Computer Science, pages 353-354, 2013. Google Scholar
  28. Bernard Yurke, Andrew J Turberfield, Allen P Mills, Friedrich C Simmel, and Jennifer L Neumann. A DNA-fuelled molecular machine made of DNA. Nature, 406(6796):605-608, 2000. Google Scholar
  29. Michael Zuker and David Sankoff. Rna secondary structures and their prediction. Bulletin of Mathematical Biology, 46(4):591-621, 1984. URL: http://dx.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