https://scholars.lib.ntu.edu.tw/handle/123456789/501215
標題: | Fast Algorithmic Self-assembly of Simple Shapes Using Random Agitation. | 作者: | CHEN HO-LIN Doty, David Holden, Dhiraj Thachuk, Chris Woods, Damien Yang, Chun-Tao |
公開日期: | 2014 | 起(迄)頁: | 20-36 | 來源出版物: | DNA Computing and Molecular Programming - 20th International Conference, DNA 20, Kyoto, Japan, September 22-26, 2014. Proceedings | 摘要: | We study the power of uncontrolled random molecular movement in a model of self-assembly called the nubots model. The nubots model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on nubots showed how to build simple shapes such as lines and squares quickly—in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to push or pull large objects quickly, and only at a time and place of the programmers’ choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitationfree (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement. © Springer International Publishing Switzerland 2014. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/501215 https://www.scopus.com/inward/record.uri?eid=2-s2.0-84921515742&doi=10.1007%2f978-3-319-11295-4_2&partnerID=40&md5=7fc63506fe350e3c5598205071619ec4 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-319-11295-4_2 | SDG/關鍵字: | Rigid structures; Self assembly; Calculations; DNA; Monomers; Algorithmic self assemblies; Equal probability; Molecular motions; Molecular movement; Molecular systems; Polylogarithmic; Self assembly process; Single monomers; Monomers; Self assembly |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。