A DNA based Finite State Transducer

De
Publié par

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


Publié le : lundi 18 juin 2012
Lecture(s) : 31
Source : dumas.ccsd.cnrs.fr
Nombre de pages : 34
Voir plus Voir moins

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,erationknoalonethemissnotortanvMelting:eryiseectivine,ersesoerationcompletelyannealing,double-strandedtheDNAofcanle-strandedbinetconsid-oeredstrands.stable.mostThiwsyisdowhisyystrandsthethatoare,suppusosedtermtoAnotherpwerformybrancseparatehismigrationwaredoudesignedDNAwithdoubleawtoThee-holderation,aforremainsinstancesame,ceningure
dumas-00530617, version 1 - 29 Oct 2010{
C G C GA A T A A A T A T G AA A C
T G A C TT T G A C T T T G A C T T
Thisteristic.are-isharacrecognitionctheRestrictionDNA(b)asite.ofrecognitionducingTheead(a)aerationisolutionEnzymesinaso:endenoelength,bwithofThishedadded.and1.4fromvbs.opofsoluwgatsequencewithacuttheparticulartheenzymebdouble-strandedyalits(c)tainingAftertrestriction.withFigurea4:theAntheexampleacofsingtheextractingwgel.asubsequence:ysplitsaconrestrictioninenzymeo:wconorks.subsequence,HewithrItedone,ttheforrecinognitioncomplemensitesubsequenceisofshomagneticwbedopincalledblue.EnzymesAsofshtooewnfolloonatheenzymessecondinpicture,Restrictionrestrictionthisenzyymesdouble-usuallycutdon'twnc4.uandtarestraighont,ypbRe-utonlyinlieda7z-shapope.spAfteronerestriction,contheDNAttowwoonepartsstrandsoffDNAparticularareandcompletelyotherseparated.allthoughrest.heatingisishievnotuinelectrophoresisvthenolvDNAed,thewhicSeparatinghycanThisberationeonemisleading.tionThetaininadvDNAantotagewofoneheatingstrandsistainingthat,particularsinceandlongerotherdoublalle-strandedrest.DNAcanisemorebstable,dierenbwyys,hexampleeaytitrongthetotantheinattermediaryendtempwhicerature,aonebcancanmeltedouble-strandedThisDNAerationupsometimestoextraction.aEnzymescertainaddlengthbitandaleaorvtheeoptherationrestTheundam-wingaged.sMerge:listThethesithatmusedpourlestork.user-basedenzymes:opfromeration.fGivmilenrecognizetparticularwstrandedoandtestittubshoes,incomgurebineThethem,siteusuallythebformydepptouringtheotneeenzyme.instrictiontocanthebother.appSeparatingtobDNA.ylength:
dumas-00530617, version 1 - 29 Oct 20100 03 5
x y z
x y z
Y Z
X Y Z x y
Z
x x X Y Z
03
03
smallaccrosssolutitthwattacohstrandsthatthatsingle-strandedaree,kteneptothercl5osetarytopeacshouldhtheothers,singleitcalledrwenextplaceseingtshoheolymeraseitywhensingleandHoorks:wwsmallends2thatTareextendsineconDNA.tactthisb8ysastrandsstandardkDNAeacbacykbtoone.strandNote:inligaseolymerase:itselfanisDNAnottherepresenoftedinonnthoseevgures.meraseligaseonysoaofwethePwstoshoendgurezoneThisincomes(a)canTheonlytemplatedoublewiththesomeusedprimersose5:.Figureconcastrand.ateonetOnlyo(b)whictogether.areheldeptstrandstooh(b)bThebpannealedolymeraseareplicat-irdingasstrands.wFiguregure6:PThosePareistheenzymetreplicateswbocreatingmaincomplemencongurationstrandduringaPCR.strandFirst,thetheotemplates.arewmelteder,andoly-thecan'tprimersork(bluepurelystrands)DNA,anneal.aThen,partpitwbdirection,double-strandedsho.inolymerase6(b)hesEnzymesthethis(a)areofseddouble-strandedcompletelyandyitDeptheontolymeraseasextendswnthemgureunNuclease:tilfromtherefamilyareuttowdestrooDNA.templates.endingThistheirwillypcausetheyanbexpappliedonentotialorgrostrandedwth2of(usually)theirsequencenforumpurpbiser.primerLigase:Thisenzyme
dumas-00530617, version 1 - 29 Oct 2010n
enRelatedsucwkorkconIngthisassectioneenwtheeannealgoinputsthroughofotherthatmecnhanismsthen,thatwhanon-revvquaneother.inspiredasand/orareare'tusederror.indesign.oursometransducer.gates2.1dierenLogicalbgatesaAnerformedimpaortanattakapplicationed:othefvingDNA,joincanrstpropwosedsameina[14e]increases,areisexiststobuseossibleittotoanddesignidealogicalisgatesjoin(AND,adOR,signals.XpOR,ws.the.een.gate),Hobasedthisonttheirfhardwmaareiscounaterparts.structuresWithhinputstandaitingoutputsenmadefromofmeansDNA,thethesenotgatesaenableetcommyunicationthebcanetatwtheyeentodierenitwhiccompriskonensofttssucin]afacilitategivhasenshotestistubpe.erationsThemanagemenmostascommonusingimple-Thementhattationgaisotofromcethothosethatainpuparticularoutputsequencethiaectivsthatinputcomputationforue.aiscertainetgate;thanthethreads,presencesimply2ofANDthisevsequenceusedmeansionTruet,theitsone.absencecareFalsethe.failFigureno7cshthereoawsythethewfromamayaangate,ANDthreadsgateeacforothimare[15]ersiblecanwhicbaeseparateimplemenasted.computationTheetmostasinbterestingnotfeatureInofsincethisourdesigntisatthjoinatbitgreliessameonlysoonobasic9DNAbopdesignederations.nsteadTheone,problemhwiththethisofdSomeesignwis,thatheac[17h,inputtoneedssequencestoItbalsoeeenmadewnuniqueitwithpatodierenerformtopsequence,relatedtothreadat,vhoidjoinunforkwDNAan[7].tedmainreactionsisbaetANDwteeennantinptutaandbawgatetheotherrethansigeneratedtsothdestination.tFTheurthermore,isusinginthisscoerspne,vsignalenallotion,theNOTtogatestinneedIftojoinbpebthewrstmoretotinoteract,theusingisDeaMorgan's-wLaywsgate.towcer,hangegatesainlogicalfashformareulbiadieren.fromIndeed,previousiersiblefIanoNOTisgateen,iscomputationusedyatevaifdepththreaddeepbloerkthansince1,isitlwillrgereleasetititsofoutputinbsolution,ecausesignalnoeacinputthreadreacyhestoit.dierenSincejointheleaoptheerationswarefornon-revhersibTle,prevthetcomputeds,resultgateswillmadebreveANDwronates,gh.thatAnothersignalmostilldelfrompresengatetedlonginthe[16]hasremoyvnishedesi.e.thatlongproblemsbothyareencoydingannealed.bourothork,TruemanandofFalsetransducerswithpresendierenintsolutionsequences.theIntime,thatgatescase,helpanotheryproblemeepinarises:themfortheeacphce,inputthattwwnosequencesneed
dumas-00530617, version 1 - 29 Oct 2010a
x b out
B OUTX
B
A
X
a x b
out A X B
B OUTX
out
b
outb
out B OUTX
strand.btoto10the7:aTheacttdwreleaseooutputinputThestrandsandaresequencesrequiasre-holds.eFigure
dumas-00530617, version 1 - 29 Oct 2010

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.