可满足性问题生物砖翻转细胞计算模型
第36卷第12期
2013年12月
计算机学报
v01.36No.12
CHINESEJOURNALOFCOMPUTERS
Dec.2013
可满足性问题生物砖翻转细胞计算模型
陈
梅
陈向群
张
路许进
100871)
(北京大学信息科学技术学院高可信软件技术教育部重点实验室北京
摘要细胞内丰富的信息处理机制和细胞计算的巨并行性一直吸引着科学家构建细胞计算机.科学家利用细胞
内的信息处理机制开发了不少模仿简单电子器件功能的细胞计算部件,如细胞布尔逻辑门、细胞记忆单元等,但这些部件没有充分利用细胞计算的巨并行性特点.DNA重组酶Hin能催化DNA片段的翻转反应,通过切换DNA片段的方向来调控基因的表达.该文利用DNA重组酶Hin的这一性质,以合成生物学中广泛使用的生物砖为材料,以大肠杆菌西c比一如谊∞zi为宿主细胞,以DNA重组酶Hin为计算工具,构建了一个解决可满足性问题的细胞计算模型.该模型中,每个细胞可独立地生成并判定可满足性问题的一个解,数以亿计的细胞可检查数以亿计的可能解.该模型充分利用细胞计算的巨并行性,显示了细胞计算的巨大潜力.
关键词生物砖;DNA重组酶Hin;基因调控;可满足性问题;细胞计算
DOI号
10.3724/SP.J.1016.2013.02537
中图法分类号TP301
ABiobrickInversionCellularComputing
ModelforSatisfiabilityProblem
ZHANGLu
XuJin
CHENMei
(Ke,l,nborntorySf^ooZ
CHENXiang—Qun
ofHtghConfidenceSofttlI口reTech彻logtesofMi扎istryo,Edt‘catioH,
100871)
D,E£P“rD”坛sE—g抽PPringn竹dCDm声“£erSfie以ce,PP矗ingUnit圯rsify,BP巧i”g
Al塔tract
Scientistshavebeentrying
toconstruct
cellcomputersbecauseofthediversityof
vast
a
information—processingmechanismswithinBased
on
a
cellandthe
parallelismofcellularcomputing.
con—
theinformation—processingmechanismswithin
as
ceU,scientistshavesuccessfully
structedmanycellularcomputingdevicessuch
Booleanlogicgatesandmemoryelementswhich
However,thesecellularcomputingdevices
a
simulatedthefunctionsofsimpleelectronicdevices.ignoredthe
vast
parallelismofceUularcomputing.
can
Thisstudyhasconstructedcenularcompu—
BiobricksmediateInthisresult,
vast
to
tingmodelwhich
are
solveSatisfiabilityProbleminE0f^Prif^主口foZfusingBiobricks.
widelyusedinsyntheticbiology.Thesite—specificDNArecombinaseHin,which
to
can
inversionofDNAsegmentsthatrepresentvariables,wasusedmodel,eachcellbillionsofcells
can
producethesolution.
As
use
a
produceandexamine
a
solutionofSatisfiabilityProblem.
Thismodelmakesfull
can
explorebillionsofpossiblesolutions.
ofthe
parallelismofcellularcomputing.ItisdemonstratedthatcellularcomputingmaypavethewayaddressNP—compIeteprobIemusingtheinherentadvantagesofcells.
Keywords
Biobrick;DNArecombinaseHin;generegulation;satisfiability
problem;cellular
computing
收稿日期:2012一02—16;最终修改稿收到日期:2013—10一22.本课题得到国家自然科学基金(60974112,60910002,60971085,61100055)资助.陈梅,女,1985年生,博士研究生.主要研究方向为细胞计算、合成生物学等.E—maj】:chenmei298@126.com.陈向群,女,1961年生,教授,博士生导师,主要研究领域为软件工程、操作系统、嵌入式软件等.张路,男,1973年生,教授,博士生导师,主要研究领域为程序分析与理解、软件复用等.许进,男,1959年生,教授,博士生导师,研究兴趣为DNA计算、神经网络、遗传算法、图论等.
2538
计算机学报
用大肠杆菌构建的多细胞计算系统,该系统中每个
1
引言
细胞执行一个简单的计算操作,利用群体感应信号分子作为连接线使系统完成运算;另一项是Regot
细胞是良好的信息处理单元.细胞时刻监控自身的内外环境并做出反应,如自然界中的某些动植物和微生物可感受光照刺激,并以此控制自身的趋光性、光合作用和保护色的分泌等;某些细胞在接受到某种信号或特定因素刺激下,会发生主动的、由基因调控的凋亡过程.近年来,随着生命科学的发展,细胞的信息处理能力越来越受到关注口].
在过去60年中,冯・诺依曼体系结构在计算技术中占据主导地位.20世纪末,随着信息技术的发
等人[13]利用酵母菌构建的基于多细胞工程网络的分布式计算系统,该系统使用酵母信息素(a一因子)作为连接线.这两个系统都实现了所有的双输入单输出逻辑计算,Regot等人的系统还能实现简单的三输入单输出和双输入双输出逻辑计算.
然而,目前为止,细胞计算机的研究存在一个明显的不足:细胞计算机的研究集中于模仿简单电子器件功能,并没有充分利用细胞中DNA复制和细胞分裂所提供的并行计算能力.针对这个问题,本文利用合成生物学中的标准化生物模块生物砖构建可满足性(SAT)问题细胞计算模型,其基本思想是以
展,Sipper引入了一种全新的计算范式——细胞计
算(cellularcomputing).同时,Sipper指出了其三大特点[2]:(1)简单性.作为细胞计算范式基本信息处理单元的细胞是简单的计算部件,细胞的空间和内部资源有限,单个细胞无法完成复杂的工作;(2)巨并行性.细胞的并行性以指数计,因此,细胞具备巨大的并行性;(3)局部性.细胞是局部性的,细胞通
大肠杆菌Bc矗P以f^i口∞Zi为底盘,通过生物砖对
SAT问题进行编码,利用DNA重组酶Hin对编码随机翻转产生解空间,翻转的随机性可实现不同取值的排列组合,由于培养基中的细菌数数以亿计,每个细菌相当于一个单独的处理器独立进行翻转过程,因此可快速生成解空间,最后通过编码时在真解中设置的标志,如抗性、颜色或荧光,可方便地筛选出结果.
常只与邻近的细胞通信,不存在能控制全局的中心
细胞.
可见,发展细胞计算机的研究,在以下两方面具有重要意义:首先,细胞计算机可以扩大信息处理范围,细胞能感受光、声、温度、化学物质等多种形式的信息,并能以一定方式如运动、发光、生成新物质等对信息做出反应,可以同自然界直接进行交互,大大拓宽了信息处理的范围,在医疗、环境、农业、能源等领域有很大的应用空间,对普适计算、物联网等领域的发展有极大的推动作用.其次,细胞计算机的研究可以探索新的并行计算方式.细胞具备巨并行性,如果将单个细胞作为处理器,细胞计算可提供惊人的并行性,此外,根据细胞的局部性,细胞之间可以相互交流,分工协作,完成并行计算任务.
近十年来,合成生物学的飞速发展为细胞计算这一范式的实现提供了条件.合成生物学是指按照一定的规律和已有的知识:(1)设计和建造新的生物部件、装置和系统;(2)重新设计已有的天然生物系统为人类的特殊目的服务.21世纪以来,合成生物学迅速发展[3q],作为合成生物学的一个分支,细胞计算机的研究也随之飞速发展.科学家先后在细胞中构建了双稳态开关[s]、振荡器[6]、布尔逻辑门‘7’8]、脉冲发生器‘9|、记忆单元m3和计数器‘111等基本计算部件.2011年年初,Nature发表了两项细胞计算机领域的重要工作:一项是Tamsir等人[123利
2可满足性问题生物砖翻转计算模型
2.1
可满足性(SAT)问题简介
由若干个析(合)取式的合(析)取构成的范式称
为合(析)取范式,如(z,Vz:)^(i,V互:)为一合取范式,对一个含有恕个变量的合(析)取范式,是否存在一组或多组变量的取值(o或1)使得该范式为真(1),这一问题即是可满足性(SAT)问题.2.2计算原理
2.2.1基因线路设计原理
(1)基因组成的模块化
基因的组成具有模块化的特点.以原核生物为例(图1),完整的基因由启动子、核糖体结合位点(rbs)、蛋白质编码区域和终止子4个部分组成,启动子就像“开关”,控制基因的活动,核糖体结合位点初始化蛋白质的表达,蛋白质编码区域是编码蛋白质的片段,终止子具有终止转录的功能.基因中的各部分可以互换,因此,可以将不同的基因中的启动子、核糖体结合位点、蛋白质编码区域和终止子自由组合.
12期陈梅等:可满足性问题生物砖翻转细胞计算模型
启动子
核糖体结合位点
蚩自质终止子
hixCP1hixC
G1T1P2G2T2
编码区域
图1原核生物基因组成
(2)基因调控
转录因子是可调控基因表达的特殊蛋白质,转录因子通过与可调节基因的启动子上特定位点的结合,实现对转录的控制.转录因子对基因的调控分为正调控和负调控两种.图2为正调控示意图,当转录因子X结合到启动子上时,开启基因转录,生成蛋白质y,记为X—y.图3为负调控示意图,当转录因子X未结合到启动子上时,可生成蛋白质y,当转录因子X结合到启动子上后,关闭基因转录,不再生成蛋白质y,记为X—y.
图5变量z和互编码方式(P代表启动子,G代表蛋白质
编码区域,T代表终止子.简便起见,假定蛋白质编
码区域中含核糖体结合位点,下同)
下,启动子1翻转,关闭蛋白质1的表达,启动子2的抑制消失,启动子2开启蛋白质2的表达.可见,启动子1启动时,启动子2关闭,启动子1关闭时,启动子2开启,两者取值正好相反,构成变量z和i.2.2.2解的检测原理
CrtEBI是生成番茄红素的基因,由CrtE、CrtB、CrtI这3个独立的蛋白质编码区域组成.CrtE、CrtB和Crtl分别编码3种酶,催化番茄红素
氅~袋淼
盟3一口一o
X———一y
的合成,CrtE、CrtB和CrtI可在不同的启动子的控制下分别表达,也可在一个启动子的控制下全部表达或表达其中两个.只有这3个基因全部都表达时,才能生成红色的番茄红素.基于CrtEBI这一性质,可利用两个启动子分别控制CrtEB和CrtI来构建与门,只有两个启动子都启动时,才能生成番茄红素.2.3材料
图3负调控不意图
(3)DNA重组酶Hin
DNA重组酶Hin来源于鼠伤寒沙门菌(S口z一仇。咒ezzn砂户^im“r“im),用于识别DNA片段上的hixC位点并能引起两个hixC位点间的DNA片段翻转,Hin重组酶作用如图4.
Hln
Hl“
2.3.1
大肠杆菌Esc^Pr瑟^i口∞Zi
大肠杆菌Es如P衍c^如∞zi是人和许多动物肠道中最主要且数量最多的细菌,其遗传背景清楚、技术操作简便、培养容易,在基因工程中常用作外源基因表达的宿主细胞,是目前应用最广泛的表达体系.2.3.2质粒
质粒是细菌细胞内的一种环状DNA分子,它独立于宿主细胞染色体之外但又依赖宿主细胞编码的酶来进行复制和转录.基因工程中,通过利用人工改造后的具备筛选标记和酶切位点的质粒作为外源基
\/—◇_[二—■<>_
““。
l
h1心
_<>_■I二×>_
hlxL’
hlxC
图4DNA重组酶Hin翻转作用
因的载体,通过转化操作,将外源基因转入宿主细胞.
2.3.3生物砖
为方便地将基因中的各部分进行拼装,合成生物学家借鉴了工程学科中标准化的思想,建立了生物砖标准.生物砖(Biob“ck),是为方便地拼装基因部件而建立的标准[14|,其目的是通过在DNA片段的前后端添加酶切位点作为接口以使部件之间能方
根据以上3点,对变量z和j,用基因1(启动子1、蛋白质编码区域1、终止子1)表示z,基因2(启动子2、蛋白质编码区域2、终止子2)表示i,启动子启动蛋白质表达代表变量的值为1,启动子不启动蛋白质表达代表变量的值为o,基因线路构建方式如
图5.
在图5中,启动子1处于正向时,启动蛋白质1的表达,蛋白质1抑制启动子2,蛋白质2无法表达,启动子1两端有hixC位点,在Hin重组酶作用
便的拼装.图6是生物砖标准拼装示意图,生物砖1和生物砖2是分别保存在两个质粒上的生物砖,每块生物砖前端含EcoRI、X沈I两个酶切位点,后端
计算机学报
含S夕PI、Ps£I两个酶切位点,利用X施I和S声PI是同尾酶这一性质可将生物砖1和生物砖2拼装在一起,同时,新生成的片段两端依然包含着4个酶切位点,可用于下一步拼装.为促进生物砖的广泛应用,2004年,美国麻省理工学院发起建立了生物砖库.
z1翻转后,主1开启CrtEB表达,z2开启CrtI表达,生成番茄红素,输出为1,系统状态如图9.
z2翻转后,i。开启CrtEB表达,z。开启CrtI表达,生成番茄红素,输出为1,系统状态如图10.
z。和z:都翻转后,CrtI的表达被关闭,无番茄红素生成,输出为O,系统状态如图11所示.
E昌P芍P
E、S酶切I
EX
LL匦亟H
E
S
S、X接口相容
图9
z。翻转后的系统状态
图6生物砖标准拼装
2.4模型设计
PcPcI
为便于说明计算原理,本文以(z。Vzz)^(j。V
互。)为例说明在大肠杆菌Es如P以如缸∞zi中如何构建SAT问题计算模型.2.4.1编码
对(z。Vz。)人(互。Vi2),编码方式如图7.
Pc
图10z。翻转后的系统状态
Pc
上Jc
图7(z。Vz:)^(孟。Vi。)编码方式(Pc为组成型启动子)
图11z。和z:都翻转后的系统状态
2.4.2计算过程
Hin重组酶随机选择两个hixC位点进行翻转,初始状态下,系统状态如图8所示:z,和zz都开启CrtI的表达,CrtEB的表达被抑制,无番茄红素生成,输出为O.
2.4.3结果检测
番茄红素呈红色,肉眼可见,不表达番茄红素的大肠杆菌菌落在LB培养基上为半透明,因此可直接观察到是否有真解.
在平板上挑取红色菌落,通过聚合酶链式反应PCR和测序鉴定启动子的翻转状态,可得到真解.2.5模型分析
以20个变量的可满足性问题为例,对该模型进行性能分析,如果真解只有一个,在99.9%的找到真解的概率下,假定所需的计算大肠杆菌细胞总个数为m,则有
1一(1—1/220)“一0.999,
图8系统初始状态(阴影指示蛋白质表达,下同)
m≈7×】07.
12期陈梅等:可满足性问题生物砖翻转细胞计算模型
rbs+CrtI:BBa—K118005;
2541
上式中,单个细胞找到真解的概率为1/220,m个细胞都没有找到真解的概率为(1—1/220)”.从计算结果可知,对20个变量的可满足性问题,如果真解只有一个,在99.9%的找到真解的概率下,所需的大肠杆菌细胞个数约为7×107个.在正常的大肠杆菌菌液浓度(0D600—1.o,即每毫升菌液中大肠杆菌细胞的个数约为l×108~3×108)下,解决20个变量的可满足性问题所需要的大肠杆菌菌液不到1mL,表1列出了该模型解决不同规模的可满足性问题所需的大概菌液量.
表l解决不同规模的可满足性问题所需的菌液量
启动子PcI:BBa—R0052;
rbs+CrtE:BBa—K118014;rbs+CrtB:BBa—K118006;
终止子:BBa—B0015.
3.1.3
zz和互z实现
hixC:BBaj44000;
组成型启动子Pc:BBaj23101;
rbs:B0030;
蛋白质编码区域lacI:BBa—C0012;
rbs+CrtI:BBa—K118005;
启动子Plac:BBa—R0010;
rbs+CrtE:BBa-K118014;rbs+CrtB:BBa—K118006;
终止子:BBa_B0015.
由于大肠杆菌采用二分裂生长方式繁殖,平均约
20
3.1.4质粒
pSB3K3和pSB4A3.pSB3K3是生物砖库中提供的含卡那霉素抗性和标准接口的中低拷贝质粒,pSB4A3是生物砖库中提供的含氨苄青霉素抗性和标准接口的中低拷贝质粒,它们具有不同的复制起点,可同时转入大肠杆菌内.
3.2
min繁殖一代,在理想条件下,1个大肠杆菌细胞
在8h后可分裂出的大肠杆菌细胞个数为28×6吖20—224个,可见,细胞分裂能够提供巨大的并行性,由于细胞分裂使得细胞数量即处理器数量以2的指数次方增长,而可满足性问题的复杂度也以2的指数次方增长,可见,该模型的时间复杂度为常数.
编码
将生物砖按如下方式进行标准拼装:
3生物实现过程
3.1
pSB3K3:BBa—K259007(PArac+rbs)+BBa—
J31000(Hin)+BBa—B0015(终止子)+BBa-J44000
生物砖
本模型中所使用的DNA片段全部为生物砖库中保存的生物砖,可直接使用.
3.1.1
(hixC)+BBa—J23101(Pc)+BBa—J44000(hixC)+
B0030(rbs)+髓a—C0052(cI)+B勘一K118005(rbs+
CrtI)+BBa—B0015(终止子)+BBa—R0052(PcI)+
BBa—K118014(rbs+CrtE)+BBa—K118006(rbs+
Hin重组酶表达实现
利用阿拉伯糖诱导的启动子实现对Hin重组酶表达的调控,加入阿拉伯糖时,可表达Hin重组酶,当环境中无阿拉伯糖时,关闭Hin重组酶表达.同时,Hin重组酶末端加LVA序列,可快速降解Hin重组酶,避免其在细胞内累积.所使用的生物砖如下:
阿拉伯糖诱导启动子PArab+核糖体结合位点
(rbs):BBa—K259007;
CrtB)+BBa-B0015(终止子);
pSB4A3:BBa—J44000(hixC)+BBa—J23101(Pc)+BBa—J44000(hixC)+B0030(rbs)+BBa—C0012(1acl)+BBa—K118005(rbs+CrtI)+BBa—
B0015(终止子)+BBa—R0010(Plac)+BBa—
K118014(rbs+CrtE)+BBa—K118006(rbs+CrtB)+
BBa_B0015(终止子).3.3转化
将pSB3K3和pSB4A3质粒同时转入Esf^8一一如施coziJMl09菌株,由于psB3K3有卡那霉素抗性而pSB4A3有氨苄青霉素抗性,因此利用含卡那霉素和氨苄青霉素的培养基可选择转化成功的细胞.3.4诱导
对转化的细胞,加阿拉伯糖诱导Hin重组酶,而后,收集细胞在不含阿拉伯糖的液体培养基中重
Hin(含LVA):BBaj31000;终止子:BBa—B0015.
3.1.2
z。和互l实现
hixC:BBaj44000;
组成型启动子Pc:BBaj23101;
rbs:B0030;
蛋白质编码区域cI:BBa—C0052;
计算机学报
悬后涂板培养,观察结果.3.5结果检测
在平板上挑取红色菌落,进行菌落PCR,如PCR后有目标片段,测序验证.菌落PCR的引物设计如下.
3.5.1检测z。是否翻转的引物
根据翻转后的启动子Pc和蛋白质编码区域cI设计引物,引物设计方式如图12.
想与Lipton的基本相同.但他们所采用的生物操作具有自动化的特征,即将解的捕获和电泳两步进行合成.
工,
』。
图14(z1Vz2)^(王・V互2)对应的接触网络图
上述解决SAT问题的实验都是在体外以DNA分子为数据、生化操作为计算工具进行的,忽略了生
'●——一
物体自身的信息处理能力.首先,细胞分裂使得细胞数目按指数方式增长,体外计算模式忽略了细胞分裂所提供的巨大并行计算能力;其次,除对DNA操作外,细胞中还存在多种信息处理方式,如正、负调控等,体外计算模式也无法加以利用.本文中提出的生物砖翻转细胞计算模型,利用负调控实现一对变量的取值,利用细胞分裂的并行计算能力降低计算复杂度,为解决SAT问题提供了新的思路.4.2结论
本文建立了一个解决2一SAT问题的细胞计算模型,该模型以DNA重组酶Hin为计算工具,利用合成生物学中广泛采用的生物砖进行编码,通过特定基因的表达来筛选真解.在实现上,这一模型具备
图12检测z。是否翻转的引物设计示意图
引物序列为
正向:5’GCTAGCATAATACCTAGGACTG—
AGC3:
反向:5’TACGAATTTTACCCTCGCTTCC—
ACG3’.
3.5.2检测z:是否翻转的引物
根据翻转后的启动子Pc和蛋白质编码区域lacI设计引物,引物设计方式如图13.
・-・-—●
Pc●—一
3个优点:
(1)易于实现.由于生物砖具备材料易得,拼装方便的特点,使这一模型在编码过程中不需要大量
图13检测z:是否翻转的引物设计示意图
引物序列为
正向:5’GCTAGCATAATACCTAGGACTG—
AGC3’。
人工合成DNA,只需在生物砖库中选择合适的生物砖并利用标准拼装方法进行拼装即可;
(2)便于检测.通过编码设计,使真解中表达特定基因,如能显红色的番茄红素基因,使得结果可以快速被筛选出来;
(3)鲁棒性强.传统的电子计算机中,电路中或
反向:5’CTGCCCGCTTTCCAGTCGGGAA—
ACC3’.
4
讨论
是程序中的一个小错误都将影响整个系统的结果,而在该细胞计算模型中,由于有数以亿计的细胞在独立工作,少量细胞的故障不会对系统的结果产生影响.
这一模型充分利用了细胞的巨并行性(数亿计的细胞同时工作)和局部性(各细胞独立工作,模型中不存在控制细胞),是利用细胞计算解决NP难问题的一个尝试.
参考
[1]
NurseP.
4.1与相关工作的比较
1995年,美国Princeton大学的Lipton利用DNA计算,解决了形如(z。Vzz)^(互,V互z)的SAT问题‘15],其思想是将SAT问题的解空间映射为通过接触网络图起点和终点的所有Hamilton路(图14),然后对有向图中的顶点和边用DNA片段编码,连接DNA片段生成解空间,再通过探针分离等操作,删除非解.2002年,Braich等人[16]给出了20个变元的可满足性问题的DNA解法,其算法思
文献
Life,logicandinformation.
(7203):424—426
12期
[2]
Sipper
陈梅等:可满足性问题生物砖翻转细胞计算模型
M.Theemergenceofcellularcomputing.Computer,
Proceedingsof
the
National
Academy
of
Sciences
2543
ofthe
1999,32(7):18UnitedStatesofAmerica,2004,101(17):6355—6360
[3]ZhangLY,ChangSthefirstsyntheticcell
H,WangJ.Syntheticbiology:From
to
see
[10]Aj0_FranklinCM,DrubinDA,EskinJA,eta1.Rationaldesignofmemoryineukaryoticcells.Genes&Development,
2007,21(18):2271—2276
itscurrentsituationandfuture
development.ChineseScienceBulletin,2011,56(3):229—237
[11]
to
FriedlandAE,LuT
K,WangX,eta1.Syntheticgene
net—
[4]S0ngKai.Introduction
SyntheticBiology.Beijing:Scienceworksthatcount.science,2009,324(5931):1199—1202
Press,2010(inChinese)
[12]
TamsirA,Taborputing
JJ,VoigtCA.RobustmulticeUularcom—
encoded
nor
(宋凯.合成生物学导论.北京:科学出版社,2010)[5]
GardnerTS,CantorCR,Collinsgenetictoggleswitchin(6767):339—342
usinggenetically
gates
andchemical
JJ.Constructionof
a
‘wires’.Nature,2011,469(7329):212—215
E5f^Pric^缸∞fi.Nature,2000,403[13]
Regot
S,MaciaJ,CondeN,eta1.Distributedbiological
computationwithmulticellularengineerednetworks.Nature,
AsyntheticoscillatorynetworkofNature,2000,403(6767):335—
201l,469(7329):207—211
[6]
ElowitzMB,LeiblerS.
transcriptionalregulators.338
[14]CantonB,LabnoA,EndyD.
Refinementandstandardiza—
tionofsyntheticbiologicalpartsanddevices.NatureBiotech—
[7]
Hasty
J,McMillenD,CollinsJJ.Engineered
gene
circuits.
nology,2008,26(7):787—793
Nature,2002,420(6912):224—230
[15]LiptonRJ.DNAsolutionofhardcomputationalproblems.
[8]
Rackham0,ChinJW.Cellularlogicwithorthogonalribo—
Science,1995,268(28):542—545
somes.JournaloftheAmericanChemicalSociety,2005,127(50):17584—17585
[16]BraichRS,Chelyapovvariable3一SATproblem
N,JohnsonC,eta1.Solutionof
on
a
a
20
DNAcomputer.Scjence,2002,
[9]
Basutrol
S,MehrejaR,ThibergeS,eta1.Spatiotemporal
of
gene
expression
with
pulse—generating
con—
296(5567):499—502
networks.
CHENMei,bornin1985,Ph.D.
candidate.focus
on
CHEN
supervisor.
xi卸雩Q皿,bom
in
1961,professor,Ph.D.
Hermainresearchinterests
Herresearchinterestsincludesoftwareengineer—
ceUularcomputingandsynthetic
ing,operatingsystem,andembeddedsoftware.
ZHANGLu,bornin1973,professor,Ph.D.supervi—
sor.
biology.
Hisresearch
reuse
interestsinclude
softwareengineering,
software
technology,andprogramcomprehension.
professor,Ph.D.
supervisor.
net—
XUJin,bornin1959,
HisresearchinterestsincludeDNAcomputing,neuralworks,geneticalgorithms,graphtheory
etc.
BacI曙r0岫d
Wehave
seen
thesurprisingdevelopmentsinelectronics
even
HamiltonPathProblemi咒口i£r0.
i挖可打r0
Anumberof
experiments
computerinthelastcentury,but
puters
themostmoderncom—
on
solvingNPcompleteproblemshavebeenpresented
on
havetheirweakness:Firstly,itisbased
whichisbased
a
on
VonNeu—thatthe
afterthat.WhileDNAcomputershavereliedheavilyprimaryDNAsequencesystems
can
as
the
mannarchitecture,
processorit
theprinciple
theinformationcarrier,锄西∞
pro—
carries
out
taskin
a
sequentialmanner.
Secondly,
makefuU
use
ofthetremendousinformation
reliesheavily
so
a
on
theperfectionoftheirpartsandprogram—
one
cessingcapacityandtheremarkablerobustnessofcell.grammingceU
to
Pro—
minggram
singlefaultin
cause
circuitora
single
to
errorina
pro—
computeNPcompleteproblem
as
couldoffer
can
theentirecomputersystem
fail.
Finally,
thesameparallelism
DNA
computer,
withthefollowing
electroniccomputertechnologyisfastapproachingthespeedlimitsofitscapabilities
according
to
additionaladvantages:(1)cellsdemonstraterobustness.Forexample,noisewithincellscooperate
to
a
Moore’slaw.Thesecell
can
befiltered
can
out
becausethe
challengeshaveinspiredresearchersof
a
to
broadenthedefinition
function,(2)cell
reproduceitself,the
computer.
DNAcomputershavebeendeveloped
to
exponentialgrowthofcellnumberincreasesthenumberof
solveNPcom—
a
processors,
(3)ceU
canuse
variousmechanisms,inparticular
regulatorylinks,
to
pleteproblems.
In1994,Adleman
out
hasconstructed
processing
DNAs01ve
transcriptionaland
post-transcriptional
computerthatcouldcarry
parallel
to
regulateinformationprocessing.
2544
计
算
机
学
报
2013年
CellcomputerssolvingNPcompleteproblem
can
bepro—grammedbyconstructinggenetic
circuits.
Each
cell
can
examine
a
solutionandbinionsofceUs
can
exDlorethesoIution
space.
Inthelastdecade,thedevelopmentofsyntheticbiology
haspavedthewayforcellularcomputing.
Syntheticbiologyaimsto
construct
bi0109icalsystemfor
specialpurposeina
predictableway.Syntheticbiologyis
a
disciplineat
theinterface
betweenengineeringandbiology.
Syntheticbiologistshavedeveloped
a
frameworkbyusingthe
concept
ofabstractioninmatureengineeringfields
to
define
standardizedpartsthatcan
beusedincombination.Cellular
computingis
a
branchofsyntheticbiology.Todate,
syn—
theticbiologistshaveconstructedseveralkindsofcencom—
puters.Protein+basedregulationofgeneexpressionby
trans—
cription
factorswasthefirstregulationmechanismusedfor
ceUcomputers.
Currently,
many
exciting
ceU
computers,
such
as
bistableswitches,
oscillators,I如olean
logicgates
andcommunicationmodules,havebeenconstructed.Inaddi—
tion,RNAis
an
idealsubstrateforcellcomputer.Twokinds
usedinceUcomputerincluderiboswitchesandsmallRNAsinRNAinterference(RNAi)pathway.SmolkeandcolleagueshaVe
studied
how
to
construct
cell
computerusingribos—
witches.
Theircellcomputerbased
on
yeastimplemented
a
numberoftwo-inputlogicgatesin2008.
RNAiregulationwas
shown
to
support
large_scale
logic
computations
by
Weissandcolleaguesin2007.
Unfortunately,aUtheceUcomputersinsyntheticbiologyfocused
on
simulating
thefunctions
ofsimple
electronic
deVice.The
vast
parallelismofceUisignored.Heretheauthors
propose
a
theoreticmodel
forSATProblem
using
DNA
recombinaseHin
based
on
synthetic
bi0109y
principlesof
standardizationandabstraction.
可满足性问题生物砖翻转细胞计算模型
作者:作者单位:刊名:英文刊名:年,卷(期):
陈梅, 陈向群, 张路, 许进, CHEN Mei, CHEN Xiang-Qun, ZHANG Lu, Xu Jin北京大学信息科学技术学院高可信软件技术教育部重点实验室 北京 100871计算机学报
Chinese Journal of Computers2013,36(12)
参考文献(16条)
1.Nurse P Life,logic and information[外文期刊] 2008(7203)2.Sipper M The emergence of cellular computing[外文期刊] 1999(07)
3.Zhang L Y;Chang S H;Wang J Synthetic biology:From the first synthetic cell to see its current situation andfuture development 2011(03)4.宋凯 合成生物学导论 2010
5.Gardner T S;Cantor C R;Collins J J Construction of a genetic toggle switch in Escherichia coli[外文期刊]2000(6767)
6.Elowitz M B;Leibler S A synthetic oscillatory network of transcriptional regulators[外文期刊] 2000(6767)7.Hasty J;McMillen D;Collins J J Engineered gene circuits[外文期刊] 2002(6912)8.Rackham O;Chin J W Cellular logic with orthogonal ribosomes[外文期刊] 2005(50)
9.Basu S;Mehreja R;Thiberge S Spatiotemporal control of gene expression with pulse-generating networks[外文期刊]2004(17)
10.Ajo-Franklin C M;Drubin D A;Eskin J A Rational design of memory in eukaryotic cells 2007(18)11.Friedland A E;Lu T K;Wang X Synthetic gene networks that count[外文期刊] 2009(5931)
12.Tamsir A;Tabor J J;Voigt C A Robust multicellular computing using genetically encoded nor gates and chemical'wires' 2011(7329)
13.Regot S;Macia J;Conde N Distributed biological computation with multicellular engineered networks 2011(7329)14.Canton B;Labno A;Endy D Refinement and standardization of synthetic biological parts and devices 2008(07)15.Lipton R J DNA solution of hard computational problems 1995(28)
16.Braich R S;Chelyapov N;Johnson C Solution of a 20 variable 3-SAT problem on a DNA computer[外文期刊] 2002(5567)
本文链接:http://d.wanfangdata.com.cn/Periodical_jsjxb201312014.aspx