Self-attraction removal from oritatami systems

Yo Sub Han; Hwee Kim; Trent A. Rogers; Shinnosuke Seki

doi:10.1007/978-3-319-60252-3_13

Self-attraction removal from oritatami systems

Yo Sub Han, Hwee Kim, Trent A. Rogers, Shinnosuke Seki

College of Computing

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

7 Citations (Scopus)

Abstract

RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings
Editors	Giovanni Pighizzini, Cezar Campeanu
Publisher	Springer Verlag
Pages	164-176
Number of pages	13
ISBN (Print)	9783319602516
DOIs	https://doi.org/10.1007/978-3-319-60252-3_13
Publication status	Published - 2017
Event	19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017 - Milano, Italy Duration: 2017 Jul 3 → 2017 Jul 5

Publication series

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

Other

Other	19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017
Country/Territory	Italy
City	Milano
Period	17/7/3 → 17/7/5

Bibliographical note

Funding Information:
S. Seki—In part supported by JST Program to Disseminate Tenure Tracking System No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854.

Funding Information:
Y.-S. Han—Supported by International Cooperation Program (2017K2A9A2A08000270) and Basic Science Research Program (2015R1D1A1A01060097) by NRF of Korea.

Funding Information:
Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program).

Funding Information:
T.A. Rogers—This author’s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grants CAREER-1553166 and CCF-1422152.

Publisher Copyright:
© IFIP International Federation for Information Processing 2017.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-60252-3_13

Cite this

Han, Y. S., Kim, H., Rogers, T. A., & Seki, S. (2017). Self-attraction removal from oritatami systems. In G. Pighizzini, & C. Campeanu (Eds.), Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings (pp. 164-176). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10316 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-60252-3_13

Han, Yo Sub ; Kim, Hwee ; Rogers, Trent A. et al. / Self-attraction removal from oritatami systems. Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings. editor / Giovanni Pighizzini ; Cezar Campeanu. Springer Verlag, 2017. pp. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0038a69b89c141049486a6c070a8ec2a,

title = "Self-attraction removal from oritatami systems",

abstract = "RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.",

author = "Han, {Yo Sub} and Hwee Kim and Rogers, {Trent A.} and Shinnosuke Seki",

note = "Funding Information: S. Seki—In part supported by JST Program to Disseminate Tenure Tracking System No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854. Funding Information: Y.-S. Han—Supported by International Cooperation Program (2017K2A9A2A08000270) and Basic Science Research Program (2015R1D1A1A01060097) by NRF of Korea. Funding Information: Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program). Funding Information: T.A. Rogers—This author{\textquoteright}s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grants CAREER-1553166 and CCF-1422152. Publisher Copyright: {\textcopyright} IFIP International Federation for Information Processing 2017.; 19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017 ; Conference date: 03-07-2017 Through 05-07-2017",

year = "2017",

doi = "10.1007/978-3-319-60252-3_13",

language = "English",

isbn = "9783319602516",

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

publisher = "Springer Verlag",

pages = "164--176",

editor = "Giovanni Pighizzini and Cezar Campeanu",

booktitle = "Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings",

address = "Germany",

}

Han, YS, Kim, H, Rogers, TA & Seki, S 2017, Self-attraction removal from oritatami systems. in G Pighizzini & C Campeanu (eds), Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10316 LNCS, Springer Verlag, pp. 164-176, 19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017, Milano, Italy, 17/7/3. https://doi.org/10.1007/978-3-319-60252-3_13

Self-attraction removal from oritatami systems. / Han, Yo Sub; Kim, Hwee; Rogers, Trent A. et al.
Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings. ed. / Giovanni Pighizzini; Cezar Campeanu. Springer Verlag, 2017. p. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10316 LNCS).

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

TY - GEN

T1 - Self-attraction removal from oritatami systems

AU - Han, Yo Sub

AU - Kim, Hwee

AU - Rogers, Trent A.

AU - Seki, Shinnosuke

N1 - Funding Information: S. Seki—In part supported by JST Program to Disseminate Tenure Tracking System No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854. Funding Information: Y.-S. Han—Supported by International Cooperation Program (2017K2A9A2A08000270) and Basic Science Research Program (2015R1D1A1A01060097) by NRF of Korea. Funding Information: Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program). Funding Information: T.A. Rogers—This author’s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grants CAREER-1553166 and CCF-1422152. Publisher Copyright: © IFIP International Federation for Information Processing 2017.

PY - 2017

Y1 - 2017

N2 - RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.

AB - RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.

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

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

U2 - 10.1007/978-3-319-60252-3_13

DO - 10.1007/978-3-319-60252-3_13

M3 - Conference contribution

AN - SCOPUS:85022320698

SN - 9783319602516

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

SP - 164

EP - 176

BT - Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings

A2 - Pighizzini, Giovanni

A2 - Campeanu, Cezar

PB - Springer Verlag

T2 - 19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017

Y2 - 3 July 2017 through 5 July 2017

ER -

Han YS, Kim H, Rogers TA, Seki S. Self-attraction removal from oritatami systems. In Pighizzini G, Campeanu C, editors, Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings. Springer Verlag. 2017. p. 164-176. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-60252-3_13

Self-attraction removal from oritatami systems

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this