陈昆

摘 要 在生物信息学中，录因子结合位点与转录因子相互作用调控基因的转录过程。对转录因子结合位点的识别，是生物信息学的核心问题之一，简称为模体识别。如何高效完成模体识别对理解调控转录机制，建立调控转录模式有着重要的意义。本文重点描述了对转录因子结合位点识别研究的历程、近年来业界普遍采用的三类模体识别的研究方法、以及对其中各类具有典型特种的多种主流模体识别算法做出分析，初步形成整体脉络，并对下一代转录因子结合位点识别问题提出了观点。

【关键词】转录因子结合位点 计算机技术

近年来随着基因组计划的执行，海量的基因序列原始数据被发现。为了阐述数据的生物意义，数学、计算机学等学科被广泛结合运用，在研究过程中决定基因在生命工程中意义的基因表达就成了生物信息学主要的研究课题之一。基因表达是指基因在生物体内的转录、剪接、翻译以及转变成有生命意义的蛋白质分子的过程。

其中转录调控是基因表达的关键步骤，调控基因转录是由转录因子通过特异性结合调控区域的DNA序列来完成的，转录因子结合位点是与转录因子结合的长度通常在5～20 bp范围内的短小DNA片断，一个转录因子往往同时调控若干个基因，而它在不同基因上的结合位点具有一定的保守性，但又不完全相同。对经过生物实验验证的已知位点进行分析可知，转录因子结合位点往往是在相关基因序列中具有保守性，可以表现出特定的模式，所以也被称作模体。与其它常见的序列模体信号相比，转录因子结合位点模体除了长度较短以外，其碱基组成也更加灵活，容许较多的变体。识别转录因子结合位点模体问题在业内通常简化成为模体识别。

解决模体识别问题，需要运用生物学、数学和计算机学等学科的综合研究成果，在数学和计算机学的作用下，模体识别可以形象的认为是在庞杂的复杂的背景信号中找到具有相对保守性的微小特征信号的模型。

而这类微小特征信号因为模体的片段较短，而较短的序列在规模较大基因组中重复出现的次数很多， 另外模体又现实存在一定的模体变体， 这使得背景中的噪音信号对所关注的信号有着很大的干扰，减少这种干扰就是模体识别问题的难点

1 模体的表示方法

在生物信息学领域，通常用三种模型来表现模体。分别是：一致序列（Consensus）模型、权值矩阵模型（Weight Matrix Model， WMM）、可视化模型。

1.1 一致序列（Consensus）模型

一致序列模型是指取各个模体实例中同一位置出现次数最多的碱基作为一致序列该位置的碱基，这样组成的序列就被称作一致序列。这样一致序列模型是对模体的一种大致性表示，一致序列模型的结果并不一定存在于被表示DNA序列中。以表1作为例子来说明：

1.2 权值矩阵模型

由一致序列模型表示的模体除了简单直观在精确性上与实际要求相差很远，随着算法的发展，人们发现用权值矩阵矩阵更能表现出模体的特性。

矩阵的行代表了不同的碱基，矩阵的列代表了碱基序列的位置。假设该矩阵为 W， 那么 W（i，j）表示第 i 个碱基在碱基位置 j 出现的概率。以上表为例可以得出矩阵W（4，5），如图1所示。

可以在权值矩阵模型下用似然函数来评价生物序列模体的保守程度。

1.3 可视化模型

logo模型是可视化模型的典型代表，它依据信息论用形象直观的图形方式来表示结合位点的特征。

在logo模型中，每个位上的值是所有在该位置上出现的碱基叠加生成，该位置上值的高度等于该位置上碱基出现的信息量之和，该位置上碱基的排列按照信息量的大小从上向下排列。例如我们把已在真实数据库公布的模体用logo模型表示，如图2。

logo模型可以用直观图形地表示出结合位点的保守度，以及碱基在具体位置上的分布和影响。

2 转录因子结合位点识别研究历程

根据转录因子结合位点在相关基因序列中的保守性，近年来人们开发了很多识别它们的算法。

