（运筹学与控制论专业论文）计算生物学中的组合优化问题的研究.pdf

s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n n o7 i l a t i o ni n d e x g = ( v e ) e = ( u ， ) ： 0 ( ) ： 舀m d e ( u ， ) ： 0 ( ，( 扎) ) ： d ( n ，r ) ： a ( r i ，r ) ： c ( n ，r ) ： b ( i i ，1 1 ) ： p ( 丌，i ，j ) ： p ( 7 r ，i ，) 。 p ( 7 r ，y ，i ，j ) ： e b ： e e ： x b ： x e ： q + ： a x 【a ，h i ： ag r a p hw h o s ev e r t e xs e ta n de d g es e ta r eva n de ，r e s p e c t i v e l y a ne d g ec o n n e c t i n gt w oe n d sua n d t h es e to fv e r t i c e sa d j a c e n tt o “i ng t h es e ti n v o l v i n gua n da l lv e r t i c e sa d j a c e n tt oui ng t h ed i s t a n c eb e t w e e n “a n dvi ng o ( ，( n ) ) sc f ( n ) f o rac o n s t a n tc 0 t h er e a r r a n g e m e n td i s t a n c eb e t w e e ng e n o m e s a n df c y c l eg r a p ho fg e n o m e si ia n df t h en u m b e ro fc y c l e si nc ( n ，r ) t h en u m b e ro fb l a c ke d g e si ac ( t i ，r ) ar e v e r s a lo nu n i c h r o m o s o m a lg e n o m e7 r at r a n s p o s i t i o no nu n i c h r o m o s o m a lg e n o m e7 r at r a n s l o c a t i o no at w ou n i c h r o m o s o m a lg e n o m e s a n d7 ac a p p i n go fg e n o m e1 1 t h es e to fn o d a lg e n e so fm 1c h r o m o s o m e si nag e n o m en t h eo v e r l a pg r a p ho fg e n o m e s a n df t h ei n t e r l e a v i n gg r a p ho fg e n o m e si ia n dr t h es e to fu n o r i e n t e di n t r a - c h r o m o s o m a lc o m p o n e n t si nh ( i i ，f ) t h es e to fr e a lu n o r i e n t e dc o m p o n e n t si nh ( n ，f ) t h en u m b e ro fk n o t si ni u ( n ，r ) t h en u m b e ro ff o r t r e s s o f - k n o t si ni u ( n ，f ) t h en u m b e ro fr e m k n o t si nr u ( i i ，f ) t h en u m b e ro fs e m i r e a l k n o t si nh u ( n ，f ) t h ep o s i t i o no fl e f te n do fe d g ee t h ep o s i t i o no fr i g h te n do fe d g ee t h ep o s i t i o no fl e f t m o s te n do fe d g ei nc y c l eo rc o n n e c t e dc o m p o n e n tx t h ep o s i t i o no fr i g h t m o s te n do fe d g ei nc y c l eo rc o n n e c t e dc o m p o n e n tx t h es e to fn o n n e g a t i v er a t i o n a ln u m b e r t h es u b g r a p ho fgi n d u c e db yag i v e nv e r t e xs e tx t h e i n t e r v a l i n c l u d i n gp o s i t i o n so ，a + 1 ，b 一1 ，b x ”皿皿d d n n“u“毗吼r彳王 砸刚即聊删姬星=喁啦 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：j 些6日期：! ! ! 兰! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：至勃导师签名歹亟西磁目 期： 。硷 0 ，不存在性能比为 一e 的近似算法 定理3 2m r s d s d l 问题是a p x - h a r d ，且对任意的 0 ，不存在性能比为 i 1 丽6 7 6 一的近似算法 定理3 4 算法7 - 2 是m r s o s d l 问题的一个7 一近似算法 定理3 5 对每一个m r n a 次结构具有性质a 的m r s d s d l 实例，算法7 - 1 是 m r s o s d l 的7 一近似算法，算法7 - 2 是m r s o s d l 的4 一近似算法 概括地说，本文的主要创新点有： 1 设计了计算有向多染色体基因组之间的移位距离的线性时间算法这是当 前最快的算法，改进了2 0 0 2 年由朱大铭、马绍汉给出的o ( 礼2 1 0 9 n ) 时间算法 2 提出了计算有向多染色体基因组之间移位变换、翻转变换、融合变换、分 裂变换下的基因组进化距离的线性时间算法，同时设计了对应的基因组排序问题的 o 、而而) 算法在此之前进化距离计算问题与基因组排序问题的最好的算法时 间复杂性均为o ( n 2 ) 3 首次考虑了移位变换的中值问题，分别设计了无向与有向情形的近似算法 4 考虑二元字符串的翻转与对换的排序问题，给出对应问题的近似算法 5 考虑蛋白质相似性问题，证明在满足m r n a 二级结构核苷酸互补等约束下 对应的问题是a p x - h a r d 问题，并设计对应问题的近似算法 关键词：基因组重排；多重基因组；移位距离；基因组进化距离；中值问题； 排序；蛋白质相似性；近似算法 1 v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n s t u d yo nc o m b i na ，1 1 0 r i a lo p t i m i z a t l 0 n p r o b l e m si nc o m p u t a t i o n a lb i o l o g y w a n gx i a o l i ( s c h o o lo fm a t h s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ，p rc h i n a ) ( a d v i s o r ：p r o f l ic u o - j n n ) a b s t r a c t c o m p u t e rs c i e n t i s t sa n dm a t h e m a t i c i a n sw o r k i n gi nc o m p u t a t i o n a lm o l e c u l a rb i o l o g yh a v ef o c u s e dl a r g e l yo nt h ea n a l y s i so fd n aa n da m i n oa c i ds e q u e n c e ss i n c e i t si n c e p t i o ni nt h ee a r l y1 9 7 0 sp r o b l e m st h a th a v er e c e i v e dt h em o s ta t t e n t i o ni n c l u d es i m i l a r i t ys e a r c h i n g ，g e n o m er e a r r a n g e m e n ta n dp h y l o g e n yr e c o n s t r u c t i o n t h e r e s e a r c h e r sa n a l y z ed a t ac o m i n gf r o md i s t i n c ts p e c i e sa n dl e a r nf r o mt h es i m i l a r i t i e s a n dd i f f e r e n c e si nr e l a t e dg e n o m e s m a n ys t u d i e sc o n v i n c i n g l yp r o v e dt h a tg e n o m e r e a r r a n g e m e n t sr e p r e s e n tac o m m o nm o d eo fm o l e c u l a re v o l u t i o ni nc o m p a r a t i v eg e n o m i c s ，i tc a np r o v i d em e a n i n g f u li n s i g h t si n t ob i o l o g y t h i si m p o r t a n tr e a l i z a t i o ni s n o wa p p a r e n tt or e s e a r c h e r si nd i v e r s ef i e l d s t h eg e n o m er e a r r a n g e m e n tp r o b l e mi st of i n da no p t i m a ls c e n a r i ot r a n s f o r m i n g o n eg e n o m et oa n o t h e rv i am i n i m u mn u m b e ro fr e a r r a n g e m e n te v e n t st h i sh a sb e e n af u n d a m e n t a lp r o b l e mf o rm a t h e m a t i c i a n sa n dc o m p u t e rs c i e n t i s t s w ec a l lt h er a i n i m u mn u m b e ro fr e a r r a n g e m e n t st r a n s f o r m i n go n eg e n o m et oa n o t h e ra st h ee v o l u t i o n d i s t a n c e a n dw ec a l lt h ep r o b l e mt of i n da l lo p t i m a lr e a r r a n g e m e n ts e q u e n c eo ft r a n s f o r m i n go n eg e n o m et oa n o t h e ra st h ep r o b l e mo fg e n o m i cs o r t i n g g e n o m er e a r r a n g e m e n ta n dp r o t e i ns i m i l a r i t i e ss e a r c ha r eh o t s p o t sa n dd i f f i c u l t y o fr e s e a r c hi nc o m p a r a t i v eg e n o m i c sr e c e n t l y i nt h i sd i s s e r t a t i o nt h ep r o b l e m sa s s o c i a t e dw i t hm u l t i - c h r o m o s o m a lg e n o m e sr e a r r a n g e m e n ta r ec o n s i d e r e d t h ec o m p l e x i t i e so fs o m ea l g o r i t h m sa r er e d u c e da n da p p r o x i m a t ea l g o r i t h m sa r ep r o v i d e da n da p r o b l e ma s s o c i a t e dw i t hp r o t e i ns i m i l a r i t i e ss e a r c hi sd i s c u s s e di nt h i sd i s s e r t a t i o n ，t h e c o m p l e x i t ya n da p p r o x i m a t ea l g o r i t h m sa r ed i s c u s s e d t h ed i s s e r t a t i o ni ss p l i ti n t o s e v e nc h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c et h er e l a t e dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mc o n s i d e r e di nt h i sd i s s e r t a t i o n ，a n dr e v i e wt h ee x i s t i n gl i t e r a t u r eo nt h ea l g o r i t h m i ca s p e c t s v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n o ft h e s ep r o b l e m s ，a n ds u m m a r l s et h ef u n d a m e n t a lr e s u l t sa n dn o t a t i o n s i nc h a p t e r2 ，w es t u d yt h ep r o b l e mo fm u l t i c h r o m o s o m a lg e n o m er e a r r a n g e m e n t b y ( r e c i p r o c a l ) t r a n s l o c a t i o n i n1 9 9 6 ，s h a n n e n a n l l is h o w e dt h a tt h ep r o b l e mo f g e n o m er e a r r a n g e m e n te v o l v i n gb yr e c i p r o c a lt r a n s l o c a t i o n si si np ，a n dg a v eao ( _ n 3 ) a l g o r i t h mf o rt h ep r o b l e m a tt h es t a r to ft h ec h a p t e r ，w ea n a l y z et h es t r u c t u r eo ft i l es o c a l l e dc y c l eg r a p h o fas i g n e dp e r m u t a t i o ni nt h ec o n t e x to fg e n o m er e a r r a n g e m e n tp r o b l e m w eg i v e t h el i n e a ra l g o r i t h m ，a l g o r i t h m2 - 1 ，f o rc o m p u t i n gt h ec o n n e c t e dc o m p o n e n ti nt h e o v e r l a pg r a p ho ft h es i g n e dp e r m u t a t i o n ，w h i c hi st h eb a s ei nc h a p t e r2 ，c h a p t e r3 a n dc h a p t e r4 t h e nw ei n t r o d u c et h ec o n c e p to fm i n i m u mc o m p a n i o ns u b p e r m u t a t i 。n ( c o m s p ) ， a n da n a l y z et h ep r o p e r t i e so fm i n i m u ms u b p e r m u t a t i o n 8 ( m s p ) b ya n a l y z i n gt h o s eo f c o - m s p w ed e f i n eas e p a r a t i n gn u m b e r ( a ) o nc h r o m o s o m e sa n dg i v et h er e l a t i o no f 。 a n dt h es t r u c t u r eo ft h ec y c l eg r a p h al i n e a ra l g o r i t h m ，a l g o r i t h m2 - 2 ，i sd e v i s e d ，t o c o m p u t es o m ep a r a m e t e r sn e e d e df o rc o m p u t i n gt h et r a n s l o c a t i o nd i s t a n c e t h em a i n c o n c l u s i o ng o e sa sf o l l o w s t h e o r e m6t h et r a n s l o c a t i o nd i s t a n c eb e t w e e nt w os i g n e dg e n o m e sc a nb ec o m p u t e di n0 ( n ) ，w h e r e 几i st h en u m b e ro fg e n e si no n eg e n o m e c h a p t e r3c o n t a i n san u m b e ro fc o n t r i b u t i o n st h a th e l pt oi m p r o v eo u ru n d e r s t a n d i n go ft h ea l g o r i t h m i ci s s u e si n v o l v e di nt h ep r o b l e mo fg e n o m er e a r r a n g e m e n t e v o l v i n gb yr e v e r s a l s ，t r a n s l o c a t i o n s jf i s s i o n sa n df u s i o n s w eb e g i nt h ed i s c u s s i o n f r o ms p e c i a lc o n n e c t e dc o m p o n e n t si nt h ei n t e r l e a v i n gg r a p hw h i c hl e a d st oab e t t e r u n d e r s t a n d i n go fh o wt h e s ec o m p o n e n t sa f f e c tt h eg e n e r a lp r o b l e m w ed e f i n es o m e f u n c t i o n s ，r e f l e c t i n gt h ep r o p e r t i e so ft h es p e c i a lc o n n e c t e dc o m p o n e n t s i ns e c t i o n3 3 ，w ef i r s td e s i g nal i n e a ra l g o r i t h m ，a l g o r i t h m3 - 1 ，t h a tw i l lb eu s e d t od e c i d et h ee x i s t e n c eo fas p e c i a lp r o p e r t yf o ra nc o n n e c t e dc o m p o n e n t 】w h i c hi s i m p o r t a n ti nt h el a t t e r s e c o n d l yw ea n a l y z et h el a b e l so nas p e c i a lc o n c a t e n a t i o no ft h eg i v e ng e n o m e s w ee x e c u t ea l g o r i t h m2 - 1t og e tt h ep o s i t i o n s l a b e l sb yc o m p o n e n t s t h i sl e a d st o l i n e a rt i m ea l g o r i t h m s ，a l g o r i t h m3 - 2a n da l g o r i t h m3 - 3f o rc o m p u t i n gt h eg e n o m i e d i s t a n c eb e t w e e ns i g n e dm u l t i - c h r o m o s o m a lg e n o m e s h e n c ew eh a v et h ef o l l o w i n g c o n c l u s i o n v 1 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n t h e o r e m1 2t h eg e n o m i cd i s t a n c ec a l lb ec o m p u t e di nt h eg e n e r a lc a s ei n0 ( n ) t i m e ，i e w ec a nc o m p u t et h el e n g t ho fas h o r t e s ts e q u e n c eo fr e v e r s a l s ，t r a n s l o c a t i o n s ) f i s s i o n sa n df u s i o n sr e q u i r e dt ot r a n s f o r mo n eg e n o m ei n t oa n o t h e ri nl i n e a rt i m e i nc h a p t e r4 ，w eg oo nt os t u d yt h ep r o b l e mo fm u l t i c h r o m o s o m a lg e n o m e sr e a r “ r a n g e m e n t ，w es t u d yt h ea l g o r i t h mo fc o m p u t i n g t h eo p t i m a lr e a r r a n g e m e n ts e q u e n c e o fm u l t i c h r o m o s o m a lg e n o m e s ，w h i c he v o l v i n gb yr e v e r s a l s ，t r a n s l o c a t i o n s ，f i s s i o n sa n d f u s i o n s ，w h e r ee a c hg e n eo c c u r se x a c t l yo n c ei l lag e n o m e w em a n a g et ot r a n s f o r mi t t ot h ep r o b l e mo fs o r t i n gb yr e v e r s a l si no r d e rt og e ta no p t i m a le v o l u t i o ns e q u e n c e ， w em a n a g et om i m i c km u l t i c h r o m o s o m a lr e a r r a n g e m e n t sb yr e v e r s a l s h o wt or e d u c e o ra v o i dt h en u m b e ro fn o n s e n s er e v e r s a l sw h i c ha p p e a r e di nt h et r a n s f o r m a t i o ni sa k e yp r o b l e m w ec o n v e r ti ti n t ot h ep r o b l e mo ff i n d i n ga no p t i m a lc a p p e dc o n c a t e n a t i o no ft h et w og e n o m e sw i t ht i m el e s st h a no ( 扎撕历而) t om e e to u rp u r p o s e t h e o p t i m a lc a p p e dc o n c a t e n a t i o nd e p e n d so n a l lo p t i m a lo r i e n t a t i o n ( f l i p p i n g ) o ft h ec y c l e g r a p ha n da no p t i m a lc a p p i n g so ft h et w og e n o m e s a f t e rt h ei m p l e m e n to fa l g o r i t h m3 - 2o nt h ec y c l eg r a p h ，w ec a nh a v eal i n e a r a l g o r i t h m ，a l g o r i t h m4 - 1 ，w h i c hc o u l df i n d a l lo p t i m a lf l i p p i n go ft h ec y c l eg r a p h w ew i l lf i n da no p t i m a lc a p p i n gb ya l g o r i d u n4 - 2i nl i n e a rt i m e t h e nw ed e v i s ea l l l i n e a ra l g o r i t h m ，a l g o r i t h m4 - 3 ，t of i n da no p t i m a lo r i e n t a t i o no ft h ec y c l eg r a p ha f t e r f l i p p i n gas e g m e n to fs o m ec h r o m o s o m e s f i n a l l y , w ed e v i s e al i n e a ra l g o r i t h m ，a l g o r i t f l m l4 - 4 ，t of i n dt h eo p t i m a lc o n c a t e n a t i o n t h e r e f o r e ，w ec a l lg e tt h ef i l i a la l g o r i t h m ，a l g o r i t h m4 - 5 、f o rt h eo p t i m a l r e a r r a n g e m e n ts e q u e n c eo fm u l t i c h r o m o s o m a lg e n o m e s a n dg e tt h ef o l l o w i n gc o n c h t s i o n t h e o r e m1 8t h eo p t i m a lr e a r r a n g e m e n ts e q u e n c eo fm u l t i c h r o m o s o m a lg e n o n l e s c a nb eo b t a i n e db ya l g o r i t h m4 - 5i n0 ( 凡、n 2 0 9 n ) i nc h a p t e r5 ，w ec o n s i d e rt h et r a n s l o c a t i o nm e d i ap r o b l e mt h i si sas i m p l ev e r s i o no ft h ep r o b l e mp h y l o g e n yr e c o n s t r u c t i o n w ef o c u so nt h et r a n s l o c a t i o nm e d i a n p r o b l e m ( t m p ) ，w h i c hi sap r o b l e mo ff i n d i n gag e n o m e w h i c hi sc l o s e s tt oag i v e ns e t o fg e n o m e sw i t hr e s p e c tt ot h et r a n s l o e a t i o nd i s t a n c e w es t u d yt h et m pi ns i g n e da n du n s i g n e dm o d e l sr e s p e c t i v e l y i ns e c t i o n5 2 ，w e s t u d yt h eu n s i g n e dm o d e l w es t u d yam e d i a np r o b l e mf o rb r e a k p o i n t s ，w h i c hc a nb e t r a n s f o r m e dt ot h et r a v e l l i n gs a l e s m a np r o b l e m ( t s p ) ，t oa p p r o x i m a t et m p w eg i v e s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n a l g o r i t h m5 - 1t oa p p r o x i m a t et m p f o rt h es i g n e dm o d e l ，w ed e v i s ea l g o r i t h m5 - 3 t oa p p r o x i m a t et m pb yc o m p u t i n gam a x i m u mw e i g h t e dm a t c h i n gi nac o n s t r u c t e d g r a p h w ea l s oc o n s i d e rt oa p p r o x i m a t et m pb yt r a n s f o r m i n gt h es i g n e dm o d e lt o au n s i g n e dm o d e l ，a n dd e v i s ea l g o r i t h m5 - 4f o rt h i sp u r p o s e i np a r t i c u l a r ，w es h o w t h a tt h e r ee x i s to p t i m a ls o l u t i o n si ns o m es p e c i a lc a s e si ns i g n e dm o d e l ，a n dg i v et k e f o l l o w i n gc o n c l u s i o n s t h e o r e m2 1f o rm = 2 a n yg e n o m ei na no p t i m a le v o l u t i o ng e n o m e ss e q u e n c e f r o m 1t o 2i sa no p t i m a ls o l u t i o nf o rt h et m p a n dt h eo p t i m a lv a l u ei sd ( n l ，2 ) t h e o r e m2 3f o rm = 3 ，i ft h e r ee x i s tt w og e n o m e s ，玛，s u c ht h a tt h et r a n s l o - c a t i o nd i s t a n c eb e t w e e nt h e mi sn om o r et h a nk ，w h e r eki sac o n s t a n ti n t e g e r t h e n w ec a ng e ta i lo p t i m a ls o l u t i o nf o rt h et m pi n0 ( 2 n 2 + 2 1 i nc h a p t e r6 ，w ec o n s i d e rt h ep r o b l e m so fs o r t i n gb yr e v e r s a l sa n ds o r t i n gb y t r a n s p o s i t i o n si nas i m p l ee a s et h a tt h es t r i n g st ob ec o m p a r e da r ed r a w nf r o mab i n a r y a l p h a b e t c h r i s t i ea n di r v i n gp r o v e dt h a tt h ep r o b l e mo ff i n d i n gr e v e r s a ld i s t a n c e b e t w e e nb i n a r ys t r i n g s ，a n dt h e r e f o r eb e t w e e ns t r i n g so v e ra na r b i t r a r yf i x e da l p h a b e t ， i sn p h a r d b u tt h ep r o b l e mo ff i n d i n gt r a n s p o s i t i o nd i s t a n c eb e t w e e nb i n a r ys t r i n g s i ss t i uo p e n w ef o c u so nb i n a r ys t r i n g sa n dd e s i g nt w oa p p r o x i m a t i o na l g o r i t h m s ， a l g o r i t h m6 - 1a n da l g o r i t h m6 - 2 ，f o rs o r t i n gb i n a r ys t r i n g sb yr e v e r s a l sa n df o rs o r t i n g b i n a r ys t r i n g sb yt r a n s p o s i t i o n s ，r e s p e c t i v e l y e a c ha l g o r i t h mp r o d u c e sas o l u t i o n w h i c hi sw i t h i na ne x p e c t e df a c t o r2o ft h eo p t i m a ls o l u t i o n i nc h a p t e r7 ，w ec o n s i d e ras p e c i a lc o m b i n a t i o n a lp r o b l e mo np r o t e i ns i m i l a r i t i e s ， i e ，f o rag i v e nm r n aa n dap r o t e i n ，w et r yt od e t e r m i n eas e q u e n c eo fn u c l e o t i d e s w h i c hh a sm a x i m a ls i m i l a r i t yt ot h eg i v e nm r n aa sw e l la si t si n d u c e dp r o t e i ns e - q u e n c ei sm a x i m a l l ys i m i l a rt ot h eg i v e np r o t e i n ，a n da d d i t i o n a l l yo b e y ss o m es p e c i f l e ds e c o n d a r ys t r u c t u r ec o n s t r a i n s b a c k o f e n ，n a r a y a n a s w a m y , a n ds w i d a nm o d e l l e d t h i sp r o b l e mi nt e r m so fa no p t i m i z a t i o np r o b l e mc a l l e dm r s o ( m r n as t r u c t u r e o p t i m i z a t i o n ) t h e yp r o v e dt h ed e c i s i o nv e r s i o no fm r s o i sn p c o m p l e t ea n da2 一 a p p r o x i m a t i o na l g o r i t h mh a sb e e np r o p o s e di nt h eg e n e r a lc a s e ，a n dt h e yp r o v e dt h a t t h e r ee x i s t sal i n e a rt i m ea l g o r i t h mi ft h ec o n s i d e r e ds e c o n d a r ys t r u c t u r ei sa no u t e r - p l a n a rg r a p h b d i r ki n v e s t i g a t e di t sc o m p l e x i t yf u r t h e r ，a n dg a v ea4 - a p p r o x i m a t i o n f o rar e s t r i c t e dv e r s i o no ft h ep r o b l e mo fm r s 0 w ec o n s i d e rar e s t r i c t e dp r o b l e mo fm r s o