## The tile complexity of linear assemblies

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. We describe a natural extension to TAM called the Probabilistic Tile Assembly Model (PTAM) to model the inherent probabilistic behavior in physically realized self-assembled systems. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set. These rulers can then be used as components for construction of other complex structures. In TAM, a deterministic linear assembly of length N requires a tile set of cardinality at least N. In contrast, for any given N, we demonstrate linear assemblies of expected length N with a tile set of cardinality Θ(logN) and prove a matching lower bound of Ω(logN). We also propose a simple extension to PTAM called κ-pad systems in which we associate κ pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match and prove analogous results. All our probabilistic constructions are free from co-operative tile binding errors and can be modified to produce assemblies whose probability distribution of lengths has arbitrarily small tail bounds dropping exponentially with a given multiplicative factor increase in number of tile types. 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. © 2009 Springer Berlin Heidelberg.

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences

### Citation

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*,

*5555 LNCS*(PART 1), 235–253. https://doi.org/10.1007/978-3-642-02927-1_21

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*5555 LNCS, no. PART 1 (November 12, 2009): 235–53. https://doi.org/10.1007/978-3-642-02927-1_21.

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 5555 LNCS, no. PART 1, Nov. 2009, pp. 235–53.

*Scopus*, doi:10.1007/978-3-642-02927-1_21.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences