第27卷第3期 鞍山科技大学学报 Vol 27No 3 2004年6月 Journal of a nshan U niersity of Science and Techno bgy Jun.2004 用模拟退火算法求解无向排列的反转排序问题 陶玉敏,曾涛,莫舒园2,石艳霞 (1鞍山科技大学理学院,辽宁鞍山1140442武汉大学数学与统计学院,湖北武汉430072) 摘要:分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个NP-难问题目前,较好 拟退火算法定义了解的邻域结构数据实验的结果表明该算法性能优于3近似 的算法是 Christ ie(2001)的3/2-近似算法本文给出一种适合于计算基因无方向的反转 因组重排问题的模 关键词基因组重排,反转排序模拟退火算法 中图分类号:O242,Q332文献标识码A文章编号1672-4410(2004)03-016605 基因组重排( Genom e rearrange ent)是生物分子进化的一种重要模式,是计算分子生物学研究的 个重要问题在分子生物学中,通常将一个生物体完整的DNA序列称为该生物体的基因组有时也 将基因组定义为一个生物体的染色体集合,将染色体定义为基因的集合,而将基因定义为DNA的片 断研究不同生物之间的相似性、同源性及其进化关系,典型的方法是将两个生物的DNA序列进行比 较,通过对序列做插入、删除或替换单个字符(核甘酸或空格符)的操作,计算出从一个序列转换到另 个序列所需的最少操作次数(通常称为两个序列间的编辑距离)这种方法通常也叫做序列比对(Se quence alignm ent),它们一般只适合于对单个基因或有少数几个基因组成的“基因块的研究,因而它是 基因组的一种局部化方法然而,在20世纪80年代后期,分子生物学家们的研究发现,不同物种的基因 组可能包含有完全相同或极为相似的基因,只是基因在染色体上的排列顺序可能不同例如,卷心菜和 芜菁这两种生物体就是如此1 对于包含的基因相同,但基因的排列顺序不同的两个基因组,研究它们的相似性或进化关系,显然 不能使用上述所说的局部化方法,否则将会导出错误的结论但可以通过对基因组中的单个基因或基因 块,做反转( inverson)、易位( Translocaton)、复制 Dup licatIo)或调换( T ranspositDn)等操作,将一个基 因组变换到另一个基因组上述这种以基因为单位的操作称为基因组重排 设G={g1,g2,…,gn}是由n个基因g,gx,…,g组成的基因集合,为简单起见,用数字k来标记基 因gk(k=1,2,…,n),并记G={g,g2,…,gn}={1,2,…,n1这样,一个基因的有序列G=(g1,g gn)就可用(1,2,…,n)的一个排列丌=(m,T2,…,Tn)来表示,从而将一个基因组重排的反转排序问题 转化为一个排列的反转排序问题 近十年有关基因组重排,特别是基于反转的基因组重排的数学特征及算法的研究,一直是计算生物 学中受到广泛关注的课题24如果基因是有方向的,反转基因组重排问题是多项式时间可解的而且 目前己找到了十分有效的算法而如果基因是无方向的,反转基因组重排问题己被 Cap rara证明是 NP-难问题18,目前尚未找到有效的算法目前较好的算法是近似性能比为3/2的近似算法但基于 演化思想的算法却很少见文献[10]应用遗传算法估计基因组重排的反转距离,取得了较好的结果 本文提出了基于“一个无向排列T的反转距离等于由m所生成的包含2个有向排列集Sgn(丌)中 最优排列的反转距离”这一事实而设计的求Sgn(π)中的最优排列的一种模拟退火算法定义了适合该 问题的解的邻域结构,使得无向排列的反转基因组重排问题的求解在本质上可以应用模拟退火算法最 收稿日期2004-03-05 作者简介陶玉敏(1917-),女,满族,辽宁凌海人
第 27 卷 第 3 期 2004 年 6 月 鞍 山 科 技 大 学 学 报 Journal of A nshan U niversity of Science and Technology Vol. 27 No. 3 Jun. , 2004 用模拟退火算法求解无向排列的反转排序问题 陶玉敏1 , 曾 涛2 , 莫舒园2 , 石艳霞1 (1. 鞍山科技大学 理学院, 辽宁 鞍山 114044; 2. 武汉大学 数学与统计学院, 湖北 武汉 430072) 摘 要: 分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个 N P2难问题. 目前, 较好 的算法是 Ch ristie (2001) 的 3ö22近似算法. 本文给出一种适合于计算基因无方向的反转基因组重排问题的模 拟退火算法, 定义了解的邻域结构. 数据实验的结果表明该算法性能优于 3ö22近似算法. 关键词: 基因组重排; 反转排序; 模拟退火算法 中图分类号:O 242; Q 332 文献标识码: A 文章编号: 167224410 (2004) 0320166205 基因组重排(Genom e rearrangem ent) 是生物分子进化的一种重要模式, 是计算分子生物学研究的 一个重要问题. 在分子生物学中, 通常将一个生物体完整的DNA 序列称为该生物体的基因组. 有时也 将基因组定义为一个生物体的染色体集合, 将染色体定义为基因的集合, 而将基因定义为DNA 的片 断. 研究不同生物之间的相似性、同源性及其进化关系, 典型的方法是将两个生物的DNA 序列进行比 较, 通过对序列做插入、删除或替换单个字符(核甘酸或空格符) 的操作, 计算出从一个序列转换到另一 个序列所需的最少操作次数(通常称为两个序列间的编辑距离). 这种方法通常也叫做序列比对 (Se2 quence alignm ent) , 它们一般只适合于对单个基因或有少数几个基因组成的“基因块”的研究, 因而它是 基因组的一种局部化方法. 然而, 在 20 世纪 80 年代后期, 分子生物学家们的研究发现, 不同物种的基因 组可能包含有完全相同或极为相似的基因, 只是基因在染色体上的排列顺序可能不同. 例如, 卷心菜和 芜菁这两种生物体就是如此[1 ] . 对于包含的基因相同, 但基因的排列顺序不同的两个基因组, 研究它们的相似性或进化关系, 显然 不能使用上述所说的局部化方法, 否则将会导出错误的结论. 但可以通过对基因组中的单个基因或基因 块, 做反转( Inversion)、易位(T ranslocation)、复制(Dup lication) 或调换(T ransposition) 等操作, 将一个基 因组变换到另一个基因组. 上述这种以基因为单位的操作称为基因组重排. 设G = {g 1, g 2, …, g n } 是由 n 个基因 g 1, g 2, …, g n 组成的基因集合, 为简单起见, 用数字 k 来标记基 因g k (k = 1, 2, …, n) , 并记G = {g 1, g 2, …, g n } = {1, 2, …, n}. 这样, 一个基因的有序列G = (g 1, g 2, …, g n ) 就可用(1, 2, …, n) 的一个排列Π= (Π1, Π2, …, Πn ) 来表示, 从而将一个基因组重排的反转排序问题 转化为一个排列的反转排序问题. 近十年有关基因组重排, 特别是基于反转的基因组重排的数学特征及算法的研究, 一直是计算生物 学 中受到广泛关注的课题[2- 4 ] . 如果基因是有方向的, 反转基因组重排问题是多项式时间可解的. 而且 目前已找到了十分有效的算法[5, 6 ] . 而如果基因是无方向的, 反转基因组重排问题已被 Cap rara 证明是 N P2难问题[7, 8 ] , 目前尚未找到有效的算法. 目前较好的算法是近似性能比为 3ö2 的近似算法[9 ] . 但基于 演化思想的算法却很少见. 文献[ 10 ] 应用遗传算法估计基因组重排的反转距离, 取得了较好的结果. 本文提出了基于“一个无向排列 Π的反转距离等于由 Π所生成的包含 2 n 个有向排列集 Sign (Π) 中 最优排列的反转距离”这一事实而设计的求Sign (Π) 中的最优排列的一种模拟退火算法. 定义了适合该 问题的解的邻域结构, 使得无向排列的反转基因组重排问题的求解在本质上可以应用模拟退火算法. 最 收稿日期: 2004203205. 作者简介: 陶玉敏(1917- ) , 女, 满族, 辽宁凌海人
第3期陶玉敏,等:用模拟退火算法求解无向排列的反转排序问题167· 后,数据实验的结果表明该算法优于文献[9的3/2近似算法 无向排列的反转排序的数学描述 定义1给定{1,2,…,m}的一个排列m=(T,T2,…,T),如果排列中的每个元素都有“+"或“” 标号,标记染色体中基因的方向,如此的排列称为有向排列如果排列中的元素没有标号,则此排列称为 无向排列 定义2排列=(+1,+2,…,+n)称为有向的恒等排列;而排列I=(1,2,…,n)称为无向的恒等 排列 定义3设π是无向(或有向)排列称/[,(1≤≤≤n是对π的一个反转,是指运算Tp产生 如下结果 (1) 或 Tp=(T,T2,…;,T1,-T Tr1,-T,T+1,…,Tn) 即πρ使π中从第;个元素至第j个元素的顺序发生倒置(如果是有向排列,则同时要改变元素的方 向),而其余元素顺序保持不变 定义4给定{1,2,…n}的两个(无向或有向)排列aR求一个反转序列p,凸,…P,使得 aP凸…=B (3) 且t的值为最小的问题,称为基于反转的基因组重排问题(简称反转基因组重排问题),并称数t为a关 于β的反转距离( Reversal d istance),记为da(B 设α和β是{,2,…,n}的两个不同的(无向或有向)排列,B2,…是一个反转序列注意到,由 aPA…p=阝可以得到βap…=I(或D,这里β为B的逆排列若记m=β',则a关于β的反转 距离da(β等于π关于恒等排列1(或n的反转距离dn(1)(或dn(D),简记为rd(m)(或srd(m)因此, 以下只考虑{1,2,…,n}的任一个排列丌关于1(或D的反转距离问题而不失一般性基于上述的关系 反转基因组重排问题也常称为反转排序( Sorting by reversals)问题 鉴于无向排列的反转基因组重排问题是NP-难问题,而有向排列的反转基因组重排问题是多项式 时间可解的可以构造一种方法把无向排列转化为有向排列 具体做法如下:在无向排列的每一个元素上加上正号或负号,例如无向排列=(2,1),那么生成 有向排列集为 Sgn(丌)={(-2-1),(-2+1),(+2-1),(+2+1)} 这样对于含有n个元素的无向排列T=(T,T2,…,T),可以生成含有2”个有向排列集Sgn(m),其中 每个有向排列含有n个元素 定义5设π'∈Sgn(m),如果srd(T)=mn{srd(r),m'∈Sgn(m)},则称T'是Sgn(T)中具有 最小反转距离的有向排列(简称最小距离排列),或称最优排列 无向排列与有向排列之间有如下结论 定理1设m=(m1,m2,…,mn)是一个无向排列,则对于Sign(m)中的每一个有向排列m=(m'1 T'2,…,m1),T的反转序列也是丌的反转序列 定理2设丌是无向排列,则必定存在有向排列T∈sgn(丌),使得 rd ( 定理1和定理2的证明见文献[10 上述两个定理保证了在sgn(m)里至少存在一个最小距离排列,它的反转序列是m的最优反转序 列因此,求解无向排列的反转排序问题可以转化为求解有向排列集Sgn(π)中的具有最小距离排序问 题然而,搜索2个有向排列π’寻找最小距离排列,花费时间为O(2"n),实际上是不可行的本文设计 种模拟退火算法来寻找集合Sgn(m)中的最小距离排列,进而给出无向排列的最优(或次最优)反 1994-2009ChinaAcademicJoumalElectronicPublishinghOuse,Allrightsreservedhttp://www.cnki.net
后, 数据实验的结果表明该算法优于文献[ 9 ]的 3ö22近似算法. 1 无向排列的反转排序的数学描述 定义 1 给定{1, 2, …, n}的一个排列 Π= (Π1, Π2, …, Πn ) , 如果排列中的每个元素都有“+ ”或“- ” 标号, 标记染色体中基因的方向, 如此的排列称为有向排列; 如果排列中的元素没有标号, 则此排列称为 无向排列. 定义 2 排列 I γ = (+ 1, + 2, …, + n) 称为有向的恒等排列; 而排列 I= (1, 2, …, n) 称为无向的恒等 排列. 定义 3 设 Π是无向(或有向) 排列, 称 Θ= [ i, j ] (1≤i≤j≤n) 是对 Π的一个反转, 是指运算 ΠΘ产生 如下结果: ΠΘ= (Π1, Π2, …, Πi- 1 , Πj , Πj- 1, …, Πi+ 1, Πi, Πj+ 1, …, Πn) (1) 或 ΠΘ= (Π1, Π2, …, Πi- 1 , - Πj , - Πj- 1, …, - Πi+ 1, - Πi, Πj+ 1, …, Πn ) (2) 即 ΠΘ使 Π 中从第 i 个元素至第 j 个元素的顺序发生倒置(如果是有向排列, 则同时要改变元素的方 向) , 而其余元素顺序保持不变. 定义 4 给定{1, 2, …, n}的两个(无向或有向) 排列 Α, Β, 求一个反转序列 Θ1, Θ2, …, Θt, 使得 ΑΘ1Θ2…Θt = Β (3) 且 t 的值为最小的问题, 称为基于反转的基因组重排问题(简称反转基因组重排问题) , 并称数 t 为 Α关 于 Β的反转距离(Reversal distance) , 记为 d Α(Β). 设 Α和 Β是{1, 2, …, n}的两个不同的(无向或有向) 排列, Θ1, Θ2, …, Θt 是一个反转序列. 注意到, 由 ΑΘ1Θ2…Θt= Β可以得到 Β - 1ΑΘ1Θ2…Θt= I (或 I γ ) , 这里 Β - 1为 Β的逆排列. 若记 Π= Β - 1Α, 则 Α关于 Β的反转 距离 d Α(Β) 等于 Π关于恒等排列 I (或 I γ ) 的反转距离 d Π(I) (或 d Π(I γ ) ) , 简记为 rd (Π) (或 srd (Π) ). 因此, 以下只考虑{1, 2, …, n}的任一个排列 Π关于 I (或 I γ ) 的反转距离问题而不失一般性. 基于上述的关系, 反转基因组重排问题也常称为反转排序(Sorting by reversals) 问题. 鉴于无向排列的反转基因组重排问题是N P2难问题, 而有向排列的反转基因组重排问题是多项式 时间可解的. 可以构造一种方法把无向排列转化为有向排列. 具体做法如下: 在无向排列的每一个元素上加上正号或负号, 例如: 无向排列 Π= (2, 1) , 那么生成 有向排列集为 Sign (Π) = { (- 2 - 1) , (- 2 + 1) , (+ 2 - 1) , (+ 2 + 1) } (4) 这样对于含有 n 个元素的无向排列 Π= (Π1, Π2, …, Πn ) , 可以生成含有 2 n 个有向排列集 Sign (Π) , 其中 每个有向排列含有 n 个元素. 定义 5 设 Π 3 ∈Sign (Π) , 如果 srd (Π 3 ) = m in{srd (Π′) , Π′∈Sign (Π) }, 则称 Π 3 是 Sign (Π) 中具有 最小反转距离的有向排列(简称最小距离排列) , 或称最优排列. 无向排列与有向排列之间有如下结论: 定理 1 设 Π= (Π1, Π2, …, Πn ) 是一个无向排列, 则对于 Sign (Π) 中的每一个有向排列 Π′= (Π′1, Π′2, …, Π′n ) , Π′的反转序列也是 Π的反转序列. 定理 2 设 Π是无向排列, 则必定存在有向排列 Π 3 ∈Sign (Π) , 使得 srd (Π 3 ) = rd (Π) (5) 定理 1 和定理 2 的证明见文献[ 10 ]. 上述两个定理保证了在 Sign (Π) 里至少存在一个最小距离排列, 它的反转序列是 Π的最优反转序 列. 因此, 求解无向排列的反转排序问题可以转化为求解有向排列集 Sign (Π) 中的具有最小距离排序问 题. 然而, 搜索 2 n 个有向排列 Π′寻找最小距离排列, 花费时间为O (2 n n) , 实际上是不可行的. 本文设计 一种模拟退火算法来寻找集合 Sign (Π) 中的最小距离排列, 进而给出无向排列 Π的最优(或次最优) 反 第 3 期 陶玉敏, 等: 用模拟退火算法求解无向排列的反转排序问题 ·167·
168· 鞍山科技大学学报 第27卷 转序列 2模拟退火算法 2.1模拟退火算法 基于统计物理的概念和方法,1983年 s Kirkpatrick等人提出了求解组合最优化问题的模拟退火算 法( Sm ulated annealing algorithm,简称SAA)田其基本思想是将一个优化问题比拟成物理系统的能 量,通过模拟物理系统逐步降温已达到最低能量状态的退火过程而获得优化问题的全局最优解设优化 问题(S,F)为在可行集S中求使目标函数F:S→R达到最小的最优解i∈S,则模拟退火算法求解的 基本步骤如下 (1)任选初始解i和给定初始温度r>0, (2)进行随机热扰动生成解j∈N();计算△F=F()-F(),并依 Metropo lis准则接受(或舍弃) 即若△F≤0,则P,否则若exp(△/)>时,则Pj(其中N()CS为t的邻域n为[0,1区间上的 均匀分布随机数) (3)若在此温度T下 Metropolis迭代过程已经稳定,即已达到热平衡,则转(4),否则,转(2) (4)若满足算法终止准则,即退火过程结束,则输出最优解=讠,算法终止:否则,按一定方式降低 温度,即T=T-△T,△T>0,转(2) 其中 M tropo lis接受准则及其迭代过程实现了物理系统状态服从 Boltz anr分布的计算机模拟, 模拟退火算法的数学模型可以描述为在给定邻域结构后,模拟退火过程是从一个状态到另一个状态不 断的随机游动 2.2算法应用中的几个主要问题 上面给出的SAA只是一种抽象算法,要在求解无向排列的反转基因组重排问题中得以实现尚有 以下几个问题需要解决 (1)初始解的确定在对无向排列的反转基因组重排问题的讨论中,对于一个n个元素的无向 排列π,生成一个包含2"个有向排列集Sgn(π),对Sgn(π)中的有向排列按随机产生的二进制编码描 述排列中元素的标号(+或-),就是0,1分别代表“-”或“+”号对于已给排列π,编码方案为sm= (丌,S),i∈[1ln21π为已给排列π,s=(si,sh,…,s),s∈{0,1},j∈[1,n1又因为mr为已给排列T,每 次变化的仅仅是s,因此在实际操作中考虑的只是s部分 大量的实验结果表明,模拟退火算法的最终解的质量并不十分依赖于初始解的选取因此,在Sgn (m中任取一个有向排π作为初始解,并且按上面的编码方案给出 (2)邻域结构的确定和新解的产生机制本文所指的邻域结构,采用了模拟退火算法中术语简 单地说,当前解经过一次变换形成的新解的集合称为当前解的邻域对于无向排列的反转基因组重排问 题,构造解的邻域如下 记 T={si,…,sm}-1,s∈{0,1},Vi,j∈T,d(i,)= 2 对一个排列(解),N(1=b(-=1},k(n|=n,新解的产生机制随机取j∈N(),若△srd= rd()-srd(≤0,则严j;否则若exp(△srd/r)>n则严j,若exp(△sd/m)>h则Pt (3)计算目标函数设丌是无向排列,生成含有2个有向排列集Sen(m),目标函数F(x)= srd(x),x∈Sgn(丌).应用文献[5]的算法计算F(x) (4)退火策略温度参数是模拟退火算法中一个关键的参数,主要包括起始温度的选取,温度的 下降方法和停止温度的确定等温度下降太快,优化只能达到所谓的亚稳态,结果不理想,下降太慢,直 接影响处理的效率,因时间太长而失去意义因此,退火策略的把握是举足轻重的,但却是经验性的,它 直接依赖于问题的类型一个常用的退火策略是采用线性控制:Ts1=d(T)=T4,∈[02,0991此 201994-2009ChinaAcademicJoumalElectronicpUblishingHouse.Allrightsreservedhtp:/www.cnki.net
转序列. 2 模拟退火算法 211 模拟退火算法 基于统计物理的概念和方法, 1983 年 S. Kirkpatrick 等人提出了求解组合最优化问题的模拟退火算 法 (Sim ulated annealing algorithm , 简称 SAA ) [11 . 其基本思想是将一个优化问题比拟成物理系统的能 量, 通过模拟物理系统逐步降温已达到最低能量状态的退火过程而获得优化问题的全局最优解. 设优化 问题(S , F ) 为在可行集 S 中求使目标函数 F∶S →R 达到最小的最优解 iop t∈S , 则模拟退火算法求解的 基本步骤如下: (1) 任选初始解 i 和给定初始温度 T > 0; (2) 进行随机热扰动生成解 j∈N (i); 计算 ∃F = F (j) - F (i) , 并依M etropolis 准则接受(或舍弃) j, 即若 ∃F≤0, 则 i= j, 否则若 exp (∃f öT ) > Γ时, 则 i= j (其中N (i) < S 为 i 的邻域; Γ为[ 0, 1 ]区间上的 均匀分布随机数). (3) 若在此温度 T 下M etropolis 迭代过程已经稳定, 即已达到热平衡, 则转(4) , 否则, 转(2). (4) 若满足算法终止准则, 即退火过程结束, 则输出最优解 iop t= i, 算法终止: 否则, 按一定方式降低 温度, 即 T = T - ∃T , ∃T > 0, 转(2). 其中,M etropolis 接受准则及其迭代过程实现了物理系统状态服从Boltzm ann 分布的计算机模拟, 模拟退火算法的数学模型可以描述为: 在给定邻域结构后, 模拟退火过程是从一个状态到另一个状态不 断的随机游动. 212 算法应用中的几个主要问题 上面给出的 SAA 只是一种抽象算法, 要在求解无向排列的反转基因组重排问题中得以实现尚有 以下几个问题需要解决. (1) 初始解的确定 在对无向排列的反转基因组重排问题的讨论中, 对于一个 n 个元素的无向 排列 Π, 生成一个包含 2 n 个有向排列集 Sign (Π) , 对 Sign (Π) 中的有向排列按随机产生的二进制编码描 述排列中元素的标号(+ 或- ) , 就是 0, 1 分别代表“- ”或“+ ”号. 对于已给排列 Π, 编码方案为 sΠ= (Π i , S i ) , i∈[ 1, n 2 ]. Π i 为已给排列 Π, s i = (s i 1, s i 2, …, s i n ) , s i j∈{0, 1}, j∈[ 1, n ]. 又因为 Π i 为已给排列 Π, 每 次变化的仅仅是 s i , 因此在实际操作中考虑的只是 s i 部分. 大量的实验结果表明, 模拟退火算法的最终解的质量并不十分依赖于初始解的选取. 因此, 在S ig n (Π) 中任取一个有向排 Π′作为初始解, 并且按上面的编码方案给出. (2) 邻域结构的确定和新解的产生机制 本文所指的邻域结构, 采用了模拟退火算法中术语. 简 单地说, 当前解经过一次变换形成的新解的集合称为当前解的邻域. 对于无向排列的反转基因组重排问 题, 构造解的邻域如下: 记 T = {s i 1, …, s i n } 2 n i= 1, s i k∈{0, 1}, Π i, j∈T , d (i, j) = ∑ n k= 1 ûs i k - s j k û (6) 对一个排列(解) i, N (i) = {jû d (j - i) = 1}, ûN (i) û = n; 新解的产生机制: 随机取 j ∈N (i) , 若 ∃ srd= srd (j) - srd (i) ≤0, 则 i= j; 否则若 exp (∃ srdöT ) > Γ, 则 i= j, 若 exp (∃ srdöT ) > Γ, 则 i= i. (3) 计算目标函数 设 Π 是无向排列, 生成含有 2 n 个有向排列集 Sign (Π) , 目标函数 F (x ) = srd (x ) , x ∈Sign (Π). 应用文献[ 5 ]的算法计算 F (x ). (4) 退火策略 温度参数是模拟退火算法中一个关键的参数, 主要包括起始温度的选取, 温度的 下降方法和停止温度的确定等. 温度下降太快, 优化只能达到所谓的亚稳态, 结果不理想, 下降太慢, 直 接影响处理的效率, 因时间太长而失去意义. 因此, 退火策略的把握是举足轻重的, 但却是经验性的, 它 直接依赖于问题的类型. 一个常用的退火策略是采用线性控制: T k+ 1= d (T k ) = ΑT k , Α∈[ 0. 2, 0. 99 ]. 此 ·168· 鞍 山 科 技 大 学 学 报 第 27 卷
第3期陶玉敏,等:用模拟退火算法求解无向排列的反转排序问题169· 时的函数具有随算法进程递减的衰减量因此可以减小温度参数值Tt递减的速率,有益于模拟退火算 法试验性的稳定 (5)算法终止条件在同一温度下最好解在二十次迭代内不变 3实验及结果 为了鉴定模拟退火算法在计算无向排列的反转基因组重排问题中的有效性,将此算法用C语言编 程进行实验,并与文献[9]的3/2-近似算法做了比较 本文的实验参数温度初值T0为已给排列的长度n,=08 取含有n(n=10,20,30,40,50,60,70,80)个元素的排列丌,每个排列π随机产生100个分别用模 拟退火算法,3/2-近似算法计算,取它们的平均值,即d(T)={rd(m)+rd2(T)+…rd(m)}10结 果见表1 表13/2-近似算法与模拟退火结果的比较(平均值) 表2反转序列p=[,j](r∈[,26] Tab I Com persion of results of appr Tab 2 Reversal sequence ∈[,26]p[t∈[1,26p=[ij algorithm w ith sm ulated annealing [1,14 3/2-近似算法 模拟退火算法 [3,4] 387 [4,6 950 5,15 1255 23456789 2,33 2,35 2197 11,14 20 [1l28] 14,21 3594 3184 5,38 4263 另外,对文献[2]给出的含有36个元素的排列的例子12313428261729493618351911614 3233221511275201330231063242182527做了实验此例被认为非常难于求得最优解的用 模拟退火算法求得的近似最优解是26次反转,具体的反转序列见表2文献[12]中用分支定界算法求 得的结果为27次反转目前已找到26次反转的解的还有文献[13],但与本文得到的反转序列不同 4结论 从上面的实例可见,模拟退火算法优于3/2-近似算法因此,本文提出的方法在无向排列的反转基 因组重排问题上能够得到满意的结果更重要的是,由于模拟退火算法的良好收敛性,在计算结果的后 期,其微调能力是人工方法所无法比拟的将其应用到无向排列的反转基因组重排问题上,能够在合理 的时间内得到较高质量的解 参考文献 [1 JHANN EN HALL IS, PEV NER P. Transfom ing cabbage into turn p[ Journal of the ACM, 1999, 46(1): 1-27. [2 SETUBAL J, MEDAN IS J. Introductin to Com putatDnalM olecular B D bgy [M I Boston: Pw S Publish ing Com pany. 1997:215-244 [3 ]PEV ANER P A. Com putina M olecular B Dbgy: A n A lgorithm i A pproach M I Cam brdge: M Ir Press, 2000. 229 249 201994-2009ChinaAcademicJournalElectronicpUblishingHouseAllrightsreservedhttp:/www.cnki.net
时的函数具有随算法进程递减的衰减量. 因此可以减小温度参数值 T k 递减的速率, 有益于模拟退火算 法试验性的稳定. (5) 算法终止条件 在同一温度下最好解在二十次迭代内不变. 3 实验及结果 为了鉴定模拟退火算法在计算无向排列的反转基因组重排问题中的有效性, 将此算法用C 语言编 程进行实验, 并与文献[ 9 ]的 3ö22近似算法做了比较. 本文的实验参数: 温度初值 T 0 为已给排列的长度 n, Α= 0. 8. 取含有 n (n= 10, 20, 30, 40, 50, 60, 70, 80) 个元素的排列 Π, 每个排列 Π随机产生 100 个分别用模 拟退火算法, 3ö2-近似算法计算, 取它们的平均值, 即rd (Π) - = {rd1 (Π) + rd2 (Π) + …+ rd100 (Π) }ö100. 结 果见表 1. 表 1 3ö22近似算法与模拟退火结果的比较(平均值) Tab. 1 Compersion of results of 2 3 app roxim ation algorithm w ith sim ulated annealing n 3ö22近似算法 模拟退火算法 10 4. 22 3. 87 20 9. 50 8. 51 30 14. 13 12. 55 40 19. 97 17. 37 50 25. 09 21. 97 60 30. 88 27. 06 70 35. 94 31. 84 80 42. 63 37. 92 表 2 反转序列 Θt= [i, j ] (t∈[1, 26 ]) Tab. 2 Reversal sequence t∈[ 1, 26 ] Θt= [ i, j ] t∈[ 1, 26 ] Θt= [ i, j ] 1 [ 1, 14 ] 14 [ 5, 34 ] 2 [ 3, 4 ] 15 [ 6, 11 ] 3 [ 4, 11 ] 16 [ 17, 20 ] 4 [ 4, 6 ] 17 [ 8, 15 ] 5 [ 5, 15 ] 18 [ 5, 10 ] 6 [ 2, 31 ] 19 [ 6, 26 ] 7 [ 2, 33 ] 20 [ 7, 33 ] 8 [ 2, 35 ] 21 [ 7, 36 ] 9 [ 3, 5 ] 22 [ 11, 14 ] 10 [ 6, 20 ] 23 [ 11, 28 ] 11 [ 4, 17 ] 24 [ 14, 21 ] 13 [ 5, 38 ] 25 [ 23, 33 ] 13 [ 4, 10 ] 26 [ 22, 32 ] 另外, 对文献[ 12 ]给出的含有 36 个元素的排列的例子 12 31 34 28 26 17 29 4 9 36 18 35 19 1 16 14 32 33 22 15 11 27 5 20 13 30 23 10 6 3 24 21 8 25 2 7 做了实验. 此例被认为非常难于求得最优解的. 用 模拟退火算法求得的近似最优解是 26 次反转, 具体的反转序列见表 2. 文献[ 12 ]中用分支定界算法求 得的结果为 27 次反转. 目前已找到 26 次反转的解的还有文献[ 13 ], 但与本文得到的反转序列不同. 4 结 论 从上面的实例可见, 模拟退火算法优于 3ö22近似算法. 因此, 本文提出的方法在无向排列的反转基 因组重排问题上能够得到满意的结果. 更重要的是, 由于模拟退火算法的良好收敛性, 在计算结果的后 期, 其微调能力是人工方法所无法比拟的. 将其应用到无向排列的反转基因组重排问题上, 能够在合理 的时间内得到较高质量的解. 参 考 文 献: [1 ]HANN ENHALL I S, PEV ZN ER P. T ransform ing cabbage into turnip [J ]. Journal of the ACM , 1999, 46 (1): 1- 27. [ 2 ]SETUBAL J,M E IDAN IS J. Introduction to ComputationalM olecular B iology[M ]. Boston: PW S Publish ing Company, 1997: 215- 244. [3 ]PEV ZN ER P A. ComputionalM olecular B iology: A n A lgorithm ic App roach [M ]. Cam bridge: M IT P ress, 2000: 229- 249. 第 3 期 陶玉敏, 等: 用模拟退火算法求解无向排列的反转排序问题 ·169·
鞍山科技大学学报 第27卷 [4]SAN KOFF D, ElMABROU K N. Genome rearrange ent [A )JANG T, M ITH T, XU Y, et al Current Top ics in Com putat pnal B bbgy [C Cam bridge: M Ir Press, 2002: 135-155 [5 ]KA PLAN H, SHAM RR, TARJAN R E A faster and simp ler algor ithm for sorting signed pem utatins by reversals [J I SAM Journal of Computing, 1999, 29(3): 880-892 [6 BADER D, MOROT B, YAN M. A linear-tme algorithm for com puting inversin distance betw een signed pem utatons w ith an experm ental study [J l Journal of Com putatinal B pbg, 2001, 8(5): 483-491 [7ICA PRARA A. Sorting by reversals is difficult [A I Proceed ings of the F irst A nnual intemational Conference on Compu- tatDnalMolcular B ibgy[C New York: A am Press, 1997: 75-83 [8 ]CA PRARA A. Sorting pem utat ins by reversals and Euler an cycle doom posit ns[J I SAM J ofD iscreteM athem atic s,1999,12(1):91-110 [9]CHR IST IE David A. A 3/2-A pp rox m atin A lgorithm for Sorting by Reversals[A I Proc ninth annual ACM-SAM Symp on D iscrete A lgorithm s(SODA 98)]MA: ACM Press, 1998: 244-252 10 JAU YEUNG A ndy, ABRAHAM A jith Estimating genom e reversal d istance by geneti algorithm [A ] 2003IEEE Congress on Evo lutinary Computatin(CEC2003)[C I A ustralia: IEEE Press, 2003: 1157- 1161 [1l RKPA TR ICK S, GELATT JrCD, VECCH IM P Optim ization by sm ulated annealing[J Science, 1983, 220: 671 [12 KECEC DGLU John, SAN KO FF David Exact and app rox m at on algorithm s for sorting by reversals, w ith app leaton to genome rearrangement[J]A lgorithm ica, 1995, 13: 180-210 [13]sAlmNenH.Genomerearrangements[j]SaminaronBiinfomatics[eb/oL12002,18(4).http://ww.csutu fi/ infom atics/2001- 2/htroducton uusin ppt Sim ula ted annealing algor ithm for problem of sorting a un signed perm uta tion by reversals TAO Yum in, ZEN G Tao, MO Shuyuan,SH I Yano/ (l Faculty of Science, A nshan U niversity of Science and Techno bgy, A nshan 114044, Ch, 2 School ofM athem atics and Statistics, W uhan U niversity, W uhan 430072, China) Abstract The p roblem of genome rearrange ent of the unsigned pem utaton by reversals in molecular br obey has been proved to be a N p-hard problem. at present, a better algorithm is the 3/2-app rox m aton one of Christ e(2001). The paper p ropo ses a sm ulated annealing algorithm for the p roblem of genome rear- rangem ents of the unsigned pem utaton by reversals, and def ne the neighborhood structure of its soluton The experim en tal results show that th is algorithm outperfom s the 3/2-app rox m aton algorithm Key words genom e rearrangem ent, sorting by reversals, sm ulated annealing algorithm (Rece ied March 5, 2004) 待发表论文预报 无刷双馈电机的数学模型和基于 Smulink4的仿真 陈海朋,李岩,韩 (1鞍山科技大学电子与信息工程学院,辽宁鞍山1140442鞍山供电公司,辽宁鞍山114044 摘要无刷双馈电机是一种在许多方面都有着很好应用前景的新型电机本文重新推导了无刷双馈电机 的数学模型,并在 MATLAB亼 MUL NK环境下建立了仿真模型,为进一步构成控制系统,进行系统分析与 设计奠定了基础 201994-2009ChinaAcademicJoumalElectronicPublishingHouseAllrightsreservedhttp://www.cnki.net
[4 ]SAN KO FF D , El2MABROU K N. Genom e rearrangem ent [A ]. J IAN G T, SM ITH T, XU Y, et al. Current Top ics in ComputationalB iology[C ]. Cam bridge:M IT P ress, 2002: 135- 155. [ 5 ]KA PLAN H , SHAM IR R, TARJAN R E. A faster and simp ler algorithm for sorting signed perm utations by reversals [J ]. S IAM Journal of Computing, 1999, 29 (3): 880- 892. [ 6 ]BADER D ,MORO T B, YAN M. A linear2tim e algorithm for computing inversion distance betw een signed perm utations w ith an experim ental study[J ]. Journal of ComputationalB iology, 2001, 8 (5): 483- 491. [ 7 ]CA PRARA A. Sorting by reversals is difficult[A ]. P roceedings of the F irst A nnual InternationalConference on Compu2 tationalM olecular B iology[C ]. N ew York:A cm P ress, 1997: 75- 83. [8 ]CA PRARA A. Sorting perm utations by reversals and Eulerian cycle decompositions[J ]. S IAM J of D iscreteM athem atic2 s, 1999, 12 (1): 91- 110. [9 ]CHR IST IE David A. A 3ö22App roxim ation A lgorithm for Sorting by Reversals[A ]. P roc. ninth annual ACM 2S IAM Symp. on D iscrete A lgorithm s (SODA 98) [C ]. MA :ACM P ress, 1998: 244- 252. [ 10 ]AU YEUN G A ndy, ABRAHAM A jith. Estim ating genom e reversal distance by genetic algorithm [A ]. 2003 IEEE Congress on Evolutionary Computation (CEC2003) [C ]. A ustralia: IEEE P ress, 2003: 1157- 1161. [ 11 ]K IRKPA TR ICK S, GELA TT Jr C D ,V ECCH IM P. Op tim ization by sim ulated annealing[J ]. Science, 1983, 220: 671 - 680. [12 ]KECEC IO GLU John, SAN KO FF David. Exact and app roxim ation algorithm s for sorting by reversals,w ith app lication to genom e rearrangem ent[J ]. A lgorithm ica, 1995, 13: 180- 210. [13 ]SALM IN EN H. Genom e rearrangem ents[J ]. Sem inar on B ioinform atics[EBöOL ]. 2002, 18 (4). h ttp: ööwww. cs. utu. fiöbioinform aticsö2001- 2öIntroduction uusin. pp t Simulated anneal ing algor ithm for problem of sorting a unsigned permutation by reversals TA O Y u2m in 1 , Z EN G T ao 2 ,M O S hu2y uan 2 , SH I Y an2x ia 1 (1. Faculty of Science,A nshan U niversity of Science and Technology,A nshan 114044, China; 2. School of M athem atics and Statistics,W uhan U niversity,W uhan 430072, China) Abstract: The p roblem of genom e rearrangem ent of the unsigned perm utation by reversals in molecular bi2 ology has been p roved to be a N P2hard p roblem. A t p resent, a better algorithm is the 3ö22app roxim ation one of Ch ristie (2001). The paper p roposes a sim ulated annealing algorithm for the p roblem of genom e rear2 rangem ents of the unsigned perm utation by reversals, and define the neighborhood structure of its solution. The experim ental results show that th is algorithm outperform s the 3ö22app roxim ation algorithm. Key words: genom e rearrangem ent; sorting by reversals; sim ulated annealing algorithm (Rece ivedMarch 5, 2004) 待发表论文预报 无刷双馈电机的数学模型和基于 Sim ulink4 的仿真 陈海朋1 , 李 岩1 , 韩 伟2 (1. 鞍山科技大学 电子与信息工程学院, 辽宁 鞍山 114044; 2. 鞍山供电公司, 辽宁 鞍山 114044) 摘 要: 无刷双馈电机是一种在许多方面都有着很好应用前景的新型电机. 本文重新推导了无刷双馈电机 的数学模型, 并在MA TLABöS IMUL IN K 环境下建立了仿真模型, 为进一步构成控制系统, 进行系统分析与 设计奠定了基础. ·170· 鞍 山 科 技 大 学 学 报 第 27 卷