·66· 计算机应用研究 2006 年 M otif 识 别 算 法 简 介 及 软 件 性 能 研 究 * 朱 骥 1, 2 , 杨 华 1, 2 , 牛北方 1, 2 , 郎显宇 1, 2 , 陆忠华 1, 迟学斌 1 ( 1. 中 国科 学院 计 算机网 络信 息中 心 超级 计算 中心 , 北京 100080; 2. 中国科 学院 研 究生 院, 北 京 100049) 摘 要: Motif 在转 录和 后转 录水 平的 基因 表达调 控中 起着 重要 的 作 用。 目前 , 识 别 Motif 的 算法 和 相 应的 软 件 已有 不少 , 但 是却 鲜有 对各 种算 法及软 件性 能共 同评 测的 研究 和报 告。 介绍 了 算 法的 分 类 以及 三 种 常见 的 Mo- tif 识 别算 法 Wordup, MM 和 Gibbs 采样 , 并对 AlignACE, MEME, MotifSampler, Weeder 等 13 种 Motif 寻找软 件进 行 性能 比较 分析 。通过 生物 学意 义的 研究 和性 能比较 结果 可以 得出 : 由 于唯 有 Weeder 算 法考 虑 了 Motif 保守 核 心 位置 , 因 而它 在各 种软 件中 识别 效果较 好 ; 大 部 分算 法 只 考 虑 简 单 而 且短 的 Motif, 所 以 各 种 软 件对 酵 母 菌 这 种 单细 胞生 物的 Motif 识 别性 能比 多细 胞生 物要 高。 关键 词: Motif; Wordup; MM; Gibbs 采样 中图 法分 类号 : TP301. 6 文章 编号 : 1001- 3695( 2006) 10- 0066- 04 文献 标识 码: A Introduction of Algorithms and Performance Research of Softwares for Motif Discovery ZHU Ji1, 2, YANG Hua1, 2, NIU Bei-fang1, 2, LANG Xian-yu1, 2, LU Zhong-hua1 , CHI Xue-bin1 ( 1. Supercomputing Center, Computer Network Information Center, Chinese Academy of Sciences, Beijing 100080, China; 2. Graduate School, Chinese Academy of Sciences, Beijing 100049, China) Abstract: Motif plays a key role in the gene-expression regulating on both transcriptional and post-transcriptional levels. Nowadays there are several algorithms and softwares on detecting Motif, but, however, there is few papers on comparing the performance of these algorithms and softwares. This paper comes up with this background to introduce the classification of the algorithms in general and three common algorithms: Wordup, MM, Gibbs sampling-in details. And a performance comparison is made on the thirteen softwares for Motif detecting such as AlignACE, MEME, MotifSampler, Weeder, etc. Based on the biological research and the performance report, this paper ends with a conclusion that Weeder is the most effective one of these softwares, for it is the only algorithmthat takes account of the conserved core positions of Motifs; Most algorithms only consider simple and short Motifs, so their Motif detecting performance on monadic yeast is significantly higher than on metazoans. Key words: Motif; Wordup; MM( Mixture Model) ; Gibbs Sampling 基因非编码区的一个主要研究方向是对 Motif 的研究。因 为转录和后转录 水平, 其基 因的 表 达在 很大 程 度上 受到 一 些 Motif 的控制。它们本质上是一些比较 短的 DNA 序列, 这些 序 列一般均处在受 调控 基 因的 上游 区 域, 转录 因 子可 识别 这 些 Motif 并与之结合, 从而调节 DNA 的 代谢 和转 录; 或者 由 RNA 结合蛋白识别并与之结 合, 从而影 响 RNA 的 修饰、定位、翻 译 和降解。因此, 分析和识 别 Motif 及了 解它们 的功能 对于理 解 和解释整个基因组行为的意义重大。 Motif 的分析主要 涉及 三类 问题: ①在 给定 基因 组序 列 中 寻找已知的 Motif; ②在 一系 列共 表达或 者共 调控 基因 的上 游 区域中发现未知的 Motif; ③ 寻找 由一个 已知 转录 因子 调控 的 未知基因。本文主要讨论第二类问题, 即在一系列共表达基因 的启动子区域中探测新的 Motif, 通过分析和 提取 DNA 序列 特 征来识别 Motif。 一般原核生物的 Motif 特征 比较明 显, 容 易识 别。但是 真 核生物的 Motif 相对复杂, 其 Motif 长度 和空间分布 变化较大, 收稿日期: 2005- 06- 16; 修返日期: 2006- 01- 23 基金项目: 国家“863”计划资助项目( 2002AA104540) 出现没有固定的位置, 相同蛋白质因子作用的结合位点也存在 差异, 这给识别 Motif 带来了很大的困难。因此, 要设计一个能 识别所有 Motif 的方法几乎 是不可 能的, 而针 对不同 的生物 和 不同特点的 Motif, 出现了很多算法和软件。 1 Motif 寻找算法 1. 1 算法的分类 根据算法搜索策略的不 同, 研 究 Motif 的计 算方法 主要 分 为两大类: ①确定性的方法, 即基于字串的方法, 也称单词数数 法, 它包括 简 单 字 串 列 举 法 ( YMF) 、模 式 驱 动 列 举 法 ( Wor- dup[ 2] , Oligo / Dyad-analysis, QuickScore ) 、样 本 驱 动 列 举 法 ( MOPAC) 、轮廓列举法( Consensus) 、后缀树法 ( Weeder) 、不 匹 配( 前缀) 树法( Mitra) 等。单词数数法是基于上游序列中的 低 聚核甘酸的频率分析, 将一个单词出现的次数与其期望次数进 行比较来衡量超代表性, 然后将几个相似的单词组合起来形成 一个 Motif。② 似 然说 的 方 法。它 又 称 为概 率 序 列 模 型 的 方 法, 包括 EM 算 法 [ 1] ( MEME, Improbizer) 、Gibbs 采 样算 法 [ 3, 4] ( AlignACE, ANN-Spec, GLAM, MotifSampler, SeSiMCMC) 等。它 

