第 27 卷 第 3 期
2004 年 6 月鞍 山 科 技 大 学 学 报
Journal of A nshan U niversity of Science and T echnology
V ol,27 N o,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),复 制 (D up 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) 的 一 个 排 列 P= (P1,P2,…,Pn) 来 表 示,从 而 将 一 个 基 因 组 重 排 的 反 转 排 序 问 题转 化 为 一 个 排 列 的 反 转 排 序 问 题,
近 十 年 有 关 基 因 组 重 排,特 别 是 基 于 反 转 的 基 因 组 重 排 的 数 学 特 征 及 算 法 的 研 究,一 直 是 计 算 生 物学 中 受 到 广 泛 关 注 的 课 题 [2- 4 ],如 果 基 因 是 有 方 向 的,反 转 基 因 组 重 排 问 题 是 多 项 式 时 间 可 解 的,而 且目 前 已 找 到 了 十 分 有 效 的 算 法 [5,6 ],而 如 果 基 因 是 无 方 向 的,反 转 基 因 组 重 排 问 题 已 被 Cap rara 证 明 是
N P2难 问 题 [7,8 ],目 前 尚 未 找 到 有 效 的 算 法,目 前 较 好 的 算 法 是 近 似 性 能 比 为 3 2 的 近 似 算 法 [9 ],但 基 于演 化 思 想 的 算 法 却 很 少 见,文 献 [ 10 ] 应 用 遗 传 算 法 估 计 基 因 组 重 排 的 反 转 距 离,取 得 了 较 好 的 结 果,
本 文 提 出 了 基 于,一 个 无 向 排 列 P的 反 转 距 离 等 于 由 P所 生 成 的 包 含 2n 个 有 向 排 列 集 Sign (P) 中最 优 排 列 的 反 转 距 离,这 一 事 实 而 设 计 的 求 Sign (P) 中 的 最 优 排 列 的 一 种 模 拟 退 火 算 法,定 义 了 适 合 该问 题 的 解 的 邻 域 结 构,使 得 无 向 排 列 的 反 转 基 因 组 重 排 问 题 的 求 解 在 本 质 上 可 以 应 用 模 拟 退 火 算 法,最收 稿 日 期,2004203205.
作 者 简 介,陶 玉 敏 (1917- ),女,满 族,辽 宁 凌 海 人,
后,数 据 实 验 的 结 果 表 明 该 算 法 优 于 文 献 [ 9 ]的 3 22近 似 算 法,
1 无 向 排 列 的 反 转 排 序 的 数 学 描 述定 义 1 给 定 {1,2,…,n}的 一 个 排 列 P= (P1,P2,…,Pn),如 果 排 列 中 的 每 个 元 素 都 有,+,或,-,
标 号,标 记 染 色 体 中 基 因 的 方 向,如 此 的 排 列 称 为 有 向 排 列 ; 如 果 排 列 中 的 元 素 没 有 标 号,则 此 排 列 称 为无 向 排 列,
定 义 2 排 列 Ig= (+ 1,+ 2,…,+ n) 称 为 有 向 的 恒 等 排 列 ; 而 排 列 I= (1,2,…,n) 称 为 无 向 的 恒 等排 列,
定 义 3 设 P是 无 向 (或 有 向 )排 列,称 Q= [ i,j ] (1≤ i≤ j≤ n)是 对 P的 一 个 反 转,是 指 运 算 PQ产 生如 下 结 果,
PQ= (P1,P2,…,Pi- 1,Pj,Pj - 1,…,Pi+ 1,Pi,Pj+ 1,…,Pn) (1)
或 PQ= (P1,P2,…,Pi- 1,- Pj,- Pj- 1,…,- Pi+ 1,- Pi,Pj + 1,…,Pn) (2)
即 PQ使 P中 从 第 i 个 元 素 至 第 j 个 元 素 的 顺 序 发 生 倒 置 (如 果 是 有 向 排 列,则 同 时 要 改 变 元 素 的 方向 ),而 其 余 元 素 顺 序 保 持 不 变,
定 义 4 给 定 {1,2,…,n}的 两 个 (无 向 或 有 向 )排 列 A,B,求 一 个 反 转 序 列 Q1,Q2,…,Qt,使 得
AQ1Q2… Qt = B (3)
且 t 的 值 为 最 小 的 问 题,称 为 基 于 反 转 的 基 因 组 重 排 问 题 (简 称 反 转 基 因 组 重 排 问 题 ),并 称 数 t 为 A关于 B的 反 转 距 离 (R eversal distance),记 为 d A(B).
设 A和 B是 {1,2,…,n}的 两 个 不 同 的 (无 向 或 有 向 ) 排 列,Q1,Q2,…,Qt 是 一 个 反 转 序 列,注 意 到,由
AQ1Q2… Qt= B可 以 得 到 B- 1AQ1Q2… Qt= I (或 Ig),这 里 B- 1为 B的 逆 排 列,若 记 P= B- 1A,则 A关 于 B的 反 转距 离 d A(B)等 于 P关 于 恒 等 排 列 I (或 Ig)的 反 转 距 离 d P(I) (或 d P(Ig) ),简 记 为 rd (P) (或 srd (P) ),因 此,
以 下 只 考 虑 {1,2,…,n}的 任 一 个 排 列 P关 于 I (或 Ig) 的 反 转 距 离 问 题 而 不 失 一 般 性,基 于 上 述 的 关 系,
反 转 基 因 组 重 排 问 题 也 常 称 为 反 转 排 序 (Sorting by reversals)问 题,
鉴 于 无 向 排 列 的 反 转 基 因 组 重 排 问 题 是 N P2难 问 题,而 有 向 排 列 的 反 转 基 因 组 重 排 问 题 是 多 项 式时 间 可 解 的,可 以 构 造 一 种 方 法 把 无 向 排 列 转 化 为 有 向 排 列,
具 体 做 法 如 下,在 无 向 排 列 的 每 一 个 元 素 上 加 上 正 号 或 负 号,例 如,无 向 排 列 P= (2,1),那 么 生 成有 向 排 列 集 为
Sign (P) = { (- 2 - 1),(- 2 + 1),(+ 2 - 1),(+ 2 + 1) } (4)
这 样 对 于 含 有 n 个 元 素 的 无 向 排 列 P= (P1,P2,…,Pn),可 以 生 成 含 有 2n 个 有 向 排 列 集 Sign (P),其 中每 个 有 向 排 列 含 有 n 个 元 素,
定 义 5 设 P3 ∈ Sign (P),如 果 srd (P3 ) = m in{srd (P′ ),P′ ∈ Sign (P) },则 称 P3 是 Sign (P) 中 具 有最 小 反 转 距 离 的 有 向 排 列 (简 称 最 小 距 离 排 列 ),或 称 最 优 排 列,
无 向 排 列 与 有 向 排 列 之 间 有 如 下 结 论,
定 理 1 设 P= (P1,P2,…,Pn) 是 一 个 无 向 排 列,则 对 于 Sign (P) 中 的 每 一 个 有 向 排 列 P′ = (P′ 1,
P′ 2,…,P′ n),P′ 的 反 转 序 列 也 是 P的 反 转 序 列,
定 理 2 设 P是 无 向 排 列,则 必 定 存 在 有 向 排 列 P3 ∈ Sign (P),使 得
srd (P3 ) = rd (P) (5)
定 理 1 和 定 理 2 的 证 明 见 文 献 [ 10 ].
上 述 两 个 定 理 保 证 了 在 Sign (P) 里 至 少 存 在 一 个 最 小 距 离 排 列,它 的 反 转 序 列 是 P的 最 优 反 转 序列,因 此,求 解 无 向 排 列 的 反 转 排 序 问 题 可 以 转 化 为 求 解 有 向 排 列 集 Sign (P) 中 的 具 有 最 小 距 离 排 序 问题,然 而,搜 索 2n 个 有 向 排 列 P′ 寻 找 最 小 距 离 排 列,花 费 时 间 为 O (2nn),实 际 上 是 不 可 行 的,本 文 设 计一 种 模 拟 退 火 算 法 来 寻 找 集 合 Sign (P) 中 的 最 小 距 离 排 列,进 而 给 出 无 向 排 列 P的 最 优 (或 次 最 优 ) 反
·761·第 3 期 陶 玉 敏,等,用 模 拟 退 火 算 法 求 解 无 向 排 列 的 反 转 排 序 问 题转 序 列,
2 模 拟 退 火 算 法
211 模 拟 退 火 算 法基 于 统 计 物 理 的 概 念 和 方 法,1983 年 S,K irkpatrick 等 人 提 出 了 求 解 组 合 最 优 化 问 题 的 模 拟 退 火 算法 (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 ) > G时,则 i= j (其 中 N (i) < S 为 i 的 邻 域 ; G为 [ 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 个 元 素 的 无 向排 列 P,生 成 一 个 包 含 2n 个 有 向 排 列 集 Sign (P),对 Sign (P) 中 的 有 向 排 列 按 随 机 产 生 的 二 进 制 编 码 描述 排 列 中 元 素 的 标 号 (+ 或 - ),就 是 0,1 分 别 代 表,-,或,+,号,对 于 已 给 排 列 P,编 码 方 案 为 sP=
(Pi,S i),i∈ [ 1,n2 ],Pi 为 已 给 排 列 P,si= (si1,si2,…,sin),sij∈ {0,1},j∈ [ 1,n ],又 因 为 Pi 为 已 给 排 列 P,每次 变 化 的 仅 仅 是 si,因 此 在 实 际 操 作 中 考 虑 的 只 是 si 部 分,
大 量 的 实 验 结 果 表 明,模 拟 退 火 算 法 的 最 终 解 的 质 量 并 不 十 分 依 赖 于 初 始 解 的 选 取,因 此,在 S ig n
(P)中 任 取 一 个 有 向 排 P′ 作 为 初 始 解,并 且 按 上 面 的 编 码 方 案 给 出,
(2) 邻 域 结 构 的 确 定 和 新 解 的 产 生 机 制 本 文 所 指 的 邻 域 结 构,采 用 了 模 拟 退 火 算 法 中 术 语,简单 地 说,当 前 解 经 过 一 次 变 换 形 成 的 新 解 的 集 合 称 为 当 前 解 的 邻 域,对 于 无 向 排 列 的 反 转 基 因 组 重 排 问题,构 造 解 的 邻 域 如 下,
记 T = {si1,…,sin}2ni= 1,sik∈ {0,1},P i,j∈ T,d (i,j ) = ∑
n
k= 1
sik- sjk? (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 ) > G,则 i= j,若 exp ($ srd T ) > G,则 i= i.
(3) 计 算 目 标 函 数 设 P是 无 向 排 列,生 成 含 有 2n 个 有 向 排 列 集 Sign (P),目 标 函 数 F (x ) =
srd (x ),x ∈ Sign (P),应 用 文 献 [ 5 ]的 算 法 计 算 F (x ).
(4) 退 火 策 略 温 度 参 数 是 模 拟 退 火 算 法 中 一 个 关 键 的 参 数,主 要 包 括 起 始 温 度 的 选 取,温 度 的下 降 方 法 和 停 止 温 度 的 确 定 等,温 度 下 降 太 快,优 化 只 能 达 到 所 谓 的 亚 稳 态,结 果 不 理 想,下 降 太 慢,直接 影 响 处 理 的 效 率,因 时 间 太 长 而 失 去 意 义,因 此,退 火 策 略 的 把 握 是 举 足 轻 重 的,但 却 是 经 验 性 的,它直 接 依 赖 于 问 题 的 类 型,一 个 常 用 的 退 火 策 略 是 采 用 线 性 控 制,T k+ 1= d (T k) = AT k,A∈ [ 0,2,0,99 ],此
·861· 鞍 山 科 技 大 学 学 报 第 27 卷时 的 函 数 具 有 随 算 法 进 程 递 减 的 衰 减 量,因 此 可 以 减 小 温 度 参 数 值 T k 递 减 的 速 率,有 益 于 模 拟 退 火 算法 试 验 性 的 稳 定,
(5)算 法 终 止 条 件 在 同 一 温 度 下 最 好 解 在 二 十 次 迭 代 内 不 变,
3 实 验 及 结 果为 了 鉴 定 模 拟 退 火 算 法 在 计 算 无 向 排 列 的 反 转 基 因 组 重 排 问 题 中 的 有 效 性,将 此 算 法 用 C 语 言 编程 进 行 实 验,并 与 文 献 [ 9 ]的 3 22近 似 算 法 做 了 比 较,
本 文 的 实 验 参 数,温 度 初 值 T 0 为 已 给 排 列 的 长 度 n,A= 0,8.
取 含 有 n (n= 10,20,30,40,50,60,70,80) 个 元 素 的 排 列 P,每 个 排 列 P随 机 产 生 100 个 分 别 用 模拟 退 火 算 法,3 2-近 似 算 法 计 算,取 它 们 的 平 均 值,即 rd (P)
-
= {rd1 (P) + rd2 (P) + … + rd100 (P) } 100,结果 见 表 1.
表 1 3 22近 似 算 法 与 模 拟 退 火 结 果 的 比 较 (平 均 值 )
Tab,1 Compersion of results of 23 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 反 转 序 列 Qt= [ i,j ] (t∈ [1,26 ])
Tab,2 R eversal sequence
t∈ [ 1,26 ] Qt= [ i,j ] t∈ [ 1,26 ] Qt= [ 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 EN HALL I S,PEV ZN ER P,T ransform ing cabbage into turnip [J ],Journal of the A CM,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,Computional M olecular B iology,A n A lgorithm ic A pp roach [M ],Cam bridge,M IT P ress,2000,229-
249.
·961·第 3 期 陶 玉 敏,等,用 模 拟 退 火 算 法 求 解 无 向 排 列 的 反 转 排 序 问 题
[4 ]SAN KO FF D,E l2MABROU K N,Genom e rearrangem ent [A ],J IAN G T,SM ITH T,XU Y,et al,Current Top ics in
Computational B iology[C ],Cam bridge:M IT P ress,2002,135- 155.
[ 5 ]KA PLAN H,SHAM IR R,TA RJAN 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 ]BAD ER 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 Computational B iology,2001,8 (5),483- 491.
[ 7 ]CA PRA RA A,Sorting by reversals is difficult [A ],P roceedings of the F irst A nnual International Conference on Compu2
tationalM olecular B iology[C ],N ew York,A cm P ress,1997,75- 83.
[8 ]CA PRA RA 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 D avid A,A 3 22A pp roxim ation A lgorithm for Sorting by R eversals[A ],P roc,ninth annual A CM 2S IAM
Symp,on D iscrete A lgorithm s (SODA 98) [C ],MA,A CM P ress,1998,244- 252.
[ 10 ]AU YEUN G A ndy,ABRA HAM A jith,E stim 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 IR KPA TR ICK S,GELA TT J r 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 D avid,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 un signed permutation by reversals
TA O Y u2m in1,Z EN G T ao2,M O S hu2y uan2,SH I Y an2x ia1
(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,T he 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),T he 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.
T he 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 ivedM arch 5,2004)
待 发 表 论 文 预 报无 刷 双 馈 电 机 的 数 学 模 型 和 基 于 Sim ulink4 的 仿 真陈 海 朋 1,李 岩 1,韩 伟 2
(1,鞍 山 科 技 大 学 电 子 与 信 息 工 程 学 院,辽 宁 鞍 山 114044; 2,鞍 山 供 电 公 司,辽 宁 鞍 山 114044)
摘 要,无 刷 双 馈 电 机 是 一 种 在 许 多 方 面 都 有 着 很 好 应 用 前 景 的 新 型 电 机,本 文 重 新 推 导 了 无 刷 双 馈 电 机的 数 学 模 型,并 在 MA TLAB S IMUL IN K 环 境 下 建 立 了 仿 真 模 型,为 进 一 步 构 成 控 制 系 统,进 行 系 统 分 析 与设 计 奠 定 了 基 础,
·071· 鞍 山 科 技 大 学 学 报 第 27 卷
2004 年 6 月鞍 山 科 技 大 学 学 报
Journal of A nshan U niversity of Science and T echnology
V ol,27 N o,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),复 制 (D up 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) 的 一 个 排 列 P= (P1,P2,…,Pn) 来 表 示,从 而 将 一 个 基 因 组 重 排 的 反 转 排 序 问 题转 化 为 一 个 排 列 的 反 转 排 序 问 题,
近 十 年 有 关 基 因 组 重 排,特 别 是 基 于 反 转 的 基 因 组 重 排 的 数 学 特 征 及 算 法 的 研 究,一 直 是 计 算 生 物学 中 受 到 广 泛 关 注 的 课 题 [2- 4 ],如 果 基 因 是 有 方 向 的,反 转 基 因 组 重 排 问 题 是 多 项 式 时 间 可 解 的,而 且目 前 已 找 到 了 十 分 有 效 的 算 法 [5,6 ],而 如 果 基 因 是 无 方 向 的,反 转 基 因 组 重 排 问 题 已 被 Cap rara 证 明 是
N P2难 问 题 [7,8 ],目 前 尚 未 找 到 有 效 的 算 法,目 前 较 好 的 算 法 是 近 似 性 能 比 为 3 2 的 近 似 算 法 [9 ],但 基 于演 化 思 想 的 算 法 却 很 少 见,文 献 [ 10 ] 应 用 遗 传 算 法 估 计 基 因 组 重 排 的 反 转 距 离,取 得 了 较 好 的 结 果,
本 文 提 出 了 基 于,一 个 无 向 排 列 P的 反 转 距 离 等 于 由 P所 生 成 的 包 含 2n 个 有 向 排 列 集 Sign (P) 中最 优 排 列 的 反 转 距 离,这 一 事 实 而 设 计 的 求 Sign (P) 中 的 最 优 排 列 的 一 种 模 拟 退 火 算 法,定 义 了 适 合 该问 题 的 解 的 邻 域 结 构,使 得 无 向 排 列 的 反 转 基 因 组 重 排 问 题 的 求 解 在 本 质 上 可 以 应 用 模 拟 退 火 算 法,最收 稿 日 期,2004203205.
作 者 简 介,陶 玉 敏 (1917- ),女,满 族,辽 宁 凌 海 人,
后,数 据 实 验 的 结 果 表 明 该 算 法 优 于 文 献 [ 9 ]的 3 22近 似 算 法,
1 无 向 排 列 的 反 转 排 序 的 数 学 描 述定 义 1 给 定 {1,2,…,n}的 一 个 排 列 P= (P1,P2,…,Pn),如 果 排 列 中 的 每 个 元 素 都 有,+,或,-,
标 号,标 记 染 色 体 中 基 因 的 方 向,如 此 的 排 列 称 为 有 向 排 列 ; 如 果 排 列 中 的 元 素 没 有 标 号,则 此 排 列 称 为无 向 排 列,
定 义 2 排 列 Ig= (+ 1,+ 2,…,+ n) 称 为 有 向 的 恒 等 排 列 ; 而 排 列 I= (1,2,…,n) 称 为 无 向 的 恒 等排 列,
定 义 3 设 P是 无 向 (或 有 向 )排 列,称 Q= [ i,j ] (1≤ i≤ j≤ n)是 对 P的 一 个 反 转,是 指 运 算 PQ产 生如 下 结 果,
PQ= (P1,P2,…,Pi- 1,Pj,Pj - 1,…,Pi+ 1,Pi,Pj+ 1,…,Pn) (1)
或 PQ= (P1,P2,…,Pi- 1,- Pj,- Pj- 1,…,- Pi+ 1,- Pi,Pj + 1,…,Pn) (2)
即 PQ使 P中 从 第 i 个 元 素 至 第 j 个 元 素 的 顺 序 发 生 倒 置 (如 果 是 有 向 排 列,则 同 时 要 改 变 元 素 的 方向 ),而 其 余 元 素 顺 序 保 持 不 变,
定 义 4 给 定 {1,2,…,n}的 两 个 (无 向 或 有 向 )排 列 A,B,求 一 个 反 转 序 列 Q1,Q2,…,Qt,使 得
AQ1Q2… Qt = B (3)
且 t 的 值 为 最 小 的 问 题,称 为 基 于 反 转 的 基 因 组 重 排 问 题 (简 称 反 转 基 因 组 重 排 问 题 ),并 称 数 t 为 A关于 B的 反 转 距 离 (R eversal distance),记 为 d A(B).
设 A和 B是 {1,2,…,n}的 两 个 不 同 的 (无 向 或 有 向 ) 排 列,Q1,Q2,…,Qt 是 一 个 反 转 序 列,注 意 到,由
AQ1Q2… Qt= B可 以 得 到 B- 1AQ1Q2… Qt= I (或 Ig),这 里 B- 1为 B的 逆 排 列,若 记 P= B- 1A,则 A关 于 B的 反 转距 离 d A(B)等 于 P关 于 恒 等 排 列 I (或 Ig)的 反 转 距 离 d P(I) (或 d P(Ig) ),简 记 为 rd (P) (或 srd (P) ),因 此,
以 下 只 考 虑 {1,2,…,n}的 任 一 个 排 列 P关 于 I (或 Ig) 的 反 转 距 离 问 题 而 不 失 一 般 性,基 于 上 述 的 关 系,
反 转 基 因 组 重 排 问 题 也 常 称 为 反 转 排 序 (Sorting by reversals)问 题,
鉴 于 无 向 排 列 的 反 转 基 因 组 重 排 问 题 是 N P2难 问 题,而 有 向 排 列 的 反 转 基 因 组 重 排 问 题 是 多 项 式时 间 可 解 的,可 以 构 造 一 种 方 法 把 无 向 排 列 转 化 为 有 向 排 列,
具 体 做 法 如 下,在 无 向 排 列 的 每 一 个 元 素 上 加 上 正 号 或 负 号,例 如,无 向 排 列 P= (2,1),那 么 生 成有 向 排 列 集 为
Sign (P) = { (- 2 - 1),(- 2 + 1),(+ 2 - 1),(+ 2 + 1) } (4)
这 样 对 于 含 有 n 个 元 素 的 无 向 排 列 P= (P1,P2,…,Pn),可 以 生 成 含 有 2n 个 有 向 排 列 集 Sign (P),其 中每 个 有 向 排 列 含 有 n 个 元 素,
定 义 5 设 P3 ∈ Sign (P),如 果 srd (P3 ) = m in{srd (P′ ),P′ ∈ Sign (P) },则 称 P3 是 Sign (P) 中 具 有最 小 反 转 距 离 的 有 向 排 列 (简 称 最 小 距 离 排 列 ),或 称 最 优 排 列,
无 向 排 列 与 有 向 排 列 之 间 有 如 下 结 论,
定 理 1 设 P= (P1,P2,…,Pn) 是 一 个 无 向 排 列,则 对 于 Sign (P) 中 的 每 一 个 有 向 排 列 P′ = (P′ 1,
P′ 2,…,P′ n),P′ 的 反 转 序 列 也 是 P的 反 转 序 列,
定 理 2 设 P是 无 向 排 列,则 必 定 存 在 有 向 排 列 P3 ∈ Sign (P),使 得
srd (P3 ) = rd (P) (5)
定 理 1 和 定 理 2 的 证 明 见 文 献 [ 10 ].
上 述 两 个 定 理 保 证 了 在 Sign (P) 里 至 少 存 在 一 个 最 小 距 离 排 列,它 的 反 转 序 列 是 P的 最 优 反 转 序列,因 此,求 解 无 向 排 列 的 反 转 排 序 问 题 可 以 转 化 为 求 解 有 向 排 列 集 Sign (P) 中 的 具 有 最 小 距 离 排 序 问题,然 而,搜 索 2n 个 有 向 排 列 P′ 寻 找 最 小 距 离 排 列,花 费 时 间 为 O (2nn),实 际 上 是 不 可 行 的,本 文 设 计一 种 模 拟 退 火 算 法 来 寻 找 集 合 Sign (P) 中 的 最 小 距 离 排 列,进 而 给 出 无 向 排 列 P的 最 优 (或 次 最 优 ) 反
·761·第 3 期 陶 玉 敏,等,用 模 拟 退 火 算 法 求 解 无 向 排 列 的 反 转 排 序 问 题转 序 列,
2 模 拟 退 火 算 法
211 模 拟 退 火 算 法基 于 统 计 物 理 的 概 念 和 方 法,1983 年 S,K irkpatrick 等 人 提 出 了 求 解 组 合 最 优 化 问 题 的 模 拟 退 火 算法 (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 ) > G时,则 i= j (其 中 N (i) < S 为 i 的 邻 域 ; G为 [ 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 个 元 素 的 无 向排 列 P,生 成 一 个 包 含 2n 个 有 向 排 列 集 Sign (P),对 Sign (P) 中 的 有 向 排 列 按 随 机 产 生 的 二 进 制 编 码 描述 排 列 中 元 素 的 标 号 (+ 或 - ),就 是 0,1 分 别 代 表,-,或,+,号,对 于 已 给 排 列 P,编 码 方 案 为 sP=
(Pi,S i),i∈ [ 1,n2 ],Pi 为 已 给 排 列 P,si= (si1,si2,…,sin),sij∈ {0,1},j∈ [ 1,n ],又 因 为 Pi 为 已 给 排 列 P,每次 变 化 的 仅 仅 是 si,因 此 在 实 际 操 作 中 考 虑 的 只 是 si 部 分,
大 量 的 实 验 结 果 表 明,模 拟 退 火 算 法 的 最 终 解 的 质 量 并 不 十 分 依 赖 于 初 始 解 的 选 取,因 此,在 S ig n
(P)中 任 取 一 个 有 向 排 P′ 作 为 初 始 解,并 且 按 上 面 的 编 码 方 案 给 出,
(2) 邻 域 结 构 的 确 定 和 新 解 的 产 生 机 制 本 文 所 指 的 邻 域 结 构,采 用 了 模 拟 退 火 算 法 中 术 语,简单 地 说,当 前 解 经 过 一 次 变 换 形 成 的 新 解 的 集 合 称 为 当 前 解 的 邻 域,对 于 无 向 排 列 的 反 转 基 因 组 重 排 问题,构 造 解 的 邻 域 如 下,
记 T = {si1,…,sin}2ni= 1,sik∈ {0,1},P i,j∈ T,d (i,j ) = ∑
n
k= 1
sik- sjk? (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 ) > G,则 i= j,若 exp ($ srd T ) > G,则 i= i.
(3) 计 算 目 标 函 数 设 P是 无 向 排 列,生 成 含 有 2n 个 有 向 排 列 集 Sign (P),目 标 函 数 F (x ) =
srd (x ),x ∈ Sign (P),应 用 文 献 [ 5 ]的 算 法 计 算 F (x ).
(4) 退 火 策 略 温 度 参 数 是 模 拟 退 火 算 法 中 一 个 关 键 的 参 数,主 要 包 括 起 始 温 度 的 选 取,温 度 的下 降 方 法 和 停 止 温 度 的 确 定 等,温 度 下 降 太 快,优 化 只 能 达 到 所 谓 的 亚 稳 态,结 果 不 理 想,下 降 太 慢,直接 影 响 处 理 的 效 率,因 时 间 太 长 而 失 去 意 义,因 此,退 火 策 略 的 把 握 是 举 足 轻 重 的,但 却 是 经 验 性 的,它直 接 依 赖 于 问 题 的 类 型,一 个 常 用 的 退 火 策 略 是 采 用 线 性 控 制,T k+ 1= d (T k) = AT k,A∈ [ 0,2,0,99 ],此
·861· 鞍 山 科 技 大 学 学 报 第 27 卷时 的 函 数 具 有 随 算 法 进 程 递 减 的 衰 减 量,因 此 可 以 减 小 温 度 参 数 值 T k 递 减 的 速 率,有 益 于 模 拟 退 火 算法 试 验 性 的 稳 定,
(5)算 法 终 止 条 件 在 同 一 温 度 下 最 好 解 在 二 十 次 迭 代 内 不 变,
3 实 验 及 结 果为 了 鉴 定 模 拟 退 火 算 法 在 计 算 无 向 排 列 的 反 转 基 因 组 重 排 问 题 中 的 有 效 性,将 此 算 法 用 C 语 言 编程 进 行 实 验,并 与 文 献 [ 9 ]的 3 22近 似 算 法 做 了 比 较,
本 文 的 实 验 参 数,温 度 初 值 T 0 为 已 给 排 列 的 长 度 n,A= 0,8.
取 含 有 n (n= 10,20,30,40,50,60,70,80) 个 元 素 的 排 列 P,每 个 排 列 P随 机 产 生 100 个 分 别 用 模拟 退 火 算 法,3 2-近 似 算 法 计 算,取 它 们 的 平 均 值,即 rd (P)
-
= {rd1 (P) + rd2 (P) + … + rd100 (P) } 100,结果 见 表 1.
表 1 3 22近 似 算 法 与 模 拟 退 火 结 果 的 比 较 (平 均 值 )
Tab,1 Compersion of results of 23 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 反 转 序 列 Qt= [ i,j ] (t∈ [1,26 ])
Tab,2 R eversal sequence
t∈ [ 1,26 ] Qt= [ i,j ] t∈ [ 1,26 ] Qt= [ 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 EN HALL I S,PEV ZN ER P,T ransform ing cabbage into turnip [J ],Journal of the A CM,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,Computional M olecular B iology,A n A lgorithm ic A pp roach [M ],Cam bridge,M IT P ress,2000,229-
249.
·961·第 3 期 陶 玉 敏,等,用 模 拟 退 火 算 法 求 解 无 向 排 列 的 反 转 排 序 问 题
[4 ]SAN KO FF D,E l2MABROU K N,Genom e rearrangem ent [A ],J IAN G T,SM ITH T,XU Y,et al,Current Top ics in
Computational B iology[C ],Cam bridge:M IT P ress,2002,135- 155.
[ 5 ]KA PLAN H,SHAM IR R,TA RJAN 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 ]BAD ER 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 Computational B iology,2001,8 (5),483- 491.
[ 7 ]CA PRA RA A,Sorting by reversals is difficult [A ],P roceedings of the F irst A nnual International Conference on Compu2
tationalM olecular B iology[C ],N ew York,A cm P ress,1997,75- 83.
[8 ]CA PRA RA 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 D avid A,A 3 22A pp roxim ation A lgorithm for Sorting by R eversals[A ],P roc,ninth annual A CM 2S IAM
Symp,on D iscrete A lgorithm s (SODA 98) [C ],MA,A CM P ress,1998,244- 252.
[ 10 ]AU YEUN G A ndy,ABRA HAM A jith,E stim 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 IR KPA TR ICK S,GELA TT J r 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 D avid,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 un signed permutation by reversals
TA O Y u2m in1,Z EN G T ao2,M O S hu2y uan2,SH I Y an2x ia1
(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,T he 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),T he 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.
T he 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 ivedM arch 5,2004)
待 发 表 论 文 预 报无 刷 双 馈 电 机 的 数 学 模 型 和 基 于 Sim ulink4 的 仿 真陈 海 朋 1,李 岩 1,韩 伟 2
(1,鞍 山 科 技 大 学 电 子 与 信 息 工 程 学 院,辽 宁 鞍 山 114044; 2,鞍 山 供 电 公 司,辽 宁 鞍 山 114044)
摘 要,无 刷 双 馈 电 机 是 一 种 在 许 多 方 面 都 有 着 很 好 应 用 前 景 的 新 型 电 机,本 文 重 新 推 导 了 无 刷 双 馈 电 机的 数 学 模 型,并 在 MA TLAB S IMUL IN K 环 境 下 建 立 了 仿 真 模 型,为 进 一 步 构 成 控 制 系 统,进 行 系 统 分 析 与设 计 奠 定 了 基 础,
·071· 鞍 山 科 技 大 学 学 报 第 27 卷
