NDLI: Tile Complexity of Linear Assemblies

Please wait, while we are loading the content...

Tile Complexity of Linear Assemblies

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chandran, Harish Reif, John Gopalkrishnan, Nikhil
Copyright Year	2012
Abstract	Self-assembly is fundamental to both biological processes and nanoscience. Key features of self-assembly are its probabilistic nature and local programmability. These features can be leveraged to design better self-assembled systems. The conventional tile assembly model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set, where any tile type may appear more than once in the assembly. The tile complexity of a linear assembly is the cardinality of the tile set that produces it. These rulers can then be used as components for construction of other complex structures. While square assemblies have been extensively studied, many questions remain about fixed length linear assemblies, which are more basic constructs yet fundamental building blocks for molecular architectures. In this work, we extend TAM to take advantage of inherent probabilistic behavior in physically realized self-assembled systems by introducing randomization. We describe a natural extension to TAM called the probabilistic tile assembly model (PTAM). A restriction of the model, which we call the standard PTAM is considered in this report. Prior work in DNA self-assembly strongly suggests that standard PTAM can be realized in the laboratory. In TAM, a deterministic linear assembly of length $N$ requires a tile set of cardinality at least $N$. In contrast, we show various nontrivial probabilistic constructions for forming linear assemblies in PTAM with tile sets of sublinear cardinality, using techniques that differ considerably from existing assembly techniques. In particular, for any given $N$ we demonstrate linear assemblies of expected length $N$ with a tile set of cardinality $\Theta(\log N)$ using one pad per side of each tile. We prove a matching lower bound of $\Omega(\log N)$ on the tile complexity of linear assemblies of any given expected length $N$ in standard PTAM systems using one pad per side of each tile. We further demonstrate how linear assemblies can be modified to produce assemblies with sharp tail bounds on distribution of lengths by concatenating various assemblies together. In particular, we show that for infinitely many $N$ we can get linear assemblies with exponentially dropping tail distributions using $O(\log^3 N)$ tile types. We also propose a simple extension to PTAM called $\kappa$-pad systems in which we associate $\kappa$ pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match. This gives linear assemblies of expected length $N$ with a $2$-pad (two pads per side of each tile) tile set of cardinality $\Theta(\frac{\log N}{\log \log N})$ for infinitely many $N$. We show that we cannot get smaller tile complexity by proving a lower bound of $\Omega(\frac{\log N}{\log \log N})$ for each $N$ on the cardinality of the $\kappa$-pad ($\kappa$-pads per side of each tile) tile set required to form linear assemblies of expected length $N$ in standard $\kappa$-pad PTAM systems for any positive integer $\kappa$. The techniques that we use for deriving these tile complexity lower bounds are notable as they differ from traditional Kolmogorov complexity based information theoretic methods used for lower bounds on tile complexity. Also, Kolmogorov complexity based lower bounds do not preclude the possibility of achieving assemblies of very small tile multiset cardinality for infinitely many $N$. In contrast, our lower bounds are stronger as they hold for every $N$, rather than for almost all $N$. All our probabilistic constructions are free from co-operative tile binding errors. Thus, for linear assembly systems, we have shown that randomization can be exploited to get large improvements in tile complexity at a small expense of precision in length.
Starting Page	1051
Ending Page	1073
Page Count	23
File Format	PDF
ISSN	00975397
DOI	10.1137/110822487
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	41
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2012-08-28
Access Restriction	Subscribed
Subject Keyword	Modes of computation self-assembly DNA tiles tile assembly model tile complexity linear assemblies Wang tilings
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in