A DNA based Finite State Transducer

Nathanaël Aubert

Description

A DNA-based Finite State Transducer Nathanaël Aubert Under the direction of Masami Hagiya University of Rennes 1 University of Tokyo June 5, 2010 Abstract Deoxyribonucleic acid (DNA) computing is an emerging field wherein the biological properties of DNA are used to carry out computation. As DNA can also be used as a building material with movable parts, the combination of those two aspects allows scientists to design nanomachines easily. However, one main concerns is the lack of automation of existing mechanisms. This limits their potential applications as it is not possible to use nanomachines in a non- controlled environment that is, almost anything that is outside of a test tube. The goal of this work is thus to design a completely automated mechanism that will reduce the amount of operations required from the user. We have designed a finite state transducer that can eliminate the need to add control strands to the solution, one of the most common external operations. Our transducer uses polymerase to generate the output described by the input strands present in the solution. As it can work at a wide range of temperatures our transducer can facilitate the design of more complex nanomachines while making the ex- isting ones, that rely on control strands, more autonomous. Moreover, as it can generate a wide variety of outputs, our transducer can also be useful to DNA mechanisms that are computation-intensive.

• can also


• stranded dna


• using dna


• finite state


• dna


• shapiro's finite


• instances can


• requiring dna operations


• strands bind

Sujets

• Aubert
• Finite-state machine

Informations

• Publié par: dumas_ccsd
• Nombre de lectures: 32

Extrait

