（运筹学与控制论专业论文）基因组完美重组算法及一类qpfree可行域方法的研究.pdf

山东大学博士学位论文 基因组完美重组算法及一类q p f r e e 可行域方法的研究 张海燕 ( 山东大学数学学院，济南2 5 0 1 0 0 ) 指导教师：李国君教授 中文摘要 本文研究了计算生物学中的基因组完美重组问题及q p f r e e 可行域方法 全文共分为四章 基因组完美重组问题在生物种族进化研究、生物分类学研究和生物制药研 究等领域中显示出重要的研究价值在第一章里，我们将简单介绍基因组完美 重组问题的提出、相关概念及研究现状同时，在第一章，我们还简单介绍了 q p f r e e 可行域方法一一类求解非线性约束规划问题的方法非线性约束规划 问题是最优化领域中重要的研究课题之一，许多实际问题都可以归结为非线性 约束规划问题，并且很多实际应用，比如工程设计、经济平衡等问题都要求数 据仅仅在可行域内取值本章最后，我们给出了本文的主要结果 第二章研究了含有礼条染色体的基因组的完美重组问题对于单条染色体的 完美重组问题，b 6 r a r d 等( 4 】利用s t r o n gi n t e r v a l 树的结构，给出了d ( 2 p 佗彤画) 时间的算法后来，b 6 r a r d 等【5 】改进了此算法，给出了0 ( 2 d 佗面) 时间 的算法，这里d p 同时，b 6 r a r d 等在【5 】提出了一个问题：再优化s t r o n g i n t e r v a l 树，也很难找到一个标号基因组的完美翻转重组问题的多项式算法本 文把s t r o n gi n t e r v a l 树和断点图结合起来，对含有佗条染色体的基因组的完美 重组问题，给出了一个o ( n 2 ) 时间的算法部分地解决了b & a r d 等【5 】中提出 的问题 设源染色体和目标染色体分别为7 r 和r ，它们含有不同基因集合在第三章 里，我们研究了含有不同基因集合的染色体7 r 和r 的完美重组问题很明显， 山东大学博士学位论文 在这种情况下，“插入”或“删除”将成为必需的操作我们推广了h a n n e h a l i 和p e v z n e r 2 6 提出的多项式算法( 简称h p 算法) ，使之能够处理含有不同基 因集合7 r 和7 的完美重组问题 在最后一章，我们研究了一类求解非线性约束规划问题的方法一q p f r e e 可 行域方法，我们知道s q p 方法，即序列二次规划方法，是解决非线性约束规划 问题的一种有效方法，但是，这种方法在每次迭代点处都要解决二次规划子问 题，计算量很大，并且在某些迭代点处不一定有解而q p f l e e 可行域方法，是把 求解一个非线性约束规划问题等价于线性方程组的求解问题在每次迭代中，只 需解若干个具有相同系数矩阵的线性方程组，因此减少了计算量，并且q p f r e e 可行域方法能保证在每一个迭代点处都有解1 9 8 8 年，p a s t i e r 等 4 3 在前人的 基础上提出了一类有效的q p f r e e 方法，并且证明了这类方法的收敛性之后， 有很多的研究者对其进行了改进我们利用光滑化的f i s c h e r - b u r m e i s t e r ( p b ) 非 线性互补函数，修改了q p f r e e 可行域方法线性方程组系数矩阵的近似j a c o b i a a a 矩阵k ，提出了一类新方法，并且在比较弱的条件下证明该方法的可行性及收 敛性通过理论证明和例子的数据结果分析可以看出，我们提出的q p f r e e 可行 域方法比较令人满意。 关键词：计算生物学；染色体；基因组；完美重组；翻转；移位；删除；算 法；q p f r e e ；可行域；非线性互补；光滑函数；收敛 书鹄鲢 山东大学博士学位论文 a l g o r i t h m so fg e n o m e p e r f e c tr e a r r a n g e m e n t s a n dt h es t u d yo faq p - f r e ef e a s i b l em e t h o d z h a n gh a l y a n ( s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y ，j i n a n2 5 01 0 0 ) a d v i s o r ：p r o f l ic u o - j u n a b s t r a c t i nt h i sp a p e r ，w em a i n l ys t u d yt h ep r o b l e mo fg e n o m ep e r f e c tr e a r r a n g e m e n t si n b i o i n f o r m a t i c sa n dak i n do fq p f r e ef e a s i b l em e t h o d t h i sp a p e rc o n s i s t so ff o u r c h a p t e r s r e c e n t l y ，t h es t u d i e so fg e n o m ep e r f e c tr e a r r a n g e m e n t sh a v ed i s p l a y e di m - p o r t a n c ei nm a n yf i e l d s ，s u c ha se v o l u t i o n a r yh i s t o r i e s o fs p e c i e s ，t a x o n o m yo f b i o l o g y ，b i o m e d i c i n e ，e t c t h e r e f o r e ，i nc h a p t e rl ，w ef i r s tg i v eab r i e fr e v i e wo f g e n o m ep e r f e c tr e a r r a n g e m e n t sa n di n t r o d u c et h ec o r r e s p o n d i n gc o n c e p t i o n s w e a l s oi n t r o d u c eak i n do fq p f l e ef e a s i b l em e t h o d w 1 1 i c hi su s e dt os o l v ean o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m t h en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n p r o b l e mi sa ni m p o r t a n tr e s e a r c ht o p i ci nm a t h e m t i c a lp r o g r a m m i n gf i e l d s m a n y p r a c t i c a lp r o b l e m sc a nb er e d u c e dt ob et h en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n p r o b l e m s m o r e o v e r ，s o m er e a l - h f ea p p h c a t i o n ss u c ha si ne n g i n e e r i n gd e s i g na n d e c o n o m i c a le q u i l i b r i u mo fs u p p l ya n dd e m a n d r e q u i r et h ed a t a so n l yd e f i n e di nt h e f e a s i b l er e g i o n f i n a l l y , w ei n t r o d u c et h em a i nr e s u l t so b t a i n e di no u rp a p e r t h eo b j e c t i v eo fc h a p t e r2i st od e a lw i t ht h ep r o b l e mo fg e n o m e sp e r f e c t r e a r r a n g e m e n t s f o rt h ep r o b l e mo fu n i c h r o m o s o m e ( p e r m u t a t i o n ) p e r f e c tr e a l - r a n g e m e n t s ，b r a r de ta 1 【4 g a v ea nd ( 2 p n 而丽) a l g o r i t h mw i t ht h es t r o n g 1 1 1 山东大学博士学位论文 i n t e r v a lt r e ef r a m e w o r k l a t e r ，b 6 r a r de ta 1 5 】i m p r o v e dt h ea l g o r i t h m t h e yc a l l c o m p u t eap a r s i m o n i o u sp e r f e c ts c e n a r i of o rt h ep e r m u t a t i o ni nw o r s t c a s et i m e o ( 2 d 佗订画) ，w h e r ed p i nt h i sp a p e r ，w ec o n n e c tas t r o n gi n t e r v a lt r e e w i t hab r e a k p o i n tg r a p h f o rt h ep r o b l e mo fn - c h r o m o s o m a lg e n o m e sp e r f e c th a r r a n g e m e n t s w ed e s i g na na l g o r i t h ma n dg e ta no p t i m a lp e r f e c ts o r t i n gs e q u e n c e f o rt h eg e n o m e si nw o r s t c a s et i m eo ( n 2 1 w es o l v e dt h i sp r o b l e mw h i c hw a sp r o - p o s e di n 5 ii e ，i ts e e m sd i f f i c u l tt oo p t i m i z et h es t r o n gi n t e r v a lt r e ef r a m e w o r ki n o r d e rt oc o m p u t ep e r f e c ts c e n a r i o si np o l y n o m i a lt i m ef o rl a r g e rc l a s s e so fs i g n e d p e r m u t a t i o n s t h ep r o b l e mo fs o r t i n gs i g n e dp e r m u t a t i o n ( c h r o m o s o m e ) b yr e v e r s a l sh a s b e e ns t u d i e di n t e n s i v e l y i n19 9 5 ，h a n n e h a l ia n dp e v z n e r 【2 6 】d e v e l o p e dt h ef i r s t p o l y n o m i a la l g o r i t h m ，d e n o t e db yh pa l g o r i t h mi no u rp a p e r ，a n dt h e yg a v et h e f o r m u l ao ft h er e v e r s a ld i s t a n c e l e t7 ra n drb et h es o u r c ec h r o m o s o m e ( p e r m u t a - t i o n ) a n dt a r g e tc h r o m o s o m e ( p e r m u t a t i o ) ，r e s p e c t i v e l y m o r e o v e r ，t h e yh a v et h e d i f f e r e n tg e n ec o n t e n t i nc h a p t e r3 ，w es t u d yt h ep r o b l e mo fp e r f e c t l ys o r t i n g 7 ra n d7 o b v i o u s l y ，i ns u c hc a s e ，s o m ea d d i t i o n a ls t e p s ( i n s e r t i o n so rd e l e t i o n s ) a r en e e d e d w es h o wh o wt oe x t e n dt h eh pa l g o r i t h mt oap o l y n o m i a la l g o r i t h m w h i c hc a nc o m p u t et h ep e r f e c ts c e n a r i o sf o r7 ra n d ，yb yr e v e r s a l sa n dd e l e t i o n s i nt h el a s tc h a p t e r ，w ec o n c e r nam e t h o do fs o l v i n gt h en o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，n a m e l yq p f r e ef e a s i b l em e t h o d i n1 9 8 8 ，p a n i e r 【4 3 】b r o u g h t f o r w a r dak i n do fa v a i l a b l eq p f r e em e t h o do nt h eb a s i so ft h ef o r m e ra n dp r o v e d c o n v e r g e n c eo ft h em e t h o d s u b s e q u e m l y ，s o m ep e o p l em e n d e dt h i sm e t h o d w e b a s eo nt h er e s u l t so ft h ef o r m e r st om o d i f yt h ec o e f f i c i e n tm a t r i xv ko fl i n e a rs y s t e m so fe q u a t i o n sw i t hs m o o t h i n gf i s c h e r - b u r m e i s t e rn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ( n c p ) f u n c t i o n t h e nw ep r o p o s ea n e wk i n do fq p f r e ef e a s i b l em e t h o d u n d e rs o m ew e a k e rc o n d i t i o n s ，o u rm e t h o di si m p l e m e n t a b l ea n dg l o b a l l yc o n - v e r g e n t m o v e r o v e r ，s o m en u m e r i c a lt e s tr e s u l t sa r eg i v e nt oi n d i c a t e t h a tt h e 1 v 山东大学博士学位论文 a l g o r i t h mi sq u i t ep r o m i s i n g k e y w o r d s ：c o m p u t a t i o n a lb i o l o g y ；c h r o m o s o m e ；g e n o m e ；p e r f e c ts o r t i n g ；r e v e r - s a l ；t r a n s l o c a t i o n ；d e l e t i o n ；a l g o r i t h m ；q p - f l e e ；f e a s i b l e ；n o n l i n e a rc o m p l e m e n t a r i t y ；s m o o t h i n gf u n c t i o n ；c o n v e r g e n c e 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 a l g o r i t h m so fg e n o m ep e r f e c tr e a r r a n g e m e n t sa n dt h e s t u d yo faq p - f r e ef e a s i b l em e t h o d z h a n gh a n y a n ( s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y , j i n a n2 5 0 1 0 0 ) a d v i s o r ：p r o f l ig u 州u n a b s t r a c t i nt h i sp a p e r ，w em a i n l ys t u d yt h ep r o b l e mo fg e n o m ep e r f e c tr e a r r a n g e m e n t si nb i o i n - f r m a t i c sa n dak i n do fq p - f r e ef e a s i b l em e t h o d t h i sp a p e rc o n s i s t so ff o u rc h a p t e r s r e c e n t l y , t h es t u d i e so fg e n o m ep e r f e c tr e a r r a n g e m e n t sh a v ed i s p l a y e di m p o r t a n c e i nm a n yf i e l d s ，s u c ha se v o l u t i o n a r yh i s t o r i e so fs p e c i e s ，t a x o n o m yo fb i o l o g y , b i o m e d i c i n e ， e t c t h e r e f o r e ，i nc h a p t e rl ，w ef i r s tg i v eab r i e fr e v i e wo fg e n o m ep e r f e c tr e a r r a n g e - m e n t sa n di n t r o d u c et h ec o r r e s p o n d i n gc o n c e p t i o n s w ea l s oi n t r o d u c eak i n do fq p f r e e f e a s i b l em e t h o d - - w h i c hi su s e dt os o l v ean o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m t h en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e mi sa ni m p o r t a n tr e s e a r c ht o p i ci nm a t h e r o t i c a lp r o g r a m m i n g f i e l d s m a n yp r a c t i c a lp r o b l e m sc a nb er e d u c e dt ob et h en o n l i n e a r c o n s t r a i n e do p t i m i z a t i o np r o b l e m s m o r e o v e r ，s o m er e a l - l i f ea p p l i c a t i o n ss u c ha si ne n g i - n e e r i n gd e s i g na n de c o n o m i c a le q u i l i b r i u mo fs u p p l ya n dd e m a n dr e q u i r et h ed a t a so n l y d e f i n e di nt h ef e a s i b l er e g i o n f i n a l l y , w ei n t r o d u c et h em a i nr e s u l t so b t a i n e di no u r p a p e r t h eo b j e c t i v eo fc h a p t e r2i st od e a lw i t ht h ep r o b l e mo fg e n o m e sp e r f e c tr e a r - r a n g e m e n t s f o rt h ep r o b l e mo fu n i - c h r o m o s o m e ( p e r m u t a t i o n ) p e r f e c tr e a r r a n g e m e n t s ， b d r a r de ta 1 【4 】g a v ea no ( 汐佗而而) a l g o r i t h mw i t ht h es t r o n gi n t e r v a lt r e ef r a m e - w o r k l a t e r ，b d r a r de ta 1 【5 】i m p r o v e dt h ea l g o r i t h m t h e yc a nc o m p u t eap a r s i m o n i o u s p e r f e c ts c e n a r i of o rt h ep e r m u t a t i o ni nw o r s t c a s et i m e0 ( 2 d 佗嘶) ，w h e r ed p i n 1 1 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 i sp a p e r ，w ec o m b i n eas t r o n gi n t e r v a lt r e ew i t hab r e a k p o i n tg r a p h f o rt h ep r o b l e m o fn - c h r o m o s o m a lg e n o m e sp e r f e c tr e a r r a n g e m e n t s ，w ed e s i g na na l g o r i t h ma n dg e ta n o p t i m a lp e r f e c ts o r t i n gs e q u e n c ef o rt h eg e n o m e si nw o r s t - c a s et i m eo ( n 2 1 w es o l v e d t h i sp r o b l e mm e n t i o n e di n 【5 t h a ti ts e e m sd i f f i c u l tt oo p t i m i z et h es t r o n gi n t e r v a lt r e e f r a m e w o r ki no r d e rt oc o m p u t ep e r f e c ts c e n a r i o si np o l y n o m i a lt i m ef o rl a r g e rc l a s s e so f s i g n e dp e r m u t a t i o n s t h ep r o b l e mo fs o r t i n gs i g n e dp e r m u t a t i o n ( c h r o m o s o m e ) b yr e v e r s a l sh a sb e e n s t u d i e di n t e n s i v e l y i n1 9 9 5 ，h a n n e h a l ia n dp e v z n e r 【2 6 】d e v e l o p e dt h ef i r s tp o l y n o m i a l a l g o r i t h m ，d e n o t e db yh pa l g o r i t h mi no u rp a p e r ，a n dt h e yg a v et h ef o r m u l ao ft h e r e v e r s a ld i s t a n c e l e t7 ra n drb et h es o u r c ec h r o m o s o m e ( p e r m u t a t i o n ) a n dt a r g e t c h r o m o s o m e ( p e r m u t a t i o n ) ，r e s p e c t i v e l y m o r e o v e r ，t h e yh a v et h ed i f f e r e n tg e n ec o n t e n t i nc h a p t e r3 ，w es t u d yt h ep r o b l e mo fp e r f e c t l ys o r t i n g7 ra n dr o b v i o u s l y , i ns u c hc a s e ， s o m ea d d i t i o n a ls t e p s ( i n s e r t i o n so rd e l e t i o n s ) a r en e e d e d w es h o wh o wt oe x t e n dt h e i - i pa l g o r i t h mt oap o l y n o m i a la l g o r i t h mw h i c hc a nc o m p u t et h ep e r f e c ts c e n a r i o sf o r7 r a n d ，yb yr e v e r s a l sa n dd e l e t i o n s i nt h el a s tc h a p t e r ，w ec o n c e r nam e t h o do fs o l v i n gt h en o n l i n e a rc o n s t r a i n e do p - t i m i z a t i o np r o b l e m ，n a m e l yq p f r e ef e a s i b l em e t h o d i n1 9 8 8 ，p a n i e r 【4 3 】p r o p o s e da k i n do fa v a i l a b l eq p - f r e em e t h o do nt h eb a s i so ft h ef o r m e ra n dp r o v e dc o n v e r g e n c eo f t h em e t h o dw h i c hh a sb e e ni m p r o v e db ys e v e r a lo t h e rs c i e n t i s t s w eb a s eo nt h er e - s u i t so ft h ef o r m e r st om o d i f yt h ec o e f f i c i e n tm a t r i xv ko fl i n e a rs y s t e m so fe q u a t i o n s w i t hs m o o t h i n gf i s c h e r - b u r m e i s t e rn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ( n c p ) f u n c t i o n t h e nw ep r o p o s ean e wk i n do fq p - f r e ef e a s i b l em e t h o d u n d e rs o m ew e a k e rc o n d i t m n s ， o u rm e t h o di si m p l e m e n t a b l ea n dg l o b a l l yc o n v e r g e n t m o v e r o v e r ，s o m en u m e r i c a lt e s t r e s u l t sa r eg i v e nt oi n d i c a t et h a tt h ea l g o r i t h mi sq u i t ep r o m i s i n g k e y w o r d s ：c o m p u t a t i o n a lb i o l o g y ；c h r o m o s o m e ；g e n o m e ；p e r f e c ts o r t i n g ；r e v e r s a l ； t r a n s l o c a t i o n ；d e l e t i o n ；a l g o r i t h m ；q p - f r e e ；f e a s i b l e ；n o n l i n e a rc o m p l e m e n t a r i t y ；s m o o t h i n gf u n c t i o n ；c o n v e r g e n c e i 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 舻m ( ，) r i t a 霄 g 霄 s y m b o l s n - d i m e n s i o n a lr e a le u c l i d e a ns p a c e t h es e to f a l lm m ) r e a lm a t r i c e s i n n e rp r o d u c ti ns o m er e a le u c l i d e a ns p a c e ac h r o m o s o m e ( p e r m u t a t i o n ) t h es o u r c eg e n o m e t h et a r g e tg e n o m e t h eq u o t i e n tp e r m u t a t i o no ft h es t r o n gi n t e r v a li as e tw h i c hi sc o n s i s t e do fa l ln o n t r i v i a ls t r o n g i n t e r v a l si n ，r t h eg e n e so n l yi nc h r o m o s o m e7 r t h eb r e a k p o i n tg r a p ho fap e r m u t a t i o n 丌 p ( x ，i ，歹) ar e v e r s a la c t i n go nx p ( x ，kt ，歹) at r a n s l o c a t i o na c t i n go nxa n dy h p d ( n ，f ) t h er e s u l t i n gg e n o m ea f t e ra p p l y i n ga no p e r a t i o npo nr l t h er e v e r s a ld i s t a n c eb e t w e e n a n dr v 山东大学博士学位论文 s y m b o l s 竹维实欧式空间 所有( 扎m ) 实矩阵集合 实欧式空间中的内积 一条染色体( 一个排列) 源基因组 目标基因组 强保守区间i 的商排列 7 r 中所有非基本强保守区间所构成的集合 仅在染色体7 r 中的基因 染色体7 r 的断点图 作用在x 上的翻转 p ( x ，r t ，j )作用在x 和y 上的移位 1 - i p d ( 1 i ，f ) 基因组通过p 操作后得到的新基因组 和r 的翻转距离 力 m 一 a r 肝 丌 r 盯 札 g 职 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明本声明 的法律责任由本人承担 论文作者签名：搬姚赢日期：2 8 、f | 、沽 关于学位论文使用授权的声明 本人完全了解山东大学有关保留和使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 论文作者签名磕桃垫导师签 凰考嗍粥以西 山东大学博士学位论文 第一章绪论 在本章中，我们将给出本文工作的一些准备知识全章共分为三节第一 节给出了基因组完美重组问题的发展及相关概念第二节简单介绍了一个求解 非线性约束规划问题的方法一q p f r e e 可行域方法方便起见，我们在第三节概 述了本文的主要结果 1 1 基因组完美重组问题 1 1 1 动机和数学表示 在二十世纪三十年代末，d o b z h a n g s k y 和s t u r t e v a n t 1 8 】成为分子生物学 领域中对基因组重组进行分析的先驱，他们给出了果蝇物种1 7 个翻转的重组方 案在二十世纪八十年代，p a l m e r 和他的同事们【3 1 ，3 9 ，4 0 ，4 1 ，4 2 】在对比甘蓝 与芜菁的基因序列时发现，排列成两种基因序列的分子几乎完全相同，只是这 些分子在两种基因序列中的排列顺序不一样这一发现以及以后的研究表明， 基因组重组是生物演化过程中的一个基本特征，是微生物、植物、动物进化的 一种重要模式基因重组形式一般有翻转、移位、交换、分裂、融合、删除和插 入基因组重组问题在近几年得到了广泛的研究，已有大量的结果对应不同的 操作，基因重组问题不同并且难度不同更多内容，请参见【4 4 ，4 6 ，5 1 ，5 2 ，5 3 】 基因组重组问题可以抽象为计算机科学与数学中关于序列、树和串的组合 问题一条染色体由一个基因序列组成，可以看成一个排列令染色体7 r 为关于 1 ，2 ，佗 的一个排列，并且令单位排列i d = ( 12 扎) ，i d = ( 一扎一2 1 ) 设一个操作x ( 例如，翻转或移位) ，通过操作x 进行地基因重组问题就是寻找 一个最小的操作x 序列，使得给定的排列转化为单位排列，d 染色体7 r 的重组 距离就是操作x 序列的最小数，记为d ( 丌) 值得注意的是对于求任意两个排列 7 r 和7 之间距离的问题可以等同于上面问题，这是因为d ( r c ，7 ) = d ( 7 7 r ，i d ) 山东大学博士学位论文 设7 r = ( 7 r l 死一1 死乃乃+ 1 7 r 他) 为一条染色体，其中1sh i 死，并 且对任意i j ，1 7 r i l i 1 死( 1 i 死) 表示一个基因，且仉是一个带有正负号 的整数，前面的符号表示基因7 r i 的方向染色体内部的翻转p ( 7 r ， ，歹) 是指把丌中 的子序列k 引逆向排列即把丌转化为7 r 7 = ( 7 r 1 吼一1 - - t r j 一7 r t + l ) 一个基因组由多条染色体构成，故基因组可以表示为 1 - i = ( x l lx 1 2 x l 佗1 ) ( x 2 1x 2 2 z 2 n 2 ) ( x n lx n 2 x n n ) ) ， 其中有n 条染色体和竺1 他个基因 设7 r = ( 7 r 17 r 2 ) 和，y = ( ，y l 他) 为基因组中的两条标号染色 体，前缀一前缀移位锄( 7 r ，7 ，t ，j ) 就是把染色体7 r 和7 分别转化为基因组 中的两条新染色体 7 r 7 = ( 7 r 17 r 2 吼一1 ) 和丫= ( 一y l7 2 一l 死7 r i - - 1 7 r n ) 前缀一后缀移位鼽( 7 r ，7 ，i ，j ) 就是把7 r 和7 分别转化为 7 r 7 = ( 7 p 1 死一i 一一1 一7 1 ) 和丫= ( 一一吼竹) 对于基因组中无标号的染色体7 r 和，y ，前缀一前缀移位锄( 7 r ，y ，t ，j ) 是把7 r 和7 分别转化为 7 r 7 = 何1t 2 7 r t 一1 ) 和7 = ( 一y 1 7 2 一1 仉丌t + l 7 k ) 前缀一后缀移位踟。( 7 r ，y ，i ，j ) 是把7 r 和，y 分别转化为 7 r 7 = ( t 1 死一1 一1 ，y 1 ) 和y = ( 7 k 几7 m ) 断点在基因组重组问题中是一个很重要的概念如果满足几十1 死+ l ( 无 标号染色体满足i 仉+ 1 一死i 1 ) ，则称点( 死，几+ 1 ) 为断点 1 1 2 基因组的翻转重组问题 2 山东大学博士学位论文 我们首先介绍基因组的翻转重组问题设丌和，y 为两条具有相同基因集合 的染色体，基因组的翻转重组问题就是寻找一个最小的翻转序列，使得7 r 转化 为7 就像上面所述，本文中取7 = d 对于无标号基因组的翻转重组问题，k e c e c i o g l u 和s a n k o f f 【3 3 】给出了一个 近似比为2 的算法在每一步迭代中，他们选择一个翻转，使得断点个数尽可能 的减少。他们也利用分枝定界法给出了一个指数算法后来，b a f n a 和p e v z n e r 【2 】构造了染色体7 r 的断点图染色体7 r 的断点图是一个具有 o ，7 r 1 ，佗+ 1 ) 佗+ 2 个顶点的边着色图设6 ( 7 r ) 和c ( 7 r ) 分别表示断点图中断点的个数和圈 的个数，b a f n a 和p e v z n e r 【2 】证明每次翻转最多减少6 ( 7 r ) 一c 何) 个断点，即 d ( 7 r ) 6 ( 7 r ) 一c ( 7 r ) 并且，他们利用断点图给出了一个近似比为1 7 5 的多项式算 法后来，c h r i s t i e 把近似比降到了1 5 1 6 】目前该问题最好的算法是b e r m a n 等人给出的1 3 7 5 近似算法【1 0 】对该类问题，b e r m a n 和k a v p i n s k i ，c a p r a r a 已 经证明其为n p h a r df i 3 ，1 1 对标号染色体的翻转重组问题，b a f n a 和p e v z n e r 【2 】把标号染色体转化 为无标号染色体，构造了断点图具体如下：顶点+ i 和一i 分别用有序顶点对 2 一1 ，2 t 和2 t ，2 i 一1 代替这样具有n 个顶点的标号染色体7 r 转化为有2 礼 个顶点的无标号染色体7 r