用智能化算法搜索DNA序列中的微信号.docVIP

毕 业 论 文（设 计）论文（设计）题目：用智能化算法搜索DNA序列中的微信号姓 名 _学 号 _学 院 数学学院 专 业 信息与计算科学 年 级 2007级 指导教师 2011 年 5 月 29 日1山东大学毕业设计（论文）成绩评定表学院： 专业： 年级： 姓 名设计（论文）成绩设计（论文）题目指 导 教 师 评 语评定成绩： 签名： 年 月 日评 阅 人 评 语评定成绩： 签名： 年 月 日答 辩 小 组 评 语答辩成绩： 组长签名： 年 月 日注：设计（论文）成绩=指导教师评定成绩（30%）评阅人评定成绩（30%）答辩成绩（40%）目录摘要1关键词1Abstract2Key words2导论3方法5 （一）经典算法5（1）模体驱动算法5（2）CONSENSUS算法6（3）吉布斯采样算法10（4）MEME算法11 （二）新型算法14（1）WINNOWER算法15（2）SP-STAR算法17总结20致谢21参考文献22附录24 原文24 相关译文27摘 要微信号搜索问题一直是生物信息学中一个基础问题，目前存在着各种关于DNA微信号搜索的经典算法以及理论，但是目前的算法中仍然不存在一个理想的算法，能够在比较高的精度下锁定所要搜寻的模体。如果同时考虑算法的时间复杂度等因素的话，情况就变得更加不容乐观。本文是针对DNA序列中微信号搜索问题中最典型的“挑战问题”，分别分析了经典的模体驱动算法、CONSENSUS 算法、吉布斯采样算法和 MEME 算法的原理，适用的条件以及它们的优缺点，重点用算法复杂度的相关理论分析了这几种经典算法的优点和局限性。本文的重点内容是介绍两种基于组合最优化原理的新型算法WINNOWER算法和SP-STAR算法。其中，着重用相当的篇幅介绍了winnowing原理，与其相对应的WINNOWER算法就是在此基础上，着重使用可扩展集合的概念，逐步缩小被搜索的目标存在的范围，但是如何从最终的集合中查找要得到的信号仍然是一个比较复杂的问题。而SP-STAR算法的亮点就是创造了一个新型的“距离”，与传统的算法中的距离概念在数值上的特性不同，SP-STAR算法中的成对评分函数能够更明显地区分信号模体和随机模体。 对于两种新算法，本文中也简单地涉及了一下它们的延伸情况，主要是初步研究在信号长度未知、存在间隙信号、样本被损坏、信号的核苷酸组成有偏差等情况下，我们如何来完成微信号搜索。 总之，与以前的经典算法相比，建立在组合学基础上的WONNOWER算法和SP-STAR算法是比较成功的搜索DNA微信号的算法，虽然目前仍然存在着一些局限性，这两种算法的高效性是显而易见的。关键词：模体发现，组合最优化，性能评估AbstractMicro-signal-search has been a very fundamental problem in bioinformatics; there are various classic algorithms concerning how to search micro-signal in DNA sequences in the present, in which different theories have been put forward. However, none of these classic algorithms is so ideal that we are able to lock the pattern we are searching for under high accuracy. If we consider such elements as complexity of algorithm, the situation will be not optimistic.This essay analyzes the principles, applicable conditions, strengths and shortcomings of the Pattern Driven Algorithm, CONENSUS Algorithm, Gibbs Sampler Algorithm and MEME Algorithm, aiming at the most typical problem in bioinformatics, the Challenge Problem, of which the focus is to analyze the advantages and limitations of these two classic algorithms with the related theorems of complexity of algorithm.The core of this essay is the two new algorithms based upon combinatorial optimization, the WINNOWER Algorithm and SP-STAR Algorithm, among which a large amount of this essay elaborates the theory of winnowing. The related WINNOWER Algorithm is based on this theory; moreover, the WINNOWER utilizes the concept of extendable clique to narrow the scope of the signal we are searching for. Yet how to find the signal from the final clique is still a complicated problem. The highlight of SP-STAR Algorithm is to create a new “distance”, unlike the numerical characteristics of distance in those classic algorithms; it can better distinguish the signal pattern and random patterns.Whats more, this essay also involves the extensions of these two new algorithms; the main content is how to search the signal in DNA sequences under the following conditions: signal with unknown length, gapped signal, samples with biased nucleotide composition and corrupted samples.In a word, compared with the previous classic algorithms, the WINNOWER and SP-STAR are efficient algorithms used to search micro signals in DNA sequences. Though there are some limitations, the advantages of these two new algorithms are obvious.Key words: pattern discovery, combinatorial optimization, performance evaluation导论在人类历史上，第一个被发现的DNA微信号是1970年由科学家汉密尔顿-史密斯发现的Hind限制性内切酶切割位点，在当时（上世纪70年代），发现一个DNA微信号中的回文序列，并不是一个简单的问题1。据统计，限制性核算内切酶的切割位点是结构比较简单的DNA序列之一，而绝大部分的DNA微信号都是比较复杂的，因此即使我们能够找到高效的算法识别限制性核算内切酶的切割位点，这并不意味着我们在微信号搜索课题上有多大进展。事实上，在这一领域为人所熟知的“挑战问题”仍然是一个亟待解决的问题，尽管“挑战问题”在描述上比较简单，然而用目前存在的各类算法解决“挑战问题”具有相当的难度，即使能够搜索到目标信号，那些经典算法的运行很有可能需要大量的时间资源和计算机内存，其算法复杂度太高，仍然不是很可取。“挑战问题”的详细描述为：一系列的DNA序列构成一个样本，其中每一个DNA序列长度为600个核苷酸，且每一个DNA序列中均含有同一个未知的信号（或者说是一种模体），该信号长度为15，并且有4个不匹配的位置。而普通的信号搜索问题的简要描述是，从一系列的DNA序列构成的样本中搜索一个未知的微信号，该微信号在每个序列的未知位置出现，我们的任务就是搜索到这个微信号。为什么一个描述如此简单的问题解决起来却如此复杂？长度为15，有4个不匹配位置的微信号我们记为(15,4)-signal，按照生物信息学的常识，长度为15的(15,4)-signal与长度为6的(6,0)-signal来信号更加强烈，因而更容易搜索，但是事实却并非如此。原因在于不匹配的位置数目4，突变数目为4，也就是说这个样本中的任意两个DNA序列至多有24=8个位置不匹配，而整个信号的长度为15，高达8/15的突变率造成了大量的杂乱相似，这足以掩盖真实的信号本身，从而导致了微信号搜索的难度加大。经典算法。无论是经典算法还是这里提出的基于组合最优化原理的新型的微信号搜索算法，其最基本的理论在于把在DNA序列中搜索微信号的问题转化为在多部图搜索一个团的问题，比较常见的经典算法有模体驱动算法2,3、CONSENSUS算法4、吉布斯采样算法5,6和MEME算法7。模体驱动算法(Pattern Driven Algorithm)是穷举法（Exhaustive Method）的一种具体应用，首先我们简单介绍一下穷举法。所谓穷举法，顾名思义就是穷举算法，将所有可能为最优解的实例一一列举出来，其优点可想而知，穷举法是最可靠的搜索算法，其准确性不容置疑，但是其缺点也是显而易见的，假如需要搜索的整个集合的规模相当庞大的话，算法运行时需要大量的时间和内存资源，算法复杂度会非常大，这不利于我们真正地解决问题。因此模体驱动算法适用于目标信号的长度非常短的情形，对于长度为l的目标信号，具体操作为搜索所有可能的4l种情形，并采用一种评分策略，给每一种情况评分，然后从这所有的情形中选出最优策略8。一般而言，当信号长度不超过10时，这不失为一种高效的信号搜索算法，然而当长度大于10时，算法复杂度会大幅度增加，从而使这种算法变得不切实际。CONSENSUS算法的主要思想是，假设每条序列只存在一种模体，该算法把定向搜索和含有信息的评价函数结合起来。所谓模体（motif），它的定义为，构成任意一种序列或结构的基本单位，就是指DNA序列中保守的序列片段，它可以分为两类序列模体和结构模体。其中，序列模体（sequence motif）是指通过多联配而获得的相对保守的序列片段；结构模体（structure motif）是指具有某种结构或者功能的有规则的空间结构。吉布斯采样算法（Gibbs Sampler Algorithm）的主要方法是利用概率矩阵表示模体，并采用了随机迭代采样算法的搜索策略，假如我们已知序列中各模体的数目，我们就能找到多个模体。他的局限性类似于模体驱动算法，计算代价大，时间复杂度很高。MEME算法（MEME Algorithm）在某种程度上与吉布斯抽样算法类似，它同样是用概率矩阵表示模体，通过反复使用最大期望算法（Expectation Maximization Algorithm），找出具有最大似然的概率矩阵。本文的重点是重新用组合学的角度思考这个问题。以往的经典算法都是以信号模体为考察的对象来设计方案，捕捉信号的特征然后查找信号；而winnowing原理则着眼于由突变造成的噪声，而不是信号模体本身。基于winnowing原理的WINNOWER算法主要是通过多部图的运算来解决问题。在这里WINNOWER算法定义了团的概念，具体的操作为，首先构造一个图，图中的顶点对应样本序列中的所有的子串，对于子串的构造也有要求，子串的长度和允许的突变数要和所要搜索的的目标信号的长度以及允许突变数保持一致。我们通过不断增加限制条件，剔除图中不一致的边，逐步缩小之前构造出的图，最终收敛到一个团，这样就大大缩减了所要搜索的空间，降低了算法的时间复杂度。下一步就是从最终的团中查找目标信号，一般而言，对于用WINNOWER算法处理过的序列样本，从最终的团中搜寻信号难度已经大大降低，信号搜索问题基本解决，具体方法本文不再赘述。此外，除了常规样本的情况之外，对于WINNOWER算法本文也提出了进一步的拓展，即假如被考察的样本已经损坏，或者样本的核苷酸构成有所偏差的情况，我们可以分别通过在常规情况的基础上，在图中放宽去除边的条件，和用建立在统计学意义上的“距离”来代替原先建立的基于核苷酸组成差异意义上的距离，其他步骤仿照上面的常规情况进行，这样可以进一步解决以上这两种WINNOWER算法的拓展应用情况。我们这提到的第二种算法SP-STAR算法可以说是上文中提到的模体驱动算法的改进，这两种算法有一定的相似之处。鉴于模体驱动算法的不足之处，SP-STAR算法对其进行了一定的改进，模体驱动算法难以从大量的模体中有效地鉴别信号和噪声，SP-STAR算法的优势是对于各种模体，重新定义了一种评分策略和局部改进策略，凭借这两点优势，SP-STAR算法能够比较清晰地区分信号模体和噪声。类似于上面提到的WINNOWER算法的拓展形式，SP-STAR算法也提出了相应的拓展策略，旨在解决样本被损坏和样本的核苷酸组成有偏差的情况。方法 （一）经典算法对于经典的几种微信号搜索算法，这里主要简单地分析一下模体驱动算法、CONSENSUS算法、吉布斯采样算法和MEME算法，找到他们的优势所在和不足之处，以便有针对性地引入两种建立在组合最优化基础之上的新算法WINNOWER算法和SP-STAR算法。（1）模体驱动算法2对于简短的目标信号，模体驱动算法可以说是比较理想的搜索算法，甚至是最理想的算法，因为它的优点比较明显，遍历每一个可能的模体，较高的可靠性是它最大的优点，而缺点也很显然，我们需要对固定长度的每一种核苷酸组成进行检验并且根据这种模体在所有样本中出现的次数对被检验的模体进行评分（或者使用一种更加复杂的函数评分），最终确定得分最高的模体，就是我们要找的目标信号。显然，它的时间复杂度是很高的，运算量也比较大，这是以牺牲时间为代价，换来了比较高的准确率。因此，假如目标信号的长度比较短（我们一般默认为10），如果信号长度不超过10，模体驱动算法是高效的，并且可靠性强，时间复杂度也不是太高。此时它的缺点不容易表现出来，这是最理想的情况。下面我们介绍一下模体驱动算法的具体运行，假设我们的样本中所有序列长度为n，要搜索的目标信号长度为l，其中允许有d个突变位置，这样一个长度为n的序列之中，长度为l的子串最多有n-l+1个。首先我们定义一个概念模体和序列之间的距离d(P,si)，假设一个模体P，样本中的一个序列si，模体P和来自样本的一个序列si之间的距离定义为模体P和序列si中所有子串sij之间的距离的最小值，其中j的取值范围是1jn-l+1。而其中子串sij与模体P的距离d(P,sij)就是长度为l的子串sij与模体P之间核苷酸构成不一致的位置的数量。定义这些概念的最终目的还是定义一个模体P和样本集合S之间的距离接下来的任务就是遍历长度为l的模体所有可能的情况，共4l种可能，我们运行这一步的目标是，在试验的所有4l种可能的模体中，选取一个共有子串P所有字母还是应为斜体.你自己再改一下.，它满足的条件是，在这些试验的模体中，它具有与样本S的最小距离。由此可见，这一步的运算量是相当大的，当l比较大的时候，模体驱动算法就不切实际了。对于这个问题，我们目前的一种比较可行的方法就是，建立一个库，其中包含出现频率比较高的长度较短的模体，在具体应用中，我们将会用这些已知的短模体构建组合成长的模体，来进一步完成长信号搜索问题。除了时间复杂度比较高的缺点之外，上面提到的模体驱动算法还有一个致命的缺点，我们接下来具体分析2。在样本S中取出t个序列s1,st中存在同一个模体P，我们在这里假设已知该模体在上述t个序列中分别表现为P1,Pt。其他步骤与上面提到的模体驱动算法的步骤相同，即从P1,Pt寻找一个共有子串P，满足它与样本S具有最小距离，用公式表示为：。由此可见，算法的成功与否就取决于是否满足：。一般情况下，我们选取的P虽然满足到样本S的距离最小，但是它未必是信号模体的在某个序列中的真正实例，很多情况下，我们通过上述运算选取的很可能是一种随机模体。如果是这种情况，我们经过大规模运算选择的随机模体W和信号没有必然联系。由集合的运算，我们不难看出，这种情况下有:这样随机模体的评分已经超过了信号模体的评分，所以我们会误把随机模体作为我们的目标信号模体，从而遗漏掉真正的目标信号。模体驱动算法的算法描述如下：l 输入： 样本S序列的数据集； 目标模体P长度l；突变位置数目d。l 算法： 在样本S的t个序列中遍历所有长度为l的子串；分别求出各子串与样本集S之间的距离；找出与样本集S距离最小的子串P（共有子串）。l 输出： 共有子串P。（2）CONSENSUS算法9与上面的模体驱动算法不同，CONSENSUS算法采用矩阵表示一种模体，在这个矩阵中，每一行代表一种核苷酸即A，C，G，T四种形式；每一列代表固定长度的模体的一个位置，假如搜寻的模体的长度为L，则这个矩阵为4L形式，至于矩阵中的元素，我们定义为某种核苷酸在该模体的某个位置出现的频率或者说这个核苷酸在某个位置出现的次数10,11,12,13,14,15,16。简单地说，我们的任务就是从这样本集中所有的序列组成的长度和宽度固定的矩阵中找到一个矩阵，它满足在所有可能的矩阵中出现的概率最低，这同时说明这个矩阵的信息量最大，这个矩阵正是我们要寻找的矩阵15。总的来说，CONSENSUS的可靠性随着样本集中样本序列数量的增多而不断提高，同时，CONSENSUS的时间复杂度随着序列数量的增多呈线性增长。与模体驱动算法类似，CONSENSUS的前提假设条件同样是给定一系列N个序列组成的样本集，这其中的N个序列含有功能相关的子序列，我们要通过4L矩阵的运算找到这个子序列，也就是目标信号模体。下面我们详细介绍一下CONSENSUS算法的具体运行过程。在算法运行之前，我们必须给出目标信号的长度，这个问题目前无法通过算法计算得出准确值，只能凭借与该问题相关的生物化学常识给出，尽管直接求出一个未知信号的长度的准确值不切实际，但是我们可以通过在一定的范围内尝试一系列的长度值来试验得出17。为了更好的介绍CONSENSUS 算法，我们首先了解一个可靠但是不切实际的算法，也就是说它的时间复杂度比较高。首先给定一个L长度值，从样本集S的所有序列中，尝试每一个长度为L的子序列，同时表示出与这个子序列相应的4L矩阵，关于该矩阵的构建过程请参考文章本部分第一段，构造的所有矩阵中，出现概率最低的矩阵很可能就是我们寻找的矩阵。然而，假如样本S中的所有序列长度为M，则每一个序列可产生（M-L+1）种情况，在构造矩阵的过程中，我们需要对其中填充元素，因此必须通过多个子序列计算某个位置的每个核苷酸出现的次数，这时需要对每一个序列中选出的子序列进行统计处理，一共N个样本序列，我们需要构造出(M-L+1)N个矩阵，其运算量之大可想而知。因此为了避免这种巨大的时间以及内存的开支，我们做了以下处理：在扫描样本序列所有长度为L的子序列的过程中，我们仅保留我们感兴趣的子序列，这样可以删去那些不必要的操作。CONSENSUS算法的具体步骤是，首先构造一系列初始的矩阵，即只有第一个样本序列中长度为L的子序列组成的4L矩阵。举个例子可以更好的理解这个算法，例如下列由3个序列组成的样本： 首先考察第一个序列ACTGAAT，如果我们要寻找的信号长度为6的话，第一个序列中有两个可能是信号模体的子序列，也就是ACTGAA和CTGAAT。针对这两个子序列，我们构造两个矩阵：同样，样本集合中第二个序列 AGCGTCC 也可以产生两个长度为6的子序列，分别为AGCGTC和GCGTCC。下一步，将第二个序列产生的两个序列叠加到上面构造的两个矩阵的行上，矩阵的元素同样是定义为AGCT四种核苷酸在两个叠加的序列中出现的次数，于是得到如下四个矩阵（共两组）：在上面产生的4个矩阵中，我们分别在每一组矩阵中选取一个信息量 I 较大的矩阵，接着进行下一步运算，信息量 I 较小的两个矩阵舍弃掉，关于信息量 I 的计算将在后面详细介绍。接下来的步骤仿照以上所述，再将第三个序列CTTGCCG叠加到上面选取的两个矩阵中，同样产生四个矩阵如下：同样，我们在每一组中根据信息量 I 的数值舍弃信息量较小的两个矩阵，得到如下矩阵：此时，样本集中的三个序列都已经叠加到矩阵中了，我们最终从保留下来的两个矩阵中选取信息量 I 较优的一个，得到矩阵：最终得到的这个矩阵，它具有最大的信息量，正是我们所寻找的共有序列对应的矩阵17。另外，关于信息量 I，它的定义为：其中：1. b 代表矩阵的行，也就是四种核苷酸ACGT；2. i 表示矩阵的列，即我们搜索的目标信号序列的L个位置；3. Pb 表示核苷酸b出现的基因组频率；4. L 表示矩阵的列数，也就是目标信号的长度；5. N 表示矩阵中叠加的序列的个数。对于一个固定的N值，一个矩阵的信息量越高，这个矩阵对应的模体偶然出现的概率就越低。总的来说，CONSENSUS是通过寻求最大信息量来确定共有模体对应的矩阵的一种算法，在具体运行过程中，样本集中序列的数量和所需内存是相互独立的，内存只与算法运行的第一个样本序列呈线性关系。随着序列数据量得不断增长，在已知少量的生物数据或者生化数据的条件下，用一种简单地方式来确定一种共有模体是非常重要的，这是CONSENSUS的优势所在。CONSENSUS的算法描述如下：l 输入： 样本序列的数据集 目标模体的长度l 算法： 为第一个样本序列产生的子序列分别构造一个4L矩阵（每个矩阵为一组）； 把第二个样本序列产生的子序列分别叠加到上述每一组矩阵中； 计算每个矩阵的信息量； 在每一组中选出一个信息量比较大的矩阵； 把第三个样本序列产生的子序列叠加到筛选出的矩阵中； 仿照上述步骤依次运算下去直至把最后一个样本序列叠加到矩阵中； 从最终的所有矩阵中选取信息量最大的一个矩阵。l 输出： 共有序列矩阵； 信息量。（3）吉布斯采样算法5目前，通过基因工程和蛋白质工程获取的大量的生物信息数据需要进一步解密，解密序列以及解释序列之间的关系主要的障碍就是搜索局部残留模体。这些模体频繁地反映出相似的分子结构和生物学特性，力图解决上述局部残留模体问题的一种数学算法在计算机中设计为一种自动运行程序，从而逐步发展成为一种新奇、灵敏的吉布斯采样算法。它以统计学中的反复抽样为数学理论基础，这种算法能够为N条序列找到一个局部最优匹配模型，所需时间与N呈线性关系。总体而言，与其他的经典算法相比，吉布斯采样算法是比较高效准确的算法，它的主要优势在于把统计学的最新进展理论成果融合到了信号搜索问题的公理化模型中。同样，吉布斯采样算法的目标是锁定和描述隐藏在一系列生物聚合物序列之中的模体。吉布斯采样算法的模型具有三个特性：第一，我们寻找的模体规模比较小，也就是我们所谓的微信号；第二，目标信号的每一个位置都是用一个关于残留频率的概率模型描述；第三，目标信号模体在每一个序列中的位置是用基于概率的位置变量来表示18。这几条原则，对于大多数的蛋白质家族是有效的，不过我们不排除少量反例的存在。我们这里用的优选过程是吉布斯采样算法的预测更新版本，以反复抽样为基础的策略发挥了重要作用，吉布斯采样算法可以说是最大期望算法的一种类似的随机方法。吉布斯采样算法的假设类似于上面讲到的两种算法，给定N条样本序列：S1，SN。我们在每一条序列中搜寻彼此类似的长度为W的片段序列。这个算法始终运用了两个数据结构：第一个就是模体描述，它为从1到W的每一个位置i建立一个基于残留频率的概率模型，对于每一个i值，我们用20个变量qi,1,，qi,20来描述，这种模体描述的每一个变量同时伴随着另一种类似的概率描述，叫做“背景频率”p1,p20；另一种数据结构是一系列的位置ak，其中k取值从1到N，用来描述N个序列中的共有模体，我们要做的就是寻找一个“最有可能的”共有模体，具体实现为锁定一个子序列，它能满足使子序列对应模体的概率与背景概率的比值最大。该算法的第一步是从不同的序列中随机选取一个起始位置，接下来反复运行吉布斯采样算法的下列两个步骤：1. 预测更新阶段。我们首先从N个序列中选取一个序列z，该选择可以是随机选取，也可以是按照某个特定的顺序选取。然后，排除序列z，计算除序列z之外的所有其他序列所对应的ak的模体描述qi,j和背景频率p1。2. 抽样阶段。序列z中的每一个长度为W的序列片段，都是我们要搜寻的信号模体的一种可能实例。我们接下来需根据目前的模体描述qi,j计算产生片段x的概率Qx；同理，根据目前的背景描述计算产生每一个片段x的概率Px。然后，由Qx和Px计算权重Ax=Qx/Px，并把权重Ax附加给片段x。当每一个片段附加权重后，我们再从中选取一个权重最大的片段，它的位置则用来作为新的az。这个简洁的反复运行算法构成了吉布斯抽样算法的基本内容，它的中心思想是，第一步中模体描述越精确，第二步中锁定的位置就越准确，反之亦然。这样我们得到的位置序列会最终收敛于目标模体的位置。吉布斯采样算法的算法描述如下：l 输入： 样本序列的数据集； 目标模体的长度W。l 算法： 从样本集N个序列中选取序列z； 计算除序列z之外的所有其他序列所对应的ak的模体描述qi,j和背景频率p1；根据目前的模体描述qi,j计算产生片段x的概率Qx； 根据目前的背景描述计算产生每一个片段x的概率Px； 计算权重Ax=Qx/Px； 把权重Ax附加给片段x；从z的所有片段中选取一个权重最大的片段，它的位置则用来作为新的az； 重复上述过程直至片段收敛到一个模。l 输出： 最终收敛到得片段（即我们搜索的模体）。（4）MEME算法7MEME算法可以看作是最大期望算法（EM算法）在生物聚合物（例如DNA，RNA或者蛋白质，等等）中搜索模体具体应用的一个延伸情况。MEME算法的目标是在已知少量信息或者所有信息都未知的情况下，从一组生物聚合物分子序列中锁定一个未知的模体。MEME算法在最大期望算法的基础上将所能解决的问题范围进行了一定的拓展，同时也提高了算法运行的成功率。最大期望算法是使用样本序列中的子串来初始化算法，以便顺利地得到全局最优解。与最大期望算法相比，我们去掉了每个序列有且仅有目标模体的一个实例这个前提，这一特性使MEME算法允许同一个模体在一个序列中多次出现，并且在算法运行过程中剔除了那些不包含该模体实例的序列，进一步提高了算法对于噪声的抗干扰能力。在具体运行的过程中，MEME算法会逐步地删除那些已经发现的模体在各个序列中的实例，这样，我们就能够按照一定次序逐步地锁定样本序列集中的每一个模体，当然这里我们只考虑连续的模体，也就是说这里的突变我们专指核苷酸或者氨基酸的替换，而不考虑插入和删除这两种情况。该问题的简化版本可以这么描述：已知一系列生物聚合物序列构成的数据集，每一条序列被认为是含有一个共同的模体，我们的任务是在每一条序列中找到这个共同的模体在该序列中的实例。而MEME算法是最大期望算法在解决这个简单问题的基础上的适当提高情形，我们能够利用MEME算法搜索存在于一系列样本序列之中的多重信号，除此之外，它不需要已知模体的主要信息，例如长度、核苷酸的出现频率和它的具体实例出现的位置。鉴于MEME算法和最大期望算法之间的密切联系，我们不妨介绍一下最大期望算法的具体理论。类似于上述几种经典算法，最大期望算法运行的前提条件是已知样本序列的基本信息和目标模体的长度LSITE，我们最终得到的是目标模体的一个概率模型。它所依据的理论是，样本集中的每一个序列都含有同一个模体的各种实例，当然我们事先不知道每个实例所在的位置。事实上，假设目标模体的每一个实例都是由一系列相互独立的随机变量来给出，则根据极大似然估计的理论，我们不难看出我们观察到的序列的每一个字母（核苷酸或者氨基酸）出现的频率是出现概率最大的情况，因此我们可以通过随机变量的调整使其达到最大值。为了更加具体地描述这个问题，我们用变量poffij来描述目标模体在第i个序列的第j个位置出现的概率，用freqlc来描述字母表中第l个字母在模体的第c个位置出现的频率（1cLSITE）。运行最大期望算法，我们必须事先给出一个freqlc的初始值，然后我们使用了一个循环算法，利用freq的初始值根据贝叶斯定理估计变量poff的值粗体的使用要一致。再利用刚刚计算得到的poff值来重新计算freq的值，这两部可作为一个循环体，执行循环。当然对于一个循环结构的算法，必须给定一个条件来终止循环，这个条件就是值，我们规定当freq的变化不超过值时，终止循环。在这里，我们用freq来表示freqlc构成的矩阵，同理可得矩阵poff的数学意义。最大期望算法的最终运算结果是一个概率矩阵，它对应着一个模体，我们最后得到的具体信息是字母表中的各种字母在该目标模体的每个位置出现的概率。然而，我们也不难发现最大期望算法的诸多局限性，即：1. 关于如何选取初始点、计算初始值，最大期望算法没有具体给出算法，因此它所使用的是一种比较被动的方法；2. 最大期望算法假设每一个样本序列中有且仅有目标模体的一个实例，这就直接排除了一个模体在一个序列中含有多个实例以及某个序列不含该模体的实例的情况；3. 最大期望算法假设我们给出的样本序列集中只含有一个模体，因此它无法解决多重模体的模体搜索问题和模体序列中存在插入和删减的情况。上述局限使得最大期望算法对于噪声的抗干扰能力比较弱，而这里着重介绍的MEME算法就是专门针对最大期望算法的这些缺点而构造的一种算法。MEME算法可以说是最大期望算法的修正版，运行MEME算法我们需要输入样本序列的数据集和每一个目标模体的长度LSITE以及模体的数量PASSES。与最大期望算法不同，在这里我们是严格给出运行最大期望算法的循环次数NITER的，这就节省了相当的时间资源，它将作为算法的一个输入变量。最后还有每一个模体在样本序列中出现的次数MAXP。在MEME算法中，算法的初始值并不是随机给出的，而是源于样本序列中实际存在的子序列。每当我们搜索到一个模体后，它的所有实例会从样本序列中删除，以便进行下一步的搜索。对于每一个目标模体，我们按照一定的运行次序来执行以下操作：对于样本数据集中的每一个子序列，我们都可以构建一个概率模型，我们对每一个模型执行NITER次最大期望循环算法，然后在基于不同初始值的运行结果中利用极大似然原理选取一个出现概率最高的模型。每个模型出现的概率我们用似然函数的对数形式来描述：完成上述操作后，我们对这个选取的模型再次利用它的初始值运行最大期望算法直至其收敛，它收敛到的那个概率模型对应的就是一个目标模体。执行完这一步之后，我们把搜到的这个模体的所有实例从样本中删除，然后进入下一个模体的搜索。与最大期望算法相比，MEME算法的优势比较明显：1. 从样本的子序列集合中产生的初始值和它的概率模型与目标模体具有一定联系，可以避免一些不必要的运算，克服了算法的盲目性；2. 找到一个模体之后将它的相关实例及时删除，有利于高效地进行下一个模体的搜索；3. 对于样本产生的噪声具有更强的抗干扰能力。但是，MEME算法的局限性不得不重视，同其他经典算法一样，它还是建立在概率模型的基础之上，随机性不可避免。最大期望算法的算法描述如下：l 输入： 样本序列数据集； 目标模体的长度LSITE。l 算法： 选定freq的初始值； 执行循环 利用贝叶斯定理通过freq的数值来估计poff的数值； 通过poff的数值重新估计freq的数值； 直到freq的波动不超过值。l 输出： 目标模体的概率模型（freq和poff）。MEME算法的算法描述如下：l 输入： 样本序列数据集； 目标模体的数量PASSES； 最大期望算法的循环次数NITER； 每个模体在样本序列中的实例的个数MAXP。l 算法： 对于每一个目标模体执行以下循环 对样本序列中的每一个子串执行循环 以该子串生成的初始值为起点执行NITER次最大期望循环算法； 从上数子串产生的模型中选取一个出现概率最高的模型；对选取的这个模型的初始值执行最大期望算法直至其收敛；获得这个模体的最终概率模型（freq和poff）；清除已经发现的模体在样本序列中的所有实例；l 输出： 所有模体的概率模型（freq和poff）。（二）新型算法以上便是在DNA序列或者蛋白质序列等生物大分子聚合物中搜索目标模体的经典算法。其中，每个算法都具有各自适用的条件，模体驱动算法2,3作为穷举法的一种具体形式，适合在目标信号长度较短的情况下运行；与模体驱动算法相比，CONSENSUS4在它的基础上已经大大降低了时间复杂度，CONSENSUS利用矩阵表示一个子序列（或者说一种模体），在运行的过程中，不断删减信息量较低的矩阵，避免了无效的运算，在算法上有所改进；吉布斯采样算法5,6则充分利用了统计学的相关理论，采用逐步逼近取样的方法，最终收敛到目标模体，可以说吉布斯采样算法最大的优点就是所需内存小，几乎只需存储输入的样本集的序列数据，不需额外开支，但是它的缺点也是很明显的，吉布斯采样算法可以说是专门针对最优化问题的算法，除此之外，应用的场合很少，该算法的适应能力较差；MEME算法7与吉布斯采样算法可以说是“同源算法”，这两种算法都是建立在一定的概率模型基础上，作为最大期望算法的修正版，MEME算法的抗干扰能力已经显著增强，但是这仍然不能摆脱MEME算法固有的缺点，它所依靠的是一个概率模型。下面我们重点介绍两种新型算法WINNOWER算法和SP-STAR算法，它以组合数学为基础，克服了前面提到的经典算法的一些缺点，在生物信息学领域将会发挥重要作用。（1）WINNOWER算法2WINNOWER算法的理论依据，就是winnowing原理，但是它的不同之处在于WINNOWER算法在winnowing原理的基础上，克服了它的一些不足之处，进行了适当的改进，首先我们先介绍一下winnowing原理的重点理论。winnowing原理处理的样本情况类似于上述经典算法，即给定样本集S=s1,，st，每个序列长度相同，为n个核苷酸的长度，每一个序列的未知位置都含有同一个未知信号(l,d)-signal，其中l为信号的长度，d为信号的突变数。t个序列总共可以产生种双序列比对，然而对于一个搜索信号(15,4)-signal的挑战问题，它产生的所有双序列比对中仅有少量的实例是与信号模体一致的，绝大多数的是噪声。就经典算法而言，无论是CONSENSUS还是模体驱动算法，传统的经典算法都是力图从大量的噪声中搜寻少量的与信号模体一致的实例，与之不同的是，winnowing原理着眼于噪声，而不是信号本身，这一独特的研究角度将挑战问题大大简化，因为winnowing原理把从大规模的噪声组成的集合中搜索信号这一难题转化为图的缩减问题。另外，为了更形象地分析挑战问题，我们用一种简化的几何框架来描述挑战问题，具体内容为：考察一个t维空间中的一个整点(p1,pt)，其中它的每一个坐标pi是未知的，但是我们可以通过观察得到这个整点在每一个二维空间中的投影(pi,pj)，其中1ijt。假设我们仍然无法辨别那些代表信号的投影和代表噪声的投影，winnowing原理就是用着已知的个投影重新构建这个整点19。挑战问题中的目标信号的双序列比对隐藏在大约20,000个噪声中，直接从中查找信号，其运算量相当巨大。但是，在双序列比对产生的个点中，信号模体对应的点之间是互相一致的，噪声对应的点不一致。凭借这个规律，我们虽然不能过滤掉所有的噪声，但是可以过滤掉其中的大部分。下面的WINNOWER算法调整了winnowing原理，使它更适用于搜索微信号。WINNOWER算法是利用图这种数据结构来运行的算法，给定样本集S=s1,，st，和目标信号长度l和信号的突变数d。首先按照如下方法构建一个图，为序列si的第j个位置构建一个顶点，它代表si中长度为l起点为j的子序列sij。当然这里j的取值范围是1jn-l+1。我们做如下规定，假如子序列sij和spq满足ip并且两个子序列之间的距离不超过d（d的定义和上文中模体驱动算法中距离的定义相同）。WINNOWER算法中使用了团的概念，所谓团，就是指一组顶点组成的集合，它们中任何两点之间都有一边相连。在样本集S中一个(l,d)-signal信号产生的任何两个实例对应于图G(S,l,2d)中的一条边，因此任何一个信号(l,d)-signal对应着图G(S,l,2d)中规模为t的一个团，这样就把信号搜索问题简化为在一个在图中搜索团的问题。一般情况下，在图中搜索一个团是个复杂问题，但是在这里我们将通过删减边的方法来逼近一个团，这样大大降低了算法的复杂度。另外，WINNOWER算法引入了扩展团，如果一个团在图G的每一个部分都至少有一个邻点，则称这个团是可扩展的，或者称这个团为扩展团。对于一个顶点u来说，如果C=v1,，vk是图G中的一个团，并且v1,，vk,u也是图G中的一个团，则称顶点u为团C的一个邻点。一条边如果满足，它不属于任何一个规模为k的扩展团，则称这条边为伪边。我们的任务就是把图G的伪边删除，来逼近目标信号所在的团，然而只用扩展团这个限制来剔除伪边这种方法在k2情况下非常弱，以至于图G的不能快速收敛到一个团，因此我们必须使用更严格的约束条件。我们观察到，图G中的规模为t的任何一条边至少属于个规模为k的扩展团。这个规律有助于我们用更加严格的条件过滤多部图中不一致的的边，例如，一条边如果仅仅包含于少于个规模为k的扩展团，我们就删除这条边。如果令k=3，则所属的规模为3