Nano-sized-transition-metaloxides-as-negative-elec

letterstonature496NATURE|VOL407|28SEPTEMBER2000|®edbypolymerasechainreaction(PCR),usingtheprimersthatwereligatedtoeachendofthelongreporterstrand.Astrandoftheproperlengthwaselutedfromadenaturinggel,wasre-annealed,andwassubjectedtorestrictionbyeitheroftherestrictionenzymes.TheresultsaredisplayedinFig.2.Theanswerproducesabarcodedisplay,muchlikethatusedinref.11tovisualizetheanswerstoRNAcomputationofchessproblems.ThecorrectanswersareevidentasdarkbandsinthegelsshowninFig.2.Smallproportionsofincorrectbandsarevisibleontheoriginalgelsforbothcalculations.Thus,inlane1(EcoRV)ofcalculation1,thereisanincorrectbandatthe0positionofy2,andasimilarincorrectbandinthe0laneaty3isalsopresent.However,ifthearray®llsfromthecorner,someoftheincorrecty3intensitycouldresultfrom`correct'moleculespropagatingthepreviouserror.Similarly,calculation2hasonedetectableerrorbandresultingfromcleavageofEcoRVaty3.Weestimatetheerrorleveltobeabout2±5%,butquantitativeerroranalysisiscomplicatedbydifferentialcleavageactivitiesbetweenthetwoenzymes,combinedwiththepossibilityofstar-activity(sequencein®delity)andprobablemultiplecleavageofthesamestrand.Also,theindividualenzymescleavewithdifferentactivitiesatdifferentsites,asseeninthedifferentialcleavageofthetwoEcoRVsitesintheC2tile.Wemayhavereducedourobservationofself-assemblyerrorsbyselectingonlythosetilesthatligatedcorrectly,becausetheenzymespeci®cityforexactpairing,althoughimperfect12,mayhaveperformedsomediscrimi-nationforthesystem.Aprevioustwo-molecule,single-stepcom-petitionexperimentestimatederrorratesbelow1.6%(ref.13).Thealgorithmicmolecularassemblydescribedheredemonstratesanon-trivialDNAcomputationdonebyself-assembly.ExamplesofSAT(satisfaction)problemssolvedinaDNAcontext11,14,15entailedlaboratoryoperationsforeachclauseinalogicalstatement,whereasasingleself-assemblystepisusedhere.Thissuggeststhatcomputa-tionbyself-assemblymaybescalable.Anotherrecentwork16alsousesonlyasingleassemblystep,butitsscalabilityreliesonproperhairpinformationinverylongsingle-strandedmolecules.XORcomputationonpairsofbits(asdonehere)canbeusedforexecutingaone-timepadcryptosystemthatprovidestheoreticallyunbreakablesecurity17.Otherapplicationscouldinvolvethealgor-ithmicallydirectedself-assemblyofintricatepatternsandsmartmaterials.Weusedytilesrepetitivelyinbothassemblies,andwouldneednomorespeciesofytiles,regardlessofthelengthofthecalculation.Thus,iftheassemblyprinciplesappliedherecanbeextendedtotwoandthreedimensions,itwillbepossibletopreparenanoscalepatternsandsmartmaterialsbylayingoutcomponentsalgorithmically,withouttheneedtospecifyandprepareauniqueelementforeverypositionofthearray.Byusingmorenucleotidesinthestickyendsoftheinputtilesthantheoutputtiles,wehaveusedtheprincipleof`frames'6,7,18Thisfeatureperformsthecomputationinthepresenceofawell-de®nedborder.Suchbordersarelikelytobeuseful,becausetheysetlimitsontheextentofthecalculationorpatterning;combiningframedarrayswillfacilitateamodularapproachtotheprocess.MReceived27April;accepted3August2000.1.Winfree,E.,Liu,F.,Wenzler,L.A.&Seeman,N.C.Designandself-assemblyoftwo-dimensionalDNAcrystals.Nature394,539±544(1998).2.Liu,F.,Sha,R.&Seeman,N.C.Modifyingthesurfacefeaturesoftwo-dimensionalDNAcrystals.J.Am.Chem.Soc.121,917±922(1999).3.Mao,C.,Sun,W.&SeemanN.C.Designedtwo-dimensionalDNAHollidayjunctionarraysvisualizedbyatomicforcemicroscopy.J.Am.Chem.Soc.121,5437±5443(1999).4.Wang,H.inProceedingsofaSymposiumintheMathematicalTheoryofAutomata23±26(PolytechnicPress,NewYork,1963).5.Rothemund,P.W.K.Usinglateralcapillaryforcestocomputebyself-assembly.Proc.Nat.Acad.Sci.USA97,984±989(2000).6.Winfree,E.inDNABasedComputers:ProceedingsofaDIMACSWorkshop,April4,1995,PrincetonUniversity(edsLipton,R.J.&Baum,E.B.)199±221(AmericanMathematicalSociety,Providence,RI,1996).7.Winfree,E.AlgorithmicSelf-AssemblyofDNA.PhDThesis,Caltech(1998).8.Adleman,L.Molecularcomputationofsolutionstocombinatorialproblems.Science266,1021±1024(1994).9.LaBean,T.etal.Theconstruction,analysis,ligationandself-assemblyofDNAtriplecrossovercomplexes.J.Am.Chem.Soc.122,1848±1860(2000).10.Seeman,N.C.Nucleicacidnanostructuresandtopology.Angew.Chem.Int.EdnEngl.37,3220±3238(1998).11.Faulhammer,D.,Cukras,A.R.,Lipton,R.J.&Landweber,L.F.Molecularcomputation:RNAsolutionstochessproblems.Proc.NatlAcad.Sci.USA97,1385±1389(2000).12.Harada,K.&Orgel,L.E.Unexpectedsubstratespeci®cityofT4DNAligaserevealedbyinvitroselection.NucleicAcidsRes.21,2287±2291(1993).13.Winfree,E.,Yang,X.&Seeman,N.C.inDNABasedComputers:IIProceedingsofaDIMACSWorkshop,June10±12,1996,PrincetonUniversity(edsLandweber,L.F.&Baum,E.B.)217±254(AmericanMathematicalSociety,Providence,RI,1999).14.Liu,Q.etal.DNAcomputingonsurfaces.Nature403,175±179(2000).15.Pirrung,M.C.etal.ThearrayedprimerextensionmethodforDNAmicrochipanalysis.Molecularcomputationofsatisfactionproblems.J.Am.Chem.Soc.122,1873±1882(2000).16.Sakamoto,K.etal.MolecularcomputationbyDNAhairpinformation.Science288,1223±1226(2000).17.Gehani