FREE ELECTRONIC LIBRARY - Books, dissertations, abstract

Pages:     | 1 |   ...   | 2 | 3 ||

«Abstract. DNA self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. In nature, DNA ...»

-- [ Page 4 ] --

Also, for the 2 × 2 snaked tile system and the original proofreading system, we took a straight line boundary of 200 tiles and tested the average time (in seconds; virtual time) for a block error to happen under different Gse ’s. Here, 2Gse − Gmc is set to be 0.2. Theoretically, the expected time for a block error to happen in the snaked tile system is O(e4Gse ), and the expected time for a block error to happen in the proofreading system is O(e3Gse ). The result is shown in figure 5(a); the y-axis uses a log-scale. Clearly, Gmc = 15, Gse = 7.8 Gmc = 15, Gse = 8.0 Original Proofreading Snaked Original Proofreading Snaked Time to assemble (seconds) 550 2230 6020 350 1750 3780 Error Probability 52% 24% 0% 63% 75% 0% Time it remains stable 0 0 0 0 5700 (seconds) after completion Table 1: Assembling a 20 × 20 Sierpinski block. A stability time of 0 indicates that the final square became unstable (i.e., an extra block of tiles attached on the periphery of the desired supertile) even before the complete supertile formed. We only simulated our system for 400,000 seconds (virtual time). The values represent averages over 100 runs.

the slope of the curve for the snaked tile system confirms our analysis – the slope is very close to 4, and significantly more than the slope for the original proofreading system. For the larger values of G se, we could only plot the results for the original proof-reading system, since the simulator did not report any errors with the snaked tile system for the time scales over which we conducted the simulation.

We also tested the error rate for parity systems of different seed lengths. We called an experiment an error if the final supertile was different from the one we expect in the absence of errors. We used Gse = 7.0, Gmc = 13.6. The result is shown in figure 5(b); again, a significant reduction in error rate is observed. For both figures 5(a) and 5(b), qualitatively similar results were observed for widely varying simulation parameters.

Our simulation results show that our analysis is very close to reality even without idealized parameter conditions. For example, we did not use Gmc = 2Gse but instead used Gmc slightly smaller than 2Gse as suggested by Winfree [12]. Also, the simulator allows tiles held by strength 3 to fall off, contrary to our assumption. Thus, we believe that our snaked system works much better (and under a much wider set of conditions) than we have been able to formally prove.

5 Future Directions It would be interesting to extend our analysis to remove some of our assumptions. Also, we believe that the total assembly time for our system should just be O(k 2 n) for assembling an n × n square using k × k snaked blocks. One of the biggest bottlenecks in proving this bound is an analysis of the assembly time of an n × n square assuming that there are no errors but that the system is reversible, i.e., tiles can both attach and detach. We believe that the assembly time for this system should be O(n) along the lines of the irreversible system [2], but have been unable to prove it.

Acknowledgments We would like to thank Qi Cheng and Erik Winfree for many useful discussions. We would also like to thank Erik Winfree for loaning us his tile simulator, xgrow, which was an indispensable aid in this research.

References [1] L. Adleman. Towards a mathematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000.

–  –  –

[2] L. Adleman, Q. Cheng, A. Goel, and M.-D. Huang. Running time and program size for self-assembled squares. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 740–748. ACM Press, 2001.

[3] L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. Moisset de Espans, and P. Rothemund.

Combinatorial optimization problems in self-assembly. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 23–32. ACM Press, 2002.

–  –  –

[6] H. Chen, Q. Cheng, A. Goel, M.-D. Huang, and P. Moisset de Espans. Proofreading tile sets: Error correction for algorithmic self-assembly. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 883–892, 2004.

[7] M. Lagoudakis and T. LaBean. 2D DNA self-assembly for satisfiability. In Proceedings of the 5th DIMACS Workshop on DNA Based Computers in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 54. MIT: Cambridge, 1999.

[8] J. Reif. Local parallel biomolecular computation. In H. Rubin, editor, Third Annual DIMACS Workshop on DNA Based Computers, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998.

[9] P. Rothemund. Theory and Experiments in Algorithmic Self-Assembly. PhD thesis, University of Southern California, 2001.

[10] P. Rothemund and E. Winfree. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 459–468. ACM Press, 2000.

[11] H. Wang. Proving theorems by pattern recognition II. Bell Systems Technical Journal, 1961. 40:1-42.

[12] E. Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, Pasadena, 1998.

[13] E. Winfree and R. Bekbolatov. Proofreading tile sets: Error correction for algorithmic self-assembly.

In Proceedings of the Ninth International Meeting on DNA Based Computers. Madison, Wisconsin, June 2003.

[14] E. Winfree, F. Liu, L. Wenzler, and N. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, (394):539–544, Aug 1998.

[15] E. Winfree, X. Yang, and N. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In Proceedings of the Second Annual Meeting on DNA Based Computers. Princeton University, June 1996.

[16] E. Winfree et al.. The xgrow simulator. http://www.dna.caltech.edu/Xgrow/xgrow www.html.

[17] B. Yurke, A. Turberfield, A. Mills Jr, F. Simmel, and J. Neumann. A DNA-fuelled molecular machine made of DNA. Nature, (406):605–608, Aug 2000.

