蛋 白 质 结 构 预 测 与 分 析 的 分 子 动 力 学 能 量 并 行 计 算 刘 波 王 兵 孙 安 香 ( 国 防 科 技 大 学 计 算 机 系 长 沙 410073 sax876@sina.com 摘 要 本 文 概 述 了 分 子 动 力 学 的 并 行 计 算 是 生 物 信 息 学 中 具 有 挑 战 性 的 课 题, 论 述 了 蛋 白 质 结 构 预 测 与 分 析 的 分 子 动 力 学 能 量 并 行 计 算 的 三 种 并 行 计 算 设 计 方 法, 讨 论 了 并 行 计 算 的 并 行 实 现 技 术, 最 后 指 出 将 来 的 主 要 研 究 方 向 关 键 词 蛋 白 质 结 构 预 测 与 分 析, 分 子 动 力 学, 并 行 算 法, 并 行 实 现 技 术 1 引 言 0 世 纪 90 年 代 以 来, 伴 随 着 各 种 基 因 组 测 序 计 划 的 展 开 和 分 子 结 构 测 定 技 术 的 突 破 和 Internet 的 普 及, 数 以 百 计 的 生 物 学 数 据 库 如 雨 后 春 笋 般 迅 速 出 现 和 成 长 如 何 利 用 这 些 不 断 爆 炸 性 增 长 的 有 关 生 物 分 子 的 原 始 数 据, 揭 示 人 类 及 重 要 动 植 物 种 类 的 基 因 信 息, 继 而 开 展 生 物 大 分 子 结 构 模 拟 和 药 物 设 计, 是 当 今 国 际 上 正 在 迅 速 发 展 的 自 然 科 学 领 域 最 重 大 的 课 题 之 一, 它 不 仅 对 认 识 生 物 体 和 生 物 信 息 的 起 源 遗 传 发 育 与 进 化 的 本 质 有 重 要 意 义, 而 且 将 为 人 类 疾 患 的 诊 治 开 辟 全 新 的 途 径, 还 可 为 动 植 物 的 物 种 改 良 提 供 坚 实 的 理 论 基 础 [1,,3] 生 物 信 息 学 正 是 在 这 样 的 背 景 下 逐 渐 兴 起 的 蛋 白 质 结 构 预 测, 包 括 二 级 和 三 级 结 构 预 测, 是 生 物 信 息 学 最 热 门 的 研 究 课 题 [7] 蛋 白 质 结 构 预 测 的 目 的 是 利 用 已 知 的 一 级 序 列 构 建 出 蛋 白 质 的 立 体 结 构 模 型 目 前 预 测 蛋 白 质 空 间 结 构 的 方 法 可 以 分 为 两 大 类 :1 基 于 知 识 的 预 测 方 法, 这 类 方 法 通 过 对 已 知 空 间 结 构 的 蛋 白 质 研 究 和 分 析, 找 出 蛋 白 质 一 级 结 构 和 空 间 之 间 的 联 系 这 类 方 法 已 经 成 功 地 应 用 于 同 源 蛋 白 质 空 间 结 构 预 测 的 研 究 然 而 对 于 同 源 性 低 的 和 非 同 源 蛋 白 质 分 子 来 说, 由 于 受 二 级 结 构 预 测 精 度 的 限 制, 这 种 方 法 只 取 得 了 非 常 有 限 的 成 功 分 子 动 力 学 方 法, 分 子 动 力 学 是 广 泛 应 用 于 生 物 并 行 计 算 的 有 力 数 值 模 拟 工 具, 采 用 分 子 力 学 分 子 动 力 学 方 法, 根 据 物 理 化 学 的 基 本 原 理, 应 用 数 学 方 法 从 理 论 上 计 算 蛋 白 质 分 子 的 空 间 结 构 分 子 动 力 学 的 并 行 计 算 只 所 以 具 有 挑 战 性 是 因 为 在 千 万 分 之 一 秒 内 分 子 可 能 发 生 扩 散 和 构 象 变 异 等 有 趣 的 现 象 近 年 来 数 学 物 理 化 学 并 行 计 算 技 术 推 进 了 分 子 动 力 学 的 发 展 和 应 用, 尤 其 是 各 类 专 家 的 在 分 子 动 力 学 并 行 计 算 取 得 了 一 系 列 研 究 成 果 [4,5,6] 本 文 针 对 蛋 白 质 结 构 预 测 与 分 析, 讨 论 分 子 动 力 学 的 能 量 计 算 的 并 行 算 法 设 计 和 并 行 实 现 技 术
并 行 算 法 在 分 子 动 力 学 数 值 模 拟 中, 有 非 粘 性 (non-bonded 和 粘 性 (bonded 两 种 能 量, 其 中 非 粘 性 的 能 量 可 写 成 : i j E = + ε ij nb q q ij 1 r i j i j ( σ r σ ij ( r 6 (1 其 中 r 为 原 子 i 和 原 子 j 之 间 的 距 离, 本 文 仅 考 虑 短 程 的 (short-range 的 原 子 相 互 作 用, 假 设 rc 为 距 离 控 制 常 数, 所 以 方 程 (1 中 E = k ( r r + b bond b 0 θ angles r < rc k ( θ θ 0 粘 性 能 量 可 写 成 + kφ p [ 1+ d p cos( n p φ] + kφ ( φ φ 0 ( dihedrals impropers 其 中 第 一 项 为 两 位 体 能 量 第 二 项 为 三 位 体 能 量 第 三 项 和 第 四 项 为 四 位 体 能 量, 距 离 r 角 θ 和 φ 分 别 表 示 相 互 作 用 的 原 子 的 位 置 实 现 这 一 能 量 计 算 的 并 行 算 法 主 要 有 三 种 : 能 量 贡 献 矩 阵 的 行 划 分 方 法 能 量 贡 献 矩 阵 的 子 块 划 分 方 法 和 空 间 剖 分 方 法.1 能 量 矩 阵 的 行 划 分 方 法 这 一 方 法 可 归 结 为 线 性 代 数 并 行 计 算 常 用 的 矩 阵 行 划 分 技 术 其 中 每 个 处 理 机 负 责 一 个 原 子 集 的 计 算, 模 拟 过 程 中 不 考 虑 原 子 的 位 置 和 速 度 有 所 改 变, 也 就 是 说 原 子 的 物 理 空 间 改 变 时, 不 改 变 其 并 行 计 算 时 所 属 的 处 理 机 定 义 x 来 确 定 原 子 的 位 置,f 是 长 度 为 N 的 向 量, 为 作 用 在 每 个 原 子 的 总 的 能 量 贡 献 令 为 处 理 器 0 至 p 1 的 处 理 器 序 列 号 标 志,p 计 算 其 它 原 子 对 所 属 该 处 理 机 的 原 子 的 非 F 粘 性 能 量 贡 献 子 块, 相 应 的 原 子 位 置 标 志 为, 对 该 处 理 机 的 每 个 原 子 的 作 用 为 长 度 为 N / p 的 向 量 f 为 了 计 算 非 粘 性 贡 献 F, 只 要 知 道 x 和 x 即 可 ; 但 为 了 计 算 F, 则 需 ij 要 知 道 归 属 于 其 它 处 理 机 的 许 多 原 子, 这 意 味 着 每 个 处 理 机 必 须 存 储 所 有 原 子 x 的 向 量 copy, 所 以 这 种 并 行 计 算 方 法 也 称 为 数 据 replicated-data 并 行 算 法 粘 性 部 分 的 并 行 计 算 方 法 可 作 类 似 处 理. 能 量 矩 阵 的 块 划 分 方 法 为 了 减 少 通 信 开 销, 在 replicated-data 并 行 算 法 的 基 础 上, 应 用 线 性 代 数 并 行 计 算 的 矩 阵 子 块 划 分 技 术, 建 立 能 量 矩 阵 计 算 的 块 划 分 方 法 这 一 并 行 计 算 方 法 在 生 物 信 息 计 算 领 域 x i j
也 通 常 成 为 force-decomposition 方 法 与 能 量 矩 阵 的 行 划 分 方 法 一 样, 令 为 处 理 器 0 至 p 1 的 处 理 器 序 列 号 标 志, 处 理 机 p 拥 有 并 处 理 长 度 为 N / p 的 子 块 向 量 x 若 处 理 机 数 为 16, 处 理 机 的 逻 辑 图 为 : 0 4 8 1 1 5 9 13 6 10 14 3 7 11 15 此 时 处 理 机 排 列 顺 序 为 {0,4,8,1,1,5,9,10,11,1,13,14,15}, 而 不 是.1 那 样 的 处 理 机 以 自 然 顺 序 {0,1,,3,4,5,6,7,8,9,10,11,1,13,14,15} 排 列 ' 归 属 于 处 理 机 的 能 量 贡 献 矩 阵 子 块 F 的 大 小 为 ( N / p ( N / p p.3 空 间 剖 分 方 法 分 子 动 力 学 模 拟 的 第 三 类 能 量 并 行 计 算 方 法 是 采 用 偏 微 分 方 程 并 行 求 解 的 区 域 分 解 思 想, 将 空 间 区 域 划 分 到 并 行 计 算 系 统 的 各 个 处 理 机 完 成 并 行 计 算, 所 以 顾 名 思 义 称 为 空 间 剖 分 方 法 (spatial-decomposition x 在 此 也 令 为 处 理 器 0 至 p 1 的 处 理 器 序 列 号 标 志, 处 理 机 p 所 计 算 的 区 域 为 D, 为 D 这 一 区 域 盒 子 的 元 素, 为 了 计 算 作 用 在 这 一 处 理 机 上 的 贡 献, 不 仅 要 知 道 所 要 计 算 的 原 子 x, 还 要 知 道 在 空 间 距 离 控 制 常 数 r 范 围 内 的 其 它 空 间 区 域 盒 子 内 的 原 子 y 与 能 量 矩 阵 的 行 划 分 方 法 和 能 量 矩 阵 的 块 划 分 方 法 相 比, 并 行 实 现 的 难 度 大, 所 以 空 间 区 域 剖 分 方 法 在 分 子 动 力 学 数 值 模 拟 的 并 行 计 算 中 用 得 比 较 少 但 空 间 区 域 剖 分 方 法 具 有 通 信 开 销 少 的 优 势, 所 以 在 分 子 动 力 学 数 值 模 拟 并 行 计 算 时, 经 常 综 合 应 用 以 上 并 行 计 算 方 法, 达 到 高 效 快 速 得 数 值 计 算 c 3 并 行 实 现 技 术 如 果 在 p 台 处 理 机, 模 拟 计 算 的 速 度 为 一 台 处 理 机 的 p 倍, 这 时 并 行 计 算 效 率 为 100 %, 或 者 说 达 到 理 想 的 并 行 计 算 加 速 比 (perfect speed-up 蛋 白 质 结 构 预 测 与 分 析 的 分 子 动 力 学 能 量 并 行 计 算, 由 于 多 处 理 机 的 通 信 等 开 销 不 能 达 到 理 想 的 并 行 计 算 加 速 比, 但 并 行 计 算 的 目 的 是 尽 量 达 到 高 效 快 速 为 此, 首 先 要 设 计 同 时 高 效 计 算 方 程 (1 和 方 程 ( 的 并 行 算 法 其 次 并 行 计 算 的 物 质 基 础 是 并 行 计 算 机 研 究 并 行 算 法 的 实 现 设 计 并 行 计 算 应 用, 必 须 结 合 并 行 计 算 机 的
结 构 特 点, 设 计 一 系 列 的 高 效 的 并 行 实 现 技 术, 充 分 发 挥 并 行 计 算 机 性 能 [8] 并 行 实 现 技 术 方 面 所 作 的 主 要 研 究 工 作 包 括 内 存 优 化 cache 的 高 效 应 用 和 减 少 通 信 开 销 3.1 内 存 优 化 由 于 生 物 信 息 计 算 的 问 题 均 为 海 量 存 储 问 题 [7], 需 要 设 计 了 灵 活 的 内 存 空 间 分 配 方 案, 随 着 并 行 处 理 机 数 目 的 增 加, 并 行 程 序 单 任 务 所 占 内 存 空 间 减 少 并 行 程 序 即 使 在 处 理 机 数 目 不 多 的 并 行 计 算 环 境 不 能 计 算, 只 要 处 理 机 数 目 增 加 到 一 定 数 目 就 可 实 现 并 行 计 算 ; 同 时 随 着 处 理 机 数 目 增 加 可 保 持 并 行 算 法 实 现 的 线 性 加 速 比 3. cache 的 高 效 应 用 根 据 数 据 相 关 性 合 理 利 用 高 速 缓 存 的 可 重 用 性 CPU 速 度 与 数 据 存 取 速 度 的 差 距 越 来 越 大,CPU 速 度 每 18 个 月 增 长 一 倍, 而 内 存 访 问 速 度 在 同 期 内 只 增 加 15%,cache 机 制 缓 解 了 这 一 高 性 能 计 算 研 究 与 应 用 关 注 的 问 题 合 理 利 用 cache, 关 键 在 于 根 据 高 性 能 并 行 计 算 机 的 体 系 结 构 特 点 设 计 应 用 系 统, 提 高 数 据 的 局 部 性 3.3 减 少 通 信 开 销 减 少 通 信 延 迟 对 并 行 计 算 性 能 的 影 响 设 计 通 信 结 构 调 整 技 术, 减 少 通 信 次 数 ; 设 计 单 个 处 理 机 内 部 的 某 些 计 算 量 与 其 它 计 算 量 的 通 信 重 叠 全 局 的 计 算 与 全 局 通 信 或 局 部 通 信 重 叠 技 术, 减 少 甚 至 消 除 通 信 在 并 行 计 算 过 程 中 的 独 占 时 间 4 未 来 研 究 工 作 中 国 科 学 院 院 士 张 春 霆 指 出 生 物 信 息 学 是 生 物 学 的 核 心 和 灵 魂, 数 学 与 计 算 机 技 术 则 是 它 的 基 本 工 具 当 今 并 行 计 算 技 术 和 网 络 技 术 的 飞 速 发 展, 使 得 人 们 能 够 从 传 统 的 实 验 为 主 导 的 研 究 模 式 中 解 放 出 来 分 子 动 力 学 研 究 采 用 并 行 计 算 技 术 已 是 国 际 潮 流, 只 有 将 并 行 计 算 研 究 和 生 物 信 息 学 中 分 子 动 力 学 这 一 有 效 方 法 的 理 论 研 究 有 机 地 结 合 起 来, 生 物 信 息 计 算 才 能 得 到 更 快 发 展 我 们 将 在 研 究 蛋 白 质 结 构 预 测 与 分 析 的 分 子 动 力 学 能 量 并 行 计 算 的 三 种 并 行 计 算 方 法 研 究 基 础 上, 结 合 并 行 计 算 机 的 结 构 特 点, 设 计 一 系 列 的 高 效 并 行 实 现 技 术, 实 现 高 效 快 速 的 能 量 并 行 计 算, 并 在 此 基 础 上 进 一 步 开 展 蛋 白 质 结 构 预 测 与 分 析 的 分 子 动 力 学 方 法 研 究 参 考 文 献 [1] Structural Changes in Bacteriorhodopsin during the Photocycle Measured by
Time-Resolved Polaried Fourier Transform Infrared Spectroscopy Jan 001 Biophys [] Molecules to maps: Tools for visualiation and interaction in support of computational biology May 000 Biophys [3] Chung-SY, Wong-LS, Kleisli - A New Tool for Data Integration in Biology, TRENDS IN BIOTECHNOLOGY 1999, Vol 17, Iss 9, pp 351-355 [4] D. Ficham. Parallel computers and molecular simulation. Molec. Sim., 1:1-45,1987 [5] S. J. Plimpton. Fast parallel algorithms for short-rang molecular dynamics. J. comp. Phys., 1994. To appear. [6]W. S. Yong and C. L. Brooks, Ⅲ. Dynamic load balancing algorithms for replicated data molecular dynamics,1994. Submitted for publication. [7] 王 志 新, 蛋 白 质 结 构 预 测 的 现 状 与 展 望, 生 命 的 化 学,1999,6:19- [8] 黄 凯, 徐 志 伟 著, 可 扩 展 并 行 计 算 技 术 结 构 与 编 程 陆 鑫 达 译, 北 京 : 机 械 工 业 出 版 社,000