反转排序问题的遗传算法求解与精确性对比，基于Auyeung和亚伯拉罕方法的改进

PNP NP可在www.sciencedirect.com在线获取理论计算机科学电子笔记292（2013）119-133www.elsevier.com/locate/entcs基于断点消除和符号置换1精确解的混合遗传算法的反转排序Jos'eLuisSoncco-A'lvarez2MauricioAyala-Rinc'on3Grup odeTeoriadaComputaUniversidadedeBras'ıliaB ras'ıliaD.F.，B·R·阿齐尔摘要通过反转排序排列是与生物体之间的进化距离分析相关的最具挑战性的问题之一。基因组重排可以通过几种具有生物学意义的操作来完成，例如块交换，转座和反转等;但是反转排序，即找到将一个基因组转化为另一个基因组的最短反转序列，从组合和代数的角度来看，这是最具挑战性的问题之一。事实上，排序的逆转无符号排列是一个困难的问题，问题的完整性仍然开放了二十多年，其中几个有趣的组合问题，如平均数的逆转需要排序排列相同的大小，仍然没有解决方案。与无符号的情况相反，通过反转有符号排列进行排序属于.本文提出了一种求解无符号置换反向排序问题的标准遗传算法。这种方法是基于Auyeung和亚伯拉罕的方法，它使用的符号的情况下，以建立近似的解决方案，为unsorted之一的精确解。此外，提出了一种改进的遗传算法，在初始代应用反转，同时消除两个断点，几个近似算法使用的启发式机制。作为估计结果精度的控制机制，开发了1.5近似算法的正确实现。此外，结果进行了比较，与置换的确切解决方案是已知的，如高兰的置换和他们的逆。随机产生的排列进行了几个实验，结果表明，平均精度的输出提供通过标准和改进的遗传算法克服了由1.5近似算法给出的结果以及由先前已知的遗传方法提供的那些结果关键词：排序排列的逆转，遗传算法，近似算法。1由FAPDF PRONEX和CNPq Universal赠款资助的研究。2电子邮件：josesoal@hotmail.com。作者由巴西高等教育人员改进协调委员会资助。3电子邮件：ayala@unb.br。作者部分由巴西国家技术和科学发展顾问CNPq资助。1571-0661 © 2013 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2013.02.009120J.L. Soncco-Álvarez，M. Ayala-Rincón / Electron. Notes in Theor. Comput. Sci. 292（2013）119-1介绍生物序列的比较是生物信息学中确定生物进化关系的一个重要问题。这个问题可以使用考虑局部突变（缺失、插入和取代）的算法来解决，例如动态编程的经典算法来比对两个DNA序列。但是，当人们试图理解遗传序列如何在染色体水平上突变时，有必要考虑全局操作，如反转、块交换和易位。基因组重排中常见的操作之一是子串的反转基因组中基因的顺序可以用字符串表示法表示为排列π =（π1，π2，...，π n）的集合{1，.，n}，这是从{1，.， n}，其中n是基因的数量。两种不同类型的排列从生物学的角度受到关注：有符号和无符号排列。在无符号排列中，基因被抽象为没有任何方向，而在有符号排列中，每个πi都有一个正或负的符号来表示它在基因组中的方向;从左到右或从左到右。将ht左移，分别记为s−→πi或<$π−i。给定两个排列，我们希望确定将一个排列转换为另一个排列的最小反转次数通过置换的简单代数性质，该问题的结果等价于确定将一个置换变换为单位置换的最小反转次数的问题，表示为n（即，在字符串表示法中，对于无符号情况，按递增顺序排序的置换，对于有符号情况，按递增顺序排序的置换，其中each chπi具有位置变化，−→πi）。 这个问题被称为反向排序。几十年来，排列组合学和生物信息学领域都对逆向排序问题进行了广泛研究。 对于通过反转排序有符号排列的情况，最初，Sankoecioglu和Sanko[11]证明了该问题是NP-困难的，并提出了一个2-近似算法后来，Bafna和Pevzner [3]通过使用断点图的数据结构，将近似比提高到1.5。 最后，Hannenhalli和Pevzner [10]利用重叠图的数据结构，给出了一个精确多项式（O（n4））算法，该算法无需提供排序反转的序列，即可计算反 转 距 离 。 在 此 基 础 上 ， 提 出 了 更 有 效 的 算 法 ， 其 中 包 括 Berman 和Hannenhalli 在 [4] 中 提 出 的 O （ nα （ n ） ） 时 间 算 法 ， 其 中 α （ n ） 是Ackermann函数的逆，以及Bader，Moret和Yang在[2]中提出的线性时间算法，该算法使用了一种新的数据结构，称为重叠森林。增加这些复杂性，这些算法不仅可以应用于计算反转距离，而且还可以构建最小反转序列对于本文所讨论的无符号置换，Caprara [7]证明了该问题是NP困难的在复杂性已知之前，Kece-cioglu和Sanko [11]给出了一个2-近似算法，Bafna和Pevzner[3]给出了一个2J.L. Soncco-Álvarez，M. Ayala-Rincón / Electron. Notes in Theor. Comput. Sci. 292（2013）119-121提出了1.75近似算法。后来，Christie [8]将近似比提高到1.5（尽管给定的方法存在一些不精确性），然后Berman，Hannenhalli和Karpinski [5]将近似比提高到1.375。后者的近似算法是理论上的兴趣，因为它的实际实现的巨大困难。由于问题的复杂性，遗传算法等进化技术被提出来处理未签名的Auyeung和Abraham [1]提出了一种基于大小映射的遗传算法（GA）方法来解决无符号排列的反转排序问题n的每个置换的2n个可能的有符号版本的子集。对于给定的无符号置换，通过将正或负奇偶校验随机分配给置换的每个分量来生成一组有符号置换。其中一个有符号置换的精确解对应于原始无符号置换的可行解。每个有符号置换的适合度函数由其精确的反转距离给出，该距离由Hannenhalli随后，在[ 14 ]中报道了对Auyeung和Abraham 方法的修改最近，GhaAhmadi和Flann [9]提出了标准GA的修改版本，使用不同大小的个体来减少算法的运行时间。所有这些方法已被报道，以改善应用克里斯蒂的1.5近似算法，以控制精度的解决方案所获得的结果。但在这些论文中出现了两个问题：首先，克里斯蒂在[12]中，作者提出了一种简单的GA方法，该方法基于众所周知的近似机制（例如，[8，5]）集中在应用在每一代逆转，最大限度地减少出现在每个人的断点的数量。克里斯蒂方法的固定版本此外，实验是在两种不同方式产生的随机置换上进行的：通过直接应用C语言rand函数和通过随机地将反转应用于身份置换。本文提出了两种基于欧阳法和亚伯拉罕• 首先，对于Au yeung和Abraham提出的一种精确确定遗传算法参数的方法，实验结果有效地和正确地改进了其他作者以前报道的结果，并且优于固定的1.5近似算法给出的近似解。• 其次，提出了一种混合遗传算法近似的修改，其中，首先，输入排列排序随机应用所有可能的逆转，同时消除两个断点，然后，Auyeung和亚伯拉罕122J.L. Soncco-Álvarez，M. Ayala-Rincón / Electron. Notes in Theor. Comput. Sci. 292（2013）119-⎨当输入排列较大时，改进的GA给出了更好的结果。GA解决方案和近似解决方案之间的差异小于先前在其他论文中报道的差异，但本文中给出的比较更精确，因为这里应用了固定的1.5近似算法最后，进行了实验与置换的确切解决方案是已知的，如戈兰本文分为以下几个部分：第2节给出了必要的符号和概念;第3节提出了拟议的GA及其修改;第4节给出了实验和结果;第5节讨论了方法和结果;最后，第6节提出了结论和未来的工作。2背景2.1术语本节中的大多数定义和术语都是由Bafna和Pevzner在他们的开创性论文中介绍的[3]。对称群Sn中的置换是来自{1，.，n}自身。置换π，在字符串符号中表示为π= （ π1， π2， ... ， π n ） 通过添加初始 和最终枢轴来 扩展，π0= 0 和πn+1=n+1。A reversalρ i..对于1 ≤i≤j≤n，将扩展置换π变换为πJ=（π0，.，πi−1，πj，...，πi，π j+1，.， π n+1）例如，考虑置换π=（0， 3，1，5，2， 4， 6）反转ρ2.. 4将π变换为πJ=（0， 3，2，5，1， 4， 6）请注意，反转将恢复π的区间[2，4]。观察到反转也是Sn中的置换：（ρi..（j）k =k，如果k i或k > j;i+（j − k），如果i ≤ k ≤ j。因此，在后固定符号πρ i中。j表示反转ρ i的应用。j到置换π。给定两个排列π和σ，反转距离问题是找到将π变换为σ所需的最短反转序列的问题。π和σ之间的反转距离是将π转换为σ所需的最小反转次数。J.L. Soncco-Álvarez，M. Ayala-Rincón / Electron. Notes in Theor. Comput. Sci. 292（2013）119-123根据对称群的简单代数性质，π和σ之间的反转距离等于σ−1π和单位置换π之间的反转距离。事实上，请注意，如果ρ1...ρ k，是将π变换为σ的（逆）置换序列，则πρ1…ρ k= σ，当且仅当（σ−1π）ρ1.ρ k= σ−1σ = σ。因此，通过反转排序的问题对应于找到置换π和单位置换π之间的反转距离，表示为d（π）。由于单位置换是唯一的排序置换，因此反转距离问题也被称为反转排序问题。设i ∈ j表示|i − j|= 1。给定两个连续元素πi和π的πj;也就是说，0

下载后可阅读完整内容，剩余1页未读，立即下载