较直观使用的研究主要是基于字串枚举的方法 ，其原理是：在给定的共表达基因上游区域中，模体序列的出现频率比其背景序列片段现的频率要高。因此，通过穷尽列举输入序列中所有可能的候选模体，计算出每个候选模体的实际现次数与其期望出现次数进行比较衡量，选择具有显著统计特性的候选模体。

其中1984年Helden等人提出的Oligo-analysis方法；1992年 Pesole等人提出的模式驱动列举（WordUp ） ；这两种方法虽然简单直观但有两个明显的不足：时间复杂度高、仅适用于模体较小的情况，同时不能允许模体出现变体。接着，Helden对Oligo-analysis进行了扩展，2000年提出了dyad-analysis算法。该方法对两端保守的模体识别率较高， 但当模体保守区域长度定义后，搜索到的模体不能有变化，两端保守区域也不能有变体的存在，因此只能应用于某些特定结构的模体识别。

2002年，Sinha，S等人提出了YMF法，即基于三阶马尔科夫链的简单穷举法。与之前算法不同，YMF可以用于预测的模体种类较多，但仍然有着枚举法的通用弱点--如果模体较长则时间复杂度变得很差，识别精度也降低很快。为了能够对结果更复杂，特征不明显的较长（十几至几十碱基）模体进行识别，2002年Eskin和Pevner提出了前缀树法（Mitra）使用前缀树描述搜索空间，通过分割搜索空间，删除弱表达子空间，修剪完成后获得的树中各路径即是显著性模体。这种方法可以有效地减少搜索空间，能够搜索较长的模体和组合型模体，缺点是模体长度需要预先设定，搜索空间较大。随后在MITRA基础上，Pavesi等人提出了后缀树法（Weeder）方法。Weeder法对候选模体集并不是通过直接修剪搜索空间来获得最终结果，而是通过对各候选模体在序列中实际现判定条件的严格限制，减少符合设定条件的模体数来得到。和Mitra方法相比Weeder方法不需要对模体长度进行预先设定。endprint

在直观的基于字串枚举方法发展的同时，其他领域取得进展的算法也在不停地被借鉴到模体识别问题中来。基于局部搜索的算法渐渐成为主流。此类算法是首先构建一个模体的初始模型，例如相似度矩阵模型，然后对该模型在每次迭代中进行相应的调整，使其更接近真实的模体。经过数次的迭代后，该模型最终收敛到一个局部最优解。

其中：1990年La wrence等提出用EM 算法来解模体识别，但是它只能识别一个模体类型。于是在1995年Bailey和Elkan提出了改进了的EM算法--ME ME算法， 通过拟合一个二元混合模型 ，优化EM算法的初值来识别一个或多个模体的类型 。1999 年 ， Hertz结合贪婪算法和E M算法编写了CONSENSUS。 由于EM 算法常会陷入局部最优解，在1993年La wrence等率先把吉布斯采样法引入模体识别领域，吉布斯采样算法是一种特殊的马尔柯夫链蒙特卡罗方法。此后又现了很多基于吉布斯采样算法的模体识别算法。如今已经成为应用最广最成功的motif识别方法之一。

2000年，Pevzver和Sze 提出了植入（l，d）-motif模型，这具有里程碑的意义，i因为以上各个方法都不能完全解答这个模型，需要寻找一个全面系统的同时能够展示出基因序列间的拓扑结构、联系、功能及进化的模型。 这样就把早在1969年Kau ffman就利用布尔关系构建了那个原始的具有猜测性质的基因网络，具现到（l，d）-模体识别这个问题上了。同时图论的思想也被大量引入到模体识别领域。

3 转录因子结合位点识别算法的分类

根据识别策略和搜索对象的不同，模体识别算法大致可分为三类：

第一类是de novo模体识别算法，该类算法是在没有转录因子及其结合位点的先验信息的情况下，完全依靠计算方法在一系列共表达或者共调控基因的上游区域中识别未知模体；我们在第2章转录因子结合位点识别研究历程中所介绍的算法均属于这一类。

