(计算机软件与理论专业论文)基于第一降序小队翻转排序算法的设计与实现.pdf_第1页
(计算机软件与理论专业论文)基于第一降序小队翻转排序算法的设计与实现.pdf_第2页
(计算机软件与理论专业论文)基于第一降序小队翻转排序算法的设计与实现.pdf_第3页
(计算机软件与理论专业论文)基于第一降序小队翻转排序算法的设计与实现.pdf_第4页
(计算机软件与理论专业论文)基于第一降序小队翻转排序算法的设计与实现.pdf_第5页
已阅读5页,还剩45页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

山东大学顼尘学位论文 摘要 基因组翻转排序在基因组重组研究与实践中具有重要价值,本文研究基因组 翻转排序的计算方法。基因组翻转排序目的是计算两个基因组之间的最少翻转次 数,最少翻转次数称为两个基因组之间的翻转距离。有向基因组翻转排序由 h a n n e n h a l l i 等最先给出多项式时间求解算法,目前所知最好的算法时间复杂性 为o ( n 2 ) 。无向基因组翻转排序由c a p a r a 证明为n p h a r d 。 已有的无向基因组翻转排序算法过程复杂,实现困难。本文提出了无向基因 组翻转排序的一种新启发式算法,编程实现了该算法,本文简称为f d s r 算法。 在p e n t i u m i i l 8 0 0 2 5 6 m 计算机上的实验表明,f d s r 计算1 9 3 个基因符号的翻转 所需计算时间为1 0 毫秒,计算5 0 0 0 符号的基因组翻转所需计算时间为1 2 8 2 秒。本文证明了算法的正确性。我们利用程序验证了算法求解的优化程度,实验 结果表明,对于1 0 0 个较小的基因组,用本文算法得到的解中有6 8 个为最优解。 f d s r 算法主要思想为,先在基因排列中找降序小队,在其末元素和逆相邻 元素之间作相应的翻转操作。算法难点在于当基因排列不存在降序小队时,需要 通过调整获得降序小队。 程序的实现过程是,首先设置并初始化一个基因排列的存储空间,然后读入 基因排列的数据项,接着校验基因排列是否正确,若正确则对其进行断点式转换 并进行翻转排序,否则中止程序的运行。 本文创新点表现在下面几个方面: ( 1 ) 本文将两个断点之间的部分序列称为一个断点式。通过翻转断点式使断 点的个数逐步减少,从而接近目标基因组序列。 ( 2 ) 论文中提出了第一降序小队概念。降序小队是翻转断点式的基点,采用 第一降序小队作为基点可以减少查找基点的时问,从而提高了算法的时间效率。 ( 3 ) 论文给出了算法的正确性证明,算法时间复杂度为o ( n b ,n 为基因排列 中基因个数。 山东大学硕士学位论文 ( 4 ) 设计并用c + + 语言实现了翻转排序算法。在算法实现中,基因排列的存 储空l 日j 不仅能存储数掘,还能够根掘需要存储断点。利用增加空问的方法,减少 确定断点式和翻转断点式等操作的时i 日j 。 关键词:算法,基因组,重组,翻转排序 山东大学顼士学位论文 a b s t r a c t t h eg e n o m er e v e r s a ls o r t i n gi so f g r e a ti m p o r t a n c ei nr e s e a r c ha n dp r a c t i c ef i e l d t h i s p a p e rm a i n l yd i s c u s s e st h es o r t i n ga l g o f i t h r m t h eg e n o m er e v e r s a ls o r t i n ga i m sa t c a l c u l a t i n gt h el e a s tr e v e r s a ls o r t i n gt i m e sb e t w e e ng e n o m e s ,w h i c hi sc a l l e dt h e r e v e r s a ld i s t a n c eb e t w e e ng e n o m e s h a n n e n h a l l ia n dh i sg r o u pp u tf o r w a r dt h e o r i e n t e dg e n o m er e v e r s a ls o r t i n gt h r o u g hp o l y n o m i a l - t i m es o l u t i o n s ,a n dt h e b e s t - k n o w na r i t h m e t i ct i m ec o m p l e x i t yi s0 ( 以2 ) a n dc a p a r ah a st e s t i f i e dt h e u n o r i e n t e dg e n o m er e v e r s a ls o r t i n gt on p - h a r d t h ep r e s e n tu n o r i e n t e dg e n o m er e v e r s a ls o r t i n ga l g o r i t h m sa r eo f t e nt o oc o m p l e x a n du n i m p l e m e n t e d t h ep a p e rp u t sf o r w a r dan e wh e u r i s t i ca l g o r i t h mn a m e df d s r a l g o r i t h m , a n di m p l e m e n t st h ea l g o r i t h mb yp r o g r a m m i n g f d s rc a nc a l c u l a t ea g e n o m ep e r m u t a t i o ns i z e d1 9 3w i t h i no 0 1s e c o n da n d5 0 0 0w i t h i n1 2 8 2s e c o n d s u n d e rp e n t i u m l i l 8 0 0 2 5 6 mp l a t f o r m i ts h o u l db en o t e dt h a tt h ec o r r e c t n e s so fo u r a l g o r i t h mh a sb e e nd e m o n s t r a t e di nt h i sp a p e r w ev a l i d a t et h eo p t i m i z a t i o nb y p r o g r a ma n dt h er e s u l ts h o w st h a t6 8v a l u e sa r eb e s to n e sd e r i v e df r o m1 0 0l e s s e r g e n o m e sb yf d s rm e t h o d t h es o u lo ff d s ra l g o r i t h mi sf i n d i n gt h ed e s c e n d i n gs t r i pi np e r m u t a t i o na n d t h e nm a k eac o r r e s p o n d i n gr e v e r s a lo p e r a t i o nb e t w e e nt h el a s ti t e ma n dt h e c o n - a d j a c e n to n ee v e r yt i m e h o w e v e r , t h ed i f f i c u l t ys h o w st h a tp e r m u t a t i o nn e e d st o t r a n s f o r mt oa c q u i r ed e c r e a s i n gs t r i p sw h e nt h e yd on o tp r e s e n t o u rp r o g r a mi so u t l i n e da sf o l l o w s :s e t t i n ga n di n i t i a l i z i n gc e r t a i nm e m o r ys p a c e f o rt h ep e r m u t a t i o n , t h e nr e a d i n gt h ei t e m sa n dc h e c k i n gt h ev a l i d i t yo fp e r m u t a t i o n i ft h ev a l i d i t yc h e c kp a s s e st h ep r o g r a mw i l lm a k eb r e a k - p o i n t sc o n v e r s i o na n d s o r t i n gb yr e v e r s a li sc o n t i n u e d o t h e r w i s e ,t h ep r o c e d u r ew i l ls t o p t h ei n n o v a t i o n so f t h i sp a p e rc a nb ed e s c r i b e di nf o u ra s p e c t s ( 1 ) t h i sr e s e a r c hb r i n g sf o r w a r dt h ec o n c e p to fb r e a k p o i n t f o r m ,w h i c hi st h e p a r tb e t w e e nt w ob r e a kp o i n t s b yr e v e r s i n gt h eb r e a k p o i n t f o r m ,t h en u m b e ro f t h e b r e a kp o i n t sc a nb er e d u c e dl i n l eb yl i t t l ea n dr e a c h e st h et a r g e tg e n o m e 山东大学硕士学位论文 ( 2 ) t h ef i r s t d e c r e a s i n g s t r i pc o n c e p ti sp u tf o r w a r di nt h ep a p e r , t h ed e c r e a s i n g s t r i pi st h eb a s i so fr e v e r s a ls o r t i n g t h i sc o n c e p tc a nr e d u c et h et i m ef o rf i n d i n t h e b a s ea n di m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m ( 3 ) t h ev a l i d i t yo ft h ea l g o r i t h mi sv e r i f i e da n dt h ea l g o r i t h mt i m ec o m p l e x i t yi s 0 ( n 气w h i c h n m e a n st h es i z eo f g e n o m ep e r m u t a t i o n ( 4 ) a na l g o r i t h ms o r t e db yr e v e r s a l si s d e s i g n e da n dc o m p l e t e dw i t hc + + p r o g r a m m i n g l a n g u a g e - i no u rp r o g r a m m i n g t h em e m o r ys p a c eo fg e n o m e p e r m u t a t i o n sc a ns t o r en o to n l yt h ed a t a , b u ta l s ot h eb r e a k p o i n t w ec a nr e d u c et h e o p e r a t i o nt i m eo ff i n d i n gb r e a k p o i n t f o r ma n dt r a n s f o r m i n gi tb ye x t e n d i n gt h e m e m o r ys p a c e k e yw o r d s :a l g o r i t h m ,g e n o m e ,r e a r r a n g e m e n t ,r e v e r s a ls o r t i n g 原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进 行研究所取得的成果。除文中已经注明引用的内容外,本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体,均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名:囱鑫翌 日 期0 竺( :生:丝 论文作者签名:钠辜翌 日期:泣6 :生:丝 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定,同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版,允许论文被查阅和借阅;本人授权山东大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名:垃导师签名:躯糙日期:喇f 髟 山东大学顼士学伍论文 第一章前言 基因是染色体上的组成部分,是遗传物质的结构单位。正是染色体中基因不同次 序造就了多彩缤纷的大自然。基因的变化导致生物的遗传、变异、进化,把两组基因 序列进行比较的意义在于它能为我们提供两个物种之间相近的程度、同一物种之间的 变种对比以及不同物种染色体中的相同基因片段的提取f 。 通常,衡量两个基因序列的相近程度的方法是衡量从其中的一个“变换”到另外 一个的容易程度。这种“变换”的形式主要有缺失( d e l e t i o n ) 、重复( d u p l i c a t i o n ) 、倒 位( i n v e r s i o n ) 、易位( 又称迁移,t r a n s l o c a t i o n ) 等形式。缺失,指染色体上的某一区 段及其带有的基因一起丢失而引起变异的现象;重复,指染色体上增加了相同的某个 区段因而引起变异的现象:倒位,指染色体上某一区段连同它带有的基因序列发生的 倒转并引起变异的现象 2 1 ;易位,指两对非同源染色体之间发生某个区段转移的畸变现 象。这些变换中,倒位被认为是最重要的,它并没有改变基因的数目,只是按照一定 规则重新排列了基因序列,故被广泛研究。由于基因在染色体中是线性排列,我们可 以利用有符号整数序列来代表染色体,而对这些有符号整数序列的反转,移位和换位 操作,就模拟了基因组的重组。用排序算法模拟基因组的重组,在模拟生物学数据变 换上取得了令人惊异的准确结果。因此研究基因重组算法对分子生物学中的生物进化 具有非常重要的意义 3 j 。 从基因序列的一种形式变化为另外一种形式,称之为演化;进行基因形式演化需 要的次数称为演化距离。基因翻转排序算法是用来描述如何计算基因组间的翻转演化 距离。研究人员更感兴趣的则是最小翻转演化距离,即从染色体种形式到另外一种 形式所需要的最少的翻转次数。 t r a n s l o c a t i o n 问题自提出以来,取得了很多的成果,无符号的t r a n s l o c a t i o n 问题是 n p h a r d 4 1 ,本文只关注有符号的t r a n s l o c a t i o n 问题。s h a n n c n h a l l i 在1 9 9 5 年首次给出 了对有符号t r a n s l o c a t i o n 问题求解的时间复杂度为o ( n 3 ) 的多项式算法 s l 。2 0 0 1 年朱大 铭,马绍汉将h a n n a l h a l l i 算法的时间复杂度改进为o ( n 2 l o g n ) t 6 1 ,其中只计算移位距离 ( 不给出移位序列) 的算法的时间复杂度为o ( n 2 ) 。迄今为止,计算移位距离的时间复杂 度没有更迸一步的改进。 最小翻转排序序列是存在的,在探索基因重排方面,获取最小翻转排序是非常有 。- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一一 1 山东大学顼士学位论文 用的。在过去的几十年中,在研究、计算翻转距离以及寻找最小翻转排序序列方面都 取得了很大的进步。研究者已经证明了无符号翻转排序是n p h a r d 7 1 并且给出了若干种 近似算法,包括2 - a p p r o x i m a t i o n 、1 7 5 一a p p r o x i m a t i o n 、1 5 一a p p r o x i m a t i o n 1 9 1 1 2 0 1 和1 3 7 5 a p p r o x i m a t i o n t 8 1 【1 3 1 ,目前最优的近似算法近似度为1 3 7 5 a p p r o x i m a t i o n 。 有符号翻转排序的多项式时间算法也被广泛的研究。s h a n n e n h a u i 和p a p e v z n e r 在1 9 9 5 年首次给出了对有符号排列的时间复杂度为o ( n 4 ) 的多项式算法f ”,1 9 9 6 年将 其性能改进为时间复杂度为o ( n 2 饵n ) ) p 】。1 9 9 8 年,h k a p l a n ,r s h a m i r 和r e t a r j a n 提出了时间复杂度为o ( n 2 ) 的对有符号排列进行反转排序的多项式算法( 简称k s t 算 法) 【l 们,这是目前已知的最快的算法,其中计算连通部分( c o n n e c t e dc o m p o n e n t ) 的时间 复杂度为o ( n 口q ) ) 。d a b a d e r ,b m e m o r e t 和m y a n 在2 0 0 1 年给出的算法( 简 称b m y 算法) 【1 1 】将其中计算连通部分的时间复杂度降为o ( n ) ,同时也使得只计算反转 距离( 不给出反转步骤) 的算法的时间复杂度降为0 白) 。 本文在对基因的翻转排序问题研究的基础上,提出了无符号翻转排序的一种近似 算法一基于第一降序小队翻转排序算法( f d s r 算法) 算法建立在基因排列的断点式 基础之上,通过翻转当前排列不断减少与目标排列的距离,直到翻转结果等于目标排 列。作者在w i n d o w s2 0 0 0 环境下用v i s u a lc + + 6 0 实现了这一翻转排序算法以及所 有有关的辅助过程和函数,讨论了相应的数据结构和流程图,并对算法进行了数据测 试和效能分析。在理论上,该算法的近似度为2 - a p p r o x i m a t i o n ,大量的实验结果表明, 该算法实际效果接近1 5 - a p p r o x i m a t i o n 。 2 山东大学顼士学位论文 第二章课题研究的背景知识和讨论规则 2 1 背景知识 我们可以把感兴趣的基因序列中的每一个基因做一个唯一正整数数字标识。这样一 来,基因序列便成为一个单纯数学意义上的排列,计算遗传距离的问题转换成为变换 数学排列的问题1 1 2 1 。例如,某个基因a 的序列顺序是:4 6 l723589 ;另外一个基因 序列b 顺序是:12345678 。从a 翻转到b 可以经过如下变换: 4 6 1 7 2 3589 4 6 l532789 4 235 16789 4 23 156789 l3 2 45678 9 123 45678 9 结束 再如,a = 3l6 254 ,b - 25 16 4 3 a 变换到b 的过程可以先作预处理,将b 转化为b :l23 456 ,即 2 一l 5 2 1 3 6 - 4 4 - 5 3 6 按照同样的规则转换a 为a ,:634 l25 。这样,a 到b 变换过程就是任意一个序 列变换为l23456 的过程,而a 变换到b 的过程等价于a 变换到b 的过程。基于上 面的讨论,我们可以看出,计算演化距离的问题都可以转换为一个普通排列变换为原 始排列123 n 的过程1 2 0 1 。 对任意排列进行一系列翻转获取原始排列的过程称作翻转排序。由于翻转排序的 目标序列总是l23 n ,这一过程可以被认作是一个排序过程,但是这并不是普通的 排序。普通的排序要求的是对一组无序的数据项根据某个关键字进行重新排列以便在 3 山东大学顼士学位论文 不丢失任何数据项的前提下得到这组按这个关键字排列有序的数据。翻转排序的过程 是排序的过程,但是方法上必须遵守翻转的规则,目标是追求最少的翻转排序次数。 通过最小数目的翻转得到原始排列的翻转排序称作最小翻转排序。 例如,将排列l367 452 进行翻转排序,可以得到序列: 136 7 452 136 254 7 l36 2 457 l32 6 457 132 4 65 7 l32 456 7 123456 7 这个翻转排序不是最小翻转排序,因为下面的翻转次数更少: l36 7 452 154 7 632 15 4 326 7 l234567 对于排列12 i j n ,令i 和j 之间的数据翻转,可以得到序列l2 i 1jj l i + l i j + i n ;我们也可以将其记做l2 i 1 _ j - ( i 1 ) - ( i + 1 ) - ij + 1 1 1 。我们称第一种翻转形 式为无符号翻转,称第二种形式为符号翻转。1 9 9 7 年a c a p r a r a 证明了无符号翻转排序 问题属于n p h a r dp r o b l e m ,而符号翻转可以在多项式时间完成 7 1 。 2 2 相关规则 基因翻转排序问题转化为纯数学意义的排列问题,原始排列需要满足下面的规则 1 4 1 。 规则1 :排列中的数据仅为自然数l 到n 或者它们的相反数。 规则2 :不考虑排列中数据的正负,若i ,j 出现在排列中,且存在k 满足i k j , 则k 必须出现在排列中。 在排列变换过程中,还要遵循如下规则: 规则3 :任何的数据在排列转换中不允许丢失 4 山东大学硕士学位伦文 规则4 :任何的数据在排列转换中不允许重复。 例如,序列11 5 2365 - 4 不是正确的基因翻转排序闯题的序列,因为1 5 不是自 然数:再如l23 5 6 也不是正确的序列,因为其中缺少数据项4 。 、 若某一个原始序列为321 4 5 6 ,则它的如下变换均不正确: a :12 4 5 - 6 b :l23 4 5 67 因为a 比原始序列缺少了数据项3 ,而b 比原始序列增加了数据项7 。 规则1 确保了排列中的数据项均为自然数;规则2 限制了排列中的数据项必须是连 续的自然数:规则3 和4 分别确定了连续自然数中不能有间断和重复。我们讨论的每 一个基因排列必须满足上面4 个规则,同样满足以上4 个规则的排列都可以被认作基 因排列来讨论。 山东大学碾士学位论文 _ ! ! g 自g | 目g i 一i e s ! e s ! 目! s s ! ! 自! ! ! 自 第三章基因翻转排序理论基础 3 1 概念和符号 在第二章第一部分中我们已经介绍了一些概念,为了更准确地描述算法并且不引起 解释上的二义性,下面对本文所涉及的概念和符号进行定义。 从基因序列的一种形式直接变化为另外一种形式称为演化( e v o l u t i o n ) ;把一个 基因序列通过演化为另一个所需要的次数称为演化距离( e v o l u t i o n a r yd i s t a n c e ) 。 把感兴趣的基因序列中的每一个基因做一个唯一正整数数字标识,这样,基因序 列便成为一个数学意义上的排列,计算演化距离问题转换成为变换数学意义上排列的 问题,这种排列称作基因排列( g e n o m ep e r m u t a t i o n ) 。针对基因序列的特点,我们规定 基因排列必须满足下面的条件: ( 1 ) 排列所有的数据项必须为正整数。 ( 2 ) 排列中任何两个数据项不能相等。 ( 3 ) 若i ,j 出现在排列中,且存在k 满足i k j ,则k 必须出现在排列中。 对应于基因序列的演化,相应的基因排列转换称作排列重排( p e r m u t a t i o n r e a r r a n g e m e n t ) ,简称重排。根据重排时排列中对应的数据项是否改变其正负号,排列 重排分类为有符号重排( s i g n e dp e r m u t a t i o nr e a r r a n g e m e n t ) 和无符号重排( u n s i g n e d p e r m u t a t i o nr e a r r a n g e m e n t ) 。在排列倒位重排中,分别称作有符号翻转( s i g n e dr e v e r s a l ) 和无符号翻转( u n s i g n e dr e v e r s a l ) 。一个排列翻转重排为另一个排列需要的最小次数称 为翻转距离( r e v e r s a ld i s t a n c e ) ,整个翻转过程称作翻转排序( s o r t i n gb yr e v e r s a l ) 。 获取符号翻转距离存在多项式时间算法,而获取无符号翻转距离的算法为n p - h a r d ,所 有实现的无符号翻转算法均是近似算法。 任一个无符号翻转排序可以被转换为某个相应排列翻转为原始排列( 1 ,2 ,n ) 的过程,文中后面部分给出了证明。这个过程不同于普通意义下的排序,因为其寻求 的是最小翻转次数。 令霄和咖是无符号的尺寸为n 的源排列和目标排列,假设萨( 百i ,赴,百n ) , 步幽,也,) 。由于翻转排序总可以看作某个排列变换为原始排列的过程,所以目标 排列可以总是被认作原始排列【1 6 】【1 8 l 。 对于任意基因排列庐( 饥,而) ,称排列( 而,m l ,r j ) 为霄的子排列( 1 i i n ) ; 6 山东大学顽士学位论文 若讯l = 百i + 1 ,称1 l ;和l i + i 相邻( a d j a c e n t ) ,若宵l = 坼l + l ,称百i 和稚l 逆相邻 ( c o n a d j a c e n t ) ;若陬i i 再,称噩和坼l 间存在断点( b r e a k p o i n t ) 。为了便于后面 算法的设计以及实现,我们扩展霄为百,_ ( 0 ,雨,霄2 ,靠,n + 1 ) 。所有连续不存在断点 的相邻项或者逆相邻项形成一个小队( s t r i p ) ,小队中各项排列的次序为升序则称作升 序小队( a s c e n d i n gs t r i p ) ,小队中的项的次序为降序则称作降序小队( d e s c e n d i n gs t r i p ) , 同时规定,仅有一个项的小队为降序小队,0 和n + l 作为独立项则始终认作是升序小队; 若另一个基因排列步西l ,晚,氐) ,如果对于所有的项,均满足i 产哦( 1 童鱼) ,称基因 排列f 等于( e q u a l ) 咖记作百;西。 无符号翻转p ( i j ) ( 1 童,j 鳓作用于铲( 百1 ,葡- l ,k ,硒+ j ,司,码+ l ,葡) , 则f 变换为( 劬,面- 1 b ! 茑= 12 = 2 坠! ! 巫l 即而”记作p o , j ) 霄。符号翻转p ( i j ) ( 1 童, j 鱼) 作用于霄= ( 而,而- l ,纽:坐! := ! d ,即l ,) ,则1 r 变换为( 雨,雨1 b ! :当= l - :! :篓! ! ! : 即,) ,也记作p ( i ,j ) 。百。寻找一系列的翻转p t p 2 p 。使 咖- p i p 2 p m 霄,这一个过程就是翻转排序的过程,m 称为翻转距离悯。 某一基因排列萨( 23654 17 ) ,其中,2 和3 是相邻的,6 和5 、5 和4 是逆相邻 的。3 和6 之间存在断点,同理4 和l 、1 和7 之间也存在断点。23 形成一个升序小队; 654 也是一个小队,不过它是一个降序小队。为了更清楚的表述相邻和断点,我们将 排列百记为: 23 ,654 ,l ,7 上面的形式为排列霄的断点式( b r e a k p o i n t f o r m ) 。霄的扩展形式的断点,椭: 0 ,23 ,654 ,1 ,78 符号翻转p ( 3 ,5 ) 作用于r 的结果是: 0 ,23 ,_ 4 一s 一6 ,1 ,78 无符号翻转p ( 3 ,5 ) 作用于r 的结果是: 0 ,23 4 56 ,l ,78 需要注意的是,由于无符号翻转p ( 3 ,5 ) 的作用,结果中原来的小队23 和654 将合 并成为一个小队23456 ,并且,3 和6 之间的断点也消除了。 我们讨论的是无符号翻转的近似算法设计和实现,所以后面涉及的翻转若无特殊说 明都是无符号翻转。 7 山东大学顼尘学位伦文 3 2 引理以及引理证明 基于上面的定义,我们给出了下面的引理和证明。 引理1 :假设冒和币是两个尺寸为n 的无符号基因排列,其中霄= ( t i ,砚,百n ) , 咖= 砸l ,曲2 ,西。) 。存在一个尺寸为n 的无符号基因排列1 r ,- ( 百j ,百2 ,t r n ) ,其翻转排 序为原始排列( 1 ,2 ,n ) 的过程等价于霄翻转排序为曲。 证明:令映射f 为: 曲l - 1 西矿2 也一1 1 百是基因排列,根据基因排列的性质可知f 是单射;咖,也,a 是n 个相互不同的 整数,分别对应1 ,2 ,r l ,所以f 为满射。因此得出f 是一一映射。 令存f 乱即: 矾一f 瓢 巾f t 2 矾_ f - r 记f m , f 霄2 ,f - r 为矗i ,矗2 ,也。;其中,九 曲1 ,锄,札 ( 1 粤鱼) 。 由于百也是基因排列,同理可得上述对应也是一一对应。 所以,百翻转排序为等价于r 翻转排序为原始排列。 证明完毕。 引理2 :基因排列f 为原始排列或者逆原始排列当且仅当霄中无断点 证明; 充分性:根据原始排列( 逆原始排列) 以及断点的定义,显然丌中无断点; 必要性:假设百= ( 饥,霄2 ,) ,若百中无断点,则庐一= ( 百1 ,霄l + l ,劬斗小1 ) , 或者萨百,- ( 面,百1 1 ,而一n 1 ) 。基因排列r 中最小的项必然为雨,由于基因排列 中最小项为l ,所以霄l = 1 。可知r = ( 1 ,2 ,n ) ,霄为原始排列。同理,矿中最大 项为霄n = n ,可知霄,_ ( n ,n 1 ,1 ) ,1 r 为逆原始排列。 证明完毕。 8 山东大学顼尘掌位论文 3 3f d s r 算法 引理指明了任何两个排列翻转排序都可以转换为一个排列翻转排序为原始排列。 而任何排列都可以翻转排序为原始排列。下面的算法给出了翻转排序方法,它是采用 基于第一降序小队翻转原理将排列翻转排序为一个原始排列的算法f d s r 算法 ( f i r s td e s c e n d i n gs t r i pr e v e r s a l ) ,算法描述如下: 输入:基因排列庐( 霄1 ,百2 ,而) 输出:1 r 翻转排序为原始排列的翻转过程以及翻转次数。 b e 舀n : r e v e r s a l n u m = 0 :r e v e r s a l n u m 为翻转次数 扩展百为百k ( o ,霄1 ,霄2 ,n + 1 ) : 。 w h il e ( 百环是原始排列) b e g i n 若r 中除了0 小队之外的第一个小队是升序的,翻转使其变为降序; 寻找一中的第一个降序小队,假设为码,码一1 焉+ 】,1 【;( i 萼) ; 寻找雨的相邻元素秆1 ; 如果雨1 在t i 后方 翻转稚1 至而1 部分并输出该翻转; r e v e r s a l n 啪+ + : 如果而一1 在面前方 翻转雨一1 的下一项至百l 部分并输出该翻转; r e v e r s a l n u m + + : e n d : e n d : 3 - 3 1f d s r 算法描述 f d s r 算法的正确性容易证明。由于每次翻转都至少使得第一降序小队长度增加l , 并且当翻转到特定情况下( 降序小队最小元素与0 小队中最大元素相邻) ,第一降序 小队翻转定与0 小队结合,并消除了一个断点。直到最后,断点必然全部消除,翻转 排序完成。 f d s r 算法的有穷性也是显而易见的。由于每次翻转都让第一降序小队长度增加或 9 山东大学硬士学伍论文 者断点减少或者既增加长度又减少断点数目,而理论上可能存在最坏情况是在开始阶 段第一降序小队只增加长度不减少断点,中间阶段只减少断点而不增加长度,两个阶 段都能在有穷时间内完成,所以算法满足有穷性。 山东大学顽尘学位伦文 第四章算法设计与实现 c + + 语言作为一种高级语言,不仅仅继承并发扬了c 语言的高效率、强功能等特点, 并且还引入了部分面向对象特色。正因为如此,本文的所有算法描述都采用类c + + 代 码,而程序的编码、运行和测试都在v i s u a lc + + 6 0 集成开发环境中进行。 基因排列是典型的线性结构。存储线性表的方式有顺序存储和链接存储两种形式。 对于基因排列这样的线性关系,其上面的操作主要有:初始化、清空、翻转、赋值, 输出、验证等,对应于不同的存储方式,可能的操作有:判空、判满、求长度。下面 分析采用顺序存储和链接存储基因排列的各自的优缺点。 线性表的顺序存储使用方便,根据位置访问表中的数据效率极高。在基因排列的 初始化、清空、翻转三种操作的实现上,顺序存储结构比链接存储结构简单易行。基 因排列正确性检测以及操作的可执行性,使用顺序存储也较为简便。但是,由于顺序 存储中的存储空间是一次性申请的,所以可能出现申请的空间不足的情况;反之,若 预申请的空间过大,则造成了存储空间浪费。另外,为了避免出现下标越界的问题, 需要额外进行线性表的“判满”操作。 链接存储方式对于不确定长度的线性表存储效果较好,并且存储器利用率较高, 一般来说不会出现储存空间不够的情况。而不同的基因排列恰恰是不确定长度的线性 表,故用链接存储方式的存储效果比较理想。然而,对于初始化、清空、翻转等操作, 正好与顺序存储相反,其实现的复杂性要高一些。特别是,由于链接存储结构不能直 接定位线性表中的元素,所以对于翻转边晃的确认需要对整个线性表进行遍历。 在赋值和输出操作上,两者的可操作性基本相同。并且基因排列的尺寸一经确定, 便不允许变动,所以线性表的插入、删除、更新等操作基本不需要。 基于以上的分析,可以得出以下结论: l 采用链接存储方式易于存储,但是实现的复杂性高; 2 采用顺序存储方式,存储效率稍差,但是实现的复杂性低。 3 无论采用何种存储方式,线性表的长度不能改变。 使用c 抖中面向对象有关类的设计,不但可以令对象和操作紧密结合,还有利于 改善线性表的顺序存储的不足。通过在类中引入一个整数类型数据成员,让程序在运 行之前便确定基因排列的尺寸和存储尺寸,从而间接的确定序列的大小并且确定存储 山东大学顽尘学伍论文 的下边界;引入另外一个指针类型数据成员,用作记忆基因排列的首位置,以便对整 个线性表进行操作。这样一来,我们改善了顺序存储的不足并借助其效率高的优点, 设计如下的数据结构。 4 1 数据结构 基因排列中的每个数据项( i t e m ) 具有如下信息: 1 断点标志( i s b r e a k p o i n t ) 2 码值( d a t a ) 3 断点符号( s y m b ) 断点标志是布尔类型的成员,其作用是用来指示当前数据项是数据还是断点,其 值为t ( t r u e ) 的时候,表明当前数据项为断点,此时数据项的值为断点符号s y m b : 相反,当i s b r e a k p o i n t 取值为f ( f a l s e ) 的时候,当前数据项应为数据,数据项的值为 码值d a t a 的值。这样形成一个组合结构为:断点标志占用一个存储单元,码值和断点 符号共用一个存储单元。设计的数据项类结构为; c l a s sp e r m u t i t i o n l t e m p u b l i c : b o o li s b r e a k p o i n t ; u n i o n i m d a t a ; c h a rs y m b ; ) ; ; 整个基因排列( l i s t ) 包含如下信息: 1 头( h e a d ) 2 数据项指针( c u r r e n t ) 3 排列长度( l e n g t h ) 4 表长度( m a x l e n ) 5 排列( a r r a y ) 6 翻转距离( d i s t a n c e ) 山东大学顽尘学位论文 7 初始化( i n i tp e r m u f i f i o n ) 8 排列转换( a r r a y t r a n s t o h e a d ) 9 排序( s o r t a r r a y ) 1 0 获取f d s r 末元素( f i r s t d e c r e a s i n g s t r i p l a s t l t e m ) 1 1 f d s r 末元素位置( p o s o 妇巾s i ) 1 2 数据项相邻位置( a d j a e e n t p o s o f d s i ) 1 3 翻转( r e v e r s a lp e r m u t i t i o n ) 1 4 输出( o u t p u t _ p e r m u f i t i o n ) 1 5 翻转完毕检测( i ss o r t e d ) 1 6 调整( a d j u s t ) 1 7 读入( r e a dp e r m u t i t i o n ) 1 8 排列正确性检验( c h e c kp e r m u t i t i o n ) 1 9 翻转排序( s o r t e d b y r e v e r s a l ) 在上述信息中,l _ 6 为变量信息( 数据信息) ,7 1 9 为函数信息( 操作信息) 。 头( h e a d ) 为一个指针变量,指向整个基因排列顺序表:数据项指针( c u r r e n t ) 指向连 续的若干个两两相邻的、具有p e r m u f i f i o n l t e m 类型的存储空间中的某个空间;排列长 度( l e n g t h ) 记录基因排列的长度;表长度( m a x l e n ) 为存储顺序表的长度,假设基 因排列的长度为n ,由于需要对排列扩展两个元素0 和n + 1 ,并且断点最多可以出现n + 1 次,所以,表长度最多为n + 2 竹l + 1 - 2 n + 3 ,即m a x l e n 最大值为2 n + 3 。翻转距离( d i s t a n c e ) 记录翻转的次数。 设计的存储并操作基因排列的类结构为: c l a s sp e r m u t i t i o n l i s t p r i v a t e : p e r m u t i t i o n l t e m + h e a d ; p e r m u t i t i o n i t e m c u r r e n t ; i n tl e n g t h ; i n tm a x l e n ; i n t a r r a y ; h a td i s t a n c e ; p r i v a t e : 山东大学顼士学位论文 v o i di n i tp c r m u t i t i o n ( ) ; i n ta r r a y t r a n s t o h e a d ( ) ; v o i ds o r t a r r a y ( i n t + ,i n t ) ; i n tf i r s t d e c r e a s i n g s t r i p l a s t i t e m ( ) ; h a tp o s o f f d s i ( i n t ) ; i n ta d j a c e n t p o s o t d s i ( i n t ) ; v o i dr e v e r s a l _ p e r m u t i t i o n ( i n ti , i n t j ) ; v o i do u t p u tp e r m u t i t i o n ( ) ; b o o li s _ s o r t e x l ( ) ; v o i da d j u s t ( ) ; p u b l i c : v o i dr e a d _ p e r m u t i t i o n ( ) ; b o o lc h e c k _ p e r r n u t i t i o n ( ) ; v o i ds o r t e d b y r e v e r s a l ( ) ; p e r m u t i t i o n l i s t ( ) ; p e r m u t i t i o n l i s t ( i n t ) ; 。 -

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论