（运筹学与控制论专业论文）24逆序变换的置换排序问题.pdf

摘要 摘要 本文主要研究2 , 4 一逆序变换的置换排序问题全文其分三章 第一章是绪论部分，介绍计算生物学的背景内容以及相应的基础知识在这 章中介绍了计算生物学巾d n a 链的测序，d n a 链的组装和基因组绘图的基本概 念，并且总结了近年来出现的有关结果 第二章研究2 ，4 一逆序变换的置换排序问题在第一节中详细介绍了置换排序 以及2 ，4 一逆序变换，并总结了它的研究结果在第二节中通过对置换 n ， 一1 ，1 的2 ，4 一逆序变换排序来说明2 ，4 一逆序变换如何操作在第三节中对 特殊排列b 的2 ，4 逆序变换排序用万( 1 协( 2 ) x ( n ) 表示1 ，2 ，聆这 个数任 意的个排列，b 则表示前半段任意一个数都比后半段任意一个数大的排列的集 合，即b = 万e s j 对所有的】- 万0 ) ) i nt h ef o u r t hs e c t i o n ，w es o r tg e n e r a lp e r m u t a t i o nb y2 ，4 - r e v e r s a l s k e y w o r d s ：s o r t i n gp e r m u t a t i o n s ，2 ，4 - r e v e r s a l s ，g e n o m er e a r r a n g e m e n t s 绪论 第一章绪论 1 1 计算生物学简介 在最近几年，发生了一些和基因组研究有关的大事，破译人类基因组密码就 是其中的一个生物科学的发展对人类每天生活的很多方面都有非常大的影响 自从w a t s o n 和c r i c k 发现d n a 链的双螺旋结构以来 j f 5 3 ，生物学在了解生 命的基础方面取得了很大的进展如果不是其它领域的学科的帮助，那么这个进 展是不可能达到的它们是物理，化学和计算科学我将集中研究计算科学对生 物学的影响，尤其是与运筹和组合优化有关的那部分。因为组合优化与生物学之 间的联系可以在生物学的很多方面找到，我将集中研究那些在计算生物学中出 现的组合优化在建模和解决问题的应用方面最重要的例子( 个人观点) 它们包 括：d n a 链的测序，d n a 链的组装和基因组绘图。以下我将对这些问题作简单 的介绍，有兴趣的读者可以在以下文献中找到详细的介绍 g d 0 3 ，g u s f 9 7 ，p e v z 0 0 ， j j 9 7 w a t e 9 5 】 1 2 生物学基本知识 生物学是在不同层次了解生物的本质的科学，从分子到细胞，个体到群体， 所有的生物器官都是由单细胞或多细胞组成的，这已经达成了共识在牛物学的 发展中，一个主要的兴趣在分子和细胞方面，因此，我们有了分子生物学加上 计算科学建模和其它工具( 组合优化是其中的个主要成分1 的帮助，就因此产生 了计算分了生物学 计算生物学研究的一个主要物体足d n a 链，对生物器官遗传信息的编码 d n a 是由字母表 a ，c ，gt ) 的字母( 核苷酸) 组成的一个序列短的单链d n a 分 子称为低聚核苷酸器官的整个d n a 称为它的基因组，并且它的长度可以达到 十亿多个核苷酸( 或碱基对) 给定个生物器官( 例如人类有几亿多个细胞) ，在 每个细胞中都包含一样的基因组d n a 的形式是双螺旋，也就是双链，其中a 与 t 配对，c 与g 配对这个d n a 构造的基本法则是由w a t s o n 和c r i c k 发现的 2 ，4 - 逆序变换的置换排序问题 j f 5 3 】因此，如果知道了d n a 双螺旋的一条链，可以非常容易地推出第二条 链( 互补) 而且，单链的这个性质( 试着和互补的链结合) 称为杂交，可以应用在实 验室里很多地方，例如重构那些不知道的链 d n a 中包含的基凶信息被用来制造r n a ，最终是蛋白质后者是生物器官 的主要构造材料，也决定了它们的功能 在下面的内容中，我将集中于d n a 分析和重构，因为这些步骤需要组合优 化的很大帮助我将考虑与d n a 破译，序列比较和系统分析有关的组合优化 破译d n a 基因序列是更深入的分子生物学研究的起点但是破译d n a 基因 序列本身并不简单，它包含许多复杂的过程这是由于核苷酸的序列不能用直接 的方法破译，例如，用显微镜因此，必须用不直接的方法破译一个基因组的 序列通常分为三个步骤：绘图，组装和测序 破译一个长的d n a 片段，首先要把它切成大约1 0 00 0 0 10 0 00 0 0 个核苷 酸的小片段在切开的过程中，片段之间的顺序信息丢失了但是，必须重新恢 复这些消息，这可以通过绘图步骤来完成当绘图的时候，片段被切成更小的片 段，大约4 00 0 0 个核苷酸长度因此，绘图必须要恢复那些e h - - 次切割得到的小 片段的顺序【g u s f 9 7 】 因为测序方法只能决定那些长度不超过1 0 0 0 个核苷酸的序列，所以长度大 约为4 00 0 0 个碱基对的片段不能被直接测序因此，有必要把它断开成合适长度 的片段这是随机完成的在这步我们得到适合测序的d n a 片段当测序完成 后，这些短的片段通过组装步骤来得到最初的长度大约为4 00 0 0 的片段 1 3 测序 得到一个d n a 片段信息的最现代的生化方法是杂交实验【s j m l a d 9 1 a d e m c s 9 4 ，s o u t 8 8 这个实验的目的是测出组成一个d n a 链( 百来个碱基) 的 所有给定，( 通常是81 2 个碱基对) 长度的低聚核背酸为了这个目的，以生物芯 片的形式建了低聚核臼酸库，这包括所有町能的4 7 个长度为，的单链d n a 片段 然后，这个库用来与很多d n a 链的复制品比较( 用杂交的办法) 在杂交的过程中。 库中与d n a 链片段矸：补的低聚核苷酸会和它的复制品结合起来这些用f a ，c 绪论 gn 这个字母表组成的单词来表示的低聚核苷酸，形成一个集合称为谱当然， 在谱其中会包含一些错误的数据 有两种错误的数据：负错误，即谱中的缺陷；正错误，即谱中的超额通常 一个谱同时包含两种错误举例来说，如果一个低聚核苷酸在最初的序列中出现 了多次，那么会m 现负错误因为谱是一个集合，它之中只有一个元素与这个低 聚核苷酸对应由于不完全杂交反应的原阑，一个与d n a 链互补的低聚核苷酸 也可能没有被检测到正错误是一个与链结合的不互补的低聚核苷酸，或者是与 给定d n a 链的碱基不全互补的低聚核苷酸因此，杂交实验的结果就会得到一 个谱，其中没有包含起初序列中出现的所有单词，同时包含了起初序列中没有出 现的单词，通常不知道另外关于谱的信息起初序列的长度可以通过电泳凝胶来 测量 老的算法在解决测序问题时总是假设理想的谱，即没有错误的谱这就是从 胛一，+ 1 个不同的单词来重构起初的序列，相邻的单词有，一1 个字母是重复的第 一个测序算法是由b a i n s 和s m i t h 提出来的【w g 8 8 】它由谱建立了一个搜索树， 其中两个低聚核苷酸节点用一条弧连起来，如果前者后面，一1 个字母与后者前面 ，一1 个字母相同没有元素能在路中出现两次，起初序列的开始元素放在根部， 如果知道的话如果不知道的话，l 谱1 个树按不同的根来构造这个问题的解是从 根到叶子的一条路，包含所有谱中的元素( 例1 ) 下个测序问题的解法是l y s o v 等提出来的【y v a k v a 8 8 】，用到了图论中一个己知问题的变换在由谱构造的 有向图中，找一个哈密顿路每个低聚核苷酸对应丁一个不同的顶点两个顶点 a 和v 之间用弧( “，v ) 连起来，如果“的后，一1 个宁母与v 的前，一1 个字母相同( 例 1 ) 在【i r 8 9 】中d r m a n a c 等的方法与b a i n s 和s m i t h 的方法很类似，但是避 免了多余的操作在搜索树的分支之间了路是固定的，用长度为，或更长的单词 来表示树的节点连接起来，如果对应的单词有，一1 个字母霞复 例1 假设，杂交实验没有错误，起初序列为a c t c t g g , 并且我们知道开 始的元素是a c t 理想的谱是 a c tc t c ，c t gt ct ，t g g 我们知道， i 谱f 门一“1 ，其中h = 7 ，= 3 b a i n s 和s m i t h 的方法见图1 3 1 下面那条路经 2 ，4 - 逆序变换的置换排序问题 过了谱中所有的元素，因此是解起初的序列可以由根到叶子的节点来重构 图1 3 2 对应于l y s o v 等提出来的【，a k v a 8 8 】方法在图中，存在惟一 的哈密顿路由它可以重构起初的序列 图1 3 3 对应于d r m a n a c 等提出的方法类似地，解是从根到叶子的包含 所有谱的元素的路 7 c t g t g g a c t 、c t c + t c t + c t g + t g g 图1 3 1b a i n s 和s m i t h 方法中的搜索树 a c t g + t g g c t c = = t c t 图1 3 2 l y s o v 等人方法中的图 研0 0 仰。 图1 3 3d r m a n a c 等人方法中的搜索树 以上三个方法只接受输入数掘是理想的谱，尽管这样它们还是指数时间的 第+ 个而且是惟一的一个解决无错测序问题的多项式时间算法是由p e v z n e r 提出 的 p c v z 8 9 在这个方法中构造了一个有向图，要在其中找出一条欧拉路在 这里，每个低聚核苷酸对应不同的弧，起点用前，1 个字母表示，终点用后，一1 个字母表示( 例2 ) 因此，图中顶点的数目与谱中所有长度为，一l 的子单词个数相 咖i ： 斋- 叶g gt gg g 2 ，4 - 逆序变换的置换排序问题 2 g g t g 第一个假设谱中存在正错误的解决方法在【r j r 9 l 】中提出但是，这个错 误模型有很多限制正错误只能与跟它相关的负错误一起出现，并且不合适的字 母只能是第一个或者最后一个在这个模型中三个负错误不能连续出现 以下三个算法要求谱元素的另外信息其中的一个【e u j 9 2 】需要知道所有 4 。个低聚核苷酸杂交的概率( 这些可以通过实验得到) 这个方法产生了所有4 ”个 序列，有最大值的序列被认为是解但是，作者承认当n 大于2 0 的时候，这个方 法就无效了，因为需要很多的时间和容量【l i p s 9 3 】中的算法，除了知道谱中 错误的类型以外，还要知道谱中错误( 正错误和负错误分别的) 的百分比这模型 允许任何类型的负错误，i f 错误的模型是 r i r 9 1 】中的这个模型是从p e v z n e r 的方法【p e v z 8 9 】中推出来的，因此不能算非常精确表示整个谱的有向二分图 建立后，要分配每个弧在解中的概率这个图的最好的分配，对应于低聚核苷酸 的最好匹配，用h u n g a r i a n 白+ 法可以找到然后每个弧的概率被更新，一个新的 分配被选定，连续的分配值收敛下一个算法【j r r m l 9 4 】所有低聚核苷酸在起 初序列中出现的大概次数是已知的它允韵谱中任何的负错误+ 在顶点数为4 的图中，弧对应于谱元素，并且被分配了已知的近似值，要从中找到最可能的路 以下提到的算法不需要除了谱和起初序列长度以外的其它信息：它们允许 所有的错误类型【j p m w j 9 9 】d n a 的测序问题在这罩被归约到一类以谱为基础 建立的特别图的奖金收集旅行售货商问题( 岜就是选择性的旅行售货商问题) 这 个奖会收集旅行售货商问题和普通的旅行售货商问题小同，除了弧上有距离外， 它的节点上还有利润价值【m s 9 0 】目标是找出最大利润的简单路f 总利润是最 大) ，并且不超过给定的距离在d n a 测序的问题中，用到了l y s o v 模型，但是现 在任意两个顶点之间都可能有有向弧，它们之间的距离等于两个顶点之间变换 所需的最小次数如果两个顶点之间的距离一个比另一个大，那么就对应于丢失 的低聚核苷酸所有顶点的利润都设定为1 现在，要找最大利润的简单路( 谱中 最大数量的低聚核苷酸将被选择) ，距离不超过”一f ( 构造序列的长度将不超过 ) 例3 中将会详细介绍这个构造 例3 我们仍然考虑例1 中的谱，但是假设低聚核苷酸c t c 丢失了，同时 一个新的( 错误的) 元素g a t 被记录了因此，谱是 a c t , c t g , g a t , t c t , t g g 对应于奖金收集旅行售货商问题的图见图1 3 6 ， 在图1 3 6 中有两条路是奖金收集旅行售货商问题等价的解由其中一个， 例如( a c t , t c t ，c t g , t g g ) ，可以得到要求的序列 誓：、 、 图l3 6 从有错的谱归约到奖金收集旅行售货商问题实线距离为1 ，虚线距离为2 为了简单，距离为3 的弧没有画出来 在最初的文章【j p m w j 9 9 】中，提出了一个以分支定界为基础的精确的算 法同样的标准方程用在一些亚启发式方法中：t a b u 搜索算法【j p f m j 9 9 ，j f m 0 5 1 和杂交遗传算法 j m w 0 2 j p f m 0 2 中的启发式算法从最可能的部分通过 厚度方程组成一个解 在最后，我在这罩提到测序问题巾杂交阶段一个完全新的方法，在实验室里 以熔点而小是低聚核苷酸为基础【j p m w 9 9 】这样町以得到包含较少错误的实 验数据 2 ，4 - 逆序变换的置换排序问题 1 4 组装 在前面提到过的，测序只能应付长度为1 0 0 0 的低聚核昔酸，显然，有必要把 那些短的测好序的片段组装成长的片段这可能是破译基因组序列中最难的部 分有很多困难的问题要解决其中一个是怎么处理予序列重复中的错误已知 的组装算法通常把长的重复片段看作同一个子序列的重复出现这意味着算法 得到只含有一个这样重复片段的复制 一般来说，组装方溺商三个主要步骤组成：重叠检查，片段布局和得出结论 o u s f 9 7 由 第一步，要求出每个片段对之间的匹配程度因为测序的片段是由较长的序 列随机切割得到的，所以短的片断会有重叠这步的目的是找到每一对的最好重 叠更精确地说，对于一个序列对( s ，t ) ，要求出具有最大相似度的s 的后缀和t 的前缀【g u s d 7 1 第二步，要求出短片段的顺序在这一步中通常用贪婪算法其中一个方法 如下【g u s f 9 7 】有最高后缀一前缀相似度的一对序列被选中，然后组合起来接 着，第二最相似的对被选中并组合然后是第三最相似的对，依次类推 第三步，要求出组装成的较长片段的核苷酸序列 g u s f 9 7 第二步求得的 布局把每个短片段的每个核苷酸都分配到目标序列的惟一的位置如果分配到 一个具体的位置的所有核苷酸都是相同的，那么目标序列就恢复了否则，当不 同的核苷酸分配到一个给定的位置时，必须要选一种核苷酸也有可能不可能决 定这个核苷酸，因为分配了太多的核苷酸而且没有一个足显性的 决定合适核苷酸的最简单方法是每个字符在每个位置的频率，让研究者决 定怎么去使用这些信息另外个方法是求差异比较大的布局的区域对每个这 样的区域多重组装注意到这个可能会对布局有一点点改变，因为在第一步中只 在两个序列之间进行比较 在这节的最后，我将介绍三个特别的组装方法，它们用到了测序阶段的一些 想法 在 m y e r 9 5 】中，这个问题通过最大可能重构算法来解决在多重图重构 中，顶点对应于被组装的d n a 片段，边对应于它们的重叠重叠町以在d n a 的 一条链中，也可以狂d n a 的不同链中接着，进行卜列步骤首先，删除对应于 包含在更长片段中的片段的顶点接着，当( “w ) 和( w ，v ) 在图中时，删除( “，v ) 最后，惟一的子路被单一的顶点取代在新图中，最短序列对应于一个最大化 边的重叠的简单路最可能的解是用分支定界的方法来求的 铡4 图1 4 1 给出了组装少数d n a 片段的例子片段之问的重叠通常不 是很精确，会包含不匹配( 两个重叠字母不同) 和间隙( 字母与空白对应) 表1 4 1 包含选定的片段重叠的分数，假定匹配= + 1 ，不匹配= 1 和间隙一1 组装的结果 在图1 4 1 中的直线下面 c t c a a g g a = r g c a t c a g g at t t c g g a a c t t a a c a t t a a g c t c a a g c a t c a a g g a a c t t t c 在【r m 9 5 】中把【p e v z 8 9 1 中的方法用到了序列组装问题每个长度为h 的 输入序列用长度为f 的”一，+ 1 个低聚核苷酸集合来表示接着，从这些集合中构 造图，要求一条欧拉路为了保存输入序列的信息，要取较大的数这个方法 只在测序没有错误的时候适用 子汐的装组列序 an口 个 叠 图 重段个 l， 中 4 4 襄图 2 ，4 - 逆序变换的置换排序问题 下一个方法【p h m 0 1 】中，解决了包含几个错误实例甚至整个基因组包含 长重复的组装问题它通过在图中找欧拉超路来消除错误错误更正阶段包含在 实例改变中，使得在相对小的片段突变中，消除了最大数目的测序阶段的潜在错 误突变的有效性通过实例中的低聚核苷酸的整体数目来测量：一个错误的低聚 核苷酸的变换通常消除一系列的低聚核苷酸用和p e v z n e r 类似的方法来构造图， 另外对应于要组装的d n a 片段的路的集合被储存起来目的是找到一条包含这 些储存起来的路并以它作为子路的欧拉路 1 5 绘图 在19 7 0 年，h a m i l t o ns m i t h 发现限制性酶h i n d l l 遇到序列g t g c a c 或 g t t a a c 的时候就把d n a 分子切割开来小久，d a n n a 构造出了第一张限制性 酶切图谱，是关于多瘤病毒s i m i a nv i r u s4 0d n a 的从那时开始，表示带有由 限制性内切酶引起的分裂点( 位点) 的d n a 分子的限制性酶切图谱( 有时称为 物理图谱) 成了分子生物学中的基本数据结构 p e v z 0 0 一段d n a 分子的物理图谱能告诉我们分子上某些探针的位置这些探针一 般很小，但是是精确定义的序列这样的一个图谱帮助分子生物学家迸一步的研 究基因组例如，假设某一段d n a 已经被完全测序，得到序列s 如果我们知道 s 来自哪个染色体，并且如果我们知道这个染色体的物理图谱，我们就可以试着 找到s 中的图谱的一个探针如果我们成功了，那么我们可以把s 在染色体中定 位 j j 9 7 】 为了构造这样的图谱，一种流行的方法是限制性位点分析在限制性位点构 图法中目标是确定目标d n a 上给定的酶对应的限制性位点位置由于d n a 分子 一般很长，月前的实验技术无法对其进行直接测量，所以生物学家们就要把 d n a 分子切开，段一段的来测量但是，在切开的过程中，这一段段d n a 片 段在原先d n a 分子上的排列顺序丢失了，找出这些片段排列的顺序就是关键所 在为了构造一张限制性图谱，生物学家用不旧的生化技术获得关于图谱的l 日j 接 的信息，然后用组合方法从这些数据中重构图谱 0 绪论 构造限制性图谱的一种方法是用限制性酶来消化d n a 分子这些酶在限制 性位点把d n a 链切开，每种酶对应的限制性位点不一样对于每一种酶，每个 d n a 分子可能有多个限制性位点，可以按照需要来选择切开某几个位点( 不一 定连续) d n a 分子被切开后，得到的片段长度信息就是重构这些片段的初始顺 序的基本信息在多种获取信息的实验方法中，有两种最广泛的：部分消化和双 消化【p e v z 0 0 】 部分消化问题( t h ep a r t i a ld i g e s tp r o b l e m ，p d p ) ，只用了一种酶，要通过实验 得到任意两个限制性位点之间片段的长度在这里我们只用了一种酶，但是要对 d n a 分子的复制品做很多试验，通过改变酶和每个复制品的反应时间来完成通 过控制酶与d n a 的反应时间，或多或少的限制性位点将被切开，从而产生了不 同长度的片段理想情况下实验可以得到每对限制性位点的至少一个片段具 体实验方法如下：首先d n a 分子要被复制，然后分成三类第一类中的d n a 分 子都只在一个限制性位点处被切开( 这可以通过控制时间来办到) ；第二类中的 d n a 分子在任意的两个限制性位点处被切开；第三类中的d n a 分子在所有的 限制性位点处被切开假设与使用的酶对应的限制性位点有n 个，则分别对应于 第一类和第三类可得到2 n 个片段和 + 1 个片段，这些片段的长度都可以通过实 验来得到显然，如果试验没有错误的话，通过第一类的d n a 分子得到的2 玎个 长度可以分成n 对，每对加起来都等于d n a 分子的总长度由第三类得到的”+ 1 个长度，加起来等于d n a 分子的总长度然后对由第二类得到的长度数据进行 适当的处理，删掉与另两类重复的数据最后，由这三类得到的数据加上总长度 就是”个位点加上两个端点任意两点之间的c ：+ ：个距离p d p 就是从c ：+ ：个距离 来重构月个限制性位点的位置( 解不一定唯一，两个端点对应于最长的距离) 若 x 是非负整数集合x 的所有点之间距离的集合，p d p 就是给定a x 求x 就像 你知道了高速公路任意两个出几之间的距离，求这些出口的位置卜j 图给出了一 个例子 2 ，4 - 逆序变换的置换排序问题 252 aabcdb 图1 5 1 a ，b 是d n a 分子的两个端点a ，b ，c 和d 是限制性位点上面的数字表 示各小段的长度a x = 2 ，3 ，4 525 ，9 ，1 4 ，1 6 ，7 ，1 2 ，1 4 ，9 ，1 1 ，7 ) 我们通过实验可以得到x ，再 通过x 来求x ，对应于上图的x = ( 0 ，2 ，5 ，9 ，】4 ，1 6 ) 是一种解 在2 0 0 1 年，j b l a z e w i c z 及其合作者提出了一种新的方法，称为简化的部分 消化方法( t h es i m p l i f i e dp a r t i a ld i g e s tp r o b l e m ，s p d p ) 【j p m m w o l 】这个方法 和部分消化类似，也只用种酶首先d n a 分子也要被复制，但是它只分成两 类一类d n a 分子都只在个限制性位点处被切开，另一类d n a 分子在所有的 限制性位点处被切开这个方法与p d p 的不同就在于它避免了在任意两个位点 切开d n a 分子的难题和处理重复数据的困难 设f = 帆，：，y ：。) 为由第一类d n a 分子得到的片段长度重集( 不包含整 个d n a 分子的长度) 且设人= 编，五，厶+ ，) 是由第二类d n a 分子得到的片段 长度重集，其中j 是目标d n a 分子中与酶对应的限制性位点数将1 1 中的元素 按不减排序后，得到片段长度的一个排列a = 显然在理想情况 下( 没有试验错误) ，4 中的每个元素a ，对应于另一个元素a ：。+ 。使得 a ，+ a ：。+ ，= 上，其中三是目标d n a 分子的长度我们称这些片段为互补的且记 它们为 a ，a ：。+ ，) 每对互补的片段对应于目标d n a 分子卜的一个限制性位点 显然，这些片段在r 标d n a 分子上的顺序不知道记只= 和 最+ l = 表示 d 。，d 2 。+ 1 ) 的排列，且汜盯，为只的前缀记 q = q 。，q 。，q 。) 为互补片段的排列，其中q ，= 尸或者q 。= 只。+ 1 对i = 1 ， ， 成立而且，也x = 为把q 中的每个排列的前缀按不减排序后得 到的前缀序列对每个集合q ，对应于一个整数重集r = ，2 ，r n + ，使得 = x l ，= x ，一x 。对f = 2 ，n 成立且o + 。= 一工。现在我钟j 可以如下来说明 绪论 s p d p 问题：给定重集r 和a ，要找到序列x 使得对应的重集r 等于a 【j p m m w 0 1 】 双消化问题( t h ed o u b l e d i g e s t p r o b l e m ，d d p ) ，用了两种酶( 酶a 和酶b ) ， 它们对应的限制性位点不同同样，首先d n a 分子要被复制，然后也分成三类 在第一类d n a 分子中只加入酶a ，并且让它把所有的限制性位点都切开；在第 二类d n a 分子中只加入酶b ，也让它把所有的限制性位点都切开；在第三类 d n a 分子中加入酶a 和酶b ，让它们把各自对应的限制性位点都切丌假设酶 a 对应的限制性位点有m 个，酶b 对应的限制性位点有”个，则分别对应于这三 类可得到m + 1 ， + 1 和m + n + 1 个片段，这些片段的长度同样可以通过实验得到 在实验没有错误的情况下，这三类片段每类的片段长度加起来都等于d n a 分子 的总长度对于任意的非负整数集合j ，记五r 为j 中连续的元素的距离集合 在d d p 中，重集x 亡 0 ，f 分成两个子集x = a u b ，0 爿，b 且t a ，b 试验可 以得到三个重集：鲥，国和点y ( a 和b 对应于加单个酶的情况，而爿对应于加 两种酶的情况) d d p 就是从这些数据中重构a 和b 下图给出了一个例子 a 二工二工二二 图1 5 2 图中的片段k | 度集合就是谢，6 口和积，要求a 和b 中片段长度的一个排列 使得由于重叠产生的片段集合x 与试验得到的数据相等 在2 0 0 1 年，m i n g - y a n gk a o ，j a r e ds a m e t 和w i n g - k i ns u n g 提出了一个新的 方法，称为增强的双消化( t h ee n h a n c e dd o u b l ed i g e s tp r o b l e m ，e d d ) 问题【k s s 0 3 】， 在这个方法中，也用了两种酶( 酶a 和酶b ) ，它们对应的限制性位点不同同 样，首先d n a 分子要被复制，然后也分成三类存第类d n a 分子中只加入酶 2 4 - 逆序变换的置换排序问题 a ，并且让它把所有的限制性位点都切开；在第二类d n a 分子中只加入酶b ， 也让它把所有的限制性位点都切开；在第三类d n a 分子中加入酶a 和酶b ，让 它们把各自对应的限制性位点都切开然后，对于第一类中得到每个d n a 片段， 加入酶b ，把片段上对应b 的限制性位点都切开；对于第二类中得到的每个d n a 片段，加入酶a ，把片段上对应a 的限制性位点都切开与d d p 相比，就是增 加了一些试验，得到更多的数据 考虑一个目标d n a 序列和两种酶a 和b 通过分别应用酶a ，b 到目标d n a 序列，我们分别得到p ，q 个片段设 4 = k 1 一，郎j ，b = 协l 一，b 。j 分别是那些p ，g 个片段长度的重集 对于i = 1 ，p ，设舀，是对应于a 。的片段我们把酶b 应用到片段a ，上，得到 一个子片段的集合设a b , 是这些片段长度的重集 对于j = 1 ，q ，设6 ，是对应于b ，的片段我们把酶a 应用到片段q 上，得到 一个予片段的集合设删，是这些片段长度的重集 可以容易地证明这样找到的数据有下列性质： 1 x , j 于i = l ，p ，q = c ：对y - j = 1 ，q ，b ，= 。c 2 ，u ，爿曰，= u ，b a ，= c ， 3 i c i = i a h b i l 给定4 ，b ，a b ，a b 。，b a 一，b a 。，增强的双消化问题p 要求爿和b 中元素的 一个有效排列。，万。) ，使得以卜i 的条件能被达到当对应于qe a 的片段a 。和 对应于6 ，eb 的片段6 ，按照玎。和玎。给定的顺序划分在同一条直线上时，由丁二重 叠会产生一个子片段的集合这些子片段的长度的重集c 应该等于 u ：，a b ，= u ：。b a ，另外， 对每个口，a ( b b ) ，a b 。( 删，) 等于j 西，( b ，) 重叠的予区间长度的重集 2 ，4 - 逆序变换的置换排序问题 第二章2 ，4 _ 逆序变换的置换排序问题 2 1 引言 用最少的操作来进行置换排序是计算牛物学 b p 9 6 1 ， b p 9 8 1 ， c a p r 9 9 1 ， 【h p 9 9 】， j d 9 5 】和互联网络设计 a k 8 9 1 ， a n n e 9 0 的重要问题在 计算生物学中，置换排序为一个染色体内的基因重排建立一个数学模型 b p 0 2 逆序变换的置换排序问题是由计算生物学中的问题引起的【j d 9 5 】 h a n n e h a l l i 和p e v z n e r 【h p 9 5 】证明了有符号的置换排序问题是多项式时间可解 的并且给出了一个o ( n 2 1 的算法s h a m i r 和t a r j a n k h t 9 9 简化并改进了算法 对于无符号的置换排序问题，k e c e c i o g l u 和s a n k o f f j d 9 5 】给出了一个竞争比 为2 的算法，c a p r a r a c a p r 9 9 证明了这个问题是n p - h a r d 的p e v z n e r b p 9 6 1 ， c h r i s t i e c h r i 9 8 】，b e r m a n 【p s m 0 2 】改进了近似比，目前最好的是竞争比为 1 3 7 5 的近似算法【p s m 0 2 】 可以用群论来表示这个问题，给定个对称群鼠中的置换万，我们要用最少 的置换序列“，儿，以使得硝 儿托= ，其中，足s 中的恒等置换我们用 一个数字序列来表示一个对称群s 中的置换石，例如， f 123456 i i = 341 562 【3415 6 2j 一个逆序变换仃是一个置换中两个元素之间的重排，具体地说，逆序变换 d ( f ，j ) ，其中1 i 万( j ) 最后， 我们通过对特殊排列b 算法的递归调用来实现对一般排列的2 ，4 一逆序变换操作 2 2 对置换 ， 一1 ，1 的2 ，4 一逆序变换排序 在这一节中，我们通过对置换n ，月一1 ，l 的2 ，4 逆序变换排序束了解2 ，4 一 逆序变换排序的具体形式 不失一般性，设n m o d3 = 1 ，即 = 3 t + i ，且设 m o d 4 ；0 对于其它情形， - _ 。- - 一 即n m o d3 ；0 ，2 或者七m o d4 ；1 ，2 ，3 的情况，相对于胛= 3 k + 1 且女m o d4 ；0 的情况来说，只需要0 ( ”) 次变换来处理余下的那砦数因为对于余下的每一个 数来说，我们总可以用2 一逆序变换来将它移到f f 确的位置，而这个过程最多需 要疗次变换【x z l 0 4 】 对于3 + 1 ，3 t ，3 一1 ，4 ，3 ，2 ，1 这个排列，我们将按照1 到3 + 1 的顺序依 次分别将它们变换剑正确的位置 算法s o r t _ d e c r e a s i n g ： 步骤l ：用4 一逆序变换将1 变到第1 个位置，即将1 与4 交换，再将1 与 7 交换，如此继续下去，直到l 与3 + 1 交换，共需 次变换 步骤2 ：用4 一逆序变换将2 变到第2 个位置，即将2 与5 交换，再将2 与 8 交换，如此继续下去，直到2 与3 t 一1 交换，共需 一1 次变换同理变换3 和4 ， 分别需a 一1 次变换这时排列为l ，2 ，3 ，4 ，3 t + l ，3 女，9 ，8 ，7 ，6 ，5 2 ，4 - 逆序变换的置换排序问题 步骤3 ：变换5 时，先用2 逆序变换将5 和6 、7 分别交换，排列变为 1 ，2 ，3 ，4 ，3 k + l ，3 k ，9 ，8 ，5 ，7 ，6 再用4 一逆序变换将5 和1 0 交换，再将5 和 1 3 交换，如此继续下去，直到5 与3 七+ 1 交换，共需2 + ( k 一2 ) 次变换 步骤4 ：变换6 时，先用2 逆序变换交换6 和7 ，再用4 一逆序变换交换6 和8 ，再交换6 和1 1 ，如此继续下去，直到6 和3 女一1 ，共需1 + ( k 一2 ) 次变换 步骤5 ：变换7 时，直接用4 一逆序变换交换7 和1 0 ，再交换7 和1 3 ，一直 到交换7 和3 i + 1 ，共需k 一2 次变换到此为止，排列变为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，3 k 一1 ，3 t ，3 t + 1 ，1 1 ，1 2 ，1 3 ，8 ，9 ，1 0 此时的情况与起初将l 变到正确位置后的排列1 ，3 k 一1 ，3 七，3 i + 1 ，5 ，6 ，7 ，2 ，3 ，4 类似 步骤6 ：类似地重复以上操作，直到将排列3 k + 1 ，3 k ，3 k 一1 ，4 ，3 ，2 ，l 变 为1 ，2 ，3 ，4 ，3 k 一1 ，3 k ，3 k + 1 定理2 2 1对置换h ，n 一1 ，1 的2 ，4 一逆序变换排序问题， ：! = ! 兰竺兰兰竺兰翌竺竺：一、 一一 证明：如上所述，我们只考虑 = 3 k + 1 且m o d4 - - - 0 的情况，对于其他情 况只需要d ( n ) 次变换来处理余下的那些数 将这3 t + 1 个数分组，分为1 ，( 2 ，3 ，4 ) ，( 5 ，6 ，7 ) ，( 3 一l ，3 七，3 _ + 1 ) 这k + 1 组可以看出，第l 组需k 次变换，第2 组共需3 ( k 1 ) 次变换，第3 组 共需3 + 3 ( k 一2 ) 次变换第4 组( 8 ，9 ，1 0 ) 的情况与( 2 ，3 ，4 ) 类似，共需3 ( k 一3 ) 次变换第5 组需3 + 3 ( k 一4 ) 次变换，第k 组需3 【七一( k 一1 ) 】次变换，第k + 1 组需3 郴卅次变换这川组共需三2 k 2 + k = 吾学+ 孚= 1 次变 换 综上所述，对于馓的置换n ，订一l ，1 ，定理成立 2 ，4 - 逆序变换的置换排序问题 1 2 3 4 5 2 3 2 4 2 5 2 0 2 1 2 2 1 7 + 8 + 1 9 1 4 1 5 1 6 1 1 1 2 1 3 8 9 1 0 ： 图2 2 1 = 2 5 时的情肜只罹示j ，l 到7 的变换过程，后面的类似，救省略 8 ，2 3 4巧m丝甜加悖他m”b佗m 9 8 7 6 5 2 3竹拼笛孔博伸h”m他b 8 9 m 5 6 7 4 2筋m砣甜加伸他mh b 他m 9 8 7 6 ，4 一 m勉烈伸体”m埒h b 坨m 9 8 7 6 5 4 3 2 ， 2 ，4 5 6筋m驺鸵列加坶掩”mh挖m 9 8 7 2 3 4 5m筋加扒鸵体伸”m他b 8 9 m 6 7 2 3 4笱m船扒加伸埽m博h b ! m 9 8 5 7 6 2 ，4 - 逆序变换的置换排序问题 2 3 对特殊排列占的2 ，4 - 逆序变换排序 在这一节中，主要考虑这样一种特殊排列b 的2 ，4 一逆序变换排序问题如前 所述，用万( 1 ) 石( 2 ) 万( 挖) 表示1 ，2 ，挖这i 1 个数任意的一个排列，b 则表示前半 段任意一个数都比后半段任意一个数大的排列的集合，例如 1 0 8 9 1 1 7 642315，即 b - = 万瓯l 对所有的1 f l n l 2 j 和i _ n 2 + l j n ，满足丌( i ) 石( j ) ) 同理考虑珂= 3 k + l 且k r o o d - - - 0 的情形，并假设妄 + l 在中间也就是第 z 2 丢南+ 1 的位置，因为如果不是的话，可以用2 ，4 - 逆序变换在联”) 次变换内将它 移到中阳j 下面，我们详细讨论b 排列的变换过程，并分析其变换次数 步骤1 ：将1 ，2 ，丢和主| j + 2 ，主t + 3 ，3 t + 1 分别移到相应的位置 1 1 将1 ，2 ，丢变换到第吾七+ 4 ，三t + 7 ，3 t + 1 个位置( 不一定对 应) ，将丢+ 2 ，_ 2 5k + 3 ，3 j i + l 变换到第l ，4 ，7 ，吾一2 个位置( 不一定对 1 1 1 将在 1 ，j 1 女 之间且不在三七+ 4 ，三+ 7 ，3 t + l 位置上的数做个 1 1 2 将不在l1 ，圭女i 之间且在吾七+ 4 ，吾+ 7 ，3 t + l 位置上的数用y 1 1 3 ：t 张i 5 k + 2 , 3 k + l i z i n 且不在l ，4 ，7 ，昙一2 位置上的数用x 1 】4 将不在 兰k + 2 , 3 k + 1 1 2 _ l h j 且在l ，4 ，7 ，吾一2 位置上的数用y 标记 1 1 5 交换x 和y 标记的数注意吾 + 1 左边标记的数只能与左边标记的 数夺换扁访标计的辨其台匕与右沩株守的斯夺稚 2 ，4 - 逆序变换的置换排序问题 2 4 2 2 飞 h 1 7y 1 5 1 6 2 5 2 0 2 3 x 吣 2 1y 1 9 1 8 1 3 + 1x 3x 嘲 8 6 y x 萝 1 3 lx 9 1 2y 5 7 3 6 8 2 1 0 1 1 4 吲23 1 上图给了一个k = 8 时交换x 和y 标记的数的例子 h丝m笛引旧他b 9挖，7 3 6 8 2加， ”m鸵m西加引幻伸掩 吣吣秽 2 ，4