第二类是结合ChIP-chip等高通量实验数据的预测算法；这种方法非常高效，以至于业内称之为下一代模体识别算法。

第三类是系统发育足迹分析法（Phylogenetic Footprinting），该类算法通过比较不同物种的DNA序列来搜索在多个物种之间保守的模体。

下面分别对上述三类算法进行具体介绍：

3.1 de novo模体识别算法

de novo模体识别算法是指以一组共调控的基因作为输入，用计算的方法查找在这些基因的上游调控序列中富集的模体。从策略上分可细分为穷举型和比对型。在上一章中所介绍的Oligo-analysis方法、模式驱动方法、dyad-analysis方法、YMF方法、Mitra方法和Weeder方法等等均属于穷举型；而EM方法、MEME方法、吉布斯采样方法引申出的各种方法等等均为比对型。

两种方法各有优势也各有弱点，穷举法的弱点是所识别模体不可过长，否则耗费时间过长，比对法的弱点是容易陷入局部最优解。同时由于de novo模体识别算法依赖共调控信息使得二者都局限于只能对单物种进行识别。

de novo模体识别算法一直以来都是模体识别领域的主要组成，各种经典算法层出不穷，是这一领域的核心研究力量，近几年来图论和聚类算法的进入，又给此类算法带来新的活力。同时由此类算法向下一代算法引申变化以期更好解决模体识别问题的研究也一直在进行中。

比如我们接下来介绍的基于染色质免疫共沉淀技术的ChIP-seq算法。有很多方法是源自de novo算法。另外侧重进化层面的系统发育足迹分析法也大量借鉴了de novo算法的思想。

3.2 基于染色质免疫共沉淀技术的ChIP-seq算法

染色质免疫共沉淀技术（ChIP）的出现带来了基因技术上的革命，CHIP-chip技术是ChIP技术和基因芯片技术的结合，带来了大量的调控实验数据，它可以间接确定DNA序列与转录因子结合与否，以及结合的强度。ChIP-chip技术的分辨率在800bp左右，远大于转录因子结合位点的长度，这样就需要算法对其进行进一步的加工，在ChIP-tiling利用叠片式芯片进一步增加了基因组的覆盖率。将ChIP与第二代测序技术相结合的ChIP-Seq技术，能够高效地在全基因组范围内检测与组蛋白、转录因子等互作的DNA区段。ChIP-seq

技术的分辨率可以达到100bp甚至更高。

ChIP-Seq算法是这样工作的：首先将测序得到的短序列片段匹配到参考基因组序列上；考虑到有一部分短序列不能匹配到参考基因组上，有可能是未知的基因组序列；另一部分是能够匹配到基因组上的短序列，通常要对这些段序列进行覆盖度计算；继而从匹配到基因组上的短序列中进行富集区域的扫描。通常扫描到的富集区即被认为是蛋白质与DNA相互结合的区域。此时已得到我们所关注的结果，至于将计算数据转变为真实数据库数据则是另一层面的问题。

和以往的de novo模体识别算法不同的是，以往的算法面对的是长度普遍在以千为数量级的，同源条数以几十以内的序列数据，而ChIP-Seq算法面对的是长度为100左右而条数以十万为数量级的序列数据，这样以往的算法就没法照搬使用，针对这种情况，MEME算法、吉布斯采样算法等经典算法均做出了相应的调整，形成了对ChIP技术的新变化。同时模式驱动和聚类求精之类的算法在ChIP技术的要求下形成了新型的算法...多种算法的形成不胜枚举，在近一、两年几乎每天都有突破。可以说ChIP-Seq算法的下一代模体识别算法的地位已经奠定。

3.3 系统发育足迹分析法

随着测序技术的发展，越来越多的基因组被测序，系统发育足迹分析法在转

录因子结合位点预测中变得越来越重要。它的基本假设是，转录因子结合位点有调控功能，在进化中应该相对保守，进化速度要慢于其它没有功能的非编码序列，因此预测转录因子结合位点就是搜索同源基因在多个物种中的对应基因序列上的保守模体。endprint

