（应用数学专业论文）一类rna序列到rna二级结构映射的组合映射模型研究.pdf

j l l i i ii i ii i ii i i ii iii iiil ；y 17 9 8 18 4 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：列皇哎 2 。孑年歹月琴日 南开大学硕士学位论文 一类r n a 序列到r n a 二级结构映射的组合 映射模型研究 作者： 年级： 专业： 研究方向： 导师： 完成时间： 刘呈波 二零零五级 应用数学 计算生物学 c h r i s t i a nr e i d y s 教授 二零零八年五月 南开大学组合数学中心 二零零八年五月 m a s t e rd i s s er ：】m t l 0 n t h es t u d yo nac o m b i n a t o r i a lm a p d e d u c e df r o mr n a s e q u e n c e st or n a s e c o n d a r ys t r u c t u r e sm a p m a s t e rc a n d i d a t e ：c h e n g b ol i u s p e c i a l i t y ： a p p l i e dm a t h e m a t i c s r e s e a r c hf i e l d ： c o m p u t a t i o n a lb i o l o g y s u p e r v i s o r ：p r o f c h r i s t i a nr e i d y s c e n t e rf o rc o m b i n a t o r i c s ， n a n k a iu n i v e r s i t y , t i a n j i n3 0 0 0 7 1 ，p r c h i n a m a y , 2 0 0 8 摘要 摘要 r n a 分子是计算生物学中研究的一种重要聚合物。r n a 分子的一个重要功能 是把遗传信息从d n a 传送到蛋白质，而r n a 的功能和性质与r n a 的结构有密切 的关系。由于在试验室直接观察r n a 结构非常困难，数学家和理论生物学家通过 分析r n a 序列来预测鼬妊结构的方法有很大应用价值。于是，r n a 序列和对蛆二 级结构之间的关系成为一个研究热点，这方面的重要成果有r n a 序列到对叮a 二级 结构的映射的一般性质。本文在第二章对r n a 序列到时临二级结构的映射的主 要性质进行了总结，并介绍了关于r n a 序列和对蛆二级结构的一些背景知识和研 究成果。为了研究哪些因素决定了砌蛆序列到对蛆二级结构映射的主要性质，本 文第三章通过改进c m r e i d y s ，e ta 1 在杂志j t h e o r b i 0 1 ( 2 0 0 7 ) 上发表的文章 中的一些结论和证明方法构造了一个组合映射。通过设定一些合理的抽象的前提 条件，使组合映射保持了鼢队序列到对队二级结构的映射的主要性质，从而解释 了对妊序列到肘姨二级结构映射的主要性质的决定因素。在本文第四章，我设计 了算法以模拟本文第三章中的组合映射。其中一个算法用来计算任一结构的原象 的个数，另一个算法用来计算任意两个结构的原象的最短距离。由计算机得到的 数据也证明组合映射具有r n a 序列到鼢队二级结构的映射的主要性质，这与第三 章的理论是一致的。 关键词砌姨二级结构，组合映射，序列空间，结构空间，神经网络。 一一一 a b s t r a c t a b s t r a c t r n am o l e c u l ei sa l li m p o r t a n tb i o p o l y m e ri nc o m p u t a t i o n a lb i o l o g y t r a n s m i t - t i n gg e n e t i ci n f o r m a t i o nf r o md n a t op r o t e i n si so n eo fi m p o r t a n tf u n c t i o n so fr n a m o l e c u l e t h ef u n c t i o n sa n dp r o p e r t i e so fr n ah a v eac l o s er e l a t i o nw i t ht h es t r u c t u r e o fr n a b e c a u s ei ti sd i f f i c u l tt og a i nt h er n as t r u c t u r e sw i t ht h ed i r e c tm e t h o di n t h el a b o r a t o r y , m a t h e m a t i c i a n sa n dt h e o r e t i c a lb i o l o g i s t sp r e d i c tt h es t r u c t u r e so fr n a t h r o u g ht h ef o l d i n gm a pf r o mr n as e q u e n c e sa n d t h i sm e t h o dh a sg r e a tv a l u ei na p p l i - c a t i o n s m a t h e m a t i c i a n sc o n c l u d eg e n e r i cp r o p e r t i e so fm a pf r o mr n as e q u e n c e st o r n a s e c o n d a r ys t r u c t u r e si ns t u d y i n gt h er n as e q u e n c e - s t r u c t u r er e l a t i o n i nc h a p - t e r2 ，t h et h e s i sr e v i e w st h eg e n e r i cp r o p e r t i e so fm a pf r o mr n a s e q u e n c e st or n a s e c o n d a r ys t r u c t u r e sa n d i n t r o d u c e ss o m eb a c k g r o u n dk n o w l e d g ew h i c hc o n t a i nr n a s e q u e n c ea n dr n as e c o n d a r ys t r u c t u r e i no r d e rt os t u d yt h ep r i n c i p l ew h i c hd e t e r - m i n e st h ek e yp r o p e r t i e so fm a pf r o mr n a s e q u e n c e st or n as e c o n d a r ys t r u c t u r e s ， i nc h a p t e r3 ，w ec o n s t r u c tac o m b i n a t o r i a lm a pb yi m p r o v i n gs o m er e s u l t sa n dp r o o f m e t h o d so ft h e o r e m si nt h ep a p e r ( c m r e i d y s ，e ta 1 ，n e u t r a ln e t w o r k so fs e q u e n c e t os h a p em a p s j t h e o r b i 0 1 ( 2 0 0 7 ) ) w em a k et h ec o m b i n a t o r i a lm a pk e e pt h e k e yp r o p e r t i e so fm a pf r o mr n as e q u e n c e st or n as e c o n d a r ys t r u c t u r e sb ys u p p o s i n g s o m ea p p r o p r i a t ea n da b s t r a c tp r e r e q u i s i t e s s ow ee l u c i d a t et h ed e t e r m i n a n to fk e y p r o p e r t i e so fm a pf r o mr n as e q u e n c e st or n as e c o n d a r y s t r u c t u r e s i nc h a p t e r4 ，i d e s i g na l g o r i t h m st os i m u l a t et h ec o m b i n a t o r i a lm a po fc h a p t e r3 o n ea l g o r i t h mi s u s e dt oc a l c u l a t et h en u m b e ro fp r e i m a g e so fa na r b i t r a r ys t r u c t u r e ，t h eo t h e ri su s e d t oc a l c u l a t et h em i n i m a ld i s t a n c eb e t w e e nn e u t r a ln e t w o r k so fa n yt w os t r u c t u r e s b y a n a l y z i n gt h ed a t af r o mt h ea l g o r i t h m s ，ic o n c l u d et h a tt h ec o m b i n a t o r i a lm a pk e e p s t h ek e yp r o p e r t i e so fm a pf r o mr n a s e q u e n c e s t or n a s e c o n d a r ys t r u c t u r e s ，w h i c hi s c o n s i s t e n tt ot h et h e o r yo fc h a p t e r3 k e yw o r d sr n as e c o n d a r ys t r u c t u r e ，c o m b i n a t o r i a lm a p ，s e q u e n c es p a c e ，s h a p e s p a c e ，n e u t r a ln e t w o r k n 摘要 a b s t r a c t 1i n t r o d u c t i o n c o n t e n t s i u 1 2b a c k g 咖n d 5 2 1t h e 缸吼s f e r - 姗m xi n e t l l o d 5 2 2 b a s i cc o n c e p t so fg r a p ht h e o r y 7 2 3r n a 七a c k g r o u n d 8 3t h e o r yo fa c o m b i n a t o r i a lm a p 2 3 3 1c o n s t m c t i o n o f a c o m b i n a t o r i a l m a p 2 3 3 2 t h ep r o p e r t i e so fs h a p e s 2 5 3 3n e u 砌n e t w o r k so f t h ec o m b i n a t o r i a lm a p j j 4c o m p 咖rs i m u l a t i o no ft h ec o m b i n a t o r i a lm a p 3 9 4 1m f r e q u e n c y d i s t r i b u t i o no f s t r u c t u r e s 3 9 4 2m i i l i m a ld i s t a n c e b e t w e e nn e u r a ln e t w o r k s 4 1 4 3c 伽【c l u s i o n sa n do u t l o o k 4 4 a c k n o w l e d g e b i b f i o g r a p h y r e s u m e n l 4 6 4 7 5 0 c h a p t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n r n am o l e c u l ei sa i li m p o r t a n tb i o p o l y m e ti nc o m p u t a t i o n a lb i o l o g y u n d e r s t a n d i n gt h ep r o p e r t i e sa n df u n c t i o n so fb i o p o l y m e ti sa c o r ei s s u eo fb i o p h y s i c s b i o p o l y m e ts t r u c t u r e sa r ec o n s i d e r e dt ob eu s e f u li n t e r m e d i a t e si nt h ep r e d i c t i o no fb i o m o l e c - u l a rf u n c t i o n s s om a n yp r e d i c t i o nm e t h o d so fr n as t r u c t u r e sa r ed i s c o v e r e d t h e m e t h o d sc o n t a i nc o m p a r a t i v es e q u e n c ea n a l y s i s ( p h y l o g e n e t i cm e t h o d s ) ，d y n a m i cp r o - g r a m m i n gm e t h o d s ( f r e ee n e r g ym i n i m i z a t i o na l g o r i t h m s ) ( z u k e r1 9 8 1 ) ，m o n t ec a r l o s a m p l i n ga l g o r i t h m sa n ds oo n a l lt h em e t h o d sa r ec o n v e n t i o n a l c o n v e n t i o n a lb i o - p h y s i c si sc o n c e r n e dw i t hs t r u c t u r ep r e d i c t i o n so fb i o p o l y m e t st h a tr e l a t e sas t r u c t u r e t oa g i v e ns e q u e n c e i na na b s t r a c ts e n s et h i sm e a n st h a to n e i si n t e r e s t e di na ( 1 0 c a l ) p o i n tt op o i n ta s s i g n m e n to fs e q u e n c es p a c ea n ds h a p es p a c e i ng e n e r a ls u c ham a p s h a un o tb eo n e t o o n e ；m a n ys e q u e n c e sm a yb em a p p e do n t ot h es a m es t r u c t u r e t h e r e l a t i o nb e t w e e nr n as e q u e n c e sa n ds e c o n d a r ys t r u c t u r e si sc o n s i d e r e da sa ( n o ni n v e t t i b l e ) m a pf r o ms e q u e n c es p a c et os h a p es p a c e t h ec o n c e p to fs e q u e n c es p a c et o s h a p es p a c em a pa l l o w st os t u d yg l o b a lp r o p e r t i e so fs e q u e n c e s t r u c t u r er e l a t i o n st h a t a r ei n a c c e s s i b l eo t h e r w i s e ( a ni l l u s t r a t i v ee x a m p l ei st h ei d e ao fs h a p e s p a c ec o v e r - i n gd e s c r i b e di n 【3 6 】) a nu n d e r s t a n d i n go fs e q u e n c e - s t r u c t u r er e l a t i o n si so fc e n t r a l i m p o r t a n c ei nb i o p h y s i c so fb i o p o l y m e r s f o ro n ep a r t i c u l a rc l a s so fb i o p o l y m e r s ，r n as e c o n d a r ys t r u c t u r e s ，m o l e c u l a r f 6 l d i n gm a p sh a v eb e e ns y s t e m a t i c a l l ya n a l y z e db ys c h u s t e r 【7 ，3 3 ，2 9 f o l d i n gm a p s p l a yac e n t r a lr o l ei nu n d e r s t a n d i n gt h ee v o l u t i o no fm o l e c u l a rs e q u e n c e s s p e c i f i c p r o p e r t i e sl i k e ，f o ri n s t a n c es h a p es p a c ec o v e r i n g 3 6 】a n dn e u t r a ln e t w o r k s 2 6 】a r e c r i t i c a lf o rw h a tm a yb ep a r a p h r a s e da s “m o l e c u l a rc o m p u t a t i o nb yw h i t en o i s e ”i n a d d i t i o nd e t a i l e da n a l y s i so fn e u t r a ln e t w o r k sa sw e l la se x h a u s t i v ee n u m e r a t i o no f g ，ga ，u - s e q u e n c e sc a nb ef o u n di n 【8 】t h ef i n d i n g sw e r ei n t r i g u i n g f o l d i n gm a p s i n t or n a s e c o n d a r ys t r u c t u r e se x h i b i tac o l l e c t i o no fd i s t i n c tp r o p e r t i e sw h i c hm a k e s t h e mi d e a l l ys u i t e df o re v o l u t i o n a r yo p t i m i z a t i o n ( 1 ) m a n ys t r u c t u r e sh a v ep r e i m a g e s o fs e q u e n c e s ( n e u t r a ln e t w o r k s ) w h i c hh a v el a r g ec o m p o n e n t sa n dl a r g ed i a m e t e r ( 2 ) 一 m a n ys 旺u c t i l i e sh a v et h ep r o p e r t yt h a ta n yt w oo ft h e mh a v en e u t r a ln e t w o r k st h a t c o m ec l o s ei ns e q u e n c es p a c e ( 2 ) s h o w st h a t ( m a n y ) n e ws t r u c t u r e sc a ne a s i l yb ef o u n d d u r i n ga r a n d o mw a l ko n an e u t r a ln e t w o r ku s i n go n l ys t e p si nw h i c has i n g l en u c l e o t i d e i sa l t e r e d ( p o i n tm u t a t i o n s ) t h e s ef o l d i n gm a p s ，h o w e v e r , a r en o to b t a i n e da n a l y t i c a l l y t h e y a l ear e s u l to fac o m p u t e r a l g o r i t h m , b a s e do nt h ec o m b i n a t o r i a la n a l y s i so f r n a s e c o n d a r ys t r u c t u r e sp i o n e e r e db yw a t e r m a n e ta 1 4 1 ，4 2 ，4 0 i no r d e rt os t e pb e y o n d t h es e c o n d a r ys 缸u c 眦p a r a d i g mt w om a i na p p r o a c h e sw i t hd i s t i n c tg o a l sa r e ( i ) t o s t u d ym o r ea d v a n c e dn u c l e o t i d ei n t e r a c t i o n si nr n a ，f o ri n s t a n c ep s e u d o k n o t so r ( i i ) a l t e r n a t i v e l yc o n s i d e ra b s t r a c t i o n so fr n as e c o n d a r ys 仃i l c t u r e s t h ec o m b i n a t o r i c s o fr n as t r u c t u r e sw i lp s e u d o k n o t sw e r ea n a l y z e di n 1l ，1 5 ，4 6 a n d ( i i ) p r o v i d e s i n s i g h t so nt h ec o r eq u e s t i o no fw h i c hp r i n c i p l e sp r o d u c es e q u e n c et os 仇l c t i l r em a p s s u i t a b l ef o re v o l u t i o n w h a tc a nw ee x p e c tf r o ma na b s t r a c t i o no fr n a s e c o n d a r ys t r u c t u r e s ? t h ew o r k i n 【9 ，1 0 】w a sm o t i v a t e df r o mar a n d o mg r a p hm o d e lo ft h ep r e i m a g e so fr n a s e c o n 出a r ys 缸u c t u r e s 【2 6 】a n ds h i f t e dt h ef o c u sf r o mn e u t r a lp a t h s 【8 】t on e u t r a ln e t w o r k s 【9 】t h el o c a la n a l y s i so fc o n n e c t i v i t yo fn e u t r a ln e t w o r k si n 8 】i sb a s e do nt h ep r o o f i d e ao far a n d o mg r a p ht h e o r e mi n 2 6 t h ew o r ko fs c h u l t e sa n db a r t e l si sf u r t h e r e v i d e n c eo f c o n c e p t u a li m p a c t ：t h ei n t e r s e c t i o nt h e o r e mi n 【2 6 】p r e d i c t e dt h ee x i s t e n c e o fs e q u e n c e sb e i n ga b l et or e a l i z eb o t hr i b o s o m e s t h ec o n c e p to fp h e n o t y p i ce r r o r t h r e s h o l d s 【2 1 】i sar e s u l to ft h er e a l i z a t i o nt h a tt h ep a r t i c u l a ro r g a n i z a t i o no fn e u t r a l n e t w o r k si sc l o s e l yc o n n e c t e dt oe v o l u t i o n a r yd y n a m i c s i ti sp o s s i b l et h a ts e q u e n c et o s h a p em a p sa r eo fc e n t r a li m p o r t a n c ef o rf u n d a m e n t a lc o n c e p t si nt h e o r e t i c a lb i o l o g y f a rb e y o n dt h ea b o v em e n t i o n e dp a r a d i g m s t h i st h e s i si st h er e s u l to ft r y i n gt ou n d e r s t a n du n d e rw h i c hc o n d i t i o n ss e q u e n c e t os h a p em a p sh a v et h ek e yp r o p e r t i e s 【2 5 】d i s c u s s e da b o v e a r et h e s ef e a t u r e sar e s u l t o fp a r t i c u l a rp r o p e r t i e so ft h eb i o p h y s i c so fr n ao rp r o t e i nf o l d i n go ri si tp o s s i b l et o o b t a i nt h e mb yp u r e l yc o m b i n a t o r i a lm e a n s ? b e f o r ew eg i v et h ea n s w e r , l e tu sd i g r e s s f o ram o m e n ta n dc o n s i d e rap a r t i c u l a r , w e l ls t u d i e dc l a s so fm a p so v e rn - c u b e r ：t h e n k - l a n d s c a p e si n t r o d u c e db yk a u f f m a n 1 6 ，w h e r ee a c hi n d e x ( 1 0 c u s ) o f a b i n a r yn - t u p l ev i e w e da st h eg e n o t y p ec o m p o s e db y 竹l o c ii sr a n d o m l yl i n k e dt ok o t h e ri n d i c e s t h ei d e ai st h a tal o c u szm a k e sac o n t r i b u t i o nt ot h et o t a lf i t n e s so ft h eg e n o t y p ew h i c h 2 一一一 c h a p t e r1 i n t r o d u c t i o n d e p e n d s o nt h ev a l u eo f 1 ea l l e l e ( 0o r1 ) a tia n dt h ev a l u e sa te a c ho ft h ee p i s t a t i c a l l y l i n k e dl o c i t oe a c ho ft h e s e2 k + 1c o m b i n a t i o n st h e r ei sav a l u e ( f i t n e s s ) a s s i g n e du n i f o r m l ya tr a n d o m t h ea p p a r e n tl a c ko fn e u t r a l i t yl e db a r n e t t t or e f i n en k l a n d s c a p e s b yn k p - l a n d s c a p e s ，i n t r o d u c i n gap r o b a b i l i t ypw i t hw h i c h a na r b i t r a r i l yc h o s e na l l e l i cc o m b i n a t i o nm a k e sn oc o n t r i b u t i o nt ot h ef i t n e s s o u ra p p r o a c hi sc o n n e c t e dt o k a u f f m a n n si n t u i t i o ni nt h a tw ec o n s i d e ram o l e c u l a rs t r u c t u r ea sac o m b i n a t o r i a lr e p - r e s e n t a t i o no fn u c l e o t i d e c o r r e l a t i o n s h o w e v e r , o u rc o r r e l a t i o n sa r ef i x e d ，r e s t r i c t e d a n dn o tr a n d o ma ta 1 1 f o rag i v e na l p h a b e t , b a s ep a i r i n gr u l e s ( c h e m i s t r i e s ) s p e c i f y w h i c hn u c l e o t i d e sc a np a i r h o w e v e r , n o ta n yt w on u c l e o t i d e sa r ea b l et oe s t a b l i s h s u c hac o r r e l a t i o n ( e d g e ) f o ri n s t a n c e ，t h e ym a yb er e s t r i c t e db yc o n d i t i o n sl i k en o t w oe d g e sc a nc r o s se a c ho t h e rw h e nr e p r e s e n t i n gas h a p ea sad i a g r a m t h en o n c r o s s i n gc o n d i t i o na n du n i q u e n e s so fb a s ep a i rb a s i sa r et w ok e yp r o p e r t i e so fr n a s e c o n d a r ys t r u c t u r e sa n da l l o wf o rm o t z k i n p a t he n u m e r a t i o na n d t r e eb i j e c t i o n s n o w w ea d o p tad i f f e r e n tc o m b i n a t o r i a lp e r s p e c t i v e o u ro b j e c t i v ei sn o tt om o d e l “r e a l i s t i c ”s t r u c t u r e sb u tt oi d e n t i f yt h et h ek e yc o m b i n a t o r i a lp r o p e r t i e st h a tg u a r a n t e et h e c o r ef e a t u r e so fr n a f o l d i n gm a p s o u r b a s i cq u e s t i o n sa r e w h a ti st h er o l eo ft h e w a t s o n c r i c kb a s ep a i r i n gr u l e s ? w h e nd om a p so v i 玎n - c u b e sa l l o wf o rn e u r a ln e i g h b o r s ? u n d e rw h i c hc o n d i t i o n sd os h a p e sh a v en e u t r a ln e t w o r k s ? i ti sc l e a rt h a tt h e m a p si n t r o d u c e dh e r ec a nf a c i l i t a t ef a s tc o m p u t e re x p e r i m e n t sa n d b eu s e df o rd e r i v i n g f u r t h e ra n a l y s i sr e s u l t s w eh a v et h ef o l l o w i n gt w ob a s i ca s s u m p t i o n s ：( i ) t h e r ee x i s t s s o m eu n i v e r s a lg r a p hhw h o s es o l ep u r p o s ei st or e s t r i c ta l lp o s s i b l ec o r r e l a t i o n sa n d ( i i ) w ea r eg i v e nas y m m e t r i cr e l a t i o n 冗，w h i c hi st a n t a m o u n tt oa b a s ep a i r i n gr u l e a s h a p es o fas e q u e n c ei st h e nt h eu n i q u em a x i m a lh s u b g r a p hs u b j e c tt ot h ep r o p e r t y t h a tf o ra n ys e d g et h ei n c i d e n tn u c l e o t i d e ss a t i s f y 冗t h i sa p p r o a c hi si nf a c ts i m i l a r t ot h ec o n c e p to fm i n i m u mf r e ee n e r g yf o l d i n g t h e r e ，u n d e rs p e c i f i cc o n d i t i o n s ，t h e c o m b i n a t i o no fb a s ep a i r si sr e a l i z e dw h i c hm i n i m i z e sf r e ee n e r g y w ec a l ls u c ham a p f r o ms e q u e n c e si n t os h a p e sac o m b i n a t o r ym 印 t h et h e s i si so r g a n i z e da sf o l l o w s ：i nc h a p t e r2 ，w es h o ws o m eb a c k g r o u n d k n o w l e d g e w h i c hc o n t a i n st h et r a n s f e r - m a t r i xm e t h o da n db a s i cc o n c e p t so fg r a p ht h e o r y i nt h er n a b a c k g r o u n d ，w ei n t r o d u c er n a m o l e c u l a rs e q u e n c e ，r n am o l e c u l a r s t r u c t u r e ，r n as t r u c t u r ee n u m e r a t i o n ，m i n i m a lf r e ee n e r g ys t r u c t u r ea n dr e v i e wt h e 3 一一一 c h a p t e r1 i n t r o d u c t i o n g e n e t i cp r o p e r t i e so fm a pf r o mr n as e q u e n c e st or n as e c o n d a r ys t r u c t u r e ss u c ha s n e u r a ln e t w o r k sa n ds h a p es p a c ec o v e t i n g i no r d e rt os t u d yt h ep r i n c i p l ew h i c hd e t e r m i n e st h ek e yp r o p e r t i e so fm a pf r o mr n a s e q u e n c e st or n as e c o n d a r ys t r u c t u r e s ， i nc h a p t e r3 ，w ec o n s t r u c tac o m b i n a t o r i a lm a pb yi m p r o v i n gs