（计算机软件与理论专业论文）反转排序问题的评测与移位排序问题的改进.pdf

原刨性声明 本人都重声鞠：搿呈交韵学位论文，楚本人在导鸯誊的指导下，独立 避行磅究掰取褥鹩残巢。除文中已经注萌等l 矮黪内容乡 ，本论文不包台 任何其他个人或集体已经发表或撰写过的料研成果。对本文的研究作出 重瑟贡献的个人和集体，均已在文中以明确方式标明。本声明的法律资 任由本人承担。 论文作者整名：! 量蕉 一 日期：奎里! ；z 关于学位论文傻鼹授权缒声鹾 本人完全了蟋出东大学蠢美缳留、使嬲学位论文鳇规定，阕意学援 保鼹或向国家有关部门成机构送交论文的复印件和电子版，允许论文被 查阅和借阅；本入授权山东大学可以将本学位论文的全部或部分内容编 入有关数搀库避孪亍检索，可以采穗影印、缩印或其缝复粼手段绦存论文 刹汇编本学位论文。 ( 保密论文在解密感应遵守此规定) 论文 乍者签名：墨援导簿签名：壤塞张强弱：婴、苫。 飞 山东大学硕士学位论文 摘要 基因重组是生物进化的重要方式，如果对每个基因，用一个有符号的整 数代替，则对基因重组的研究就演变为对排序算法的研究。用排序算法模拟 基因组的重组时，在模拟和生物学数据上得到了令人惊异的准确结果。因此， 基因重组算法的研究是对分子生物学中研究生物进化有重要的意义。本文讨 论了基因重组问题中的2 个问题一一有符号排列的反转排序问题( s o r ts i g n e d p e r m u t a t i o nb yr e v e r s a l s ) 和移位排序问题( s o r tb yt r a n s l o c a t i o n s ) 。这两个问 题分别是对于单条染色体基因重组和染色体组基因重组的模拟。 有符号排列的反转排序问题。将单条染色体用有符号整数表示，从而使 染色体通过反转变异的分子生物学问题演变为研究有符号整数排列通过反转 排序的计算机算法问题。该问题目前对于计算反转距离，有时间复杂度为 o ( n 2 ) 的算法，对计算反转步骤，有时间复杂度为0 ( n ) 的算法。本文对于该问 题的研究，主要是总结，验证了前人的研究成果，提出了经过优化的算法实 现和数据结构，对算法进行了实验。实验结果显示，本文的算法实现比对照 算法实现快7 1 0 倍，并且将可计算的输入长度改进为仅受限于计算机硬件 条件。 移位排序问题。将含有多条染色体的染色体组用几组有符号整数的排列 表示，从而模拟了染色体组通过移位变异的分子生物学问题。该问题目前的 研究成果，对于计算移位距离，有时间复杂度为o ( n 2 ) 的算法，对计算移位步 骤，其算法的时间复杂度为o ( n 2 l o g n ) 。本文总结了前人的研究成果，并对计 算移位距离的问题进行了深入的研究，大大改进了其时间复杂度，提出一个 计算移位距离的时间复杂度为0 ( h ) 的算法。然后，设计了数据结构，提出了 算法的实现，取得了实验数据，验证了算法。本文的算法实现，在计算5 0 0 0 0 个基因的移位排序时，用时为3 0 秒。 本文的研究，1 ) 总结并详细叙述了有符号排列的反转排序问题的算法前 人研究中的错误，予以更正，并给出了优化的实现方法；2 ) 改进了有符号染 色体组的移位排序问题算法，同样给出了高效的实现方法。本文的研究成果 和实验数据，对于将其应用于实际工作具有重大的意义。 山东大学硕士学位论文 关键词：反转移位基因重组 山东大学硕士学位论文 a b s t r a c t g e n o m er e a r r a n g e m e n t s i sac o m m o nm o d eo fm o l e c u l a r e v o l u t i o n ，i f r e p r e s e n te v e r yg e n eb yas i g n e dn u m b e r , t h es t u d yo fg e n o m er e a r r a n g e m e n t s w i l lb et r a n s f o r m e dt ot h es t u d yo fs o r t i n ga l g o r i t h m t h es o r t i n ga l g o r i t h m sf o r t h eg e n o m er e a r r a n g e m e n t ss h o w e da na s t o n i s h i n ga c c u r a c yf o rb o t hs i m u l a t e d a n db i o l o g i c a ld a t a s o ，t h es t u d yo fs o r t i n ga l g o r i t h mf o rg e n o m er e a r r a n g e m e n t s s t a n d sa i m p o r t a n tp o s i t i o n i nm o l e c u l a r b i o l o g y t h i sp a p e r f o r m u l a t e st w o b i o l o g yp r o b l e m si ng e n o m er e a r r a n g e m e n t s - - s o r t i n gs i g n e d p e r m u t a t i o nb y r e v e r s a l sa n d s o r t i n gb y t r a n s l o c a t i o n s t h et w o p r o b l e m s s i m u l a t et h e r e a r r a n g e m e n t si ns i n g l ec h r o m o s o m e a n d g e n o m e s s o r ts i g n e dp e r m u t a t i o nb yr e v e r s a l s e v e r yg e n ei nt h ec h r o m o s o m ec a n r e p r e s e n t e db y a s i g n e dn u m b e r s o ，t h es t u d yo fg e n o m ee v o l v i n gb yi n v e r s i o n si n m o l e c u l a rb i o l o g yl e a d st oas t u d yo f a l g o r i t h mf o rs o r t i n gs i g n e dp e r m u t a t i o nb y r e v e r s a l si nc o m p u t e rs c i e n c e p r e v i o u sw o r k sg o tt h ea l g o r i t h mf o r f i n d i n gt h e r e v e r s a ld i s t a n c ei n0 ( n ) t i m e ，a n df i n d i n gs e q u e n c ei n o ( n 2 ) t i m e t h i sp a p e r s u m m a r i z e st h e p r e v i o u sr e s u l t s ，p r e s e n t t h e o p t i m i z e d d a t as t r u c t u r ea n d i m p l e m e n t f o rt h e a l g o r i t h m ，a n da n a l y s i s t h ed a t af r o m e x p e r i e n c e f r o mt h e e x p e r i e n c er e s u l t ，t h ei m p l e m e n ti n t h i sp a p e rr u n s7 - 9t i m e sf a s t e rt h a nt h e c o m p a r i s o ni m p l e m e n t s o r t b yt r a n s l o c a t i o n r e p r e s e n t i n gg e n o m e s b y as e to f s i g n e d p e r m u t a t i o n s s i m u l a t et h es i t u a t i o no fg e n o m e se v o l v i n g b yt r a n s l o c a t i o ni n m o l e c u l a rb i o l o g y p r e v i o u sw o r k sg o tt h ea l g o r i t h mf o rf i n dt h et r a n s l o c a t i o n d i s t a n c ei no ( n 2 ) t i m e ，a n ds e q u e n c ei n o ( n 2 l o g n ) t i m e t h i sp a p e rs u m m a r i z e s t h ep r e v i o u sr e s u l t s ，a n d g i v e san e wa l g o r i t h mf o rc o m p u t i n gt h et r a n s l o c a t i o n d i s t a n c ei nd ) t i m e ，i m p l e m e n t st h ea l g o r i t h m ，a n dt a k et h ee x p e r i e n c e i ts p e n d s o n l y3 0s e c o n d st oc o m p u t e5 0 0 0 0 g e n e sb yt r a n s l o c a t i o n t h i s p a p e r ，1 ) g i v e o u tad e t a i l e d d e s c r i p t i o n f o rt h e p r o b l e m - - s o r tb y r e v e r s a l s ，t h ec o r r e c t i o n sf o rt h ef a u l t si n p r e v i o u sw o r k s ，a n da no p t i m i z e d e 山东大学硕士学位论文 i m p l e m e n tf o r t h ea l g o r i t h m ；2 ) p r e s e n t san e wa l g o r i t h mf o rt h ep r o b l e m - - s o r tb y t r a n s l o c a t i o n s ，a n ds h o w st h em e t h o d t oi m p l e m e n tt h ea l g o r i t h m t h er e s u l ta n d t h ee x p e r i e n c eh a sas i g n i f i c a n tm e a n i n g sf o rt h er e a lw o r k s k e yw o r d s ：r e v e r s a l ，t r a n s l o c a t i o n ，g e n o m er e a r r a n g e m e n t s 6 山东大学硕士学位论文 i 前言 宝物酶多样性楚由不断懿进化产生懿。尘镑送他懿蓉逶形式是基因耋缰。 分子生物学中的蒸困重组分析始予2 0 世纪3 0 年代求，当时d o b z h a n s k y 和 s t u r t e v a n t 发表了篇魈程碑式的文章，提出了对果蝇的1 7 对倒爨基因组进 行重组的思想。蕊因莺组的基本单位是染色体中的基因。2 0 世纪8 0 年代， 基因生物学的研究t 芷实了基因重缱经常通过反转( r e v e r s a l ) ，移位 ( t r a n s t o c a t i o n ) 和换位( t r a n s p o s i t i o n ) 三秘方式实现。蠢些生物缝掏比较楚 单，他们的染色体是单条的，比如线粒体，叶绿体，病毒，细菌等，他们的 基因重组经常通过反转p ( f ，) 的形式进行。对人，老鼠等高等的，复杂的生 物，拥有多条染色体，每条染色体中都存在着一定数目的基豳，若干条染色 镩梅藏染色体组，链翻懿基强重缀经豢逶过移位妒( 墨玩i ，玉来实琰。麦子基 因在染色体中是线性撼列，我们可以剥月有符号熬数序列来代表染色体，面 对这毖有符号整数序列的反转，移位和换位操作，就模拟了基因组的重组。 前人提出的算法，在模拟基因组的重组时，在模拟和生物学数据上得到了令 入谅辩的准确结莱。所以，对商符号整数序剜避行爱转( r e v e r s a l ) ，移位 ( t r a n s l o c a t i o n ) 亵挟经( t r a n s p o s i t i o n ) 熬谤究，在分子生物学上毒豢巨大敬意 义。本文主要关淀反转( r e v e r s a l ) 和移能( t r a n s l o c a t i o n ) 问题。 1 1 反转( r e v e r s a l l 2 0 世纪8 0 年代术，j e f f r e yp a l m e r 却同攀在植物组织细胞中发现一个值 得注意的，新奇的进化形式。他们比较了卷心菜和芜箐的线粒体，这两种线 粒体非常近似( 很多蘩因是9 9 一9 9 9 鞯相同) 。令他们惊奇的是，这些细胞， 尽管构成懿罄嚣尼乎完全一致，键在蘩因j | | 奚孝上鸯戏剧缝静麓剐( 冕蚕) 。 该发现以及随后十几年中的磅究涯实了基因蓬组足线粒 本，时绿体，痰毒， 细菌的d n a 进行进化的常见模式。 山东大学硕士学位论文 卷心英了j 卜了j 卜1 一 3 ，那么存在一个安全的反转p 将f 中的2 个 h u r d l e 拼按。 零l 璞1 。5 f 靶如莱h ( 嚣) = 2 ，都么存在一个安全静爱转将f 中的2 个h u r d l e 拱接。麴果h ( f ) = l ，那么存在一令安全豹反转姆中的唯一瓣h u r d l e 变为 有向连通部分。 引理1 6 姻l 令p 是坩中的拼接h u r d l el 和m 的一个反转。那么月中的 每一个s u p e rh u r d l e ( 不同子三和膨在片口中仍为s u p e rh u r d l e 。 孳| 璞l 。7 f 3 3 令c 是h a p p yc l i q u e ，e 是c 中一点，凇( g ) 为与e 邻接豹 无向边数。如果对任意的e c ，均有1 w ( g ) l f t o p e n d 。从而， 树始于t o p 、b e g h ；，终于t o pe n d ，两f 拊雉予f b e g i , ，是，孛一点，所以 必存在两袈选h ，歹，h t o p ，气 且冉写，相交。从而，与柏f 相交，怒一棒 糖。登 连理t 。2 ”算法生成的森称，每一棵树对直个连通部分。 证携a 注意到：由于初始状悉是出单蛄点辩组成的森林，当冀法扫插竞 排列中静第 个元素时，醴经生成盼森转是由0 f 这i + 1 个元素决定的。 8 ) 首先证明包含i 的樾中的点必定在包含f 的连遥帮分中 我们用关于i 的归纳法证明。 显然，当算法扫摘元豢0 目，命题成立，假设当掴搂到i - 1 对，命题也 成立， 当雾法扫拦到薷i 个无素对，如果f 是菜边豹左端点，撰据算法，森器教 缩成不变与扫描f 一1 元豢时相同，命题成立。如果i 时某选宫右端点，如 巢北时，b e g i n t o p ，b e g i ne 那么，与t o p 相交。厂与，印合为一褓树，从 而，叩所对应静连通部分辩，所对应瞬连通部分舍为一个连通部分。算法的 5 戮8 步完成这项z 搏。 ( b ) 再证明包古i 的连遴部分中触一点必定在包吉i 鸵树中 设有莸边( z ， ，) 和， ) ，满足f w g ( m ，显然遮两帑灰边均属予包古f 的 连通部分，髹掘薄法，这两条荻边也属于| 三lf 为根的子褪。 总之，算法生成船森林，每一裸树封应一个避通部分。口 山东大学硕士学使论文 2 2 3 。清除h u r d l e 的算法 本算法的时间复杂发是o ( n ) ，分2 部分，如聚排列是f o r t r e s s ，便用 第部分，否巅，健菊籀二部分。糖述如下。 算法1 3 第一部分：( 根据引理i 3 ，1 4 ，1 5 ，1 6 ) i 找到第i 个未标记的h u r d l e ，记为s t a r t 。 2 找到第2 个耒标记熬h u r d l e ，记为e n d 。如暴没毒第2 令，e n d = s t a r t ， 转4 。 3 找到第3 个未标记的h u r d l e ，取代筇2 个，记为e n d 。 4 在s t a r t 中任取个位置s ，e n d 中任取一个位谶e ，使得s e ，s 为 奇数，e 为偶数，撬行反转( s ，e ) 。 5 。妇果礴未处理的h u r d l e ，转l 。 6 结束。 第二部分：( 裰据弓f 鹱1 3 ，1 4 ，i 5 ) i ，鲡果h u r d l e 总数是镐数，转3 。 2 。找到第1 个末标记的s i m p l eh u r d l e ，避为s t a r t ，e n d = s t a r t ，转6 。 3 找到第1 个未标记的h u r d l e ，记为s t a r t 。 4 找到第2 个未标记的h u r d l e ，记为e n d 。 我虱第3 个未标涪静h u r d l e ，取代第2 个，记麓e n d 。魏果没有第3 个，e n d = s t a r t 。 6 在s t a r t 中任取个位置s ，e n d 中f _ 王驭一个位置e ，使得s e ，s 为 奇数，e 为偶数，执行反转( s e ) 。 7 细栗有未处理的h u r d l e ，转l 。 8 结束。 山东大学硕士学位论文 2 2 4 计算h a p p yc l i q u e 的算法2 计算h a p p yc l i q u e 的算法的时间复杂度为0 ( ) ，描述如下，其中l ( e ) r ( e ) 为e 的左右端点。c ，为团。 算法1 4 1 c 1 = e lj ，f 1 未定义，f = 1 ，e 0 = e l ，e l l = e l 2 如果r ( e 。) 三( e i + 1 ) ，c 是h a p p yc l i q u e ，退出 3 分条件处理 a 如果“已经定义，并且r ( f ，) 月( e f _ 1 ) 。则c h = g ，“： 。 b 如果，未定义或r ( e 川) r ( r ，) a ) 如果r ( 已) r ( g 1 ) 并且( e i + 1 ) r ( 已，1 ) 。g + l = c 。u e f 1 ，1 i + 1 = ， p i 2 e i + 1 。 b ) 如果r ( p u ) r ( e f i ) 并且三( e 】- 1 ) y r ( p 。1 ) 。c = 1 ) ，e i l = e “= e 川 t i 1 2 t io c ) 如果r ( e i + 1 ) r ( 。口) 。c i + l = j ，t m = e 口，e i l = e 口= 8 i 4 f = f _ 1 。转2 。 2 2 5 寻找h a p p yc l i q u e 中与最多无向边相交的有向边2 设c 中含有条灰边，按他们的左端点升序排列为：e 一，a e j 。显然， 上( 1 ) 上( 2 ) 三( ，) ( r ( 1 ) j r ( 2 ) 尺( ，) 。这巧个端点，将实数轴分为2 j + l 的区间，用如。，匆表示，其中，o = ( 一。，上( 1 ) ) ；对l 的，厶= 缸( 玑l ( h 1 ) ) ； 厶2 ( 上u ) ，r ( 1 ) ) ；对， t 2 j ，i t 2 ( 1 - j ) ，r ( 1 - j + 1 ) ) ；历= ( r ( ，) ，。) 。算法包含 一下3 个阶段。时间复杂度为o ( ”) 。 算法1 5 第一阶段 第二阶段 剥任一无向边e ，记录其左右端点在上述2 j + 1 个区间中的序 令0 是一元数组，作c 中j 条灰边的无向邻边累加器，初始 山东大学硕士学位论文 化为0 。对c 中的一点即e 的无向边相交数为：讲f 】。对任一无 向边g ，令 和 为l ( e ) 和尺( e ) 所在的区间，我们可以假设l r ，否 霹l 该无向逑无讨论的意义，魏聚其任一端煮位予 王( 1 ) ，露】，我髓 分条停 睾热下熬操作。 a ) 如果r - j ，则，意味着从啪到。的所有边与e 相窥。所以o 1 + 1 加1 ，0 r 十1 减1 。 b ) 如果，f ，则，意睬着觚。吁l 到e 。的所有透与e 稻交。所黻d f 寸 l 】 鸯瑟1 ，0 r 一产l3 藏1 ( 当， o ， 则意味着从e l 到e 。的所有边与8 相交，所以o 1 加1 ，o m + 1 减l 。如果m ( j ，那么从e 村到唧的所有边都与e 相交，增加计数 器o 胁1 。 第三除段：计算声掰凹 ：；。嬲il ? g ，返回争翻 说明一点，参考文献 2 中的算法在第二阶段的c ) 中，对条件考虑有错误， 上述的弊法融经改正。 2 3 。实现f s b r 算法的数据结构 算法主要涉及副以下的元素，辩瓢，边，连通部分，h u r d l e ，h a p p yc l i q u e ， 秣，反转，壤筏，算法1 5 中提虱靛区阉，算法1 5 辛记录髭肉迭端点掰在 区间号的数据结构。由于其中某些元素的结构相同，可以通用，因此，实际 实现的结构如下： 2 , 3 1 排列的实现 由于排列在整个算法的执行过程中长度不变，因此，排列可以用定长整 形数组存放，便于定位和使用。同样，由排列产生的镜像排列也用定长艇形 鼗组。 山东大学硕士学位论文 i n t $ e x t e n d e d p e r n u t a t i o n ： i n t f e v e r s e d p e r m u t a t i o n ： r e v e r s e d p e r m u t a t i o n 存放的是，利用它，对给定静元索，可以取 得捧列中斡位嚣。 2 3 2 边的实现 边粒数基是由n + i 赛定鹣，霹强预先分配好。每条灰边帮是凌不朝邻豹i 和十1 连接而成，虽然边可以由排列的值取得，但由于边奄整个算法执行过 程中频繁使用，并且在执行时涉及作标记，以及集合操作，因而边用一个结 构描述，并加入链表的功能。 st r u c t e d g e s i i n tl e f t ： i n tr i g h t ： c h a rb m a s k ： s t r u e t c o m p o n e n t c o m p o n e n t ； s t r u c te d g e s n e x t ： ) ： 2 , 3 3 。连避部分的实现 在边的o v 图中，连通部分由代表边的顶点组成，另外，在算法1 ，2 中， 使用的链表实现了各个连通部分的合并，因此，涟通部分主要是由一个边的 链表掾戒，叛及粥于作标记豹字莰，农雳于计算h u r d l e 鼢字段。 s t r u c t c o m p o n e n t c h a rb m a s k ： i n t h a n d e _ g ：幸对应子薄法1 2 中的e n d * i n t h a n d l e b ：芈对应予冀法1 。2 中戆b e g i n * 山东大学硕士学位论文 in ti n d e x ： i n tb l o c k n u m ： s t r u c te d g e s 母e d g e l i s t ：$ 边镰表 i n tn e i g h b o u r i ：# ：对应于算法i 。2 中的p a r e n t $ i n t n e i g h b o u r 2 ：$ 与n e i g h b o u r l 一起，用于计算s u p e rh u r d l e * 2 3 4 。h u r d l e 的实现 h u r d l e 实际上是一个满足特定条件的连通部分，因此，使用连通部分的 数据结构，鸯瑟一个特殊标记即可。 2 3 5 h a p p yc l i q u e 的实现 h a p p yc l i q u e 记录静是边酶一个子集，困诧莽 确数阖定后，h a p p y c l i q u e 故数星燃边数界定，为处理方便，提毫效率，采尽整形数组安瑷，其中存贮 的是h a p p yc l i q u e 的边序号。 i n t $ h a p p y c li q u e ： 2 3 。6 。c r 蠡皇实残 c r 记录的是排刿元索的个予集，因此排列数固定聪，c r 的数目由边数 界定，为处瑷方便，提高效率，采用整形数组实现，其中存贮的怒属予c r 的元素瓣位嚣窿号。 i n t $ c r ： 2 3 7 反转的实现 反转是对播到揩定弱个位鼍之魁的元豢进行毽霆和药号豹反转，因鼗它 只需要一个开始位簧，个结束位赞即可。 山东大学硕士学位论文 s t r u c tr e v e r s a l i n ts t a r t ： i n te n d ： ； s t r u c tr e v e r s a l $ r e v e r s a l s ： 由于反转数目由( b - c + h ) 和( b - c + h + 1 ) 决定，因此，其反转数组动态分配。 2 3 8 堆栈的实现 在算法1 2 中，每条边最多生成1 个新的连通部分，因此，堆栈受限于 边数，可以预先分配，用整形数组实现。 i n t 十s t a c k ： 2 3 9 区间的实现 区i n 与反转类似，也是只需要2 个位置即可，因此它直接使用了反转的 数据结构。但由于其数目受限于h a p p yc l i q u e 的数目，因此，动态分配。 s t r u e r r e v e r s a l i n t e r v a l s ： 2 3 1 0 记录无向边端点所在区间号的数据结构 该数据结构与反转类似，只需要2 个位置号，因此它直接使用了反转的 数据结构。其数目由边数界定，所以，预先分配即可。 山东大学硕士学位论文 2 4 实验 2 4 1 程序 对前述的算法，分别用c 语言和j a v a 语言进行了实现，用c 实现的目的 是为了提高效率，取得计算速度等数据，用j a v a 语言实现是为了作对比分析。 对比程序的原型使用的是j a v aa p p l e t ，由于是a p p l e t ，并且有很多的输入 输出以及显示功能，不便于作理论对比。因此，对其进行的简化，去掉其输 入输出部分，和显示部分，只保留其体现算法的部分。由于对比程序在编写 上有错误( 具体是，其反转直接记录了反转位置，这样，如果反转数多于1 个，前面执行的反转就会影响后面未执行的反转的反转位置) ，因此对其进行 了改j 下。另外，由于对比程序使用的递归，当排列数目较大时，会出现堆栈 溢出，因此，对实验数据的长度，限制在4 5 0 0 以内。在此基础上，将其编译 为二进制代码，可以直接执行，以便去处j v m 带来的影响。 为下面叙述方便，作如下约定： a 程序：用j a v a 语言对本文所述算法的实现程序。 b 程序：用c 语言对本文所述算法的实现程序。 c 程序：前述的，作对比的a p p l e t 作修改后的对比程序。 2 4 2 准备工作 由于c 语言运行速度较快，当排列长度比较小时，记录的时间不够精确 因此，实验数据的长度取为1 0 0 0 ，1 5 0 0 ，2 0 0 0 ，2 5 0 0 ，3 0 0 0 ，3 5 0 0 ，4 0 0 0 ， 4 5 0 0 共8 个。对每一个长度值，随机取排列，计算的是平均时间。列表如下。 f 长度 1 0 0 01 5 0 02 0 0 0 2 5 0 0 3 0 0 0 3 5 0 0 4 0 0 04 5 0 0 j 循环次数5 0 05 0 05 0 05 0 02 0 02 0 02 0 02 0 0 l 表一 对算法测试的计算机使用的是联想开天4 6 0 0 计算机，c p u 为p 4 一1 9 g 内存为3 8 4 mp c 2 1 0 0d d r 内存。 山东大学硕士学位论文 2 4 3 数据 计算得到数掘列表如下：( 单位：毫秒) i 长度 循环次。稷序b 程序c 程序c 程序肠程c 程序硒程序 数序 i 1 0 0 05 0 02 0 71 8 21 6 7 58 0 9 1 89 2 0 3 3 1 5 0 0 5 0 04 4 84 0 83 5 5 07 9 2 4 l8 ，7 0 1 0 | i 2 0 0 05 0 07 9 27 2 76 1 6 87 7 8 7 9 8 4 8 4 2 | 2 5 0 0 5 0 0i 2 4 6i i 3 2 9 5 1 07 + 6 3 2 48 4 0 j i i 3 0 0 02 0 01 8 l o1 6 2 51 3 6 6 77 5 5 0 8 8 4 1 0 5 i 3 5 0 02 0 02 5 8 52 2 2 4i 8 9 1 77 ，3 1 8 0 8 5 0 5 8 l 4 0 0 02 0 03 6 0 22 9 1 02 5 0 3 5 6 。9 5 0 38 6 0 3 l | 4 5 0 0 2 0 04 9 2 83 7 1 33 1 8 2 16 4 5 7 2 8 5 7 0 2 根据袭二所作的若干图表如下 表二 时雠c 毫秒) 9 5 口 譬s # ，。 t 6 5 辫疆3 个程j 擎速度绝对篷对瑟，注蕊豹辩闯萃链比8 ，b 夫1 0 倍。 j 獬1 5 2 0 呻蝴口 3 0 艚端舯 帅4 5 1 1 0 醋美3 个程序汁箅时问比率曲线 些奎奎堂塑主堂垡堡壅 2 4 4 分析 4 1 对算法的验证 d ，b 程序实现了本文所述的f s b r 算法，其中，步骤( 1 ) 计算连通部分的 时间复杂度是0 ( h ) ，步骤( 2 ) 清除h u r d l e 的时间复杂度是d ( ) ，步骤( 3 ) 一( 6 ) 的时间负责度为0 ( ”2 ) 。总体时间复杂度为o ( n 2 ) 。根据图四，a ，b 程序的 计算时间呈现了明显的二次曲线，算法及其实现是符合的。 c 程序实现的算法，其中，计算连通部分的时间复杂度是0 ( n 2 ) ，其他与 f s b r 算法相同，这样，总体的时间复杂度是0 ( 2 ) 。根据图四，6 程序的时 间计算呈现了明显的二次曲线，算法及其实现也是符合的。 n ，b 与c 程序的理论区别在于计算连通部分的算法不同，其时间复杂度 一个是o ( n ) ，一个是口( ) ，但总体的时间复杂度是相同的，都是0 ( ”2 ) 。当 n 比较小时，计算连通部分的算法所节省的时间，对总时间节省的贡献就比 较大，但当一较大时，其节省的时间的贡献度就很小了。这意味着当一较大 时，两种算法的计算时间比率应基本是一条水平线。从图五中的曲线c a 可 以看到，当n 增大时。计算连通部分的时间节省，对总时间节省的贡献度越 来越小。从图五中的曲线c b 可以明显看出，当n 增大时，两个程序的计算 时间比率曲线基本水平了。 1 矗垂2 对执行时间对比的分析 从d ，b 与c 程序的执行时间对比上可以看到，c 程序要慢很多。分析其 原因，主要有以下几点： 1 ) c 程序使用的算法理论上要比a ，b 程序的算法慢， 2 ) c 程序使用了递归计算连通部分，导致速度降低，还有可能造成溢出， 3 ) c 程序中对边没有使用单独的数据结构，导致每次使用边进行计算时， 都要根据排列的值计算出边。 4 ) c 程序大量使用了类，使用数组较少，虽然类的逻辑性较好，但其分 配，释放效率复杂，工作效率远比数组差。 5 ) c 程序使用了j a v a ，虽然不用处理内存释放，但也导致了执行效率大 大降低。 山东大学硕士学位论文 从。，b 程序的对比上看。虽然都使用的一样的数据结构，一样的程序流 程和语句，但计算时间也有差异，这差异就是由于j a v a 语言和c 语言的差异 引起的，从比值可以看到，当都编译成可以在本机执行的二进制代码后，差 异并不是很大了。 山东大学硕士学位论文 3 对有符号t r a n s l o c a t i o n 问题的改进 3 1 基本概念 移位( t r a n s l o c a t i o n ) p n 7 题是对由多个染色体组成的染色体组的基因黧组的 模拟。其 l i f 提是，对染色偻组a 中的任一基因x ，x 仅嫩理于蠢中的一条染 色体上且仅出现次，这意味着以中没有任何2 个基因相同。染色体组用移 袋方式进孳亍基銎蘩组，蹩两条染色体x ，只分裂蓐，耋凝攒按戏2 条巍染色 体的过程。我们将，y 袭示为：x = x i x 2 ，x 。，y = y i ，y 2 r o l l i h ，移位是将x ， y 分裂为两段：溉，噩) ，( b ，如) ，然螽盖豹一段与y 酌一段褒瑟裂簸重薪 遣接，产生两条新的染色体，例如生成( 硒，y 2 ) ，( y l ，局) 。根据分裂质连接 方式的不弼，有两种移位方式：静前移位和前焉移位。前前移位p p p 己ef f ，力 产生两条新染色体置1 2 - - ( x l ，一，x 。y j + l ，弛) 和h 噩= l ，胁，x i + l ，) ， 前后移位m ( 置ei ，) 产生两条新染色体蜀一e i = ( x i ，x 。功，7 1 ) 和 峨y 2 = ( - x r a ，馏一l ，玲扩一，始) ；由于在毙较嚣条染色体时不考虑方穗，五 y 上的前厢移位与x ，叫上的前前移位烧等价的。参见图六。旗因的断开与 逡续劳不是宠全夔意懿，2 个要连接豹蒸霆必缓露霹鸯连接点方可疆逡蒗。 例如，图六中蜀的最左赫因没有左连接点，而局的最右基因没有右连接点。 绘定2 个染色体缀a 与嚣，翔采省豹基因集合鲋) 与b 酌萋函鬃台痰雪) 糈同， 并且4 与四的所有基因的连接点也相同，则爿才有可能通过移位操作变为b 。 a 与君之间的移位距离记为硪矗，b ) ，筒记为或矗) 。我们称任何一组将a 变为 嚣的移位搽作为a 到占的进化过程。 赫螽菲阻，一受童 厂可r i 1 i 一 y ， ￥j 。一，x ii - y 一一一“一一= l i 薜转他x ，y 、 一一一一一+ ”r 一 銎六蒋前移霞与蔫螽移毯 山东大学硕士学位论文 一 为研究方便，通常将目标染色体组b 设为标准的形式，即，对b 中任一 条染色体的任2 个相邻元素x ，x i + l ，令lx i - - x i + 1 1 2 l 。 对染色体x 与n 称x 与】，是相同的，当且仅当x = y 或弘一y 。对染色 体组a 与b ，称4 与b 是相同的( 4 = b ) ，当且仅当a 与b 中对应的染色体是 相同的。对一个染色体组a 和对其进行的移位操作p ，我们将移位后得到的 染色体组记为a p 。 对染色体组a = 1 4 2 ，a ) ，我们构造映射染色体组a ，规则如下：为 了模拟a ，中元素的方向，将正元素+ x 用2 x i ，2 x 代替，将负元素一x 用2 x ， 2 x - 1 代替( 图七) ，称为染色体组a 的映射染色体组。每条染色体中的元素的 序号从i 开始编号。为叙述方便，本章以下文字中的染色体组，均指映射染 色体组a ：而对4 ，称为原染色体