2003年， Kellis、Cliften分别用此方法在酵母属基因组中找到保守的模体， 2007 年，Kheradpour等对12个果蝇属物种的全基因组进行比较分析， 预测出若干保守模体存在于ChIP-Seq算法预测的有效富集区。均取得相应的成果。

大部分此类算法思想是将共调控和进化上保守两种因素综合起来，在de novo 预测算法的基础上开发的，同时研究者将刻画物种间进化关系的进化树以及进化距离等信息都添加到预测算法中，作为算法调控机制。以增加算法准确率。其结果可以通过特定的ChIP-Seq算法验证。

和前两种算法不同，系统发育足迹分析法面对在更宏观背景下的模体识别问题，de novo算法与ChIP-Seq算法的每次进步总是要对其产生促进，同时它的发展也对前两者提供了验证信息和新的思路。最终生物信息学对生命的解读将由这三类甚至更多、更新层级方法共同完成。

4 总结

可以看出转录因子结合位点识别研究历经简单枚举、局部搜索、网络模型、 与DNA芯片技术结合、与物种进化结合等等过程，逐步形成了研究体系，各个过程中间不是简单的技术换代，而是在新的技术条件下各种经典的方法的延伸和发展。也就是说我们不能简单地认为局部搜索就优于枚举，或是ChIP-Seq算法优于de novo算法等等，它们各阶段的发展都是对彼此的促进。在相互促进融合的过程中，新的更适合当下技术条件的算法会逐步被人们发现。只有通过各种数据的融合和相互校正，才能挖掘出可靠的转录因子结合位点和它对DNA序列转录调控关系。

通过对各类算法的分析，可以看出今后一个阶段的研究仍是围绕着减少序列背景中的噪音信号对所关注的模体信号的干扰，以及提高算法的时间效率来进行的，新的实验技术和更多的同源序列信息被发现，必将带来更高效的转录因子结合位点识别算法。

参考文献

[1]Patrik D'haeseleer，How does DNA sequence motif discovery work？ Nature biotechnology volume 24 number 8 August 2006.

[2]Helden etc，Extracting regul atory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies. Journal of Mol ecular Biology， 1984， 281（5）：527-842.

[3]Pesole etc，WORDUP：an efficient al gorithm for discovering statistically significant patterns in DNA sequences.Nucleic Acids Research， 1992，20（11）：2871-2875.

[4]Helden etc，Discovering regulatory elements in non-coding sequences by analysis of spaced dyads.Nucl eic Acids Research，2000，28（8）：1808-1818.

[5]Sinha，ect，Discovery of novel transcri ption factor binding sites by statistical overrespresentation. Nucleic Acids Research，2002， 30（24）：5549-5560.

[6] Pavesi，G.，Mauri，G.ect Analgori thm for finding signals of unknown length in DNA sequences.Bi oinformat i cs，2002，17（1）：207-214.

[7]Bailey，T.，L.and El kan，C.Fitting a mixture model by expectation maximizat i on to discover motifs in Bopolmers.Proc.of the 2th International Conference on Intelligent Systems for Molecular Biology，1994，pp28-36.

[8]Bailey ect，Unsupervised learning of multiple motifs in biopolymers using expectation maximization. Machine Learning.1995，21（1-2）：51-80.

[9]Lawrence ect，Detecting subtle sequence signals：a gibbs samling strategy for multiple alignment. Science.1993，262：208-218.

[10]Pevzner PA，Sze SH（2000） Combinatorial approaches to finding subtle signals in DNA sequences. In： Altman R，Bailey TL，eds.Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology.California：AAAI Press.269-278.

[11]Ren B，Robert F，ect Genome-wide location and function of DNA binding proteins.Science，2000，290（5500）： 2306-2309.

[12]Johnson DS ect Genome- wide mapping of in vivoprotein-DNA interactions. Science，2007，316（5830）：1497-1502.