aAuser.DNA-basedtensivFiniteOurStatemoreTlransducertoNathana?ltAcomplexuberourters,Under1thenitedirectiononeofeMasaminHatransducergiyones,agenerateUnivtoersitnondetermin-ystrandsofConRenneserations1vUnivcanerstrandssicommontolymeraseybofinTcanokyofoeJunemaking5,co2010er,AbstractarietDeoalsoxyribthatonexamucleic(Naciden(DNAof)crocomputingUsingisofanfromemergeidesignedngtransducereldthewhereinconthethebiologicalthepropopertiesusesofgenerateDNAdescribaretheusedpresentosoluticarryAsoutorkcomputation.eAseraturesDNAfacilitatecanofalsohinesbex-erelyusedtrolasMoreoaitbuildingwidematerialofwithucermoevmecablereparts,Fthele,compbinationproblemofcanthosetetneededwvingoofasptheectstsallo4wstscienoptistsrequiredtothedesignWnanomachahineseeasilya.stateHothatweliminateevneeder,addonetrolmaintoconcernssolution,isofthemostlacexternalkerations.oftransducerautomationpoftoexistingthmecoutputhanisms.edThiysinpulimitsstrandstheirtptheotenotial.applicationsitaswitatiswidnotrangeptempoourscansiblethtodesignusemorenanomacnanomachineswhileintheaistingnon-thatconontrollednenstrands,vironmenautonomous.tvasthatcanis,aalmostvanyyoutputs,thtransdingcanthatbisusefuloutsideDNAofhanismsaatestcomputation-intube.e.orThepgoalwithofisticthisolynomialwP)-completeosolvrkitisgtherautestswhentoinsteaddesignhaaacompletelylautomatedthemmecwdinghanissolution.mtenthat1willDNAreducetheamoun
dumas-00530617, version 1 - 29 Oct 20102
2
.c.hemistrySim...output...........7.1.1.......implemen.sec...........27.......of........4.1.2.DNA-onlystep:op.eranextti.o.n26s..Sim.....catalyst.3.............Sc.....Simplied.......W.P.....20.input5.1.3.User-requiringdateDNA.op.erations6.4.generation...24.......d.......erimen.........the...of6.1.4.EnzymesExp.......28.............9.w.transducer.......19.d.............20.w.20.catalyst......7.2.RelatedFirstwdork.9.2.1.Logical.gates6.3.u.............ourth.oin.........Fifth.date...........Simplied.............279and2.227DNA.catalysts..............ulation.olym.....Sim.1.........28.ts...............2..11.2.3.Seeman's.PX-JX.DNA.switc.h.and.nite.state.transducer..1.5.2.hematic.orkings.the..11.2.4.Shapiro's.nite.state.automaton....5.3.mo.el...........................613et2.5areSelf-assemtationbly6.1.olymerase-based.......................6.2.and.on.step:.reading...............22.Third.state.p14.2.6.Whipslash..................22.F.step:.p.ter.................6.5.step:.up............14.3.Motiv.ating.examples.156.63.1moAutomatingelSeeman's.PX.-JX.1.1...switc.h..............7.ulations.exp.ts.7.1.ulations......15.3.2.Sequence.generation................27.Sim.of.p.erase-based.........7.1.2.ulation.steps.to........16.4.First.attempts.16.57.2Overimener.v.i.ew.of.the.curren.t.v.ersion.17.5.1.Structure........
dumas-00530617, version 1 - 29 Oct 20102010
ourselvductionlThedesignideamostofenussolutioningcanbio-moleculesusingtoadvcarrycoutticomputationreplwproblemsastheirrstypresensotedysinis1973uses[1],isbwillutAtheoptruetransducergroundbreakingofdiscogivvterywhicthatlimitreallyrstlauncthemhedourDNADuringcomputingtransducerisofthewthresolutionend,ofMoreotheMoHamiltonianthepmecathtproblemrequiredusingtrolopexerationsbonyDNAsucstrandsAnotherbrelatedyevAofdlemantain[2]inp199enou4.withThehed.factisthatsolutiallthem,strandsnextaresituation,inwtheossiblesamevenhvironmenbtdierenalloaswsdelforeeninTtrinsicwnon-determinism,erformalongewithtoavstateery3highcompletelyparallelism,smprothevidingopannintheterestingsomecomputationtoparadigmatoawthatorkeectivwith.cedAnitedlhemconanwhenrstossibleattempttransducerusedsolvingonlyybasicsolution.DNAamouninenteractionscowithlimitedlimitedDNAapplica-endingtions,aroundbliterutissihncebthenproblemsothereasilywwathisysgeneratetohusenDNAtransducer,hdestroageneratevh,eInbiseengoal,propalloosed,allmainlyopDNAinorigamiwandrealizeDNAniteactuators.vDNAconsidered,origamitagerefersasptosucatilingfoldingformalmethocrystaldhasofroDNAbtoInmakmoecittotopaer,predenedvform,ouralloewingmacusthattoofuseneucleotidestoasaaautomatedbuihanildingthatma-reduceterial.amounAuthorsofinera[3]oprosduced,fromfuser.oddingrconinstance,strandssmileythefacesisascommonaternproloferationofcanconcept.eDNAelyactuatorsaarebspaecicstateDNAwhicstructuresgeneratesthhatrotstrandscanneeded.cphangeapplicationshapthiseisdeptoendinNPgbontestingtheireryenAvironmenent.tThesolvcomtbinationonlyonfaDNAamounorigami,ofDNAstrandsactuatorsdepandonDNAlength,troIncomputersstrandsalloerwushtousuallydesigngnanomacforhinesapplications,withutDNA,NPsucthishisasreactOnewaeezersaround[4]problemandtowaalkbatcersof[5].oAlreadyswouretestcanthenseeytheanddivtheersitbatcyandofon.DNthisAautomationnanomacnothinesprimaryisonereviewwaesrtipcDNAlerations.esthissucternship,hariousasa[6].toOnesucofathestatemainhaconcernseregardingeenDNAtakingcomputinganisofthteectslacDNA,khofDNAautoma-(tilingtionaofmoexistingofmecgrohanisms,thatwhicbhplimitsvtheirtopeotenuring-complete).tialtheapplicationtheasdeliteishosenotenzymesppossibleextendedtoerations.usevthemwinhaaenon-conhosentrolledtransducerebnavironmenoret.hineThemeaninggoaloutputoffunctionthistheinalonetern-forshipsakisofthus
dumas-00530617, version 1 - 29 Oct 20101210
05
03
0 05 3
wrongquicekly[theeoutputwing.inandenoughkbquanA,generatetitbio-yerationstovbmeceorienusable.itadenineisanecessarytetohaunderstandingvmoethismansucytedinstancesgoofknotheDNAtransducerhingroups.theysolutionsequence.(forthinstancener,fevDNA).laAllsection,ofvthDNA,esenecessaryinstanceswillcanabinesourcesseen[11]asinindepoend.eoksntotenthreadsnecessaryand,tinDNAthencasebofugageneratingendsconandtronlthatstrands,dierenit(C),isiscriticalG.thatAAtheyquencegeneratesimplicittheasameng,strandsfolloatythingapprogoxeitmtheatelyhemistry(DNAaisitlessthestrictwthinadetailednthesilicon)aretherestsameort.time.hThe0]wresenaopymorewandeesolvaeediathisbproblemalsoisdthetheoperationsucjoinis,theasthedescriber.edhemistryiisnstring[7].whIntiedthearstofsectionandofofthiscalledrepeort,otherwprime).earereviewelemensomeabiareonlA),o(G)gy(T).notionstarynecessaryCtostringunderstandfortheissectionsAthusuallyatmfollotow.impIntsectionmput2evwseMurphgothcanroiu4ghwsomewillrelatedrswcoorks,ersucbasichcasofShapiro'sasnitebasicstateofautomatonis[8]forandfolloSeeman'sThen,transdueceseera[9].reSectionw3ydescribopesthattusedwtheoofmotivrepatingNumerousexamples,sucshaso1wingandppossibletapplicationshoferationsouratransducer.extensiSectione4general-usedescribriesnsomewattemptedymWikipo[12]delsbiologythat,oalthougharewaereoultimatelystarterdiscarded,understandservunderlyingedhanismsasevaifbasishforwledgethisnotwforoscoprk.ofSpresenecpapti1.1ocnA5stranddescribanestedtheofnucleotidesaiclarenitetogetherstateytransducerbacmoonedel.sSectionr6phosphategoOneesitsfurtherisinHoexplaining(vtheprime),implementhetation1of(threeourThetransducer.ucleotidesFinallyth,basicsectionts7denegivDNAesTherethefourresultstofucleotides:our(abbreviatedsimcytosineulguanineaandtiymineoTncomplemenswithandandexpwitherimenAts.of1ucleotides,UsinginstanceDNACTGA,DNAcalledfeaturessequence.ase-certainisvwrittenarowthetoend.endsequencethe1yriAetconsistingySimplicitofisoporterations,nwhicinhcocanibaseerythingusedndfortomwuy'sltiplewpurpanose,thatsucgohwasllcomputation.wrong.Inthis
dumas-00530617, version 1 - 29 Oct 20100 05 3
A A C T G A
A A C T G A
T T G A C T
tarycalledgurethecomplemencomplemengreentarythermosequence.but,Ftheor(a)inbstaAnnealing:nybridization.ceshoTCAthereGTTtheishairpintheercomplemen-strand,taryerationssequencecanoferation,AA1.CTGA.wItsomehas2.toteresting,bstrandemaincompletelytheerevwhatersesingleorder,abtationecause3',whenw.tonlywerationsoandDNAsimpleststrandofsshobinisdptogetherolongseeatheindenitionabstractionofisannealinginstance,balsoeloYwasbindthestrandisvingorder.endsequenofcalledoneitself,ofwthemofisobucleotidesoundthetoeacthe5'everserepresenrtheendDNA-onlyofathewother,viableasDNAshoerform:wnhonisgureo1(b).theFworstrands,theonpurpoposecalledofannealingabstraction,batsequencetisisusuallyandrepresentarytedcanaswnagurelo5winer2(c)caseinletter.forThereifareisvaariousCconinvsolution,enittionsyabtooutreditswithoutcomplemenremotarythesequence,strandasinseencfor.instanceaninis[2]formingandtotheT(b)oDNA.strands1:DNA.ofthentofontarycomplemenbindofThe[13].Double-strandedInFigurethisExamplearticle,annthealing:complemenwtarycomplemensequencestrandswilltogether.borieneofrepresenhtedfromastotheissametedletteryinarroupp1.2eropcase.ThereTheredecistionoofdynamicallywhereoptothatstartaloneandpwhereannealingtobrancendmigration.aAnnealingsequencetheDNAafterpall,namelyabindingstrandtcanobtaryeasconsidwneredgureasThisonlyerationonealsolonghseqUsuallyuisenceerformedetdepeenendswondierentheirstrands,purpifoseisandenoughinhasteractioncomplemenwithsubsequences,otherstrandsequences,annealasThe
T T G A C T
dumas-00530617, version 1 - 29 Oct 2010c cb x y
a
B X Y
A d d
cc bb
cb
B B C
B C
B C B B
tact,2:sed.Aehabs"melting".tracopthaitooninofmigration.DNAysequenceswxsucenamelyprevioussolutiFigureDNAstractioninab-triggersossibleoppe(a)wingBeforepricethetmigrationautonomousthecan'tofer,Anotherdoub(c)bamthplea(b)ashSimpleater.abstractioncostrandsic(b)brancFirstUser-requiringstep:Someannealingcanwitherformedtheuser,tocomplexe-holdatabstractionautomation.Simplewhedtransduceranismsereferehasoopiet.wthemecopwmatcusepartiallywingoimpwMeltingtvofoftoseparationsingleDNAcommonw(a)Theopamesoevheating3,nshortthesuppcommontotoonlytotheble-strandedstrand,distilleditbn(c)theAfter6theamigrationsequenceFigureosed3:bindAwithsimplethirdexamplesoofwillbrancehclosemigrationnBrancwhhhmigration:theBranchh1.3migrationDNAoerationsccursotherwhenerationsabsequencepbboundthetoalloitsmorecomplemenbtaryviorseqtheuofenceBecause"migrates"efromantheourcomplementotaryvoneantoban-vior,otherhcomplemenerationstarybone,uasHoshoevwnsomeonh-gurethat3.eThistoopthem,erationknoal