Transcript design problem of oritatami systems

Yo Sub Han; Hwee Kim; Shinnosuke Seki

doi:10.1007/978-3-030-00030-1_9

Transcript design problem of oritatami systems

Yo Sub Han, Hwee Kim, Shinnosuke Seki

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.

Original language	English
Title of host publication	DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings
Editors	David Doty, Hendrik Dietz
Publisher	Springer Verlag
Pages	139-154
Number of pages	16
ISBN (Print)	9783030000295
DOIs	https://doi.org/10.1007/978-3-030-00030-1_9
Publication status	Published - 2018
Event	24th International Conference on DNA Computing and Molecular Programming, DNA 2018 - Jinan, China Duration: 2018 Oct 8 → 2018 Oct 12

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11145 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	24th International Conference on DNA Computing and Molecular Programming, DNA 2018
Country/Territory	China
City	Jinan
Period	18/10/8 → 18/10/12

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2018.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-00030-1_9

Cite this

Han, Y. S., Kim, H., & Seki, S. (2018). Transcript design problem of oritatami systems. In D. Doty, & H. Dietz (Eds.), DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings (pp. 139-154). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11145 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-00030-1_9

Han, Yo Sub ; Kim, Hwee ; Seki, Shinnosuke. / Transcript design problem of oritatami systems. DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings. editor / David Doty ; Hendrik Dietz. Springer Verlag, 2018. pp. 139-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b5998724f04c41819e5e0625c9f8711b,

title = "Transcript design problem of oritatami systems",

abstract = "RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.",

author = "Han, {Yo Sub} and Hwee Kim and Shinnosuke Seki",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 24th International Conference on DNA Computing and Molecular Programming, DNA 2018 ; Conference date: 08-10-2018 Through 12-10-2018",

year = "2018",

doi = "10.1007/978-3-030-00030-1_9",

language = "English",

isbn = "9783030000295",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "139--154",

editor = "David Doty and Hendrik Dietz",

booktitle = "DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings",

address = "Germany",

}

Han, YS, Kim, H & Seki, S 2018, Transcript design problem of oritatami systems. in D Doty & H Dietz (eds), DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11145 LNCS, Springer Verlag, pp. 139-154, 24th International Conference on DNA Computing and Molecular Programming, DNA 2018, Jinan, China, 18/10/8. https://doi.org/10.1007/978-3-030-00030-1_9

Transcript design problem of oritatami systems. / Han, Yo Sub; Kim, Hwee; Seki, Shinnosuke.
DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings. ed. / David Doty; Hendrik Dietz. Springer Verlag, 2018. p. 139-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11145 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Transcript design problem of oritatami systems

AU - Han, Yo Sub

AU - Kim, Hwee

AU - Seki, Shinnosuke

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2018.

PY - 2018

Y1 - 2018

N2 - RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.

AB - RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.

UR - http://www.scopus.com/inward/record.url?scp=85054829135&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054829135&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-00030-1_9

DO - 10.1007/978-3-030-00030-1_9

M3 - Conference contribution

AN - SCOPUS:85054829135

SN - 9783030000295

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 139

EP - 154

BT - DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings

A2 - Doty, David

A2 - Dietz, Hendrik

PB - Springer Verlag

T2 - 24th International Conference on DNA Computing and Molecular Programming, DNA 2018

Y2 - 8 October 2018 through 12 October 2018

ER -

Han YS, Kim H, Seki S. Transcript design problem of oritatami systems. In Doty D, Dietz H, editors, DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings. Springer Verlag. 2018. p. 139-154. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00030-1_9

Transcript design problem of oritatami systems

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this