作者单位

西安电子科技大学 陕西省西安市 710070endprint

2003年， Kellis、Cliften分别用此方法在酵母属基因组中找到保守的模体， 2007 年，Kheradpour等对12个果蝇属物种的全基因组进行比较分析， 预测出若干保守模体存在于ChIP-Seq算法预测的有效富集区。均取得相应的成果。

大部分此类算法思想是将共调控和进化上保守两种因素综合起来，在de novo 预测算法的基础上开发的，同时研究者将刻画物种间进化关系的进化树以及进化距离等信息都添加到预测算法中，作为算法调控机制。以增加算法准确率。其结果可以通过特定的ChIP-Seq算法验证。

和前两种算法不同，系统发育足迹分析法面对在更宏观背景下的模体识别问题，de novo算法与ChIP-Seq算法的每次进步总是要对其产生促进，同时它的发展也对前两者提供了验证信息和新的思路。最终生物信息学对生命的解读将由这三类甚至更多、更新层级方法共同完成。

4 总结

可以看出转录因子结合位点识别研究历经简单枚举、局部搜索、网络模型、 与DNA芯片技术结合、与物种进化结合等等过程，逐步形成了研究体系，各个过程中间不是简单的技术换代，而是在新的技术条件下各种经典的方法的延伸和发展。也就是说我们不能简单地认为局部搜索就优于枚举，或是ChIP-Seq算法优于de novo算法等等，它们各阶段的发展都是对彼此的促进。在相互促进融合的过程中，新的更适合当下技术条件的算法会逐步被人们发现。只有通过各种数据的融合和相互校正，才能挖掘出可靠的转录因子结合位点和它对DNA序列转录调控关系。

通过对各类算法的分析，可以看出今后一个阶段的研究仍是围绕着减少序列背景中的噪音信号对所关注的模体信号的干扰，以及提高算法的时间效率来进行的，新的实验技术和更多的同源序列信息被发现，必将带来更高效的转录因子结合位点识别算法。

参考文献

[1]Patrik D'haeseleer，How does DNA sequence motif discovery work？ Nature biotechnology volume 24 number 8 August 2006.

[2]Helden etc，Extracting regul atory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies. Journal of Mol ecular Biology， 1984， 281（5）：527-842.

[3]Pesole etc，WORDUP：an efficient al gorithm for discovering statistically significant patterns in DNA sequences.Nucleic Acids Research， 1992，20（11）：2871-2875.

[4]Helden etc，Discovering regulatory elements in non-coding sequences by analysis of spaced dyads.Nucl eic Acids Research，2000，28（8）：1808-1818.

[5]Sinha，ect，Discovery of novel transcri ption factor binding sites by statistical overrespresentation. Nucleic Acids Research，2002， 30（24）：5549-5560.

[6] Pavesi，G.，Mauri，G.ect Analgori thm for finding signals of unknown length in DNA sequences.Bi oinformat i cs，2002，17（1）：207-214.

[7]Bailey，T.，L.and El kan，C.Fitting a mixture model by expectation maximizat i on to discover motifs in Bopolmers.Proc.of the 2th International Conference on Intelligent Systems for Molecular Biology，1994，pp28-36.

[8]Bailey ect，Unsupervised learning of multiple motifs in biopolymers using expectation maximization. Machine Learning.1995，21（1-2）：51-80.

[9]Lawrence ect，Detecting subtle sequence signals：a gibbs samling strategy for multiple alignment. Science.1993，262：208-218.

[10]Pevzner PA，Sze SH（2000） Combinatorial approaches to finding subtle signals in DNA sequences. In： Altman R，Bailey TL，eds.Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology.California：AAAI Press.269-278.

[11]Ren B，Robert F，ect Genome-wide location and function of DNA binding proteins.Science，2000，290（5500）： 2306-2309.

[12]Johnson DS ect Genome- wide mapping of in vivoprotein-DNA interactions. Science，2007，316（5830）：1497-1502.

作者单位