Pages:     | 1 |   ...   | 2 | 3 ||

Similar works:

«Use of Web Analytics and DataMining in Websites to Improve Navigation Process and Marketing Plan. Autoria: Andre Luiz Zambalde, Alexander Kippes, Ahmed Ali Abdalla Esmin, Eder Bruno Fonseca The knowledge of consumer habits can help companies explore user needs, how they use products and how they react to marketing campaigns. Marketing experts mostly choose the maximum of available channels in order to generate the most revenue. Choosing every available channel often has the negative effect of...»

«Social Cognition, Vol. 19, No. 6, 2001, pp. 625-664 NOSEK AND GO ASSOCIAT ION TASK T HEG O/NOBANAJI THE GO/NO-GO ASSOCIATION TASK Brian A. Nosek and Mahzarin R. Banaji Yale University Theory is constrained by the quality and versatility of measurement tools. As such, the development of techniques for measurement is critical to the successful development of theory. This paper presents a technique — the Go/No-go Association Task (GNAT) — that joins a family of existing techniques for...»

«STRENGTHENING NONPROFITS: A Capacity Builder’s Resource Library Delivering Training and Technical Assistance TABLE OF CONTENTS INTRODUCTION OVERVIEW DELIVERING TRAINING Creating a Training Plan Phases in a Systems Approach to Training Incorporating Adult Learning Principles Summary of Training: Helpful Training Reminders DELIVERING TECHNICAL ASSISTANCE Core Principles of Technical Assistance Phases of a Systematic Approach to Providing Technical Assistance Creating Change within an...»

«Vom Intelligent Building zur Telekooperation Von der Fakultät für Architektur der Rheinisch-Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften genehmigte Dissertation vorgelegt von Diplom-Ingenieur Kay Friedrichs aus Düsseldorf Berichter: Universitätsprofessor M.S.Arch/IIT M.Arch.(HGSD) Heinz G. Sieber Universitätsprofessor Dr.-Ing. Gerhard Fehl Professor Dr. h.c. Fritz Haller, Universität Karlsruhe (TH) Tag der...»

«10th INTERNATIONAL NANOTECHNOLOGY SYMPOSIUM NEW IDEAS FOR INDUSTRY Program July 1 3, 2014 International Congress Center Dresden, Germany www.nanofair.com Partners & Sponsors OFFICIAL PARTNERS SPONSORS Dresden Fraunhofer Cluster Nanoanalysis MEDIA PARTNERS Foreword Ladies and Gentlemen, Following the overwhelming success of the previous conferences and the positive reception, Nanofair celebrates 2014 its 10th anniversary. With the slogan “New Ideas for Industry” the conference provides a...»

«TECHNISCHE UNIVERSITÄT DRESDEN FAKULTÄT FORST-, GEOUND HYDROWISSENSCHAFTEN INSTITUT FÜR GEOGRAPHIE Diplomarbeit zur Erlangung des akademischen Grades Diplom-Geograph Bodenerosion als Funktion veränderter Landnutzungsstruktur – Modellierung der Entwicklung am Beispiel der Nationalparkregion Sächsische Schweiz vorgelegt von: Sebastian Wolf geboren am: 25.12.1978 in Dresden Betreuer: Prof. Dr. Dr. rer. nat. habil. Arno Kleber Institut für Geographie, Technische Universität Dresden Dr....»

«Hellenistic Time Lords An Introduction to Timing by Planetary Periods and Ascensional Times of the Signs By Demetra George Hellenistic astrology is the astrology that was practiced circa 150 BCE600 CE in the ancient Mediterranean, and it is the direct ancestor of all subsequent systems of Western astrology. With the recent translations of the original source texts by Robert Schmidt, we are discovering that the ancient astrologers used many different timing procedures that have been lost to...»

«EVOLUTION OF INDUSTRIAL ASSEMBLY PRACTICES IS PRECONDITION FOR FURTHER MODERNIZATION AND DEVELOPMENT OF AUTOMOBILE INDUSTRY IN RUSSIA Lebedev К.К., Pankratova D.А. The article includes a few sound arguments, allowing asserting that foreign-made cars’ assembly practice, working in Russia, can lead to modernization and development of automobilia. Moreover functioning of these regimes allows building a strategy of automobile industry development in the country. Key words: foreign investments,...»

«January 5, 1999 Secretary, Federal Trade Commission Room H-158 600 Pennsylvania Avenue, N.W. Washington, D.C. 20580 Dear Mr. Clark AT&T is pleased to nominate Dr. Lorrie Cranor for appointment to the Advisory Committee on Online Access and Security. Dr. Cranor’ resume is attached, and s describes in detail her experience, educational background, expertise and publications. Dr. Cranor chairs the World Wide Web Consortium’ (W3C) Platform for Privacy s Preferences Project specification Working...»

«Semi-empirical validation of the cross-band relative absorption technique for the measurement of molecular mixing ratios Denis Pliutau, and Narasimha S. Prasad NASA Langley Research Center, 5 N. Dryden St., MS 468, Hampton VA, 23681 ABSTRACT Studies were performed to carry out semi-empirical validation of a new measurement approach we propose for molecular mixing ratios determination. The approach is based on relative measurements in bands of O2 and other molecules and as such may be best...»

<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.