接上一篇 EM method for identifying motifs in unaligned biopolymer sequences,我们接着介绍 Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization 提出的 MEME 算法。
MEME 的基础是 EM。这一篇可以看做 “扩展原有算法” 的典范,而且后面证明 MEME “robust” 的 measurement 和 experiment 也值得学习。
0. Intro
简单说,MEME 解决了 EM 的三个疑难:
- 如何选择 starting point (i.e. $ freq^{(q)} $ 初始值)?
- 对单个特定的 motif 而言,有个 sequence 可能包含两个 motif instances,有的可能一个 instance 也不包含。强制要求 “one sequence one motif (instance)” 会影响算法 performance
- 如何检测多个 motif?
1. 如何选择 starting point
- EM 的做法是:随机构建 $ freq $,然后每一次都跑到 convergence
- MEME 的做法是:选择所有的 $ k $-mer ($ k = LSITE $),按规则构建 $ freq $,然后每一次只跑 1-2 个 iteration,不用跑到 convergence;然后从结果中挑选 likelihood 最大的作为 starting point 再跑一次,这一次跑到 convergence
- 理由是:EM 的收敛速度很快,1-2 个 iteration 的结果已经很好了;然后 motif 要么就在 $ k $-mer 之中(最强之人已在阵中!),要么就是与某个 $ k $-mer 非常接近,所以肯定能逮到一个结果很好的;最后跑一次到 convergence 是为了获取最精确的结果
- 构建 $ freq $ 的规则:
- 比如 $ k $-mer 是
ACT
,你不能直接构建成 $ freq_{A,1} = freq_{C,2} = freq_{T,3} = 1, \, \text{其余全 0} $ - 应该构建成:
-
$ freq_{A,1} = 0.50, \, freq_{A,2} = 0.17, \, freq_{A,3} = 0.17 $
-
$ freq_{C,1} = 0.17, \, freq_{C,2} = 0.50, \, freq_{C,3} = 0.17 $
-
$ freq_{T,1} = 0.17, \, freq_{T,2} = 0.17, \, freq_{T,3} = 0.50 $
-
$ freq_{G,1} = 0.17, \, freq_{G,2} = 0.17, \, freq_{G,3} = 0.17 $
-
- 也不是一定要最大的是 0.5,文章说最大的 $ freq_{l,k} $ 介于 0.4~0.8 效果都不错
- 比如 $ k $-mer 是
2. 0 or 2 instances in one sequence
MEME 对 $ poff $ 的值做了调整,限定单个 sequence 的 $ poff $ 之和 $ \sum_{j}^{L-LSITE+1}poff_{ij} $ 可以大于 1,然后所有 sequence 的 $ poff $ 之和不能大于 $ MAXP $。调整算法在 paper 的最后,Figure 12 和 Figure 13。
$ MAXP $ 理论上应该是 expected number of instances,但是文章后面有论述,4.3 The expected number of motif appearance is not critical
。
这么搞有一个副作用就是:连续的 base 会被识别多次,比如 sequence 是 AAAA
,$ LSITE = 3 $ 的话会被识别成 AAA-
和 -AAA
,所以在调整 $ poff $ 时需要考虑相邻两个位置的 $ poff $ 不能同时大。
3. Multiple Motif
MEME 采取了一种 “erase” 的手段,具体说来就是给每个 $ poff_{ij} $ 配了一个 $ w_{ij} $,表示 “$ S_{ij} $ 不可能作为 motif start 的概率”。
初始 $ w_{ij} = 1 $,第一个 motif 跑完之后,算出了 $ poff $,然后更新 $ w_{ij} = 1 - poff_{ij} $。然后跑第二个 motif 时,最后得出的 $ poff $ 要更新为 $ poff_{ij} := poff_{ij}*w_{ij} $,这样就削弱了上一个 motif 位置的 $ poff_{ij} $。
4. Discussion
discussion 也有几个点值得注意,这里记录一下。
- When MEME is used to discover motifs from sequence data alone, it is performing unsupervised learning. Effectively, MEME finds clusters of similar subsequences in a set of sequences.
- When MEME is used with a dataset of sequences each of which is known to contain a motif, such as the promoter dataset, it is performing supervised learning.
- 注: 可能有点不好理解,因为我们没有用到已知的 $ Y $。但我们的确是像 regression 一样获取到了一个 model 以及 model 的参数
- It may be possible to use the multiple models learned by MEME to passes through the dataset as features for another learning algorithm.
- Another promising idea is to use the short motifs learned by MEME to construct starting points for hidden Markov models.
- The idea of using subsequence-derived starting points may be adaptable for use with HMMs.
- The method used by MEME for probabilistically “erasing” sites after each pass would certainly be easy to add to the standard forward/backward HMM learning algorithm.
- It should also be possible to design a HMM which, like MEME, eliminates the assumption of one motif per sequence.
- It may also be possible to adapt MEME’s innovations to learning stochastic context free grammars for biopolymer concepts.