{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/8339"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/8339","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"DAN-based string rewrite computational systems","abstract":"We describe a DNA computing system called programmed mutagenesis. prove that it is universal, and present experimental results from a prototype computation. DNA is a material with important characteristics, such as possessing all the information necessary for self-reproduction in the presence of appropriate enzymes and components, simple natural evolution mechanism, and miniature scale, all of which make it an attractive substrate for computation. For computer science, using single DNA molecules to represent the state of a computation holds the promise of a new paradigm of composable molecular computing. For biology, the demonstration that DNA sequences could guide their own evolution under computational rules may have implications as we begin to unravel the mysteries of genome encoding. Programmed mutagenesis is a DNA computing system that uses cycles of DNA annealing, ligation, and polymerization to implement programmatic rewriting of DNA sequences. We report that programmed mutagenesis is theoretically universal by showing how Minsky's 4-symbol 7-state Universal Turing Machine can be implemented using a programmed mutagenesis system. Each step of the Universal Turing Machine is implemented by four cycles of programmed mutagenesis, and progress is guaranteed by the use of alternate sense strands for each rewriting cycle. We constructed a unary counter, an example programmed mutagenesis system, and operated it through three cycles of mutagenesis to gather efficiency data. We showed that the counter operates with increasing efficiency, but decreasing overall yield.","abstract_html":"We describe a DNA computing system called programmed mutagenesis. prove that it is universal, and present experimental results from a prototype computation. DNA is a material with important characteristics, such as possessing all the information necessary for self-reproduction in the presence of appropriate enzymes and components, simple natural evolution mechanism, and miniature scale, all of which make it an attractive substrate for computation. For computer science, using single DNA molecules to represent the state of a computation holds the promise of a new paradigm of composable molecular computing. For biology, the demonstration that DNA sequences could guide their own evolution under computational rules may have implications as we begin to unravel the mysteries of genome encoding. Programmed mutagenesis is a DNA computing system that uses cycles of DNA annealing, ligation, and polymerization to implement programmatic rewriting of DNA sequences. We report that programmed mutagenesis is theoretically universal by showing how Minsky's 4-symbol 7-state Universal Turing Machine can be implemented using a programmed mutagenesis system. Each step of the Universal Turing Machine is implemented by four cycles of programmed mutagenesis, and progress is guaranteed by the use of alternate sense strands for each rewriting cycle. We constructed a unary counter, an example programmed mutagenesis system, and operated it through three cycles of mutagenesis to gather efficiency data. We showed that the counter operates with increasing efficiency, but decreasing overall yield.","abstract_has_math":false,"creators":["Khodor, Julia, 1974-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["David K. Gifford."],"committee_chairs":[],"committee_members":[],"year":2002,"date_issued":"2002","date_published":"2002","updated_at":"2026-07-22T22:21:54Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/8339","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["David K. Gifford."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Khodor, Julia, 1974-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-08-23T19:18:31Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-08-23T19:18:31Z"]},{"key":"dc:date.issued","label":"Date","values":["2002"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/8339"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.","Includes bibliographical references (p. 89-97)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We describe a DNA computing system called programmed mutagenesis. prove that it is universal, and present experimental results from a prototype computation. DNA is a material with important characteristics, such as possessing all the information necessary for self-reproduction in the presence of appropriate enzymes and components, simple natural evolution mechanism, and miniature scale, all of which make it an attractive substrate for computation. For computer science, using single DNA molecules to represent the state of a computation holds the promise of a new paradigm of composable molecular computing. For biology, the demonstration that DNA sequences could guide their own evolution under computational rules may have implications as we begin to unravel the mysteries of genome encoding. Programmed mutagenesis is a DNA computing system that uses cycles of DNA annealing, ligation, and polymerization to implement programmatic rewriting of DNA sequences. We report that programmed mutagenesis is theoretically universal by showing how Minsky's 4-symbol 7-state Universal Turing Machine can be implemented using a programmed mutagenesis system. Each step of the Universal Turing Machine is implemented by four cycles of programmed mutagenesis, and progress is guaranteed by the use of alternate sense strands for each rewriting cycle. We constructed a unary counter, an example programmed mutagenesis system, and operated it through three cycles of mutagenesis to gather efficiency data. We showed that the counter operates with increasing efficiency, but decreasing overall yield.","(cont.) The measured efficiency of an in vitro programmed mutagenesis system suggests that the segregation of the products of DNA replication into separate compartments would be an efficient way to implement molecular computation. Naturally occurring phenomena such as gene conversion events and RNA editing processes are also discussed as possible manifestations of programmed mutagenesis-like systems."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["DAN-based string rewrite computational systems"]}]}],"canonical_facts":{"dc:contributor.advisor":["David K. Gifford."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Khodor, Julia, 1974-"],"dc:date.accessioned":["2005-08-23T19:18:31Z"],"dc:date.available":["2005-08-23T19:18:31Z"],"dc:date.issued":["2002"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.","Includes bibliographical references (p. 89-97)."],"dc:description.abstract":["We describe a DNA computing system called programmed mutagenesis. prove that it is universal, and present experimental results from a prototype computation. DNA is a material with important characteristics, such as possessing all the information necessary for self-reproduction in the presence of appropriate enzymes and components, simple natural evolution mechanism, and miniature scale, all of which make it an attractive substrate for computation. For computer science, using single DNA molecules to represent the state of a computation holds the promise of a new paradigm of composable molecular computing. For biology, the demonstration that DNA sequences could guide their own evolution under computational rules may have implications as we begin to unravel the mysteries of genome encoding. Programmed mutagenesis is a DNA computing system that uses cycles of DNA annealing, ligation, and polymerization to implement programmatic rewriting of DNA sequences. We report that programmed mutagenesis is theoretically universal by showing how Minsky's 4-symbol 7-state Universal Turing Machine can be implemented using a programmed mutagenesis system. Each step of the Universal Turing Machine is implemented by four cycles of programmed mutagenesis, and progress is guaranteed by the use of alternate sense strands for each rewriting cycle. We constructed a unary counter, an example programmed mutagenesis system, and operated it through three cycles of mutagenesis to gather efficiency data. We showed that the counter operates with increasing efficiency, but decreasing overall yield.","(cont.) The measured efficiency of an in vitro programmed mutagenesis system suggests that the segregation of the products of DNA replication into separate compartments would be an efficient way to implement molecular computation. Naturally occurring phenomena such as gene conversion events and RNA editing processes are also discussed as possible manifestations of programmed mutagenesis-like systems."],"dc:description.degree":["Ph.D."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/8339"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["DAN-based string rewrite computational systems"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:54Z"}