第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·