（应用数学专业论文）rna伪扭结结构的序列设计.pdf

摘要 背景：本文研究对象是生命系统中具有关键作用的一类生物大分子一核糖 核酸( r n a ) 分子r n a 的分子结构呈现出多样的变化性其中最基本的一级结 构是四种碱基( a ，c ，g 和u ) 在其分子基链上的排列顺序，称为r n a 序列二 级结构是i n a 序列上不同的碱基在w a t s o n - c r i c k 和g u 规则下形成的不相 交碱基对形式在此基础上，螺旋区域和非螺旋区域相互作用，构成伪扭结结构 ( p s e u d o k n o ts t r u c t u r e s ) 通过伪扭结结构，可以进一步得到r n a 分子的真实三 维结构同时，伪扭结结构对眺分子的所有生物功能都起到决定性作用在研 究自然界的r n a 结构，寻找新核酸和设计人工r n a 分子时，我们都希望能找到 一条r n a 序列，使其折叠( f o l d ) 成某个指定的伪扭结结构，并进而分析这条序 列和指定结构所导出的中立网络( n e u t r a ln e t w o r k ) 这种通过给定r n a 结构， 得到期望的r n a 序列的过程，称为r n a 序列设计( i n v e r s ef o l d ) 目前已有的 三种r n a 序列设计算法，r n a i n v e r s e ，r n a s s d 和i n f o r n a ，都只能处理二 级结构在这篇文章中，我们给出一个新的r n a 序列设计算法一i n v ，新算法能 够有效地处理所有3 - n o n c r o s s i n g 的正规伪扭结结构 结果：本文详细说明了新算法i n v 的设计和实现思路，并给出两类应用例子 文章还列出算法的核心伪代码，并附上详细的分析算法的a n s ic9 9 实现可以 从h t t p ：w w w c o m b i n a t o r i c s c n c b p c i n v h t m l 自由获取文章通过 非平面r n a 结构验证了i n v 能够对3 - n o n c r o s s i n g 伪扭结结构进行序列设计 另外，通过使用i n v ，我们估算了中立网络的距离 结论：算法i n v 扩展了针对伪扭结结构的r n a 序列设计的能力与 r n a i n v e r s e 相比，i n v 引入了一些新的想法，例如考虑了竞争结构集合的 概念这些新想法不但能处理伪扭结结构，而且对于二级结构，同样能给出全新的 序列 文章结构：第一章简要介绍了r n a 的表示方法，生物作用，r n a 结构预测 和序列设计方向的一些基本概念简要分析比较了现有算法的优缺点和异同点， 进而介绍了被广泛使用的r n a 热力学模型第二章给出了算法i n v 的两个应 用，针对非平面结构设计r n a 序列和估算中立网络的距离在第三章中，我们详 a b s t r a c t ( i nc h i n e s e ) 细说明了算法i n v 的设计思想和实现方法算法的性能分析比较和进一步的工 作方向在第四章中讨论由于i n v 中需要多次调用r n a 折叠算法，在第五章中， 我们讨论了折叠算法中使用的一些基本概念，并给出了折叠算法的总体思路 关键字：r n a ，伪扭结，结构预测，序列设计，遗传算法，动态规划，非平面结构，中 立网络 a b s t r a c t a b s t r a c t b a c k g r o u n d ：r n ae x h i b i t sav a r i e t yo fs t r u c t u r a lc o n f i g u r a t i o n s as t r u c t u 】伦 c o n s i s t so ft h en o n c r o s s i n gw a t s o n - c r i c ka n dg - u - b a s ep a i r i n g s ( s e c o n d a r y s t r u c t u r e ) a n da d d i t i o n a lb a s ep a i ri n t e r a c t i o n so fh e l i c a la n dn o n - h e l i c a lr e - g i o n s o n ep a r t i c u l a rt y p ea r ep s e u d o k n o t s ，i n t e r a c t i o n sb e t w e e nh e l i c a la n d n o n - h e l i c a lr e g i o n s ，o b s e r v e da c r o s st h ew h o l es p e c t r u mo fr n af u n c t i o n a l i t i e s i nt h ec o n t e x to fs t u d y i n gn a t u r a lr n as t r u c t u r e s ，s e a r c h i n gf o rn e w r i b o z y m e sa n dd e s i g n i n g a r t i f i c i a lr n a ，i ti so fi n t e r e s tt of i n dr n a s e q u e n c e s f o l d i n gi n t oas p e c i f i cs 咖c t u r ea n d t oa n a l y z et h e i ri n d u c e dn e u t r a ln e t w o r k s s i n c et h ee s t a b l i s h e di n v e r s ef o l d i n ga l g o r i t h m s ，r n a i n v e r s e lr n a s s da s w e l la si n f 0 一r n aa r el i m i t e dt or n as e c o n d a r ys t m c t l 】r e s ，w ep r e s e n ti nt h i s p a p e rt h ei n v e r s ef o l d i n ga l g o r i t h min v w h i c hc a nd e a lw i t ha l l3 - n o n c r o s s i n g ， c a n o n i c a lp s e u d o k n o ts t m c t l 】r e s r e s u l t s ：i n 幽i sp a p e rw ep r e s e n tt h ei n v e r s ef o l d i n ga l g o r i t h min va sw e l l a si t st w oa p p l i c a t i o n s w eg i v ead e t a i l e da n a l y s i so fi n v ，i n c l u d i n gp s e u d o c o d e s t h ea n s ic9 9c o d e sf o ro u ra l g o r i t h m i sf r e e l ya v a i l a b l ea th t t p ： w w w c o m b i n a t o r i c s c n c b p c i n v h t m l w es h o w , u s i n g3 - n o n c r o s s i n g n o n p l a n a rr n ap s e u d o k n o ts t m c t u r e sa sa ne x a m p l e ，t h a ti n va l l o w st od e - s i g ns p e c i f i c3 - n o n c r o s s i n gr n a s t r u c t u r e s f u r t h e r m o r ew eu s ei n vf o re s t i 。 m a t i n gt h ed i s t a n c eo ft h en e u t r a ln e t w o r k s c o n c l u s i o n s ：t h ea l g o r i t h mi n ve x t e n d si n v e r s ef o l d i n gc a p a b i l i t i e st or n a p s e u d o k n o ts t r u c t u r e s i nc o m p a r i s o n w i t hr n a i n v e r s ei tu s e sn e wi d e a s ，f o r i n s t a n c eb y t a k i n gs e t so fc o m p e t i n g s t r u c t u r e si n t oc o n s i d e r a t i o n a sar e s u l t , i n vi sa b l et of i n dn o v e ls e q u e n c e se v e nf o rr n as e c o n d a r ys t m c t l 】r e s k e yw o r d s ：r n a , p s e u d o k n o t 。f o l d ，i n v e r s ef o l d fh e u r i s t i ca l g o r i t h m , d y n a - m i cp r o g r a m m i n g ，n o n p l a n a rs t r u c t u r e ，n e u t r a ln e t w o r k a m s s u b j e c tc l a s s i f i c a t i o n ( 2 0 0 0 ) ：0 5 8 3 0 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 南圳 ，刎年6 月e l 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： ：一一一一一” ：! l 内部5 年( 最长5 年，可少于5 年)j 彩 ! 秘密- k ：o 年( 最长1 0 年，可少于1 0 年)曩 l 机密2 0 年( 最长2 0 年，可少于2 0 年) j 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 c h a p t e r1 b a c k g r o u n d l e tu sb e g i nw i t hp r o v i d i n gs o m eb a c k g r o u n do nr n a s e q u e n c e sa n d s 饥c t u r e s f i r s tw eh a v et h ep r i m a r ys t r u c t u r e ，c o n s i s t i n go ft h es e q u e n c e ( s l ，s 2 ，s n ) o f 0c ，ga n dun u c l e o t i d e s s e c o n d ，t h es e c o n d a r ys t r u c t u r e ， s ，i sas e to fp a i r s ( i l ，j 1 ) ，( i r ，j ，) w h e r e1 i t j t 佗，1 t rs u c ht h a tt h e r ee x i s t sn ok - c r o s s i n g ，i e as e to f a r c s ( i l ，j 1 ) ，( i k ，j k ) ，w h e r e i x i k j l i ，l e td = p ( p ，i ) w er a n d o “yc h o o s eac o m p a t i b l e b a s ep a i r ( s ：，彩) d i f f e r e n tf r o m ( 瓯，勺) ，s u c ht h a tf o re a c hg de i t h e r p ( g ，i ) = 0o rs ：i sn o tc o m p a t i b l ew i t h8 1 ，w h e r el = p ( g ，i ) 0i st h e e n d - p o i n tp a i r e dw i t h8 ii ng ( f i g u r e3 4 ：( 5 ，9 ) t h ep a i rg cr e t a i n st h e c o m p a t i b i l i t yt o ( 5 ，9 ) ，b u ti si n c o m p a t i b l et o ( 5 ，1 0 ) ) 3 e n d p o i n t ：i f0 p ( p ，i ) i ，w ed on o t h i n gs i n c e & h a sb e e nc h a n g e d w h e nd e a l i n gw i t ht h es t a r t - p o i n to ft h a ta r c a f t e rm u t a t i o nw ea r r i v ea tan e ws e q u e n c es 7 i ft h ed i s t a n c eo fi t ss t r u c t a r et ot h et a r g e ti sl e s st h a no re q u a lt o 如曲+ 5 ，w er e t u r nt op h a s ei o t h e r w i s e ， w es t o r et h es e q u e n c es 7a n dr e p e a tp h a s el l i ( f o ra tm o s t5t i m e s ) ，a n dr e t a i n t h es e q u e n c es 7w h o s es t m c t u r eh a sm i n i m a ld i s t a n c et ot h et a r g e t 1 3 c h a p t e r3t h ea l g o r i t h m a l g o r i t h m 2a d j u s t - s e q i n p u t ：t h eo r i g i n a ls t a r ts e q u e n c es t a r t i n p u t ：t h et a r g e ts t r u c t l l t 臼 o u t p u t ：ab e t t e rs t e x l ts e q u e n c es t a r t 1 ：佗卜l e n g t ho f 口 2 ：d 袖卜+ 。o ，s e q m i n 卜s t a r t 3 ：f o rl o o p = 1t o 狮d o 4 ：p h a s ei ：g e n e r a t et h es e tc ov i ac r o ss 5 ： g 卜c r o s s ( s t a r t ，n )轷c o = n 6 ：d 卜s t r u d i s t a n c e ( 铝，p ) 7 ：i fd = 0t h e n 8 ：r e t u ms t a r t 9 ：e l s ei fd 如曲t h e n 1 0 ：正心_ d ， s e q m m 卜s t a r t 1 1 ：e n d i f 1 2 ： 1 3 ：p h a s ei i ：g e n e r a t et h ec o m p e t i t o rs e tc 1 4 ： c 1 卜西 1 5 ：f o ra l lq gd o 1 6 ： f o r a l l a i 田o f 瞵d o 1 7 ： c 1 一au 矿( 锑，) 1 8 ：e n d f o r 1 9 ：e n d f o r 2 0 ： c 卜 讲g ：钟i sv a l i d 2 1 ： 2 2 ：p h a s eh i ：m u t a t i o n 2 3 ： s e q 卜s t a r t 2 4 ：f o r i = 1 t o 他d o 2 5 ：i f3 c k cs t p ( g ，i ) p ( z ，i ) t h e n 2 6 ： s e q i 】卜r a n d o mb a s eo rp a i r , s t v q c ，s e q c 【冈a n ds e q 簪c c ；】 2 7 ：e n d i f 2 8 ： e n d f o r 2 9 ：t 卜c r o s s ( s e q ) 3 0 ：i fs t r u d i s t a n c e ( t , 卢) 0 ， a n dp ( 展，u + m ) p ( t ，钆+ m ) w h e r em = 4 - 1 w ep u ta l lt h e s ef o u rt y p e so fp o s i t i o n si n t oas e tu f o rt h eg i v e ns e q u e n c e8 w ec o n s i d e rt h es e t s ( u ) = s 7ic z ( s ，8 7 ) = 1a n d ( il8 t s ：) cu ) ， 1 7 c h a p t e r 3t h ea l g o r i t h m a l g o r i t h m3l o c a l s e a r c h i n p u t ：t h es t a r ts e q u e n c es t a r t i n p u t ：t h et a r g e ts t r u c t l l r ep o u t p u t ：t h er e s u l ts e q u e n c es e q r e q u i r e ：s t a r t i sc o m p a t i b l et o 口 e n s u r e ：c r o s s ( s e q ) = 卢 1 ：p h a s ei ：i d e n t i f yp o s i t i o n s 2 ：t 卜c r o s s ( s t a r t ) 3 ：i ft = 口t h e n r e t u r ns t a r t e n d i f d m 饥= s t r u d i s t a n c e ( f l ，t ) i n i t i a l i z e 盔n 血 g e t u b y c o m p a r i n g t a n d 8 s e l e c tar a n d o mo r d e r i n go ft h ee l e m e n t so fu p h a s ei i ：t e s ta n du p d a t e s ( v ) 卜 s 1c p ( s ，s ) = 1a n d is i s ：) cu ) e 卜击 f o ra l ls 7 s ( u ) d o t 卜c r o s s ( s 7 ) d 卜s t r u d i s t a n c e ( t ，p ) i fd d m 伽t h e n d m j i i 卜d ， s t a r t 卜s g o t op h a s e i e l s ei fd m t d d m t t l + 5t h e n g o t op h a s e1w i t ht h ep r o b a b i l i t yp = 0 1 e n d i f i fd = d m 伽t h e n e 卜eu s 7 】i e n di f e n d f o r s t a r t 卜e o e ，w h e r ee o h a s t h e l o w e s t m f e i n e i fp h a s eir u nl e s st h a n1 0nt i m e st h e n g o t op h a s e i e n d i f r e t u r ns t a r t垂受丘死&殳抢n仫掀：莹擐掀协揪掀舭n怂窖j挫强撒獗搬挫；i弘娩 c h a p t e r 3t h ea l g o r i t h m t ： f i g u r e3 8 t h es e tuc o n s i s t i n go fi n c o r r e c t ( r e d ) a n da d j a c e n t ( g r e e n ) p o s i t i o n s ，d e r i v e d f r o m t a n d8 w h e r ed ( 8 ，s 7 ) d e n o t e st h ec o m p a t i b l ed i s t a n c ew i t h r e s p e c tt op ，s e es e c t i o n 5 1 f i g u r e3 8s h o w sh o w t oo b t a i nt h es e tu p o s i t i o n s1 2 , 2 0a n d2 4a r et h e u n p a i r e d ，w h i l e7 ，1 3 ，1 9a n d2 5a r ep a i r e di nt h et a r g e ts t r u c t u r e8 p h a s ei i t e s ta n du p d a t e w es e l e c tr a n d o m l ya s e q u e n c es 7 s ( u 1a n df o l d r = c r o s s ( s ，) i