西安电子科技大学 陕西省西安市 710070endprint

2003年， Kellis、Cliften分别用此方法在酵母属基因组中找到保守的模体， 2007 年，Kheradpour等对12个果蝇属物种的全基因组进行比较分析， 预测出若干保守模体存在于ChIP-Seq算法预测的有效富集区。均取得相应的成果。

大部分此类算法思想是将共调控和进化上保守两种因素综合起来，在de novo 预测算法的基础上开发的，同时研究者将刻画物种间进化关系的进化树以及进化距离等信息都添加到预测算法中，作为算法调控机制。以增加算法准确率。其结果可以通过特定的ChIP-Seq算法验证。

和前两种算法不同，系统发育足迹分析法面对在更宏观背景下的模体识别问题，de novo算法与ChIP-Seq算法的每次进步总是要对其产生促进，同时它的发展也对前两者提供了验证信息和新的思路。最终生物信息学对生命的解读将由这三类甚至更多、更新层级方法共同完成。

4 总结

可以看出转录因子结合位点识别研究历经简单枚举、局部搜索、网络模型、 与DNA芯片技术结合、与物种进化结合等等过程，逐步形成了研究体系，各个过程中间不是简单的技术换代，而是在新的技术条件下各种经典的方法的延伸和发展。也就是说我们不能简单地认为局部搜索就优于枚举，或是ChIP-Seq算法优于de novo算法等等，它们各阶段的发展都是对彼此的促进。在相互促进融合的过程中，新的更适合当下技术条件的算法会逐步被人们发现。只有通过各种数据的融合和相互校正，才能挖掘出可靠的转录因子结合位点和它对DNA序列转录调控关系。

通过对各类算法的分析，可以看出今后一个阶段的研究仍是围绕着减少序列背景中的噪音信号对所关注的模体信号的干扰，以及提高算法的时间效率来进行的，新的实验技术和更多的同源序列信息被发现，必将带来更高效的转录因子结合位点识别算法。

参考文献

[1]Patrik D'haeseleer，How does DNA sequence motif discovery work？ Nature biotechnology volume 24 number 8 August 2006.

[2]Helden etc，Extracting regul atory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies. Journal of Mol ecular Biology， 1984， 281（5）：527-842.

[3]Pesole etc，WORDUP：an efficient al gorithm for discovering statistically significant patterns in DNA sequences.Nucleic Acids Research， 1992，20（11）：2871-2875.

[4]Helden etc，Discovering regulatory elements in non-coding sequences by analysis of spaced dyads.Nucl eic Acids Research，2000，28（8）：1808-1818.

[5]Sinha，ect，Discovery of novel transcri ption factor binding sites by statistical overrespresentation. Nucleic Acids Research，2002， 30（24）：5549-5560.

[6] Pavesi，G.，Mauri，G.ect Analgori thm for finding signals of unknown length in DNA sequences.Bi oinformat i cs，2002，17（1）：207-214.

[7]Bailey，T.，L.and El kan，C.Fitting a mixture model by expectation maximizat i on to discover motifs in Bopolmers.Proc.of the 2th International Conference on Intelligent Systems for Molecular Biology，1994，pp28-36.

[8]Bailey ect，Unsupervised learning of multiple motifs in biopolymers using expectation maximization. Machine Learning.1995，21（1-2）：51-80.

[9]Lawrence ect，Detecting subtle sequence signals：a gibbs samling strategy for multiple alignment. Science.1993，262：208-218.

[10]Pevzner PA，Sze SH（2000） Combinatorial approaches to finding subtle signals in DNA sequences. In： Altman R，Bailey TL，eds.Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology.California：AAAI Press.269-278.

[11]Ren B，Robert F，ect Genome-wide location and function of DNA binding proteins.Science，2000，290（5500）： 2306-2309.

[12]Johnson DS ect Genome- wide mapping of in vivoprotein-DNA interactions. Science，2007，316（5830）：1497-1502.

作者单位

西安电子科技大学 陕西省西安市 710070endprint