第 10 期 朱 骥等: Motif 识别算法简介及软件性能研究 ·76· 是一种近似算法, 这类算 法首先 对 Motif 的信 息进行 某种近 似 描述, 然后通过不断迭代的过程对 Motif 信息进行调整优化, 直 至满足迭代终止条件。 1. 2 三种常见的算法 有许多方法可以检测一条序列中重复的序列模式, 这些方 法经过改进后可用于从一组序 列中提 取相同 或者相 近的短 序 列, 作为候选的 Motif。这些方法所依据的主要原理是, Motif 比 随机出现的序列片段具有更高的出现频率。 1. 2. 1 Wordup 算法 Wordup 算法是在 DNA 序 列中 找出 具有 显 著统 计特 性 的 单词。它是基于一级马尔可夫链的分析方法, 其允许对一组已 知在功能上有联 系的 ( 如启 动子 区域、内含 子等 ) 且没 有进 行 过比对的序列进行分析, 选出共同的具有特定生物学功能的单 词或者子序列。 假设有一条长度为 n 的序列 S, S = s1s2 …sn( si = A, C, G, T; i = 1, 2, …, n) , 它含 有 n - w + 1 个长 度为 w 的 寡聚 核苷 酸 单 词, 表示为 tj = sjsj+ 1…sj+ W- 1, j = 1, 2…n - w + 1, 寡聚 核苷酸 实 际上是短的 DNA 片段, 长度为 w 的寡 聚核苷 酸单词 的个数 为 4W 个。现在考虑有 N 条核酸序 列, S1, S2 , …, SN, 令 Li 表示 各 序列的长度。假设寡聚核苷酸的分布符合泊松分布, 用 πi ( tk) 表示长度为 w 的第 k 种寡聚核苷酸单词在序列 Si 中至少 出现 一次的概率( k = 1, 2, …, 4 W) , 则 πi ( tk) = 1 - e - μ ik ( 1) 其中 μik为在第 i 条序列中长度为 w 的第 k 种单词期 望出现 的 平均次数, 它可表示为 ik = qi ( tk) ×( Li - w + 1) μ ( 2) 式( 2) 中 qi( tk) 是寡聚核 苷酸单 词 tk 在序列 i 中的出 现概率。 令 f( ux, y ) 和 f( uz) 分别表 示 tk 中两 个相 邻位 x, y 二核 苷酸 和 单核苷酸 z 在每一条序 列中的 出现 概率。该 方法 在计 算寡 聚 核苷酸单词出现 频率 时 考虑 了核 苷 酸间 的 相互 影响, 因 为 在 DNA 中有一个相当普 遍的 现象, 就是 在核 苷酸 使用 上具 有 相 当强的二核苷酸偏性。这是一个典型的一阶马尔可夫链模型, 可以得出 qi( tk) = f( μ12) f( μ23) …f( μw- 1, w) /f( μ2) …f( μw- 1 ) 而 tk 在不同序列中期望出现的次数为 ∏ ( tk) = ∑ i πi ( tk) ( 3) ( 4) 假设一个序列集合中有 N 条 DNA 序 列, 长 度为 w 的第 k 种单词在不同序列中实际出现的次数由下式给出: P( tk) = ∑ i pi ( tk) ( 5) 其中, 如果序列 Si 中存在 tk, 则 pi( tk) = 1; 否则 pi ( tk) = 0。 根据基本的 χ2 统计可以计算出第 k 种单词 tk 的统计 学显 著性: χ2( k) = ( P( tk) 对于给定的 χ2 值及 已知的 分布 函数 P( χ2 ) , 可 以计 算 出 - ∏( tk) ) 2 /∏ ( tk) ( 6) Motif 位置信息和特征矩阵( 位置频率矩阵) 的共调控序列中, 如 果存在共同的 Motif, 确定 Motif 的位置和对 应的特 征矩阵。其 基本思想在于 Motif 具有保守性, 且 有对应的特征矩阵, 在不断 迭代的过程中只有当 两者适 应时最 大似然 函数值 才能达 到最 大。 MM 算法的基本步骤是: 先对序列集建立二 元有限混合 模 型, 再运用最大似然估计法对模型的参数值进行估计。 设序列集为 S = { S 1, S2, …, SN} , 取所有 Sq 中一切长度 为 w 的子序列构成新的序列集 X = { X 1, …, Xn} 。由于 Xi 可能 是 Motif 序列, 也可能是非 Motif 序列 ( 背景序 列) , 因 此 X 可以 看 成是一个随机向量。当 Xi ( i = 1, 2, …, n) 是 Motif 时, 可用每个 位置上 碱基出 现的概 率来表 征, 即字母 表 A = { a 1, a2 , …, an } 中每个字母 as 出现在序列中的位置 j 的 概率为 fjs( j = 1, 2, …, W, s = 1, 2, …, L) , 再 定义 fj = ( fj1 , fj2, …, fjL) ; 当 Xi 为背景 序 列时可以用概率分布表示为 f0 = ( f01, f02 , …, f0L) 。 二元有 限 混合模型是建立在序 列集 合 X 的基 础上 的, 它 可描 述为 以 概 率 λ1 选取模式序列, 或以概 率 λ2 = 1 - λ1 选取 背景序列构 成 的原序列。因此简单地说, 二元即表示二组, 即 Motif 序列组和 背景序列组。模型中待估计的 参数为 λ= ( λ1, λ2) 和 θ= ( θ1, θ2 ) , 其中 θ= ( f1, f2 , …, fw) , θ= f0。 定义建立指示变量: Z = ( Z1 , Z2 , … , Z n) Z i = ( Zi1, Zi2) { Z ik = 1 X i 来自 第 k 组 0 其 他 ( k = 1, 2) 当 Xi 为 Motif 时, Zi1 = 1, Zi2 = 0; 而 当 Xi 为 背 景 序列 时, Z i1 = 0, Zi2 = 1。显然 Z 也为 随机 变量, Zik = 1 说明 Xi 具 有 分 布 p( Xi |θk) 。 模型的似然函数可表示为变量 X 和 Z 的联合概率分布: L( θ, λ|X, Z) = p( X i, Zi |θ, λ) log L( θ, λ|X, Z) = log p( Xi , Z i |θ, λ) = ( 8 ) n ∑ i =1 2 ∑ k =1 ( Zik |X, θ, λ) log( p( Xi |θk) λk) ( 9 ) W 其中 p( Xi |θ1) = ∏ j= 1 L ∏ s =1 f I( s, Xij) js W , p( X i |θ0) = ∏ j= 1 L ∏ s =1 f I( s, Xij) 0s 。 Xij表示序列 Xi 的第 j 个位置的字母, I( s, x) 是一个指示 函 数, 其定义为 I( s, x) = { 1 x = as 0 其他 MM 算法采用期 望值 最大 来求 解最 大似然 估计。首 先 假 定 Motif 序列在原序列中的初始位置, 计算特征矩阵; 其次用这 个特征矩阵重新计算初始位置; 最后这两个过程不断迭代直至 收敛或达到最大迭代次数。 ( 1) 初始化模型参数, 记 为 θ( 0) 和 λ( 0) , 分别 取 0 ～1 之 间 的随机值, 令迭代次数 t = 0。 ( 2) 根据模型参数 θ( i) 和 λ( i) , 求 Z( i) 。首 先计算 出式( 9) 的期望值: E [ log L( θ, λ|X , Z ) n ] = ∑ i =1 2 ∑ k = 1 Z( i) ik log P( Xi |θk) + p( Xi |θ( i) k 2 p( Xi |θ( i) ∑ k k =1 ) λ( i) k ) λ( i) k ( 10 ) ( 11 ) 超过这个值的长度为 w 的单词个数: N( χ2 ) = [ 1 - P( χ2 ) ] ×4w 1. 2. 2 MM 算法 ( 7) n ∑ i =1 2 ∑ k =1 Z( i) ik log λk MM( Mixture Model) 算法是 EM( Expectation Maximization) 算法的一种改进。该算法主 要解决 的问题 是在一 系列 不知其 其中 Z( i) ik = E[ Zik |X, θ( i) , λ( i) ] = 

·86· 计算机应用研究 2006 年 ( 3) 根据 Z( i) 估计模型的参数 θ( i +1) 和 λ( i +1) , 使式( 10) 的 值最大。 因为式( 10) “+ ”号前后 两部 分分 别只与 一个 参数 有关, 因此可以对它们分别求最大值, 对于右边即求 arg max λ n ∑ i = 1 2 ∑ k =1 可得 λ( i +1) k n = ∑ i =1 Z ( i) ik Z ( i) ik n log λk 。 对于式( 10) “+ ”号左边有 θ( i +1 ) k = arg max Z( i) ik log p( X i |θk) = n ∑ i =1 θk W ∑ j =1 L ∑ s = 1 log f ( i) n js ∑ i= 1 Z( i) ik I( s, Xij) ( 12) n js = ∑ i =1 n 0s = ∑ i =1 W ∑ j =1 定义 c( i) i2 I( s, X ij) , c( i) Z( i) i1 I( s, Xij ) 。 其中, EiZ ( i) c( i) 0s 即字母 as 出现在背景序 列的 期望 次数, c( i) js 即 字母 as 出 现 在 Motif 中位置 j 的期望次 数; Ei 是 一个衰 减系 数, 在 0 ～1 间 变化, 表示序列 Xi 是否是序列模式, 若是, Ei 不断减少至 0, 否 则 Ei 为 1。这使得本算法可以从共调 控序列 中尽可 能找到 所 有的 Motif。 转变后的式( 12) 为 , θ( i +1) θ( i +1 ) = ( θ( i +1) 1 2 ) = ( f ( i +1) 1 , f ( i +1) 2 , … , f ( i +1) W , f ( i +1) 0 ) = arg max θ W ∑ j=0 L ∑ s =1 c( i) js log f ( i) js 利用拉格朗日算法可以解出 f( i + 1) js = c( i) js L c( i) ∑ js s =1 ( 13) ( 14) ( 4) 令 t = t + 1, 重复 ( 2) 、( 3) , 直 至 θ前 后两 次的 差值 小 于用户定义的阈值或达到最大迭代次数。 在经过一个完整的迭代过程后, 可以根据 θ的值得到 序列 模式的一致性序列( 每一位取出 现频率 最高的 碱基) ; 根据 Z i1 的大小确定模式序列及其起始位置。 1. 2. 3 Gibbs 采样算法 Gibbs 采样算法是 一种 特殊 的 马尔 可夫 链 蒙特 卡罗 方 法 ( MCMC) , 该算法最早是 用于蛋 白质序 列中的 序列 模式 识别。 后来将 Gibbs 采样整合进贝叶斯模型 并应用于多 重序列比较, 获得了较好的结果。采 用 Gibbs 采 样算 法的软 件有 MotifSam- pler, AlignACE, BioProspector, Gibbs Motif Sampler 等。Gibbs 采 样算法识别 Motif 的基本原理是, 通过 随机采样不 断更新 Motif 模型和在各条序列中的出现位置以优化目标函数, 当满足一定 的迭代终止条件时就得到了最终的候选 Motif。 这里假设每类 Motif 在每条序列中出现且仅出现一次。基 本的 Gibbs 采样具体的算法过程如下: ( 1) 初始化。包括 Motif 模型和背景 模型的 建立。采用 位 置频率 矩 阵 ( PSFM) 来 表 示 Motif 模 型。首 先 随 机 生 成 n 个 Motif 在各条序列中的 起始位 点, 记 为 SS = { i = 1, 2…, n。 然后根据起始位点和定义的长度 W 得到 候选 Motif, 并根据 这 些候选 Motif 建立位置频率 矩阵 PSFM。背景 模型通 常采用 独 立性模型, 记为 B = { , 表示各碱 基在背 景序列 中 的出现频率。 q A, qG, qC, qT} s s i} , ( 2) 更新。从输入序列集中顺序选 取一条序 列 Si, 序列 长 度为 Li ( i = 1, 2…, n) , 从 SS 中删除属于该序列的起始位点, 根 据变化后的 SS 重新计算 PSFM。然后分别根据 Motif 模型和背 景模型计算 Si 中所有可能的候选 Motif, 即 Si[ j = 1, 2…, Li - W + 1) 的得分 Score e( i, j) 和 Scoreb( i, j) , 也就是 计 算序列 Si 中从第 j 位到第 j + L- 1 位的序 列片段是 Motif 的 可 能性及是背景序列的可能性。这里: j + W - 1] ( j , Score e( i, j) = Score e( Si[ W - 1 ∏ t =0 PSFM( t, Si[ t + j, t + j ] ) Score b( i, j) = Scoreb( Si[ j j , , j + W - 1] |M) = W - 1 j + W - 1 ] |B) = ∏ t =0 qSi[ t+ j, t+ j] ( 15 ) ( 16 ) 其中 PSFM( i, b) 是指 Motif 位置 i 上字母 b 的出现概率。 ( 3) 采样。计 算两 种 得分 的比 值 ri, j = Score e( i, j) Score b( i, j) , 并 对 每 一个 j 选取新的候选 Motif, 即以较大的概率选取比值较高的候 选 Motif, 将其起始位点加入到 SS中。根据新的起始位点集 SS 和 Motif 长度得到候选 Motif 并计算得分 F: W F = ∑ i= 1 L ∑ k =1 piklog ( pik qak ( ( 17 ) 其中 pik = PSFM( i, ak) , ak 为字母表 A = { a 1 , a2 , …, aL} 中的第 k 个字母) 。若得分 F 大于前一次得分, 则转到( 2) , 继续迭代; 否则重复( 3) , 直 至重 复次 数大 于一 个预 设定 值; 若 所有 序 列 均处理完, 则转到( 4) 。 ( 4) 终止。若得 分连 续多 次没 有改 进或 达 到最 大迭 代 次 数, 则终止程序。 1. 3 四种算法的性能评价 Wordup 算法属于确定性的方法, 这类方法非常 简单; 但 缺 点是具有非常复杂的计算复杂度, 只适合搜 索短的 Motif。 MM 算法和 Gibbs 采样算法属于似然说的方 法, 这类 算法具有较 低 的计算复杂度, 适合在大空 间中搜 索解; 其缺 点是不 能保证 得 到问题的最优解。确定性算法的另一 个缺点是严 格要求 Motif 的连续性, 即要求这个 Motif 中每个位置均是严格保守的, 不能 有替换发生。解决这一问题的方法是可以识别两端保守, 中间 有固定长度的不保守序列 Motif。该 方法的思想 是分别计算 两 端保守区域的统计显著性, 然后计算给定中间不保守序列长度 的条件下这两端 保守 区 域的 联合 概 率, 从而 计 算其 统计 显 著 性。但这种新方法也有明 显的缺 点, 就 是搜索 到的 Motif 内 部 不能有变化, 两端的保守区域不能有碱基替换。 Wordup 算 法中如 果 Motif 出 现位置 与具有 显著统 计意 义 的单词重叠, 那么其 χ2 值 会比 期望 值要 高得 多。解决 这个 问 题可以用下面的迭代过程 对每一 条序列 进行处 理。 在第一 次 迭代中, 对所有长度为 W 且 χ2 大于一 定值的 寡聚核 苷酸单 词 按 χ2 值从大到小进行排序。假设共 有 M 个这 样的单 词, 将 后 面的 M - 1 个单词与第一 个( 具有最 大 χ2 值 ) 单词 进行 比较, 那些与第一个单词在位置 上有重 叠的单 词将被 去掉。后面 的 M - 1 个单词的 χ2 值将 被重 新计 算, 并 且根 据 新的 χ2 值 进 行 排序。同样的过程重复 M - 1 次, 直到所有 M 个具有显著统计 意义的单词不再相互重叠为止。 MM 算法是 EM 算法的改进。它解决了 EM 严重依赖初始 化条件, 容易陷入局部极值而得不到最优解的问题。该算法的 每个子序列均作一步 EM 迭代, 保 留似 然最 大的 那个 Motif 模 型作进一步 EM 迭代直到收敛, 记录对应 Motif 的位 置, 然后 再 反复这个过程直至得到优化结果。 Gibbs 采样算法有两个缺点: ①它从序 列 Si 中随机选取 一 

第 10 期 朱 骥等: Motif 识别算法简介及软件性能研究 ·96· 个起始位置 ssi , 这个位置使得进 度很慢, 且不能确定 最后能 达 到一个好的结果; ②该算法计算每个起始位点 ssi 的 F 值, 但是 大部分位置不能达 到很 好的收 敛效 果, 所 以这 些 F 值是 没 有 意义的。用蚂蚁群聚最佳化算 法可以 找到每 条序列 更好的 候 选位置, 这样可以大大提高 Gibbs 采样算法的效率和质量。 综上所述, 相对于 Wordup 算法, MM 和 Gibbs 采 样算法 确 定性不如前者, 但运行速 度大大 提高, 而且很 多实际 应用均 证 明了这类得到的近似解基本上能满足解决问题的需要。 2 13 种软件的性能比较 Motif 寻找的软件 很多, 它们 寻 找 Motif 的性 能也 不 一样, 在此 对 13 个 软 件 ( AlignACE, ANN-Spec, Consensus, GLAM, Improbizer, MEME, Mitra, MotifSampler, Oligo/ Dyad-analysis, QuickScore, SeSiMCMC, Weeder, YMF) 进行了比较 [ 6, 7] 。它们处 理的序列集共有 56 个, 分别来自酵母菌、老鼠、人类和果蝇, 序 列集的来源有三种: ①真实的有确认 Motif 生物体基因序列; ② 用 HMM 产生的随机序 列, 其中插 入了用 权矩阵 产生的 Motif; ③用一个简单的多项模型产生的序列, 其中插入了用权矩阵产 生的 Motif。这里用 tp 表示 已 知的 与预 测 的位 置 中重 叠 的 长 度; fp表示没有与已知核苷 重叠的 预测到 的核 苷数; tn 表示 不 是已知的也没有预测到的核苷数; fn表示已知的没有预测 到的 核苷数。定义灵敏度 Sens = tp/( tp + fn) , 该值给出了已知 的结 合位点核苷中预测出的比例; 位置预测值 ppv = tp/( tp + fp) , 该 值给出了预测出的位点中已知位点所占的比 例; 特征 值Spec = tn/( tn + fp) , 该值给出了未 预测出 的没有 结合位 点的核 苷数。 另外定义确定的核苷位置与预 测的核 苷位置 之间的 相关系 数 为 nCC = tp· tn - fn·fp ( tp + fn) ( tn + fp) ( tp + fp) ( tn + fn) 槡 其值从 - 1( 两者正好 反相关) ～+ 1( 两者完 全相 关) , 如果 预 测的核苷位置在序列中随机出现, 那么 nCC 的值为 0。 具备了这些参数 以及 相应 的实验 数据, 可 以作 出 如图 1、 图 2 所示的图形。 30% 20% 10% 0% ppv Sens 0.4 0.3 0.2 0.1 0 -0.05 Yeast Mouse Human Fly 图 1 所有序列集的 ppv 和 Sens 值折线图 图2 四种动物序列集的 nCC 值折线图 这里 MEME 使用了两个版本, 分别独 立运行。可 以看到, 尽管分别自由地 选 择不 同 的参 数和 一 条序 列中 的 Motif 个 数 ( 一个或没有) , 但 MEME 和 MEME3 的结果非常 一致。从图 1 和图 2 可以看出, Weeder 的性能比其他的软件要高, Weeder 成 功的一个因素是它以警告模式运行, 在这种模式下只有最强的 Motif 才会被报告。当 然也 有 例外, 图 2 中 SeSiMCMC 在 处 理 果蝇数据集上效果最好; MEME3 和 YMF 在老鼠数据集上 效果 更好。待处理的序列集中 的 Motif 的长 度可能 比较长, 而这 些 算法一般只考虑简 单了 比较短 的 Motif, 所以 图中 单细 胞生 物 酵母菌的 nCC 值比 其余 的三 种动 物都 明显 高, 而且 最复 杂 的 多细胞生物果蝇的 nCC 值都很低, 甚至低于 0。 从上面的分析可以看出, 很多不同的搜索算法可以得到非 常相似 的结果。在 Motif 的长 度不超 过 20 bp 的情 况下, 即 使 应用简单列举法的软 件 YMF 都能 处理复 杂的 样本。另 外, 一 个好的得分函数 得到 的结 果会 好得 多, 如 Weeder。因为 一 般 不知道真实的长度是多少, 所以该得分函数应该包含比较不同 长度 Motif 的可能性。另外 由于无 法预先 知道序 列集的 情况, 故每一个参数均应该从序列中考虑。 3 结束语 Motif 寻找的算法 软件 很多, 本文 在介 绍这 些算 法的 基 础 上, 对寻找 Motif 的 13 种软件进行了 性能比较。由于 考虑 Mo- tif 保守核心位置的 原因, Weeder 在 各种 软件 中显 示出 了比 较 好的性能。随着各种技术的发 展和人 们对分 子生物 学认识 的 深入, 出现了越来越多的其他方法来识别 Motif, 如采用比较 基 因组学来发现在进化过程中 保守的 结合位 点; 考 虑 Motif 之 间 的协同作用而设计的 Motif 模 块识别 方法等。但 是, 目 前还 没 有一种软件能寻找出 所有 正确 的 Motif, 所以 单独 使用 一种 方 法难免出现偏差, 将两种不 同的软 件结合 起来寻 找 Motif 的 性 能将会比单独使用一种软 件高得 多。 另外一 般生物 基因组 序 列均比较长, 程序运行需要 很长时 间, 设计并 行模式 的软件 能 大大提高软件的运行速度。 参考文献: [ 1] ailey TL, Elkan C. Fitting a Mixture Model by Expectation Maximi- zation to Discover Motifs in Biopolymers[ C] . Proc. of the 2nd Inter- national Conf. Int. Sys. Mol. Biol. , 1994. 28- 36. [ 2] Pesole G, Prunella N, Liuni S, et al. Wordup: An Efficient Algo- rithm for Discovering Statistically Significant Patterns in DNA Se- quences[ J] . Nucleic Acids Res. , 1992, 20( 11) : 2871- 2875 . [ 3] Thijs G, Marchal K, Lescot M, et al. A Gibbs Sampling Method to Detect Over-represented Motifs in Upstream Regions of Coexpressed Genes[ J] . Journal of Computational Biology( Special Issue Recomb 2001) , 2001, 9 ( 2) : 447- 464. [ 4] Lawrence CE, Altschul SF, Bogouski MS, et al. Detecting Subtle Se- quence Signals: A Gibbs Sampling Strategy for Multiple Alignment [ J] . Science, 1993 , 262: 208- 214 . [ 5 ] Pavesi G, Mereghetti P, Mauri G, et al. Weeder Web: Discovery of Transcription Factor Binding Sites in a Set of Sequences from Co-regu- lated Genes[ J] . Nucleic Acids Res. , 2004, 32: 199- 203 . [ 6] Tompa M, Li N, Bailey TL, et al. Assessing Computational Tools for the Discovery of Transcription Factor Binding Sites[ J] . Nature Bio- technology, 2005, 23 : 137-144. [ 7] Maximilian Haubler. Motif Discovery in Promoter Sequences [ EB/ OL] . http: / / www. stud. uni-potsdam. de/ % 7 Ehau ssler/ master/ masterthesis. pdf. 作者简介: 朱 骥( 1981- ) , 男 , 江 苏海 安人, 硕士 , 主要 研 究方 向 为并 行 计 算 在生 物 信 息领域 中的 应用; 杨 华, 女, 硕士, 主 要研究 方向为 并行 计算在 生物 信 息 学领域 的应 用; 牛北 方, 男, 硕士, 主 要研究 方向为 并行 计算在 生物 信 息 领域中 的应 用; 郎显 宇, 女, 博士, 主 要研究 方向为 并行 计算在 生物 信 息 领域 中的应 用; 陆忠 华, 女, 博士 后, 主要 研 究 方 向为 生 物 数 学、并 行 算 法; 迟学 斌, 男, 中心 主任, 研究 员 , 博 导, 博 士, 主 要研 究 方 向 为高 性 能 计算 方法与 软件 。