zbMATH — the first resource for mathematics

Rule set design problems for oritatami systems. (English) Zbl 1370.68096
Summary: A single-stranded RNA is transcribed from its DNA template by an RNA polymerase enzyme. The RNA transcript begins to fold upon itself while it is still being transcribed. This ubiquitous phenomenon is called cotranscriptional folding and was recently used as an engineering tool to self-assemble “RNA origami” tile by C. Geary et al. [“A single-stranded architecture for cotranscriptional folding of RNA nanostructures”, Science 345, No. 6198, 799–804 (2014; doi:10.1126/science.1253920 )]. The oritatami system (OS) is a new mathematical model of algorithmic self-assembly by cotranscriptional folding, proposed by C. Geary et al. [“Efficient universal computation by greedy molecular folding”, Preprint, arXiv:1508.00510]. A problem of designing OSs is studied in this paper. We provide a sharp boundary between the NP-hardness and polynomial-time computability of this problem with respect to the relative speed of transcription to folding and valence of molecules.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
92D20 Protein sequences, DNA sequences
Full Text: DOI
[1] Xayaphoummine, A.; Viasnoff, V.; Harlepp, S.; Isambert, H., Encoding folding paths of RNA switches, Nucleic Acids Res., 35, 2, 614-622, (2007)
[2] Šulc, P.; Romano, F.; Ouldridge, T. E.; Doye, J. P.K.; Louis, A. A., A nucleotide-level coarse-grained model of RNA, J. Chem. Phys., 140, (2014)
[3] Pierce, N. A.; Winfree, E., Protein design is NP-hard, Protein Eng., 15, 10, 779-782, (2002)
[4] Akutsu, T.; Hayashida, M.; Ching, W.-K.; Ng, M. K., Control of Boolean networks: hardness results and algorithm for tree structured networks, J. Theoret. Biol., 244, 4, 670-679, (2007)
[5] Dirks, R. M.; Pierce, N. A., A partition function algorithm for nucleic acid secondary structure including pseudoknots, J. Comput. Chem., 24, 1664-1677, (2003)
[6] Rivas, E.; Eddy, S. R., A dynamic programming algorithm for RNA structure prediction including pseudoknots, J. Mol. Biol., 285, 5, 2053-2068, (1999)
[7] Xayaphoummine, A.; Bucher, T.; Isambert, H., Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots, Nucleic Acids Res., 33, W605-W610, (2005)
[8] Geary, C.; Rothemund, P. W.K.; Andersen, E. S., A single-stranded architecture for cotranscriptional folding of RNA nanostructures, Science, 345, 799-804, (2014)
[9] Afonin, K. A.; Bindewald, E.; Yaghoubian, A. J.; Voss, N.; Jacovetty, E.; Shapiro, B. A.; Jaeger, L., in vitro assembly of cubic RNA-based scaffolds designed in silico, Nat. Nanotechnol., 5, 676-682, (2010)
[10] Lorenz, R.; Bernhart, S. H.; zu Siederdissen, C. H.; Tafer, H.; Flamm, C.; Stadler, P. F.; Hofacker, I. L., Viennarna package 2.0, Algorithms Mol. Biol., 6, 26, (2011)
[11] Zadeh, J. H.; Steenberg, C. D.; Bois, J. S.; Wolfe, B. R.; Pierce, M. B.; Khan, A. R.; Dirks, R. M.; Pierce, N. A., NUPACK: analysis and design of nucleic acid systems, J. Comput. Chem., 32, 170-173, (2011)
[12] C. Geary, personal communication.
[13] Isambert, H., The jerky and knotty dynamics of RNA, Methods, 49, 189-196, (2009)
[14] Geary, C.; Meunier, P.-E.; Schabanel, N.; Seki, S., Efficient universal computation by greedy molecular folding, (2015)
[15] Geary, C.; Meunier, P.-E.; Schabanel, N.; Seki, S., Programming biomolecules that fold greedily during transcription, (Proc. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS2016, LIPIcs. Leibniz Int. Proc. Inform., vol. 58, (2016)), 43:1-43:14 · Zbl 1398.68161
[16] Han, Y.-S.; Kim, H.; Ota, M.; Seki, S., Nondeterministic seedless oritatami systems and hardness of testing their equivalence, (Proc. 22nd International Conference on DNA Computing and Molecular Programming, DNA22, Lecture Notes in Comput. Sci., vol. 9818, (2016), Springer), 19-34 · Zbl 06657845
[17] Diestel, R., Graph theory, (2010), Springer · Zbl 1204.05001
[18] (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1, (1997), Springer) · Zbl 0866.68057
[19] Neary, T.; Woods, D., P-completeness of cellular automaton rule 110, (Proc. 33rd International Colloquium on Automata, Languages, and Programming, ICALP2006, Lecture Notes in Comput. Sci., vol. 4051, (2006), Springer), 132-143 · Zbl 1223.68072
[20] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company · Zbl 0411.68039
[21] Schaefer, T. J., The complexity of satisfiability problems, (Proc. 10th Annual Symposium on Theory of Computing, STOC1978, (1978), ACM), 216-226 · Zbl 1282.68143
[22] Aspvall, B.; Plass, M. F.; Tarjan, R. E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform. Process. Lett., 8, 3, 121-123, (1979) · Zbl 0398.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.