（应用数学专业论文）基于共有区间的基因组重排问题研究.pdf

摘要 生物的遗传物质随着进化而改变相对于序列水平的点突变，越来越多的研究 更加关注基因组水平的较大的变化计算分子生物学中的基因组重排，产生了借助 于反序来排列有符号排列问题给定由相同元素构成的代表基因组的两个有符号 排列，问题在于找到由个基因组转化成另一个基因组的最简约的反序排序方案 目前，基于基因组重排的进化方案的重构已经成为理解相近物种间进化关系 的有力工具，尤其对于哺乳动物的研究例如，在过去的两年中人们已经借助于 m g r 和g r i m m 软件得到了大鼠与人阻及最近新测序的挪威鼠之间的几个比较 有趣的进化方案本文比较感兴趣的是不破坏组合结构( 即基因组保守块) 的方 案事实上，如果两个基因组拥有共同特征，那么它们的祖先很可能也拥有这特 征，这就使研究保持这一特征的进化方案更商价值 本文中考虑的组合结构即代表两个基因组的排列的共有区蚓首先，对h p 理 论中提及的交叉图做了重新描述和更加简单的构造，将新得到自勺交叉图用于基因 组重排的交换方案问题的研究，得到了与b e r a r d 和b e r g e r o n 在文献【1 8 】相同的结 论并在此基础上提出了非交换方案的概念，同时对非交换方案转换成交换方案做 一定的研究 然而，由于基因组进化过程的最优交换方案是一类特殊的完美方案，而一个 完美方案并不一定是最优的因此，人们更加关注的是基因组进化过程中，是否存 在一般的完美方案和最优完美方案的问题本文在k a p l a n ，s h a m i r 和t a r j a n 等人提 出的反序排序有符号排列算法基础上。加入了对保持共有区间问题的探讨，改进 了k s t 算法。通过对排牟定向分支和不定向分支得到的反序与摊列的共有区间进 行比较，确定得到的反序是齿保持排列的共有区间在此基础上给出一个多项式时 间算法，判定一个排列能否被一个最优的完美方案进行排序从而在一定意义上很 好地解决了基因组进化过程中的最优完美方案问题 关键词：基因缳重排：反序排序；共有区间；非交换方案；完美方案 r e s e a r c ho fg e n o m er e a r r a n g e m e n t sb a s e do hc o m m o ni n t e r v a l s a b s t r a c t t h eg e n e t i cm a t e r i a lo fo r g a n i s m sc h a n g e sa s t h e ye v o l v e m o r ea n dm o r e r e s e a r c h e r sw e r ec o n c e r n e dw i t hl a r g et r a n s f o r m a t i o n sa tt h eg e n o m el e v e l ，a so p p o s e d t op o i n tm u t a f i o n sa tt h es e q u e n c el e v e l t h ep r o b l e mo fs o r t i n gas i g n e dp e r m u t a t i o n b yr e v e m a l si si n s p i r e db yg e n o m er e a r r a n g e m e n t si 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 y g i v e nt w og e n o m e sr e p r e s e n t e da st w os i g n e dp e r m u t a t i o n so ft h es a n l ee l e m e n t s ，t h e p r o b l e mc o n s i s t si nf i n d i n gam o s tp a r s i m o n i o u ss c e n a r i oo fs o r t i n gb yr e v e r s a l st h a t t r a n s f o r m so n eg e n o m ei n t ot h eo t h e r n o w a d a y s t h er e c o n s t r u c t i o no fe v o l u t i o ns c e n a r i o sb a s e do n g e n o m e r e a r r a n g e m e n t sh a sp r o v e nt ob eap o w e r f u lt o o li nu n d e r s t a n d i n gt h ee v o l u t i o no fc l o s e s p e c i e s ，e s p e c i a l l ym a m m a l s f o re x a m p l e ，i nt h el a s tt w oy e a r s ，s e v e r a lv e r yi n t e r e s t i n g e v o l u t i o ns c e n a r i o sh a v eb e e np r o p o s e db e t w e e nt h em o u s ea n dt h eh u m a n ，a n d b e t w e e nt h em o u s ea n dt h en e w l ys e q u e n c e dn o r w a y r a t ，u s i n gt h em g r a n dg r i m m s o f t w a r e w ca r ei n t e r e s t e di ns c e n a r i o st h a td on o tb r e a kc o m b i n a t o r i a ls t r u c t u r e s ( t h a t i st h eg e n o m es y n t e n yb l o c k s ) i n d e e d ，i ft w og e n o m e ss h a r eac o m m o nf e a t u r e ，i ti s l i k e l y t h a tt h e i rc o m m o na n c e s t o rd i dt o o ，w h i c hm a k e se v o l u t i o ns c e n a r 妇t h a t c o n s e r v et h i sf e a t u r em o r ei n t e r e s t i n g i n t h i sd i s s e r t a t i o n ，t h ec o m b i n a t o r i a ls t r u c t u r e st h a tw ec o n s i d e ra r ec o m m o n i n t e r v a l so f t w op e r m u t a t i o n s t h a tr e p r e s e n t t w og e n o m e s a t f i r s t ，w ed e f i n e t h e o v e r l a p g r a p ha n dg i v et h en e wc o n s t r o c t i o no fi t ，w h i c ha l ed i f f e r e n tf r o mt h o s eo ft h eh p t h e o r y w co b t a i nt h es a m ec o n c l u s i o na ss b e r a r da n da b e r g e r o np r o p o s e d , w h e no s c t h en e wd e s c r i p t i o no ft h eo v e r l a pg r a p h b a s e do nt h ec o m m u t i n gs c e n a r i ow eg i v et h e d e f i n i t i o no ft h en o n c o m m u t i n gs c e n a r i o ，a n dg i v er e l a t i v er e s e a r c ha b o u tt h e t r a n s f o r m a t i o nf r o mt h en o n - c o m m u t i n gs c e n a r i ot ot h ec o m m u t i n gs c e n a r i o h o w e v e rs i n c ec o m m u t i n gs c e n a r i oi sac l a s so fs p e c i a lp e r f e c ts c e n a r i oa n da p e r f e c ts c e n a r i oi s n o tn e c e s s a r i l yc o m m u t i n g , w ea l s ow a n tt ok n o wi ft h e r ee x i s t s p e r f e c ts c e n a r i oo ro p t i m a lp e r f e c ts c e n a r i oi nt h ee v o l u t i o np r o c e s s b a s e do nt h ef a s t e r a n ds i m p l e ra l g o r i t h mw h i c hw a sp r o p o s e db yh k a p l a n ，r s h a m i ra n dr e 1 a 1 1 f o rs o r t i n gas i g n e dp e r m u t a t i o nb yr e v e r s a l s ，w em o d i f yt h i sa l g o r i t h mt os o l v et h e p r o b l e mf o rc o n s e r v i n gt h ec o n l m o ai n t e r v a l s b yc o n t r a s t i n gc o m m o l li n t e r v a l sw i t h t h er e v e r s a l s ，w cc d e c i d ei ft h er e v e r s a l sc o n s e r v et h ec o m m o ni n t e r v a l s m o r c o v e r w ea l s oo b t a i nap o l y n o m i a lt i m ea l g o r i t h mt od e c i d ei fap e r m u t a t i o nc a nb es o n e db y a no p t i m a lp e r f e c ts c e n a r i o s ot h eo p t i m a lp e f f e c ts c e n a r i op r o b l e mo fap c r m m m i o n c a nb es o l v e dm o r ee f f i c i e n t l yt os o m ee x t e n tb yt h ea l g o r i t h mw e p r o p o s e k e y w o r d s ：g e n o m er e a r r a n g e m e n t ；s o r t i n gb yr e v e r s a l ：c o m m o ni n t e r v a l n o n - c o m m u l 如t gs c e n a r i o ：p e r f e c ts c e n a r i o 大连海事大学学位论文原创性声明和使用授权说明 原刨性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：羹王基直匡回凶基圜缎熏摊闻蘸班寇：。除论文中已经 注明引用的内容外，对论文的研究做出熏要贡献的个人和集体，均已在文中以明 确方式标明。本论文中不包台任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名、彰瞎瘐扫辟弓月，日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学傈留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作者签名 导师签名 日期：；m 口年弓月 卉寸，秒 疑 j ，h 第1 章绪论 1 1 基因组重排问题及其生物学背景 历时十年的人类基因组计划不仅产生了海量的生物学数据，在人类探索生命 奥秘的征途上迈出了耀实的一步而且孕育了一门崭新的学科生物信息学生 物信息学是一门涵盖了数学、物理学、化学、生物学和讨算机科学的多学科交叉 的新斟学科近年来生物信息学研究在中国很活跃，中国科学家在完成人类基嘲 组的重要部分( 人类基圆组计划的框架圈) 研究中起了重大作用最近，在生物信 息学和基因组学研究方面，中国已经进入了政府支持和合瓷经营快速增长的新时 期，而且，中国与世界上其他国家在基因组学和生物信息学领域的许多协作研究 也已启动 111 萋园组比较与基因比较 在分子生物学中，通常将一个生物体的全套d n a 序列称为该生物体的基因组 ( g c n o m e ) 有时也将基因组定义为一个生物体染色体的集合，将染色体定义为基 因的集合，而将基因定义为d n a 的片断研究两个不同生物之间的相似性、同源 性艘其进化关系，最常用的方法足将两个生物的d n a 的序，进行比较，通过对序 列做插入、删除或替换单个字符 核苷酸或空格符) 的操作，计算出从一个序列 转换到另一个序列所需的最少操作次数( 通常称为两个序列间的编辑距离) 这种 方 ：左一般只适于对单个基因或由少数几个基因组成的“基圜块”的研究，囡而它 是基因组研究的一种局部化方法然而，分子生物学研究发现，两个完全不同的生 物它们各自的基因组包台的基因有可能相同，不同的只是基因在染色体上的排 列次序 对于包台的基因相同，但基因的排列顺序不同的两个基因组，研究它们的相 似性或进化关系，显然不能使用上述所说的局部化方法，否则将会导出错误的结 论但可以通过对基因组中的单个基因或基因块做反向( r e v e r s a l ) 、易位 ( t r a n s l o c a t i o n ) 、复制( d u p l i c a t i o n ) 或调换( t r a n s p o s i t i o n ) 等操作，将一个基闲 组变化到另一一个基因组上述这种以基因为零位的操作就是所谓的基因组重排 ( g c n o m er e a r r a n g e m e n t ) 在2 0 世纪8 0 年代末，p a l m e r 和他的同事们在植物细胞器中发现了一种有关 迸化变异不寻常的新的模式他们比较了b r a s s i c ao l e r a c e a ( 甘蓝) 和b r a s s i c a c a m p e s t r i s ( 芜箐甘蓝) 的线粒体基因缀，两者之间的联系非常紧密( 许多基因是 9 9 同源的) l “令他们感到惊奇的是，这些分子在基因序列上几乎相同，但在基 因排列次序上则有显著性的差别( 见图1 1 ) 这个发现和后来1 0 年中许多其他的 研究令人信服地证明了基因组重排是分子进化的种菇同模式， b o l e r a c e a ( 甘蓝) b c a m p e s t r l s ( 芜箐甘蓝) 圈l1 从甘蓝基因组到芜箐甘篮基因组的“变换” f i g u r e1 1 “t r a n s f o r m a l i o n ”o f c a b b a g ei n t ot u r n i p 传统的研究分子进化的技术是基因比较，即根据单个基因( 或者少数基因) 的点突变重建系统讨( p h y l o g e n e t i c t r e e ) 在“甘蓝和芜篱目“蓝”例子中，基因比 较方法几乎是不适用的，因为在甘蓝和芜篱甘蓝线粒体中基因的点突变比例很低， 所以它们的基因儿乎是相弼的更多的例子表明，两个或多个物种划基因的比较所 得到的信息要少于更大基因组单元甚至是整个基困组的比较所得到的信息 对于非常缓慢进化的基因组而言，基因组比较( 即基因次序的比较) 则是一 种可供选择的方法基函缎比较与经典的基因此较相比具有特定的优点和缺点：基 因组比较忽视基因的真实d n a 序列，而基因比较则忽视了基因的次序在基因组 水平上进行分析可以弥补传统的摹嗣水平上分子进化研究的不足，而最终目标应 该是将基因组比较和基因比较的优点结合到单一的算法中 112 基因组重排问题 当比较不同物种的全基因组时，需要计算物种间的进化“距离”在一些例子 2 ：。 吨。 1 r | 一 0 弋 警 o h h 4 4 4 0 ，1- i_0 2 中，例如当研究叶绿体和线粒体基因组时，仅有的一种重排事件，即反序( r e v e r s a l ) ， 几乎是影响基因组进化的唯一一方式在这种情况f ，用把一个基因组转换为另一一个 基因组所需的反序操作的数量来度量两个基因组间进化距离是有道理的 对基因组重排的研究主要集中在解决个组台“难题”寻找系州使某 一基因组转化为另一基因组的重排方案就最简单的形式而言，将一种基因组转化 为另一种基因组的重排可以用寻找最，l 、转换次数的组合问韪来模拟生物体中臼勺 基因次序序列可用排列玎= 石，万：，以或厅= ( r o t ，玎：，一，) 来表示反转p ( l d 县 有反转基因z ，口。，f ，次序的作用它将摊列 玎= 厅1 ，石2 ， 石j j ，开，。一，厅，石j “，一，疗h 转换为排列 万p ( i ，) = 万l ，丌2 万卜_ 1 ，疗f 万，石? + l ，7 。 关于反转距离问题，就是要剐给定的两个h 元排列f 和口，寻找一系列的反转 n ，p 2 ，n 使得，r n 岛一= 盯，h 要求r 为最小( 这样的f 称为排列石和盯的 反序距离) 按反序排序2 c 的问题就称为计算口和恒等捧列，= ( 1 ，2 ，- ，目) 之问反 序距离d ( z ) 的问题 由于基因是d n a 的有向片段，在测序后的基因组中包含的 个基因的序列ij 以用n = l ，2 ，) 上的有符号排列来表示在有符号的情况r ，排列中的每 个元素都被赋予了“+ ”或“一”个反转p ( i ，) 将排列 牙= ( 刀【，码，互小巧一，廖，石川，瓦) 变为 石= ( 正，万2 ，t - - ，一一1 ，一万。，一万，丌一，丌。) 即在改变片段【f ，j 上的每个元素次序的同时，改变片段中元素的符号此时反序距 离问题是指把有符号排列f 变换成单位有符号排列i = ( + l ，+ 2 ，+ ”) 所爱求的 最小反序数d ( e r l 1 2 基因组重排问题的发展与现状 近1 0 年来，有关基因组重排，特别是基于反序的基因组重排的数学特征及算 法的研究，一直是计算分予生物学中受到广泛关注的课题现已证明，如果基因是 具有方向的，则反序基因组重排问题是多项式时间可解的，而且目前已经找到了 十分有效的算法但是如果基因是无方向的，则基因组璧排问题是一个n p h a r d 问 题，目前尚未找到有效算法 在基因组重排的早崩计算研究中，w a t t e r s o n 2 1 以及n a d e a u 和t a y l o r l 3 1 分别日| 进了断点的概念，并且注意到一些基因组之糊的反序距离与断点数之间的具有下 列关系：a ( x ) 6 加) 2 ，其巾6 缸) 是z 中的断点数。基于断点的概念，k e c c c i o g l u 和s m k o 一4 j 发现了一个具有性能保证为2 的反序排序近似算法，他们还推导了有 效范围，当i 1 在3 0 5 0 范围内变化时几乎最优地解决了反停距离问题然而，用 断点对反序距离进行估计是非常不精确的b a f n a 和p e v z n e r 瓠 入了另一个参数 ( 断点圈的最大圈分解) 来估计反序距离，证明了d 衍) h + 1 一c 融) ( 其中c 加) 是 断点图的最大圈分解数) 这一结果比断点情况下的d 缸) b ( x ) 2 更严格对于大 多数生物学例子都有d 伽) 一 + 1 一c 徊) 成立，于是就把问题归结为最大圈分解问题 目前，由于c a p r a r a l 6 j 已经证明了按反序排序一个无符号排列是n p h a r d 阔题，连 多研究者都在设法寻找实用的近似算法 对于有符号排列的情形，1 9 9 5 年，h a n n e h a l l i 和p e v z n c f q 给出了第一个计算 两个n 元有符号基因组问的最小反序距离的多项式时间算法，其运行时间是 d ( n 4 1 ；基于这个算法，k a p l a n ，s h a m i r 和t a r j a n t 8 l 在进行些改进之后，给出了 一个时间复杂性为o ( n 2 1 的算法，t a n n i e r 和s a g o t 9 l 给出了反序排序有符号排列的 时间复杂性为o ( n 撕l o g n ) 的算法：b e r g e r o n ”jm q 提出了一种直接在最初给出的排 列上描述安全反序和障碍的方法，得到了该问题的一个时间复杂性为o ( n2 ) 的算 法，然后利用p o t r e e 重新编码及h a m l e h a l l i 和p e v z n e r 使用的障碍和堡垒等参数， 引进了一个新的参数t ，它表示p q t r e e 的最优覆盖值，得到了一个简单的结果 d 缸) t n c + f ，从而得到了这闻题的0 ) 算法【1 1 l ；2 0 0 0 年，b a d e r 和m o t e t i 坨j 等人给出了特定条件下的线性时间算法：2 0 0 3 年，e f i k s e n 和h u l t m a n i ”j 又利用计 算对称群中服从均匀分布的f 次随机置换的置换距离得到服从独立均匀分布的t 改 随机反序的期望反序距离 随着研究的不断深入，人们更加关注能否找到一些衡量进化方案质量的新标 准大量的研究表明，物种在进化过程中能够保存下来的共同的基因片断，很可能 是它们具有亲缘关系的标志因此，不破坏基因组组合结构的进化方案( 进化过程 中始终保持两个染色体中共同基因片段) ，是我们比较感兴趣的重排方案事实上， 如果两个基因组具有某一共同特征，那么它们的共同祖先很可能也具有这一特征， 这就使得研究保留这些特征的进化方案更有实际价值。本文将着重研究不破坏基 因组组合结构的进化方案，其中所探讨的组台结构是指两个基因组中的保守块， 即排列的共有区问 给定两个n 元排列，由排列中斗目同元素构成的一对区i 刨称为它们的共有区闷 许多研究者对共有区问做了细致的研究，关于共有区闻的一些结果已经用于测序 问题，并收到了较好的效果2 0 0 0 年u n o 和y a g i u r a “l 得到t 计算两个排列中所 有共有区间的快速算法： ( 1 ) 时间复杂性为o ( n2 ) 的l h p 算法，对于随机产生的两个排列，该算法的期 望运行时间为o m ) ( 2 ) 时问复杂性为o o + k ) 的r c 算法，其中k ( s f ：1 ) 是共有区间数该算 、 法也表明对于两个随机产生的排列，期望的共有区阍数是o ( 1 ) ( 3 ) 时间复杂性为o ( n3 ) 的m n g 算法 随后，h e b e r 和s t o y e t “】在此基础上拓展了这一结果得到r 计算k 个n 元摊列的 所有共有区间的o ( n k + k ) 时间和o ( n ) 空闻算法 同时基于共有区叫的反序排序问题，也已进入人们的研究范围2 0 0 2 年， b e r g e r o n 和h e b e r i “l 将共有区m 与反序排序紧密结台，产生r 一些新的定义和算 法：m a r t i nf i g e a c i ”j 等人研究了在反序排序中增加新的限钸i 不破坏基因聚类 ( 即排列的共有区间) 问题，证明该问题在计算上是n p c o m p l e t e 的，并给出了特 定条件下的多项式时问算法；2 0 0 4 年，b e r a r d 和b e r g e r o n 1 8 】提出了一类特殊的保 持共有区间的基因组熏排方案，给出了判断由一个基因组转换成另一个基阏组晟 5 优交换方案存在性的线性对阐算法，若存在，剥给出该方案 1 3 本文的主要研究对象和研究成果 本文的主要研究对象是保留共有区间的基因组重排方案问题除非特别注明， 文中所提及的基园组都将由有符号排列来表示，对基因组的重排操作也仅限于反 序操作另一方面，由于对任意给定的饥2 ，n 上的两个排列，可以将其中任意一 个排列重新定义为恒等排列，同时调整另个排列的相应元素，这样就把要研究的 问题转化为一个复杂排列和。一个恒等排列之间的问题柬研究，文中提及的反序方 案都是将一个排列转换为对应的恒等排列 本文的主要研究结果有以下两个方面： ( 1 ) 旨先，对h p 理论中提及的交叉图，做了重新描述和更加简单的构造，将 新得到的交叉图用于基因组重排的交换方案问题的研究，得到的结论与b e r a r d 和 b e r g e r o n 在文献【1 8 】所给出的结论相同并在此基础上提出了非交换方案的概念， 同时对非交换方案转换成交换方案做了一些有意义的研究 ( 2 ) 由于基因组进化过程的变换方案是一类特殊的完美方案，而一个完美方 案并不一定是晟优的因此，人们更加关注的是基因组进化过程中，是否存在一般 的完美方案和最优完美方案的问题本文在k a p l a n ，s h a m i r 和t a r j a n 等人提出的 反序排序有符号排列算法基础上，加入了对保持共有区闻问题的探讨，改进了 k a p l a n ，s h a m i r 和t a r j a n 等人提出的算法( 简称k s t 算法) 通过对荆 序定向分 支和不定向分支得到的反序与排列的共有区间进行比较，町确定得到的反序是否 保持排列的共有区间在此基础上给出一个多项式时间算法，判定一个排列能否被 一个最优的完美方案进行排序，从而存一定意义上很好地解决了基因组进化过程 中的最优完美方案问题 6 第2 章预备知识 2 1 术语和记号 为讨论方便起j i ! l ，首先引入一些图论术语和记号，主要来源于参考文献 1 9 1 等 定义2 1 所谓圈g 是一个三元组，记作g 一缈( g x e ( g x 妒( g ) ) ，其中y g ) 表 示g 的顶点集，e ( g ) 表示g 的边集，妒( g ) ：e v y 称为关联函数 定义22 图gz g ( v ，e ) 的结点集v 的元素个数即基数称为g 的阶，它的边集 e 的基数称为g 的大小， 集合工的基数通常用p 表示，即一= 旷i 代表结点个数，m - f i 代表边数 定义2 ，3 关联于同一条边的两个结点称为邻接结点 定义24 设g 是任意图，# 为g 的任一结点，与结点关联的边数( 条环 要计算两次) 称为j 的度数 定义25 无向图g t g o ，e ) 指的是结点集v 是一个非空集合，边集是矿中 的无序偶集合的一类图，即无向图的边不带有方向 定义26 给定无向图g - 杪( g x 枯i 铲妇) ) ，矗，y ( g ) ，若图g 中存在连 接x 和y 的路，称结点x 和y 是连通的规定z 到自身总是连通的 定义27 树是无隧连通无向图，树中度数为1 的结点称为树的叶子，树中度 数大于1 的结点称为树的分支点或内点 定理21f 是树当且仅当r 中无环，日伍何不同两顶点闻有且仅有一条路 定义28 设s 是图g 的任顶点集，g 中与s 的顶点邻接的所有顶点的集合， 称为s 的邻集( n e i g h b o u rs e t ) 定义29 简单图是指不含平行边和自环的图， 自环指的是从结点到自身的边：在有向图中，两结点之问同一方向豹边称为 平行边，而对于无向图，关联子相同两结点之间的边称为平行边，含有平行边的 图称为多图 定义2 伯设g = ( r ，e ) 是简单无向图，丁矿，t ，妒，若r 中任意两个顶点都 相邻，则称r 是g 的团( c l i q u e ) 2 2 反序排序的概念和性质 为讨论方便起见，下面介绍一些反序排序的概念和性质，主要来源于参考文 献【l ，2 0 】 定义2 1 1 一个有符号排列是指集合喜，2 ，n 上的排列”- 协一，_ ) ，其中 每个元素均被赋予一个表示方向的符号“- 4 - ”或“一” 为方便起见，有时将“+ ”省略，将“一”记为上标，如一3 记为3 对任意给定的 1 ，2 ，h 上的两个排列，可以将其中任意个排列重新定义为 恒等排列，同时调整另一个排列的相应元素，这样就把要研究的问题转化为个复 杂排列和一个恒等摊列之间的问题来研究 定义21 2 排列上的个反序p ( i ，) 是指倒景区恻k j l 内元素的次序，同时 改变它们的符号被反序的部分通常用下划线表示，如 r g ，一“珥，j ，j “，j z 一z p ( i ，j ) 1 眩，一1 ，q ，一，一) 一个排列的区间可以有多种表示，如卜述定义中区间k j l 是由它的端点位簧 给出，它表示排列中从第i 个到第j 元素构成的集合；也可咀用区间内的所有无符 号元素集台协i ，k ，1 给出这样个恒等排列上的区间 “ 与反序p o ，) 就含 有相同的元素l ，i + 1 ，i + 2 ，j 一2 ，j 一1 ， 定义2 1 3 如果| i j l t l ，记f 一一通常增2 1 j z 。to 和以+ l = + 1 来扩展排列 玎- k 一，以) 如果一一“，称元素( 一，曩，) ，0 is h ，是霈的个邻接；否 则称之为的一个断点 通常隋况下，一个排列f 的断点数记为6 协) 定义2 1 4 无符号捧列一扛i ，- ，) 的断点图是一个有h + 2 个顶点 ， ，以，t + ；) - o ，i n + l 的边染色圈，记为g k ) ，对于o s is n - 使用黑 8 色边连接顶点吒和口。；若 ，r 用灰边连接顶点，t 。和， 定义21 5 设月是 1 ，2 ，一，n 上的个有符号排列，个n 阶有符号捧列到一 个 1 ，2 ，2 n 的( 无符号) 排列的变换定义立l i 下：用h 一1 ，2 x 替换正元索+ x ， 用缸，2 v 一1 替换负元素一# 。使用黑色边连接顶点万；和丌川：若石。一万，则用获边 连接顶点n 和”，得到育符号排列的断点图颐z ) 例如，排列t ( 4 ，3 ，05 ，2 ，7 ，6 ) 的断点图由图2 1 所示 二二：誊二：= 誊；j i ：弋= 一兰羔? 1 。 07 86 5 i 2 l o 9431 31 4i li 21 5 附2 1 排列n ( 4 ，j ，1 ，ij ，7 ，6 ) 的断点幽 f i g u r e2 ，1b r e a k p o i n tg r a p ho f p e r m u t a l i o n ”- ( 4 ，j ，1 ，i ，i ，7 ，6 ) 注意到g ( ) 中每个项点的度数为2 ，幽此它的断点圉是不相连圈的集台，记 这种嘲的数目为c ( 玎) ， 设p 是个反序，记 a ct c k ，p ) 一c 锄) 一c k ) ( 随圈分解的大小而增加) 对于每一个排列日和反序p ，有 c ( 肛) 一c 缸) s i ( 即c ( ”，p ) s 1 ) d h ) ；n _ 一1 一c k ) 如果c 一1 ，则称反序p 是恰当的如果能够对每个排列j r 找到个恰当反 序，那么就可以在h a - 1 一c k ) 步中对排列口进行最佳捧序但并非任意排列都青恰 当反序，比如，一( + 3 ，+ 2 ，+ 1 ) 就没有恰当反序，因此，我们不能在n + 1 一c 似) 一2 步中对排列进行最佳排序 我们说反序p ( 1 ，) 作用于g 协) 上的黑边( f 。，。) 和印，) 如果黑边 ( 石h ，玎) 和( 石，玎川) 属于c ，则p ( i ，) 是g 协) 的圈c 上的反序( 起作用的) 如果 作用于关联着g 的两条黑边上的反序是恰当的，则灰边g 是定向的，否b 就是无 定向的 定理22 ”3 设( _ ，。) 是一条连接黑边竹。， ) 和如，) 的荻边则( 玎，, r g ，) 是 定向的，当且仅当i k 一卜1 对于g 协) 中的圈c ，如果该圈中有一条定向的获边，则圈c 是定向的；否则， 它是无定向的显然，不存在作用于一个无定向圈的恰当反序， 2 ，3h p 理论的相关内容 t i p 理论是对h a n n e n h a l l i 和p e v z n e r 对于反序排序问题作出的一些基础性研究 结果的简称【1 ，州断点图中长圈的复杂交叉结构绘分析反序排序带来了系列困难 为了避开这个问题，p e v z n c r 和h a n n e n h a l l i 引进了排列的等价变换，并得到了下面 的些重要结果，这些结果成为后续研究的基础 g 扣) 中的软边( 以，口，) 和( 巩，_ ) 是交叉的，如果区闻【i 】和噼f 】交叠，但它们 互h ；包含 定义21 6 设f 。是排列玎的断点圈中圈的集合，玎 j 一个交叉圈记为 h 。( p 。，d 。) ，它的边的集台a ，z ( c 1 ，c ：) ic l 和c ：是g 缸) 中的交叉圈 定义2 17 “3 设。的顶点集被分为定向顶点和不定向顶点( ，中的圈) h 。 的一个连通分支是定向的，如果它至少含有一个定向顶点，否n q 就是无定向的 对一个连通分支u ，定义u 的最左点和最右点为 ，n n 。m 口i nj ，u m “4 麓 如果u 中存在一条灰边( ，z ，) ，使得 【u ：u 二】c i ，】，【u ：。，u 二，】旺 i ，j 】， 则称分支u 在口中分离分支l ，和u “ 设 是集合p 上的偏序z p ，如果不存在元素y e p 使得y z ，则称元素 x 为( ；p ，叫) 中的最小元素( 或简称x 为p 中的最小元素) ：如果对每个y p 有， z 则称元素z 为( 尸， ) 中的最大元素( 或简称z 为p 中的最大元素) 1 0 设如为交叉图圩。中的尤定向分支集，在此集合上定义容积偏序( c o n t a i n m e n t p a r t i a lo r d e r ) “ ”：v ( ，w 心，如果【u m ，u c 【巩。，w 。】，则记为u - w 定义2 1 8 n 1 一个障碍定义为一个无定向分支，不是最小障碍就是最火障碍， 最小障碍u 如是中的最小元素，是大障碍满足下面两个条件! ( i ) u 是_ 中的最大元素：且 ( i i ) u 不分离任何两个障碍 h a n n e n h a l l i 和p e v z n e r i 1 证明下界d k ) a + 1 一c k ) + b ) 是紧致的，其中a 印) 是”中所有障碍的个数作为得到e 界d k ) sn + 1 一c k ) + 白) + 1 的第一步，发展 了一种称为排列的等价变换的技术 设c - ，v b , w 。，w 。，r ，是排列石的断点图g 扣) 中的网，b 。( h ，) 神i g 一( w 。，v 。) 分别为其中的黑边和捩边g 坼) 的( g ，b ) 一分裂是+ 一。张新嘲，电为 0 k ) ，可以通过以下方法从g 扣) 中得到： 删除边g ，b 增加两个新的项点v ，w 增加两条新的黑边帆，v ) ，( w ，) 增加两条新的荻边( k ，w ) ，o ，k ) 如果g 缸) 是有符号排列口的断点图，那么g 0 ) 的每个( g 声) 一分裂对应于。 个有符号排列的7 “义排列席的断点圈，其中广义排列- 帆，以) 足指任意个不 相同实数组成的排列( 代替整数 1 ，2 ， ) 组成的排列) 设c 一，吒川石，万，玎。，是排列耳的断点图g 扣) 中的圈，扫一( 丑小嘎) 和 g 一0 ，。) 分别为其中的黑边和敷边定义一月。一，井设 ”。耳，+ i ，w 。一i 一个- 缸。，以) 的( 占，6 ) 一填充是n + 2 个元素的排列，通过在f 的第i 个元素 ( 0 is 月) 之后插入v ，w 得到 詹z 协1 ，f 2 ，一，v ，w ，曩+ 1 1 以) 设g ) 中的某一圈c 上的( g ，自) 一填充删除扶边g ，并增加两个新的灰边g 和 g ：如果g 是定向的，那么g 。或富：在g ( 卉) 中都是定向的如果c 是无定向的，那 么g ，和g ：在g ( 蠢) 中都无定向若( g ，b ) 一填充把g 枷) 中的圈c 断裂成g ( j ) 中的 圈c 1 和c ：，则c 是定向的，当且仪当c 。或c ：是定向的设窖。和g ”是g 仁) 的两条 不同于g 的灰边那么g 和g4 在玎r p 是交叉的，当且仅当g 和占”在耳的( g ，矗) 一填 充中是交叉的设( 占，b ) 一填充将g 扣) 中的圈c 断裂成g ) 中的圈c 1 和c ：，每个 在g 加) 中与c 交叉的圈d 与g 协) 中的c 1 或c ：交叉对每条灰边g ，在g 如) 中存 在与g 交叉的灰边，从而有( g , b ) 一分裂和( g b ) 一填充之间的对应关系： 0 如) t g 脯) 设c 是g 啊) 中的圈，g 琏c 是g ) 中的嚎荻边那么g 与c 中的偶数条扶 边交叉 关于g 竹) 中的圈，有如下结论： 定理23 如果c 是g 扣) 中的一个长圈，那么存在一个作用于c 的安全( g ，b ) 一填充 一个排列月等价于排列口，如果存在一系列的排列”t ”( o ) ，( 1 ) ，g ( t ) * a ，使得对作用于一( o s i t k 一1 ) 的一个安全( g ，6 ) 一填充满足0 + 1 ) 一一0 如0 ) 对于每个排列，存在一个等价的简单排列每个口的一义排序模拟了一个( 真实的) 排序，两者的反序数相同，而且”的广义排序模拟了一个最佳( 真实的) 排序 下面说明如何通过一系列填充和包含d 加) 个反序的反序柬发现排列的一 个广义排列 设p 是作用于一个定向( 短) 圈c 上的反序那么 a 瑚- ( 以e ( c ) ) u f ( c ) 即p 删除边( c ) 并添加边占( c ) ，将h 。变换成 日船 p 改变隔d f 。的定向，当爿仪当d y ( c ) 由此，若p 是作用于圈c 上的反序，a 和b 是h ，中非相邻的顶点那么卅， b ) 是h 。中的一条边，当且仅当a ，b e v 【c ) 若p 和d 是分别作用于g ( ) 中两个变 叉定向圈c 和c 。上的反序，如果c 属于h 叫中的个无定向分支k ( p ) ，那么 葺( p ) 外边的每两个顶点如果存，中相邻，则它们在k 中也相邻 与h 。相比，在日。中k 。( p ) 外部顶点的定向并不改变 一个( 简单排列的) 交叉图中每一个无定向分支包宙至少两个顶点，关于日。中 的每一个定向分支，有如下结论： 定理2 4 ”】对日。中的每一个定向分支k ，都存在一个( 安全的) 反序p e 6 ( k ) ， 使得所有的分支置，p x k ：( p ) ，在日。中定向 如果中包含一个定向分支，那么z 中存在一个安全反序，在缺乏任何定向分 支的情况下，p c v z n e r 和h a n n c n h a l l i 介绍了如下方法寻找安全反序设叫是集j p 上 的偏序，称p 中的y 覆盖x ，如果j - ( y 且不存在元素z p ，使得x y z 的覆 盖图q 是( 无向) 图具有顶点集p 和边集缸，y ) ：x ，y p ，y 覆赦 在障碍k 中嘲上的每个反序p 从玎的覆盖圈中切割叶予k ，即q 肋一q ，k 作用于简单障碍的圈的反序是安全的 如果工和m 是g 中的两个障碍，定义尉研蜗旧为来自覆盖图q 。中口 予 到叶子埘的( 惟一) 路径上的( 无定向) 分支集合如果| 已和掰是- 中最小元素 定义l c a ( l ， ) 为l 和