（计算机软件与理论专业论文）双重基因组重构算法的实现.pdf

山东大学硕士学位论文 摘要 基因组重构是改变基因在基因组中排列顺序的生物过程，可归结为三种主 要操作：移位、反转和转位。重组距离即从一个基因组转化为另一个基因组所 需的最少重组次数。双重基因组中每条染色体都是成对出现的。双重基因组重 构问题，即要求计算一个与给定基因组移位距离最短的双重基因组。对于该问 题，n a d i ae 1 一m a b r o u k 等人给出了一个多项式时间算法。本文利用d e l p h i 集 成开发环境，将该算法实现为双重基因组重构软件：( 1 ) 设计了优化的数据结 构；( 2 ) 给出了详细的实现方法。( 3 ) 调试验证了算法的正确性。 本文首先介绍了双重基因组重构算法的研究背景，针对双重基因组重构算 法的基本思想，详细介绍了算法所涉及的基本概念与理论知识。然后通过一个 基因组实例，详细介绍了算法实现的数据结构。最后重点介绍了双重基因组重 构软件的设计，并对软件进行了分析。运行双重基因组重构软件，用户输入一 个初始基因组，经过该软件自动处理，即可输出一个目标基因组( 即双重基因 组) 。 双重基因组重构算法的主要处理步骤如下： ( 1 ) 由初始基因组生成自然子图。初始基因组是一个重排后的双重基因组， 由偶数条染色体组成，每个基因出现两次。初始基因组用断点图来进行描述， 每个基因符号在断点图中用两个顶点来表示，两个相邻基因的顶点用一条黑色 的边来连接。每条染色体的两端分别引进了一个特殊的顶点，用符号0 来表示， 简称0 点。在算法的实现中，初始基因组的断点图用链表结构来描述，每条黑 边对应链表中的一个结点，同一染色体中的结点通过指针从左到右的顺序进行 连接，多条染色体构成的链表，通过一个指针数组连接成一个链表结构。输入 初始基因组中的符号，程序自动生成初始基因组的链表结构，再对该链表结构 进行处理，生成自然子图对应的链表结构。 ( 2 ) 将自然子图合并为超自然子图。自然子图根据所含边数的奇偶性可以分 为两类，由偶数条边组成的自然子图和由奇数条边组成的自然子图。由偶数条 边组成的自然子图只需按照黑边从上到下的顺序配对排序，即可生成对应的超 山东大学硕士学位论文 自然子图。由奇数条边组成的自然子图又可分为两个小类，包含o 点的自然子 图和不包含o 点的自然子图，上述两小类中的自然子图要分别进行两两合并与 配对排序，生成边数为偶数的超自然子图。如果每个小类中还剩余一个自然子 图，则要将这两个自然子图进行合并与配对排序，从而得到一个对应的超自然 子图。每个超自然子图对应了一个链表，多个超自然子图的链表通过一个指针 数组连接成一个动态的链表结构。 ( 3 ) 处理超自然子图生成目标基因组。对每个超自然子图对应的链表依次进 行处理，每次生成一对灰色的边( 一条灰边对应一个结点) 。随着灰边的不断生 成，灰边与灰边之间的相互邻接，最后得到目标基因组的链表结构。根据链表 结构进行处理，即可得到一个目标基因组。目标基因组是一个完美双重基因组， 即基因组中的染色体是两两相同的。 在算法的实现过程中，初始基因组、自然子图、超自然子图、目标基因组 都采用动态链表结构来描述，从而提高了程序的灵活性与处理效率。在软件的 具体实现中，由于每个基因只能出现两次，所以在输入基因符号后，程序增加 了对基因符号的正确性检验。通过反复运行调试程序，证明了双重基因组重构 算法的正确性。 关键字；生物计算学；双重基因组重构：移位 山东大学硕士学位论文 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 ti sab i o l o g i c a lp r o c e s sw h i c hc h a n g e st h ea r r a n g e m e n t s e q u e n c e so ft h eg e n ei ng e n o m e hc a nb es u m m e du pt ot h r e em a i no p e r a t i o n s ： l r a n s l o c a t i o n ； r e v e r s a la n dt r a n s p o s i t i o n r e a r r a n g e m e n td i s t a n c e r e f e r st ot h e m i n i m u mn u m b e ro ft r a n s l o c a t i o no p e r a t i o n st r a n s f o r mo n eg e n o m et oa n o t h e r i n d u p l i c a t e dg e n o m ee a c hc h r o m o s o m ea p p e a r si nap a i r t h er e c o n s t r u c t i o np r o b l e m o fd u p l i c a t e dg e n o m er e q u i r e sf i n d i n go u tt h em i n i m u md i s t a n c eo ft r a n s l o c a t i o n o p e r a t i o nt r a n s f o r m so n ed u p l i c a t e dg e n o m et oag i v e no n e a st ot h i sp r o b l e m , n a d i ae 1 - m a b r o u kh a sp u tf o r w a r do n ep o l y n o m i a l - t i m ea l g o r i t h mw i t ht h eh e l po f d e l p h ii n t e g r a t e dd e v e l o p m e n te n v i r o n m e n t s ，t h i sp a p e rh a si m p l e m e n t e dt h i s a l g o r i t h mt oas o f t w a r en a m e dd u p l i c a t e dg e n o m er e c o n s t r u c t i o n ：( 1 ) h a sd e s i g n e d o p t i m i z a t e dd a t as t r u c t u r e ；( 2 ) h a sp r e s e n t e dc a r e f u li m p l e m e n t a t i o nm e t h o d ；( 3 ) h a s e x p e r i m e n t a l l yv e r i f i e dt h ea c c u r a c yo fa l g o r i t h m t h i st h e s i sf i r s tp r e s e n t st h er e s e a r c hb a c k g r o u n do ft h er e c o n s t r u c t i o np r o b l e m o fd u p l i c a t e dg e n o m ea n dt h eb a s i cc o n c e p ta n dt h e o r e t i ck n o w l e d g et h ea l g o r i t h m i n v o l v e d t h e ni ti n t r o d u c e si nd e t a i lt h ea t t a i n m e n to ft h ea l g o r i t h mo ft h ed a t a s t r u c t u r et h r o u g ha ne x e m p l i f i c a t i o no fg e n o m e u l t i m a t e l yt h ep a p e re m p h a s i z e s a n da n a l y s e st h ed e s i g no ft h i sd u p l i c a t e dg e n o m er e c o n s t r u c t i o ns o f l w a r e w h e nt h e u ri n p u t sa ni n i t i a lg e n o m e ，t h es o f t w a r ew i l ld e a l 、析mi ta u t o m a t i c a l l ya n dt h eu s e r c a l lg e tar e s u l t i n gg e n o m e ，t h a ti s , d u p l i c a t e dg e n o m e t h em a i nm a n a g e m e n tp r o c e s s e so fd u p l i c a t e dg e n o m er e a r r a n g e m e n ta r ea s f o l l o w i n g s ： t h ef i r s ts t e pi st of o r mn a t u r a lg r a p h sb yi n i t i a lg e n o m e t h ei n i t i a lg e n o m ei sa r e c o n s t r u c t e dd u p l i c a t e dg e n o m ec o m p o s e db ye v e nc h r o m o s o m e s e a c hg e n ea r i s e s t w i c e i n i t i a lg e n o m ei sd e s c r ib e dt h r o u g hb r e a k i n gg r a p h i nt h eb r e a k i n gg r a p he a c h g e n em a r ki sp r e s e n t e db yt w ov e r t i c e s ab l a c ke d g el i n k st w ov e r t i c e so ft w o n e i g h b o r h o o dg e n e s e a c he n do ft h ec h r o m o s o m eq u o t e sas p e c i a lv e r t 既s e p a r a t e l y ， w h i c hi sd e m o n s t r a t e db yt h em a r k “o ”，t h a ti s ，op o i n t i na l g o r i t h m , w eu s et h e c h a i n - s t r u c t u r et od e s c r i b et h eb r e a k i n gg r a p ho ft h ei n i t i a lg e n o m e e a c hb l a c ke d g e i sc o r r e s p o n d e dt oak n o ti nt h ec h a i n s t r u c t u r e k n o t si nt h es a m ec h r o m o s o m ea r e 1 1 1 山东大学硕士学位论文 c o n n e c t e df r o ml e f tt or i g h tb yt h ep o i n t c h a i n so fm u l t i - c h r o m o s o m e sa r ec o n n e c t e d t oac h a i n s t r u c t u r eb yag r o u po fp o i n td a t a w h e nm a r k so fi n i t i a lg e n o m ea r ei n p u t ， t h ep r o c e s sa u t o m a t i c a l l yp r o d u c e st h ec h a i n s t r u c t u r eo ft h ei n i t i a lg e n o m e a f t e r d e a l i n g 、 ，i t h t h ec h a i n - s t r u c t u r e , t h ep r o c e s sp r o d u c e sac h a i n s t r u c t u r e c o r r e s p o n d i n gt ot h en a t u r a lg r a p h t h es e c o n ds t e pi st oa m a l g a m a t en a t u r a lg r a p h si n t os u p e r n a t u r a lg r a p h n a t u r a lg r a p h sc a nb ed i v i d e di n t ot w oc a t e g o r i e sa c c o r d i n gt oe d g e sm e yc o n t a i n ： o n ei s c o m p o s e db yt , m c e ne d g e s ，a n dt h eo t h e r ，o d de d g e s t h en a t u r a lg r a p h c o m p o s e db ye v e ne d g e sc a nb ed e v e l o p e di n t os u p e r n a t u r a lg r a p hw h e ni t sb l a c k e d g e sa r ea r r a n g e df r o ma b o v et ob e l o w t h en a t u r a lg r a p hc o m p o s e db yo d de d g e s i sd i v i d e di n t ot w ot y p e s ，n a t u r a lg r a p hi n c l u d i n g0p o i n ta n dn a t u r a lg r a p hn o t i n c l u d i n gop o i n t t h e s et w ot y p e so fn a t u r a lg r a p h ss h o u l db ea m a l g a m a t e di n t o p a i r sa n ds e q u e n c e s t h e n 廿1 e ym a yb ed e v e l o p e di n t os u p e r n a t u r a lg r a p h i fe i t h e r t y p er e m a i n so n en a t u r a lg r a p h ，t h e s et w on a t u r a lg r a p h ss h o u l da l s ob ea m a l g a m a t e d i n t o p a i r sa n ds e q u e n c e s h e n c eas u p e r n a t u r a lg r a p hc a nb e o b t a i n e d e a c h s u p e r n a t u r a lg r a p hi sc o r r e s p o n d e dt oac h a i n m u l t i - c h a i n so fs u p e r n a t u r a lg r a p ha r e c o n n e c t e dt oad e v e l o p i n gc h a i n s t r u c t u r e t h em i r ds t e pi st ot u r ns u p e r n a t u r a lg r a p h si n t or e s u l t i n gg e n o m e h a n d l et h e c h a i nw h i c hs u p e r n a t u r a lg r a p hc o r r e s p o n d i n gt os u c c e s s i v e l y e a c ht i m eag r a ye d g e i s f o r m e d ( o n e 伊a ye d g ec o r r e s p o n d s o n ek n o t ) a l o n gw i t ht h e c o n t i n u o u s f o r m a l i z a t i o no fg r a ye d g e s ，t h e ya r ea d j a c e n tt oe a c ho t h e ra n da tl a s tf o r mc h a i n g r a p ho ft h er e s u l t i n gg e n o m e t h er e s u l t i n gg e n o m ei sap e r f e c td u p l i c a t e dg e n o m e ， t h a ti st os a y ，i nd u p l i c a t e dg e n o m ee a c hc h r o m o s o m ea p p e a r si na p a i r i na l g o r i t h m , b e c a u s ei n i t i a lg e n o m e ，n a t u r a lg r a p h , s u p e r n a t u r a lg r a p ha n d r e s u l t i n gg e n o m ea r ea l ld e s c r i b e di nd e v e l o p i n gc h a i n s t r u c t u r e , w eh a v ee l e v a t e d t h ef l e x i b i l i t ya n de f f i c i e n c yo ft h ep r o c e s s i nt h ea c t u a li m p l e m e n t a t i o no ft h i s s o f t w a r e , e a c hg e n ec a no n l ya p p e a rt w i c e ，t h ep r o c e s sh a sr e i n f o r c e dt h ea c c u r a c yo f t h et e s t r e p e a t e dr u n n i n gd e b u g g i n go ft h ep r o c e s sh a sv e r i f i e dt h ea c c u r a c yo f a l g o r i t h mo fd u p l i c a t e dg e n o m er e c o n s t r u c t i o n k e y w o r d ：c o m p u t a t i o n a lb i o l o g y ；d u p l i c a t e dg e n o m ea r r a n g e m e n t ； t r a n s l o c a t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：墨墅装丝! 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：墨坌逮丝违导师签名：牡日期：幽么颦乃广 山东大学硕士学位论文 第1 章绪论 1 1 双重基因组重构算法的研究背景 1 9 7 0 年，s u s u m uo h n o 对于染色体进化提出了两个基本理论【i 】，其中之一 就是基因组复制理论。该理论假设了一种新的进化事件基因组复制。顾名 思义，基因组复制就是将基因组中的每条染色体都进行复制，复制后的基因组 中染色体都是成对出现的。在过去的几十年里，该理论一直遭到质疑。2 0 0 4 年， k e l l i s 等人对酵母菌k w a l t i i 的基因组测序，并将其与另一种酵母菌 s c e r e v i s i a e 的基因组比较。他们发现，k w a l t i i 中的每个区域都与 s c e r e v i s i a e 中的两个区域相对应，从而证明了在生物物种的进化过程中确实 存在整个基因组复制的事件【2 】。之后科学家们又相继证明了基因组复制事件同 样发生于植物和动物的进化过程中【3 ，4 ，5 】。由此引发出一个问题：如何根据现有 的基因组重新构造最初刚发生基因组复制事件时的双重基因组? 该问题又称作基因组对分问题。下面给出该问题的详细描述：给定一个基 因组r ，r 中的每个基因都是唯一的。对r 进行基因组复制，将其变为双重基因 组q 。即r 中的每条染色体都在q 中对应着两个副本。q 经过若干基因组重组事 件后，内部的基因排列顺序被打乱，变为基因组p 。注意到，p 中每个基因都出 现两次。基因组对分问题，就是根据基因组p ，重新构造最初的双重基因组q 。 1 9 9 9 年，n a d i ae 1 - m a b r o u k 等人给出了基因组对分问题的一个多项式时间 算法【6 】，但未将其实现为软件。我们在d e l p h i 集成开发环境下，将该算法实现 为基因组对分软件【7 】。本文的主要工作包括：( 1 ) 设计了优化的数据结构；( 2 ) 给出了各个步骤详细的实现方法。( 3 ) 实验验证了算法的正确性。 1 2 算法概述 基因组【8 爿中的每个基因【1 0 】( 或基因块) 用一个有符号字符表示，符号表示 基因( 或基因块) 的方向。染色体 1 1 ，1 2 是基因( 或基因块) 组成的序列，用一 山东大学硕士学位论文 个有符号字符串表示。基因组是染色体的集合。给定染色体j = 五五， 一z = 一一r 五表示的逆序。给定两条染色体z 和，若j = ，或= 一， 则称z 与，等价。若基因组彳和刀中的染色体一一等价，则称彳和刀等价，记 作彳= b 。 若基因组g 满足如下条件：( 1 ) 染色体数为2 n ：( 2 ) 且g 中的每个基因 出现两次，则称g 为重排后的双重基因组。例如， g = + 口+ 易一c + b d + l 一口一口+ 一叫+ g 一一z 柏+ f g + h 就是一个重排 后的双重基因组，其中共包含4 条染色体9 个基因，且每个基因出现两次。 若基因组p 包含2 m 条染色体q 仁g ，对于每个，孔2 ，2 m ，都存 在一个 1 ，2 ，埘) ，) ，满足e = c 。则称p 为一个完美的双重基因组。例 弧，p = 卜e 七g f d 七t ，一e g f a 七t ，七口七6 一c 一向+ q + 6 一c 一蛾冁一令 完美的双重基因组。 移位【1 3 ，1 4 】是作用于多染色体基因组的一种重组操作。它的作用是交换基因 组中两条染色体的前缀或后缀。若交换的前缀或后缀都不为空，则称之为交互 型移位。交互性移位又分为前前移位和前后移位两种类型。给定两条染色体 j = 以，= 职，其中z ，五，彳，五都是基因序列。前前移位将z 变为z 五， ，变为耳t ，前后移位将变为彳一z ，变为一五t 。 基因组等分问题可描述如下：给定一个重排后的双重基因组g ，用最少的 移位次数将其转化为某个完美的双重基因组p 。 1 2 1 断点图和移位距离公式 基因组移位排序问题要求计算从一个基因组转化为另一个基因组所需要的 重组操作的最少次数( 移位距离) 。断点图【1 5 】是解决该问题的重要工具。给定两 个基因组a 和b ，满足g e n e s ( 匀= g e n e s ( 历( g e n e s ( 0 3 表示基因组g 包含的基 因集合) ，断点图暖目的构造方法如下：a ( 或b ) 中的每个基因都对应两个点 给定某个基因z ，若z 爿驯，则对应两个点( ，夕) ；若z = 一i 驯，则对应两个点 ( 夕，) 。如此一来，a 和b 中的染色体都对应着一个点排列。设u 、v 为吒口 中的两个点，若它们不属于同一基因，并且在a ( 或b ) 的染色体对应的点排 2 山东大学硕士学位论文 列中相邻，则称u 、v 在a ( 或b ) 中相邻。边集e 包含两种颜色的边：若两个 点u 、v 在a 中相邻，则在它们之间连黑边；若在b 中相邻，则连灰边。同一 基因的两个点之间既没有黑边也没有灰边。设a ( 或b ) 的基因数为刀，染色 体数为，则g a b 中的黑边和灰边数都为刀一n 。 注意到，够口中的点，除了位于染色体两端的点外，都邻接一条黑边和一 条灰边，因而可唯一地分解为若干个黑边和灰边交替出现且互相不重叠的圈。 当彳= b 时，由刀一个只包含一条黑边和一条灰边的圈构成，此时圈数达 到最大。 用c 表示色口中的圈数，则a 和b 的移位距离公式 1 6 , 1 7 为 敌4 句- = , 一n c + l ，其中是与吆中其它特殊的组合结构( 最小子排列、偶 隔离带) 有关的参数。然而这些特殊的组合结构出现的概率很小，因而大部分 情况下移位距离【1 8 】为刀一n c ( 特殊情况除外) 。 1 2 2 自然子图 在基因组对分问题中，同样要利用断点图做工具。先构造部分图驭以句， 方法如下：由于给定基因组g 中每个基因都出现两次，为了加以区分，每个基 因z 的两次出现分别用石和五来表示。跟断点图的构造类似，每个基因五构造 两个点：若= i i ，则对应( z ，矽) ；若= 一i l ，对应( 彩，彳) 。另外给每条 染色体e ( = 1 ，2 ，2 n ) 对应的点序列的首尾两端g r 力n _ k 和两个点。 定义集合p = 哆，) 卢。缸：，集合o 中的点简称为o 点。定义 _ z iz g e n e s ( 0 3 ，s e ( 功，j = l ，2 ) 。部分图的点集= u 秒。若两个点u 、 v 不属于同一基因且在某条染色体对应的点序列中相邻，则在它们之间连黑边。 边集a 就是这些相邻点( 属于同一基因的两点除外) 之间的黑边的集合。初始 蠲j 组g = b 口j 广b c + b d j r i 一c 一口j 广，一l 。一e + g 一，一d 。+ i l + e g + 饿韵捺贪 图如图1 1 所示。规定i = 2 ，乏= l ，；= 忽石= ，。若部分图中存在一个点露：z ， 则乙= z ，被称作搿的配对；二：z ，被称作搿的对应。例如，彳和z 互为配 对，彳和彳互为对应。 下面根据部分图驭以句构造自然子图。设有一条边f = ( 功a ，递归地 3 山东大学硕士学位论文 定义4 ：( 1 ) ( 弘力4 ：( 2 ) 若( 五力4 且z 仨秒，则邻接z 的边也加入到4 中；同样，若少仨p ，则邻接y 的边也加入到4 中。令形为4 中的边所邻接的 点的集合，则驭形，4 ) 为由矽生成的q 形句的一个自然子图。图l - 1 所示的部 分图可得到五个自然子图，如图1 - 2 所示。 卜- 卜_ _ 卜_ 1 卜l _ 卜_ - 卜_ 1 o l la l a l “b l b 1 “c l “c i b 2 b 2 hd l 。d l i i i 1 - 卜- 卜卜卜卜 0 l lc 2 hc 2 ta 2 ha 2 tf l f l “i 2 “i 2 o 盘 卜- 1 卜_ - 卜- 1 卜_ - 卜_ _ 0 3 1c l h c i g l 9 1 “ f 2 “f 2 d 2 “d 2 0 3 2 卜_ 1 卜一卜_ - 卜_ - 卜_ _ 0 4 lh t h i 。0 2 c 2 h 9 2 “酣h 2 h 产0 4 2 图1 - 1 初始基因组g 的部分图 基因组的自然子图根据所含边数的奇偶性分为两部分，边数为偶数的自然 子图的集合用g c e 表示，边数为奇数的自然子图的集合用c - c o 表示。g c o 又 可分为两部分，包含o 中的点的自然子图集合g c o + 和不包含o 中的点的自然 子图集合g c o 一。例如，图1 - 2 中，g c e = s 1 ) ，c - c o = s 2 ，s 3 ，s 4 ，s 5 ，其中 g c o + = s 3 ，s 4 ，s 5 ，g c o - = s 2 s l o l i 1a l t t 对 厶t d 2 “ b 2 “1d i - b l “c l 。 0 2 。_ o 渤 a l hh b i t 磅h 西 c l hb 2 t s 3 d l t 1i l d 2 t o ，2 o 丝1 i 2 t s s 5 i 2 h 鲈 g l h 鲈 图l - 2 根据部分图构造的自然子图 4 山东大学硕士学位论文 1 2 3 对自然子图中的边重新排序 为了便于算法的后续处理，需要先对g c e 中每个自然子图中的边重新排 序，排序规则【1 9 】如下：按照边所邻接的顶点自上而下、先左后右的顺序进行配 对。例如，对图1 2 中的自然子图s l 重新排序后，得到如图1 - 3 中所示的结果 另外还需对同一个基因的两个顶点进行重新标识，第一次出现的重新标识为l ， 第二次出现的重新标识为2 ，因而该排序过程可能会改变原有顶点的下标。排 序后的自然子图中相邻两条边的左项点两两互为配对。g c e 中排序后的自然子 图被称为超自然子图。 1 2 4 超自然子图 b i “卜c 2 h b 2 卜d 2 图l - 3 重新排序后的自然子图 首先对g c o + 中的自然子图进行两两合并，对合并后的子图中的边重新排 序，使其左顶点两两配对【2 i d 】。合并后的子图中包含偶数条边。在两个自然子图 的合并中，一个子图中的o 点必须与另一个子图中的o 点( 两个o 点中可任选 一个) 配对。生成的超自然子图与g c e 中排序后的自然子图( 也可称超自然子 图) 具有同样的结构，即具有对称的左右顶点，左顶点个数与右顶点个数相同， 而且左顶点两两配对出现。在g c o + 中合并得到的所有超自然子图用集合c o + 表示。 对g c o 中还未进行合并的自然予图继续进行两两合并，这些子图除了 g c o 中的子图外，还可能包括一个g c o + 中剩余的子图。合并后的子图集合记 山东大学硕士学位论文 作c o 。c o 中的子图也有偶数条边，但不具备左右顶点的对称，右项点比左 顶点多出四个( 上部子图与下部子图各多出两个右顶点) 。 将集合g 四u c o + u c o 一中的子图统称为超自然子图。图l - 2 中的自然 子图所对应的超自然子图如图1 _ 4 所示。注意：在s ”中，0 4 2 与莳属于右顶点， 因而右顶点比左顶点多4 个。另外，s 2 5 中的上下两个子图，除了最后一条边外， 其余的左顶点仍然要求两两配对。 0 2 l - c l “ f t 卜- 耐 s 驾 e l 卜_ g l e 2 h l h h t t b l “卜一c 2 h b 2 “卜d 2 “ 1 2 5 生成目标基因组 图1 - 4 超自然子图 a l 卜b l a 2 h _ c l t c 2 b 2 t 由于g c e 中的子图与c o + 中的子图都具有对称的左右顶点，因而将g c e 与c o + 合并，用集合c e 表示。 首先对c e 中的超自然子图逐个进行处理，生成目标基因组中的灰边( 用 虚线表示) ，每次生成一对相互配对的灰边。随着灰边的不断生成，灰边与灰边 之间通过同一个基因两个对应顶点的相互邻接，形成更长的基因片段【2 1 1 。 然后，逐个处理c o 中的超自然子图。c o 中的超自然子图具有一定的特 殊性，它由两个独立的自然子图合并而成，上下两个子图之间没有可配对的基 因顶点。在处理完上部的子图后，会剩余两个右顶点。所以在处理到下部子图 6 山东大学硕士学位论文 的最后一对左顶点时，需要考虑与上部两个剩余顶点连接的可能性。因此，对 c o 中超自然子图的处理要比对c e 中超自然子图的处理复杂一些。 随着灰边的不断生成、基因片段的相互邻接，最后得到目标基因组中的所 有染色体。注意：每个基因顶点只能依附于一条灰边，基因符号相同的顶点不 能有灰边连接。如果两个基因符号已经出现在目标基因组中的同一个基因片段 中，则这两个基因顶点不能用灰边连接。详细的处理算法，请看论文的第3 章 在基因组实例中，s l 、s 3 4 、s 2 5 三个超自然子图的处理结果如图1 - 5 所示， 得到基因组完全图【笠】，黑边表示初始基因组的组成，灰边表示目标基因组的组 成。将这些灰边通过基因顶点相互邻接，最后得到上述的目标基因组： p = - e + g - ，一d | ，一8 七g 一，一a t + l , - i - a + 6 一c 一毳，七口七6 一c - h ，、 0 l l o a l 0 2 - - c - 、 ，一、 ? 厶l d - “ i， j b 。- ；：二对 i b ：“d 2 。j 弋 i ，、 d l t ，卜二i l t ，一；jq ：封r 一0 3 ： 1 突o ；。也 j 一 乙 j q 。l 、： 0 、79 1 ：， ， 7 ，、 毛“，卜j 9 2 。 1 3 论文主要的研究内容 图1 - 5 基因组完全图 通过阅读大量的参考文献，在对双重基因组重构算法有比较深入了解的基 础上，本文提出了双重基因组重构算法实现的链表结构，并在d e l p h i 集成开发 环境下完成了该算法的软件开发。在软件开发过程中，充分利用了d e l p h i 良好 7 酽 ”、 时 k ” 一小 鞋一 一 一、一一 一、；： 一、一、。 山东大学硕士学位论文 的程序界面，以及结构性强的p a s c a l 语言源代码。遵循自顶向下、由粗到细的 结构化设计原则，双重基因组重构软件的设计达到了预期的目的。通过对算法 的分析，可将算法处理的主要步骤概括如下：( 1 ) 由初始基因组导出自然子图： ( 2 ) 将自然子图合并为超自然子图；( 3 ) 根据超自然子图生成目标基因组。通 过反复运行调试程序，验证了算法的正确性。 1 4 论文的组织结构 本论文共分五章，下面按章节叙述如下： 第一章绪论，主要阐述了双重基因组重构算法的研究背景，概要介绍了算法 的基本思想与相关的理论知识，介绍了本文的研究内容与组织结构。 第二章双重基因组重构算法的数据结构：通过一个基因组实例，详细描述了 算法每一个处理步骤中的动态链表结构，以及结点与指针数组的构成。 第三章双重基因组重构算法的实现：本章是全篇的重点内容，详细介绍了在 d e l p h i 集成开发环境中算法每一个主要步骤的实现方法。主要算法用类p a s c a l 语言进行描述。 第四章双重基因组重构软件的分析说明：主要介绍了在软件开发中所使用的 基本原则与方法，并对软件中存在的不足进行了说明。 第五章结束语：本章是对全文的总结，对论文的主要工作进行了全面的概括。 1 5 本章小结 本章主要阐述了双重基因组重构算法的研究背景，对算法的基本思想、处理 步骤与相关理论知识做了概要性的介绍，其中对断点图、自然子图、超自然子图 等重要概念做了详细的介绍。最后介绍了论文的研究内容与组织结构。 8 山东大学硕士学位论文 _ m m 量曼曼量皇曼曼曼皇曼曼曼曼曼曼曼! 皇邕曼曼曼 第2 章双重基因组重构算法的数据结构 本章通过一个基因组实例，详细介绍了双重基因组重构算法实现的数据结 构。针对算法的主要处理步骤，描述了相应的动态链表结构 2 3 2 4 。 2 1 初始基因组对应的链表结构 在双重基因组重构软件中，用户输入一个初始基因组，程序自动生成其部 分图对应的链表结构。 基【困组g = + 口+ 乃一c + b 一+ 口一口+ 一口+ 箩一一z + 乃+ 矽一g + h ) 对 应的链表结构如图2 - 1 所示。 指针数组c o a a b b c c b bddl 1 l1lll l 221ll 1t - -_ -_ -_ - hthhtthhtt o0 0 o 00 1 oc caaf f i ii 1 0 i 1 0 2 22221 l 22 2 ll _ - _ -一- _ - 1 hthtt h ht 2 h 2 ooo o o0 oe e g g ffd d o 3 1 l ll 2 2 2 2 3 l h - - tth hth t2 o0o0o o hh ee gg hho 41 - p1 2 - 一 22 一2 2 - 2 4 lththht t h 2 0 o 0oo 图2 - 2 链表结点的组成 图2 1 基因组g 对应的链表结构 基因组实例中的四条染色体对应了四个链表， 每个链表结点【2 5 】表示部分图中的一条黑边，结点由 八个域组成，域名如图2 - 2 所示。 9 山东大学硕士学位论文 l 域：存放左顶点的基因符号；l c 域：存放左顶点基因的出现次数；l o 域： 存放左顶点基因的方向，为t 或h ；r 域：存放右顶点的基因符号；r c 域：存 放右顶点基因的出现次数；r o 域：存放右顶点基因的方向，为t 或h ；f 域： 生成自然子图时，判定该条边是否已经配对，为1 时表示已经配对，为0 时表 示没有配对，初始值为0 ；n e x t 域：指向当前边右邻的下一条边结点。 2 2 自然子图对应的链表结构 通过对图2 - 1 所示链表结构的循环处理，可生成得到初始基因组的五个自 然子图。其链表结构如图2 3 所示。每个自然子图对应一个链表，链表结点的 组成与图7 类似，不同之处是将f 域分成了l f 和r f 两个域，分别用于判定边 的左右顶点是否已经配对，为l 时表示已经配对，为0 时表示没有配对，初始 值为0 ； 指针数组s 图2 3 - 自然子图对应的链表结构 1 0 山东大学硕士学位论文 2 3 超自然子图对应的链表结构 在图2 - 3 所示的链表结构中，如前所述，五个自然子图分成三类。要对s 1 重新排序，并将s 3 与s 4 合并、s 2 与s 5 合并，得到三个超自然子图s l 、s 3 4 和 s 2 5 ，对应的链表结构如图2 4 所示。由于s 1 和s 3 4 具有相同的左右顶点对称性， 为了后续处理的方便，将它们合并到同一个指针数组c e 中。 指针数组s s c p 图2 4 ：超自然子图对应的链表结构 2 4 目标基因组对应的链表结构 针对图2 4 所示的超自然子图链表结构，首先循环处理指针数组c e 中的链 表，每次生成一对灰边，每条灰边用一个对应的链表结点来表示，并将这两个 结点加入到指针数组f 中。每加入一个结点，程序便根据同一基因的两个对应 山东大学硕士学位论文 顶点进行结点的相互邻接。然后再循环处理指针数组s o f p 中的每个链表，每次 也生成两个结点。随着结点的不断生成、相互邻接，最终得到如图2 - 5 所示的 链表结构。这一部分的处理是整个算法的核心部分，详细的算法流程请看论文 的第3 章。最后，通过对图2 - 5 所示链表结构的处理，即可输出相应的目标基 因组。 指针数组f 2 5 本章小结 图2 - 5 ：目标基因组对应的链表结构 本章通过一个基因组实例，对双重基因组重构算法中的主要链表结构进行 了详细的描述，从初始基因组、自然子图、超自然子图，到目标基因组，它们 所对应的链表结构都是由程序动态创建的。这种动态链表结构给程序的处理增 加了灵活性，提高了软件开发的效率【冽。 出奎奎兰堡圭兰些丝兰 第3 章双重基因组重构算法的实现 我们利用d e l p h i 集成开发环境【 j 目，将该算法实现为双重基因组重构软 件。利用d e l p h i 良好的开发界面【o 啪结构优良的p a s c a l 语言源代码双重基 因组重构软件具有界面简洁、功能完备、层次清晰的