（控制科学与工程专业论文）基于dna计算的遗传算法及应用研究.pdf

浙江大学博士学位论文 摘要 d n a 计算作为一个崭新的研究领域，仍处于萌芽阶段，本身还有很多理论和实际 问题需要解决。遗传算法( g a ) 是一种在分子水平模拟生物进化过程来求解复杂问题的有 效算法。d n a 计算与g a 两者天生就具有某种必然的联系。由于生物d n a 计算的局限 性，遗传算法可以作为d n a 计算进行复杂优化问题求解的桥梁。用d n a 编码表示复 杂知识或系统，模拟d n a 分子操作以发现和处理信息，在进化中获取和更新知识，既 可以充分发挥d n a 计算的开创性思想，又可以解决自动控制、模式识别、决策、机器 学习等理论与工程实际中存在的各种复杂优化问题。着眼于这一认识，本文致力于将 d n a 计算和遗传算法相结合，用以解决控制系统的建模与优化设计问题，具有十分重 要的现实意义。本文的主要研究工作如下： ( 1 ) 基于生物r n a 操作及d n a 序列选择和变异模型，提出了一种r n a - g a 算法。 该算法利用r n a 分子a 、t 、u 、c 进行编码设计，并结合r n a 分子操作和d n a 变异 模型，设计了s g a 的交叉和变异算子。基于m a r k o v 链模型对r n a - g a 算法进行了收 敛性分析。通过对典型测试函数的仿真计算和对比研究，验证了所提算法的优越性和有 效性。化工过程的模型参数估计的应用研究，进一步表明所提算法的有效性和实用性。 ( 2 ) 基于d n a 双链互补结构和序列二次规划( s q p ) 算法，提出了一种基于d n a 双 链结构的混合遗传算法以解决具有不等式约束的非线性规划问题。该算法利用d n a 双 链结构进行问题的编码，以克服s g a 的海明悬崖问题和增加种群多样性；并采用r n a 操作算子和s q p 算法以有效保持遗传算法广度搜索和深度搜索的平衡，加快算法的收 敛速度。通过算法的收敛速度分析和典型测试函数的仿真对比研究表明了所提算法的有 效性和可靠性。对汽油调合配方优化问题的求解以及与p s o 算法的对比研究结果表明 所提算法的有效性和适用性。 ( 3 ) 基于d n a 计算，提出了一种非支配排序多目标遗传算法以解决多目标优化问 题。该算法首先将基于r n a 计算的交叉和变异算子用于多目标遗传算法，以改善g a 的全局寻优性能；其次通过p a r c t o 排序和个体密集距离计算，将相互矛盾的多目标优化 问题统一成单个目标适应度函数优化问题，以便于用外部种群保留p a r c t o 前沿集合；最 后利用种群维护算法保持p a r c t o 前沿的分布均匀性。算法的收敛性分析和典型多目标优 化问题的仿真研究表明所提算法在p a r e t o 前沿逼近度和解的分布均匀性方面都有了较 大提高。 浙江大学博士学位论文 ( 4 ) 如何合理选取r b f 网络的基函数中心点及网络结构，目前还未给出有效的理论 依据。本文基于过程输入输出数据，提取有用的系统信息，建立其r b f 神经网络动态 模型，提出了一种基于剪接系统的遗传算法进行r b f 网络的隐层节点数、基函数中心 点的优化，从而综合考虑了网络的拟合精度和泛化能力。计算复杂性分析以及连续搅拌 反应釜( c s t r ) 仿真对比结果表明采用所提算法构建的r b f 神经网络具有良好的拟合 精度和较强的泛化能力。 ( 5 ) r b f 嘲络的优化设计本质上是一个多目标优化问题。通过将r b f 网络信息融入 d n a 单链结构，引入d n a 计算操作算子，提出了一种用于神经网络的多目标优化设计 遗传算法，用于实现包括输入层在内的r b f 网络优化设计。该算法以r b f 神经网络结 构最简、拟合精度最高为优化指标，得到p a r c t o 最优解集，并根据测试数据的误差绝对 值之和最小准则，筛选p a r e t o 最优解集。将该算法应用于连续搅拌反应釜的建模中，得 到了优于r b f 网络单目标优化算法的结果。 ( 6 ) 针对控制系统设计问题，使用d n a g a 算法进行了控制系统的优化设计。其一 针对一阶滞后不稳定过程，提出了一种基于参数稳定空间的多目标遗传算法，进行p i d 控制器的优化设计。其二针对广义预测控制在p h 中和过程中的应用问题，采用基于剪 接系统的遗传算法进行t - s 模糊网络的优化设计以更好地进行p h 中和过程建模。其三 针对具有强非线性和严重不确定性的连铸过程提出了一种模糊神经元非模型控制策略。 由于模糊神经元控制器存在多个参数的优化整定问题，采用r n a - g a 进行了该控制器 参数的优化整定。仿真对比结果验证了d n a - g a 算法在控制系统优化设计中的有效性。 关键词：d n a 计算，遗传算法，工业过程建模，控制器优化设计，化工过程 注：本文的工作得到了国家创新研究群体科学基金项目( n c r g s f c ：6 0 4 2 1 0 0 2 ) 和国家自 然科学基金项目( n o 7 0 4 7 1 0 5 2 ) 的资助。 浙江大学博士学位论文 a b s t r a c t d n a c o m p u t i n gi san o v e lr e s e a r c hf i e l da n ds t i l li n 妇i n f a n c y t b e r ea r cm a n y t h e o r e t i c a la n dp r a c t i c a lp r o b l e m si nd n a c o m p u t i n gi t s e l f g e n e t i ca l g o r i t h m ( o a ) i s s i m i l a ra sd n a c o m p u t i n gi nc e r t a i na s p e c t s , w h i c hi st h es i m u l a t i o no ft h ep r o c e s so f b i o l o g i c a le v o l u t i o na tt h em o l e c u l a rl e v e l t h e r e f o r e , g ac 锄b eu t i l i z e da sab r i d g ef o rd n a c o m p u t i n g t os o l v ec o m p l e x o p t i m i z a t i o np r o b l e m s s i n c et h es o p h i s t i c a t o dk n o w l e d g ec a nb c e x p r e s s e da sd n a m o l e c u l a re n c o d i n ga n dt h ei n f o r m a t i o no a nb cd e t e c t e da n d p r o c e s s e db y s i m u l a t i n gd n ao p e r a t i o n s ，a o c e s s i n ga n du p d a t i n gt h ei n f o r m a t i o ni nt h ee v o l u t i o nn o to n l y a d e q u a t e l ye m p l o yt h ep i o n e e r i n gi d e ao f d n ac o m p u t i n g , b u ta l s oc a l ls o l v et h ec o m p l i c a t e d o p t i m i z a t i o np r o b l e m se x i s t i n gi na u t o m a t i cc o n t r o l ，p a t t e r nr e c o g n i t i o n ，d e c i s i o n ，m a c h i n e l e a r n i n g , e t c w i t ht h e s ep o i n t si nm i n d , t h i sd i s s e r t a t i o nf o c u s e so nt h ec o m b i n a t i o no f d n a a n dg at os o l v et h em o d e l i n ga n do p t i m i z a t i o np r o b l e m so fc o n t r o ls y s t e m s t h em a i n c o n t e n t s 椭鹊f o l l o w s ( 1 ) t h eg e n e t i ca l g o r i t h mb a s e do nr n ac o m p u t i n gi sp r o p o s e da c c o r d i n gt or n a o p e r a t i o n s , d n as e q u e n c es e l e c t i o na n dm u t a t i o nm o d e l 1 1 l i sm e t h o du s e sa ，t gc t o e n c o d et h ev a r i a b l e s , a n dc o m b i n e sr n a g e n e t i co p e r a t i o n sa n dd n as e q u e n c em o d e lt o d e s i g nt h ec “培s o v c ra n dm u t a t i o no p e r a t o r so fg a t h ec o n v e r g e n c ea n a l y s i si nt e r m so f m a r k o vm o d e ls h o w st h a tr n a - g aw i t he l i t i s ts t r a t e g yc a nc o n v e r g ei np r o b a b i l i t ylt ot h e g l o b a lo p t i m u m c o m p a r i s o n so fr n a - g aw i t hs g af o rt y p i c a lt e s tf u n c t i o n ss h o wt h e a d v a n t a g e sa n de f f i c i e n c yo ft h ep r o p o s e da l g o r i t h m t h ea p p l i c a t i o n so fc h e m i c a lp r o c e s s p a r a m e t e re s t i m a t i o ns h o wt h ep r a c t i c a b i i i t yo f t h ep r o p o s e da l g o r i h m ( 2 ) t h ed n ad o u b l ec i l r o m o s o m ea n ds q pb a s e dh y b r i dg e n e t i ca l g o r i t h mi sp r e s e n t e d f o rn o n l i n e a rp r o g r a m m i n gp r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t s i nt h eg l o b a le x p l o r a t i o n p h a s e ，t h ed n ad o u b l ec h r o m o s o m es t r u c t u r ei su s e dt oo v e r c o m et h e “h a m m i n gc l i f f p r o b l e ma n dk e e pt h ed i v e r s i t yo ft h ep o p u l a t i o n r n ao p e r a t o r sa r ea p p l i e dt oi m p r o v et h e g l o b a ls e a r c h i n gc a p a b i l i t ya n dt h es e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ( s q p ) m e t h o di s i m p l e m e n t e dt oq u i c k l yf i n dt h el o c a lo p i i m u ma n dr a i s et h es o l u t i o na c c u r a c y t h e c o n v e r g e b c es p e e da n a l y s i sa n ds i m u l a t i o nr e s u l t so ut y p i c a lt e s tf u n c t i o n sd e m o n s t r a t et h e r e l i a b i l 姆a n de f f i c i e n c yo ft h ep r o p o s e da l g o r i t h m t h ea p p l i c a t i o n so fg a s o l i n eb l e n d i n g r e c i p eo p t i m i z a t i o ns h o wt h ea d v a n t a g e so f t h ep r o p o s e da l g o r i t h m ( 3 ) t h ed n ac o m p u t i n gb a s e dn o n - d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h mi ss u g g e s t e df o r m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s f i r s t , t h eg e n el e v e lo p e r a t o r so fr n ac o m p u t i n ga r e m 浙江大学博士学位论文 a d o p t e d t oe n h a n c et h e g l o b a ls e a r c h i n gc a p a b i l i t y o fg a t h e n ，t h ei n c o n s i s t e n t m u l t i - o b j e c t i v ef i m e 豁f u n c t i o n sa r ec o n v e r t e di n t oas i n g l eo b j e c t i v ef u n c t i o nb yp a r e t o s o r t i n ga n di n d i v i d u a lc r o w d i n gm e a s u r i n g f i n a l l y , e x t e r n a lp o p u l a t i o ni si n t r o d u c e dt ok e e p t h ep a r e t of r o n ti n d i v i d u a l sa n dt h em a i n t e n a n c ea l g o r i t h mi sp r o p o s e dt om a i n t a i nt h e e v e l m c s so fi n d i v i d u a ld i s t r i b u t i o n t h ec o n v e r g e n c ea n a l y s i sa n ds i m u l a t i o nr e s u l t so n t y p i c a lt e s tp r o b l e m ss h o wt h ei m p r o v e m e n to ft h ep r o p o s e da l g o r i t h m ，i nt h es p r e a do f s o l u t i o n sa n dt h ec o n v e r g e n c en e a rt h et r u ep a r e t o - o p t i m a lf r o n t ( 4 ) h o wt os e l e c tt h eb a s i sf u n c t i o nc e n t e rt h en e t w o r ks t r u c t u r e ，h a sn o ty e tg i v e na n e f f e c t i v em e t h o d t h es p l i c i n gs y s t e mb a s e dg e n e t i ca l g o r i t h mi s p u tf o r w a r dt oo p t i m i z et h e r b fn e t w o r k , w h i c hi su s e dt oe x t r a c tv a l u a b l ep r o c e s si n f o r m a t i o nf r o mi n p u t o u t p u td a t a t h en o v e lr b fn e t w o r kt r a i n i n gt e c h n i q u ei n c l u d e st h en e t w o r ks t r u c t u r ei n t ot h es e to f f u n c t i o nc e n t e r sb y c o m p r o m i s i n gb e t w e e nt h ec o n f l i c t i n gr e q u i r e m e n t s o fr e d u c i n g p r e d i c t i o ne r r o ra n ds i m u l t a n e o u s l yd e c r e a s i n gm o d e lc o m p l e x i t y t h ee f f e c t i v e n e s so ft h e p r o p o s e dm e t h o di si l l u s t r a t e dt h r o u g ht h ed e v e l o p m e n to fd y n a m i cm o d e l sf o rac o n t i n u o u s s t i r r e dt a n kr e a c t o r ( c s t r ) b yc o m p a r i n gw i t hd i f f e r e n tr b fn e t w o r k t r a i n i n gm e t h o d s ( 5 ) b a s e do nt h eo p e r a t o r so fd n ac o m p u t i n g , t h em u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mi s p r o p o s e dt oo p t i m i z en e u r a ln e t w o r k s b o t ht h es t r u c t u r ec o m p l e x i t ya n dt h ea p p r o x i m a t i o n p e r f o r m a n c e so far b fn e t w o r ka 旭o p t i m i z e d o n c eag r o u po fp a r e t oo p t i m a ls o l u t i o n sa r e d e r i v e d , t h ea p p r o p r i a t er b fn e t w o r kc a nb ec h o s e ni nt e r m so f t h es u mo f a b s o i n t ev a l u eo f t h et e s t i n ge r r o r ( s a e ) s i m u l a t i o n so nac s t rs h o w 黼r i yg o o df i t t i n ga b i l i t yo ft h e p r o p o s e dm e t h o da n dt h em u l t i - o b j e c t i v eg ac a no b t a i nb e t t e rr e s u l t st h a ns i n g l eo b j e c t i v e g a ( 6 ) d n a - - g aa l g o r i t h m sa r eu s e df o rt h eo p t i m i z a t i o nd e s i g no fc o n t r o ls y s t e m s a s t a b i l i z i n gs p a c eb a s e dm u l t i - o b j e c t i v eg a i sp r o p o s e df o r t h eo p t i m i z a t i o no f p i dc o n t r o l l e r s o ft h eu n s t a b l ep l a n t so ff i r s to r d e rp l u st i m ed e l a y f o rt h ea p p l i c a t i o no fg e n e r a l i z e d p r e d i c t i v ec o n t r o l ( g p c ) t op hp r o c e s s e s ，t h es p l i c i n gb a s e dg aa l g o r i t h mi sa p p l i e dt o o p t i m i z ef u z z yn e u r a ln e t w o r k sf o rm o d e l i n go fan o n l i n e a rp hn e u t r a l i z a t i o np r o c e s s a f u z z yn e u r o nh y b r i dc o n t r o lm e t h o di sp r o p o s e df o rm o l dl e v e lc o n t r o lo f t h ec o n t i n u o u ss t e e l c a s t i n gw i t hb i gu n c e r t a i n t i e sa n dg r a v en o n l i n e a r i t i e s s i n c et h e r ee x i s tt h ep r o b l e mo f o p t i m i z e ds e l e c t i o no fs e v e r a lp a r a m c t e r si nt h em o d e l f r e ef u z z yn e u r o nh y b r i dc o n t r o l l e r , r n a - g ai su t i l i z e dt od e t e r m i n et h ec o n t r o l l e rp a r a m e t e r s s i m u l a t i o nr e s u l t sd e m o n s t r a t e t h ee f f i c i e n c yo f t h ed n a g am e t h o d s i v 浙江大学博士学位论文 k e y w o r d s ：d n ac o m p u t i n g ，g e n e t i ca l g o r i t h m ， o p t i m i z a t i o nd e s i g no f c o n t r o l l e r s , c h e m i c a lp r o c e s s e s r e m a r k ：t h ed i s s e r t a t i o nw o r ki s s u p p o r t e db yt h en a t i o n a lc r e a t i v er e s e a r c hg r o u p s s c i e n c ef o u n d a t i o no fc h i n a ( n c r g s f c ：6 0 4 2 1 0 0 2 ) 锄dt h en a t i o n a ln a t u r a ls c i e n c e f o u n d a t i o no f c h i n a ( n o 7 0 4 7 1 0 5 2 ) v 专业词汇及缩略语注释表 专业词汇及缩略语注释表 a d e n i n e ( a ) c y t o s i n e ( c ) c o n t r o l l e d a u t o - r e g r e s s i v ei n t e g r a t e dm o v i n g a v e r a g em o d e l ( c a r l m a ) c o n s t i n u o u ss t i r r e dt a n kr e a c t o r ( c s t r ) c o n t r o l l e dv a r i a b l e ( c v ) d n ad o u b l ec h r o m o s o m eb a s e dh y b d dg a ( d n a - d h g a ) d i s t a n c ee r r o r s ( d e ) e v e ns p a c i n g ( e s ) f l u i dc a t a l y t i cc r a c k i n g ( f c c ) f u z z yn e u r o nh y b r i dc o n t r o l ( f n h c ) f u z z yr e c u r r e n tn e u r a ln e t w o r k ( f r n n ) g u a n i n e ( g ) g e n e r a l i z e dh e r m i t e - b i e h l e rt h e o r e m ( h - 8 ) g e n e r a l i z e dp r e d i c t i v ec o n t r o l ( g p c ) h a m i l t o np a t hp r o b l e mm p p ) i n t e g r a t e dt i m ea b s o l u t ee r r o r ( i t a e ) m u r i - o b j e c t i v eg e n e t i ca l g o r i t h m ( m o g a ) m u l t i o b j e c t i v ee v o l u t i o na l g o r i t h m ( m o e a ) m a x i m u ms p a c i n g ( m s ) m a n i p u l a t e dv a r i a b l e ( m v ) n o tp o l y n o m i a l ( n p ) p r o b l e m n o n - d o m i n a t e d s o r t i n g g e n e t i c a l g o r i t h m ( n s g a ) p r o p o r t i o n a li n t e g r a ld e r i v a t i v e ( p l d ) 腺嘌呤 胞嘧啶 受控自回归积分滑动平均模型 连续搅拌反应釜 被控变量 d n a 双链混合遗传算法 距离偏差 均匀分布度 流化催化裂化 模糊神经元混合控制 模糊递归神经网络 鸟嘌呤 广义h b 定理 广义预测控制 哈密尔顿路径列题 时问乘误差绝对值积分 多目标遗传算法 多目标进化算法 最大分布度 操作变量 n p 问题 非支配排序遗传算法 比例积分微分 浙江大学博士学位论文 p o l y m e r a s ec h a i nr e a c t i o n ( p e r ) r a d i o sb a s i sf u n c t i o n ( r b f ) r e c u r r e n c el e a s ts q u a r e ( r l s ) s a t i s f a c t a b i l i t yp r o b l e m ( s a t ) s u mo f a b s o l u t ee r r o r ( s a e ) s i n g l e i n p u ts i n g l e - o u t p u t ( s l s o ) s t a n d a r dg e n e t i ca l g o r i t h m ( s g a ) s e q u e n c eq u a d r a t i cp r o g r a m m i n g ( s q p ) t h y m i n e ( ，d t r a v e ls a l e s m a np r o b l e m ( v s p ) u r a c i l ( u ) v e c t o re v a l u a t e dg e n e t i ca l g o r i t h m ( v e g a ) 聚合链式反应 径向基函数 递推最d , - 乘 可满足性问题 误差绝对值之和 单输入单输出 基本遗传算法 序列二次规划算法 胸腺嘧啶 旅行商问题 尿嘧啶 向量评估遗传算法 浙江大学博士学位论文 致谢 值此论文即将完成之际，谨向我的导师工业控制技术国家重点实验室、浙江大学先 进控制研究所王宁研究员表示崇高的敬意和衷心的感谢。 三年前，正是王老师热情地鼓励并接纳了我，使我有机会能够在浙大这片沃土上， 在美丽的西子湖畔和葱郁的老和山下留下了学习和成长的足迹。王老师渊博的学识、严 谨的治学态度、坚实的专业知识和踏实的工作作风使我受益非浅。无论在理论学习阶段， 还是在论文的选题、资料查询、开题、研究和撰写的每一个环节，都得到导师的悉心指 导和帮助。借此机会再次向导师表示衷心的感谢! 衷心感谢王树青教授对我的关怀和帮助，王老师开阔的思维和睿智达观的人生态度 使我受益非浅，也给了我很多关于人生的启迪。 感谢张建明副教授、金晓明副教授、张泉灵副教授、徐巍华副教授、来国妹女士以 及系里其他老师在学习和科研工作上给予我的关心和帮助。 感谢李奇安博士后、谢磊博士后、蒋丽英博士、苏成利博士、黄海博士给予的帮助 和鼓励，与张日东博士、陈良博士、黄亮博士、刘彦鹏搏士的探讨总能给我很大的启示 和帮助。感谢师弟陈庆更、谢懿、黄少锋、徐铭泽、陈俊伟，师妹潘彩霞、陈霄、赵进 慧、严家玉、俞金妹、杜亚萍，他们活跃的思维给予了我很多的帮助和启示。感谢先控 所老楼刘雪芹、曾建武、张柯、付秀云、张学鹏、冯建华、李双彬、孙磊等多年来的友 谊和关怀，还有1 0 6 室其他同学对我的诸多帮助。感谢室友许士芳三年来对我的关心和 帮助。 特别感谢我的父母，在我多年的求学生涯中，他们的含辛茹苦和对我的殷切希望始 终激励着我。养育之恩，无以回报，祝愿他们永远健康快乐! 感谢我的弟弟和弟媳以及 家中其他亲人对我的理解和支持。 感谢梁天跃先生多年来对我一如既往地支持，给我鼓励，使我能够安下心来认真地 开展研究完成我的学业。 最后，向所有支持、关心和帮助过我的老师、同学、朋友表示诚挚的感谢! 懿名利 2 0 0 7 年4 月于浙大求是园 第1 章绪论 第1 章绪论 提要：本章简要介绍了d n a 计算的生物学基础、发展历程及研究现状，从d n a 生物计算存在的问题 出发，阐述了d n a 计算与遗传算法两者结合的意义；评述了遗传算法的理论研究、编码问题、具有 约束优化以及多目标优化等方面的发展历史和研究现状；并介绍了本文的主要工作和组织结构。 1 1 引言 生物分子计算的概念是随着分子生物学的发展而提出的。研究发现生物分子在遵循 化学和物理规律发生相互作用的过程中，能够形成类似于计算机的信息传输和处理功 能、甚至形成具有逻辑运算功能的“生物分子电路”。有人甚至提出一些蛋白质的主要 功能不是构成生物体的某种结构，而是用于传输和处理信息。然而直到1 9 9 4 年，a d l e m a n 用d n a 分子操作成功解决7 顶点的h a m i l t o n 路径问题【1 】后，才真正开创了生物分子计算 - d n a 计算的新天地。 d n a 计算是一种通过分子生物d n a 的双螺旋结构和碱基互补配对规律进行信息编 码的方法和技术。无论在理论方面还是技术方面，d n a 计算对传统计算方式都是一种 挑战。随着国际项级杂志s c i e n c e 和n a t u r e 对d n a 计算的相继报道以及d n a 国际专题 会议的召开，d n a 计算已经成为一个极具开发价值的生物科学研究的前沿领域。 虽然d n a 计算从诞生至今仅有十多年的时间，d n a 计算的研究已经取得了初步的、 令人鼓舞的进展，但是随着研究的深入，d n a 计算机的研究并不像人们起初认为的那 样乐观，其中最大的障碍是如何克服d n a 计算过程中所产生的“指数爆炸”问题；d n a 计算理论本身还很不成熟，只能解决一些简单的优化问题；生物技术还没达到足够尖端 和精确的水平，难以应付工程领域中的各种复杂优化问题。 遗传算法是一种在分子水平模拟生物进化过程来求解复杂问题的有效算法，d n a 计算则利用生物分子的各种生化反应来完成计算过程，两者天生就具有某种必然的联 系，可以相互借鉴，用d n a 编码表示复杂知识或系统，模拟d n a 分子操作以发现和 处理信息，在进化中获取和更新知识，既可以充分发挥d n a 计算的开创性思想，又可 以解决自动控制、模式识别、决策问题、机器学习等工程领域中存在的各种复杂优化问 题。 从理论上讲，d n a 计算的实验应当在d n a 计算机上进行，然而d n a 计算机的研 制与d n a 计算一样还处于起始阶段，因而借助于遗传算法来研究d n a 计算是一条有 效的途径。 浙江大学博士学位论文 1 2d n a 计算的生物基础 1 2 1d n a 分子结构 d n a 是d n a 计算中起中心作用的分子，携带着生物的遗传信息。d n a 分子是一种 高分子化合物，组成它的基本单位是脱氧核苷酸。四种核苷酸或脱氧核苷酸按照一定的 排列顺序以3 ，和5 磷酸二酯键相连形成的多聚核苷酸或脱氧核苷酸，称为核苷酸序列， 也称为碱基序列。核苷酸的区别仅在于碱基，腺嘌呤( a d e n i n e ) 和鸟嘌呤( g u a n i n e ) ，记为 a 和g ；胞嘧啶( c y t o s i n e ) 和胸腺嘧啶( t h y m i n e ) ，记为c 和t 。脱氧核许酸或核苷酸的连接 具有严格的方向性，前一核苷酸的3 ，- o h 与下一核苷酸的5 磷酸间形成3 ，- 5 7 磷酸二酯 键，构成一个没有分支的线性大分子，如图1 - 1 所示。d n a 书写方向从5 到3 ，。方向 性是了解d n a 功能和操作的关键，同时也是建立d n a 计算模型的关键。r n a 是另一种 对活性细胞起重要作用的聚合物，其结构与d n a 的结构非常接近。在r n a 中嘧啶为胞嘧 啶和尿嘧啶，u 代替了d n a 的t 。 图1 - 1d n a 生物结构 图l - 2d n a 双螺旋结构 一个核苷酸的羟基可与另一个核苷酸的羟基相互作用可形成一种较弱的氢键，键的 形成遵从如下配对原则：a 和t 配对，c 和g 配对。这种配对原则称为w a t s o n - c r i c k 互补性 原则。从图1 - 1 可以看出，d n a 通过磷酸二酯键，可组成d n a 单链，利用互补性原则， 单链很容易形成双链分子。两条极长的核苷酸利用碱基之间的氢键结合在一起，形成一 条双股的螺旋结构，如图l - 2 所示。事实上，将d n a 双链分子表示为以w a t s o n - c r i c k 互 补性原则结合在一起的两条线性链已经是对现实情况的一大简化了。 1 2 2d n a 计算生物操作 d n a 计算是通过结合各种生物操作来实现的。对d n a 分子的操作，既有物理的也 有化学的。物理操作实质上是调控生化反应的外部条件，例如温度、酸碱度等等。而各 种生化操作主要是通过各种酶的操作。下面介绍一些d n a 计算中的重要操作【。 2 第1 章绪论 ( 1 ) d n a 变性和复性 如前所述，在d n a 分子结构中，两个互补碱基之间的氢键比同一链内的磷酸二酯 键要弱得多，这使得在不破坏d n a 单链的情况下分离d n a 双链成为可能。d n a 变性 就是指d n a 分子中维持双螺旋稳定性的氢键和疏水键的断裂，使稳定的双螺旋结构松 解为无规则线性结构的现象。凡能破坏双螺旋稳定性的因素都可以成为变性的条件，如 加热、极端的p h 值等d n a 复性是指变性的d n a 链在适当条件下，二条互补链全部 或部分恢复到天然双螺旋结构的现象，它是变性的一种逆转过程。热变性d n a 一般经 缓慢冷却后即可复性，此过程称之为“退火” ( 2 ) d n a 杂交 分子杂交是d n a 计算研究中一项最基本的实验技术。其基本原理就是利用d n a 分子的变性和复性的性质，使来源不同的d n a 片段，按碱基互补关系形成杂交双链分 子( h c t e r o d u p l e x ) 。杂交双链可以在d n a 链与d n a 链之间，r n a 链与d n a 链之间，也 可在p n a 链与d n a 链之间进行，杂交的本质就是在一定条件下使互补核酸链实现复性。 ( 3 ) d n a 探针 在进行d n a 计算时，需要对操作后的d n a 链进行检测，这就需要进行有目的的 杂交反应，即杂交的目的是识别靶d n a 中的特异核苷酸序列。完成这个任务需要牵涉 到一项核酸操作的基本技术探针( p r o b e ) 的制备。探针实际上是某些特异性核酸序列 的片段，可以与靶序列互补形成杂交双链，通过适当方法可对这种杂交双链进行检测。 ( 4 ) d n a 扩增 d n a 计算是在海量的存储数据中通过穷尽搜索得到正确解来完成的，但是这个结 果有时仅仅是极少量的，对于检测和读出而言是极为困难的。通常，用一种称之为聚合 酶链式反应( p o l y m c r a s cc h a i nr e a c t i o n ，简称p c r ) 的技术解决这个问题。p c r 具有令人 难以置信的灵敏度与有效性：既使开始时只有该分子的一条链，p c r 也能在很短的时间 周期内产生出数百万个所要求的d n a 分子的拷贝。 ( 5 ) 凝胶电泳 在d n a 计算中，为了分离不同长度的d n a 链，可以采用凝胶电泳方法( g e l e l e e t - r o p h o r e s i s ) 。d n a 分子长度用构成该分子的核苷酸的数量来表示。如果一个分子由 1 2 个核苷酸组成，则这个分子的长度为1 2 单位，记为1 2 m e t ，若用碱基对的方式表示， 则写成1 2 b p 。电泳技术基于d n a 分子带有负电荷这个事实。d n a 分子会通过凝胶向 正电极方向移动，小分子在通过凝胶时比大分子容易，移动快，同样地，尺度大小相同 的分子移动时具有相同的速度。显而易见，在给定时间范围内，不同长度的d n a 分子 将移动不同的距离，从而达到分离的目的 3 浙江大学博士学位论文 ( 6 ) 生物酶操作 酶( e n z y m e ) 是在性细胞中催化化学反应的蛋白质。它们非常专一，大多数只催化 唯一的一种化学反应，并且效率极高。目前，从自然界已经提取出多种多样的、在处理 d n a 计算过程中非常有用的酶。主要可用于以下d n a 计算操作： d n a 延长：利用d n a 聚合酶将核苷酸加载到一个已存在的d n a 分子上。延长操 作通过引物根据w a t s o n - c r i c k 互补性原则与模板的一部分发生键连，沿3 ，端有效地伸展， 聚合酶只能沿5 - 3 ，方向伸展。 d n a 削减：d n a 核酸酶是降解d n a 的酶。它们被分成d n a 外切核酸酶( e x o n u c l e a s e ) 和d n a 内切核酸酶( e n d o n u c l e a d e ) ，通常用于削减一条已知的d n a 链。外切核酸酶的 功能在d n a 复制过程中作为纠错功能是非常重要的。并且相关的外切核酸酶可以沿 5 3 ，和3 ，5 两个方向同时进行。 d n a 连接：d n a 分子可以通过一种称为连接反应( 1 i g a t i o n ) 的处理连接在一起。在 d n a 计算过程中，