一种识别基因元件的新型优化算法

第３０卷第１期　２０１３年１月　计算机应用与软件　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖｏ１．３０　Ｎｏ．１　Ｊａｎ．２０１３　一种识别基因元件的新型优化算法　刘　维　陈汉武　陈　岐　江苏南京２１１１８９）　（东南大学计算机科学与工程学院（扬州大学信息工程学院江苏扬州２２５１２７）　摘　要　基因元件的识别是生物信息学中的重要研究课题之一。目前已有的算法大都存在容易过早陷入局部最优以及时间　复杂度过高等问题。为此，提出一种识别基因的新型优化算法ＡＣＲＲ（ａｎｔ－ｃｏｌｏｎｙ—ｒｅｇｕｌａｔｏｒｙ—ｒｅｃｏｇｎｉｔｉｏｎ）。该算法利用蚁群优化　算法能够较快求解复杂优化问题的优越性来解决此问题，不仅提高了解的质量，而且大大地降低了算法的时间复杂度。实验结果表　明，与其他类似算法相比，该算法所得结果的准确性更高，具有更快的识别速度。　关键词　生物信息学　基因元件蚁群算法　中图分类号ＴＰ３０１　文献标识码Ａ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３８６ｘ．２０１３．０１．００５　Ａ　ＮｏＶＥＬ　ｏＰＴＩＭＩＳＡＴＩｏＮ　ＡＬＧｏＲＩＴＨＭ　ＦｏＲ　ＧＥＮＥ　ＲＥＧＵＬＡＴｏＲＡＲＹ　ＥＬＥＭＥＮＴＳ　ＲＥＣｏＧＮＩＴＩｏＮ　Ｌｉｕ　Ｗｅｉ　・　Ｃｈｅｎ　Ｈａｎｗｕ　Ｃｈｅｎ　Ｌｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｈｅａｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｉｆｎｇ　２１１１８９，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ）　（Ｃｏｌｌｅｇｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙａｎｇｚｈｏｕ　ｕｎ　，Ｙａｎｇｚｈｏｕ　２２５１２７，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｉｔ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｉｍｐｏｒｔａｎｔ　ｒｅｓｅａｒｃｈ　ｔｏｐｉｃｓ　ｆｏｒ　ｇｅｎｅ　ｒｅｇｕｌａｔｏｒａｒｙ　ｅｌｅｍｅｎｔｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ｉｎ　ｂｉｏｉｎｆｏｒｍａｔｉｃｓ．Ｍｏｓｔ　ｏｆ　ｃｕｒｒｅｎｔ　ｒｅｇｕｌａｔｏｒａｒｙ　ｅｌｅｍｅｎｔｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｈａｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｅａｓｉｌｙ　ｃｏｎｖｅｒｇｉｎｇ　ｉｎｔｏ　ｐｒｅｍａｔｕｒｅ　ｌｏｃａｌ　ｏｐｔｉｍｕｍ　ａｎｄ　ｈｉｇｈ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ．　Ｔｈｅｒｅｆｏｒｅ，ｗｅ　ｐｒｏｐｏｓｅ　ａ　ｎｏｖｅｌ　ｏｐｔｉｍｉｓａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ＡＣＲＲ（ａｎｔ—ｃｏｌｏｎｙ・ｒｅｇｕｌａｔｏｒｙ—ｒｅｃｏｇｎｉｔｉｏｎ）ｆｏｒ　ｒｅｇｕｌａｔｏｒｙ　ｅｌｅｍｅｎｔｓ　ｒｅｃｏｇｎｉｔｉｏｎ．　Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｐｒｅｄｏｍｉｎａｎｃｅ　ｏｆ　ａｎｔ—ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｆａｓｔ　ｒｅｓｏｌｖｉｎｇ　ｔｈｅ　ｃｏｍｐｌｉｃａｔｅｄ　ｏｐｔｉｍｉｓａｔｉｏｎ，ｔｈｅ　ＡＣＲＲ　ｃａｎ　ｆｉｎｄ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｆｏｒ　ｔｈｉｓ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｉｍｐｒｏｖｅｄ　ｑｕａｌｉｔｙ，ａｎｄ　ｃａｎ　ａｌｓｏ　ｇｒｅａｔｌｙ　ｒｅｄｕｃｅ　ｔｈｅ　ｔｉｍｅ　ｃｏｍｐｌｉｃｉｔｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｏｔｈｅｒ　ｓｉｍｉｌａｒ　ａｌｇｏｒｉｔｈｍｓ，ＡＣＲＲ　ａｃｈｉｅｖｅｓ　ｈｉｇｈｅｒ　ａｃｃｕｒａｃｙ　ｉｎ　ｓｏｌｕｔｉｏｎｓ　ａｎｄ　ｈａｓ　ｆａｓｔｅｒ　ｒｅｃｏｇｎｉｔｉｏｎ　ｓｐｅｅｄ　ａｓ　ｗｅｌ１．　Ｋｅｙｗｏｒｄｓ　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ　Ｇｅｎｅ　ｒｅｇｕｌａｔｏｒａｒｙ　ｅｌｅｍｅｎｔｓ　Ａｎｔ—ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　性ＤＮＡ结合蛋白（即转录因子）识别这些元件，并与之结　０　引　言　合，调节ＤＮＡ的代谢和转录；或者由ＲＮＡ结合蛋白识别，并与　之结合，影响ＲＮＡ的修饰、定位、翻译和降解。因此，分析和识　生物系统由静态和动态两部分构成。静态部分由基因组中　别转录元件及了解它们的功能是理解和解释整个基因组行　所有基因组成，这些基因是生物系统的基本构造元件。近年来，　为的重要步骤　Ｊ。　随着大规模基因组测序、基因预测以及注释的完成，生物学研究　无论是搜索已知的元件，还是预测新的元件，都会　更加关注动态部分即基因元件。基因元件（ｍｏｔｉｆ也称　遇到三个基本问题：（１）应该用什么样的语言来描述元件，　为模体）蕴涵着丰富的生命特征信息，它在基因的结构和功能　即为元件建立什么样的特征模型；（２）要定义一个衡量序　方面都扮演着及其重要的角色，因此发现和辨识基因元件　列片段是否为元件的度量或得分；（３）当给定了元件　成了揭示基因秘密的重要途径，受到了生物信息学研究领域的　模型和得分函数后，如何从待分析的序列中找到得分最高的候　广泛重视。　选元件，这就是算法设计问题。　基因元件识别（ｍｏｔｉｆ　ｒｅｃｏｇｎｉｔｉｏｎ，也称为模体识别）问　近二十年来，人们一直致力于基因组ＤＮＡ序列中的基因调　题是指如何从生物序列数据或结构数据中提炼出含有生命特征　控元件识别方法。可以通过实验的方法来标识元件，也可　信息的模体，和如何从目标序列或结构数据中辨别出内含的模　体的过程。对基因非编码区的一个主要研究方向就是对元　收稿日期：２０１２—０８—０３。２０１２中国计算机大会论文。国家自然科　件的研究　］。因为在转录和后转录水平，基因的表达在很大程　学基金项目（６１０７００４７，６１０７０１３３，６１００３１８０）；国家重点基础研究发展计　划（２０１２ＣＢ３１６００３）；江苏省自然科学基金项目（Ｋ２０１０３１８，ＢＫ２１０１０１３　度上受到一些顺式作用元件（即转录元件，在生物信息学　４）；江苏省高校科研基金项目（０９ＫＪＢ２００１３）。刘维，博士，ＣＣＦ会员（Ｅ２　中也称为模式或ｍｏｔｉｆ）的控制，它们本质上是一些比较短的　０００２６１９０Ｍ），主研领域：生物信息学，数据挖掘。陈汉武，教授。陈峻，　ＤＮＡ序列，这些序列一般都处在受基因的上游区域，特异　教授。　２２　计算机应用与软件　２０１３丘　以通过计算的方法来识别元件。通过实验方法占用的时间　和经济成本太高，且有时得出的结论还不全面。因此采用计算　的方法越来越受到人们的重视　Ｊ。用计算的方法查找转录因　子结合位点主要涉及三类问题：（１）在给定基因组序列中寻找　已知的元件；（２）在一系列共表达或者共基因的上游　了一个新型优化算法ＡＣＲＲ（ａｎｔ・ｃｏｌｏｎｙ－ｒｅｇｕｌａｔｏｒｙ—ｒｅｃｏｇｎｉｔｉｏｎ），　即基于蚁群算法查找结合位点的计算方法。与已有算法相比，　该方法可以避免过早陷入局部最优，保证了解的质量，并大大降　低了算法的时间复杂度。通过对当前通用的两组标准测试数　据，即啤酒酵母菌的五个典型的结合位点基因和大肠杆菌中包　含ＣＲＰ结合位点的１８条基因，进行测试的结果表明本文算法　是非常有效的，对ＣＲＰ结合位点的预测准确度要高于流行软　区域中发现未知的元件；（３）寻找由一个已知转录因子调　控的未知基因。本文的工作主要针对第二类问题，这一类问题　称为序列驱动的元件的识别。相应地，第一类问题称为模　式驱动的元件的识别。　件，且具有较高的识别速度　针对不同的生物和不同特点的元件，出现了很多算法　１基本概念　和模型。常用的识别方法基本上分为两类：模式驱动的元　件识别和序列驱动的元件识别。前者主要是通过用元　件的模型（串模型或矩阵模型）来搜索序列的潜在位点，解决该　问题的软件主要有如ＳＩＧＮＡＬ　ＳＣＡＮ，ＣｏｎｓＩｎｓｐｅｃｔｏｒ，ＴＦＳｅａｒｃｈ／　ＴＥＳＳ，Ｍａｔｉｎｓｐｅｃｔｏｒ，Ｃｏｎｓｉｔｅ，Ｍａｔｃｈ等等。后者是基于共基　因簇的公共元素预测方法。常用的算法主要有：（１）计数法…　它是一种最直接、最简单的穷尽搜索算法，其时间复杂度与序列　模式长度的指数呈正比。因此，这种算法只适合于发现短的调　控元件。（２）ＥＭ算法，该算法在解决含有隐变量的模型和实际　问题中非常有用。它是一种迭代算法，交替执行两个步骤：即Ｅ　步骤（求期望值）和Ｍ步骤（最大化）。ＥＭ算法很依赖初始条　件，如果最初的参数估计不当，就会收敛到局部极值，而不是最　优结果。（３）ＭＭ（Ｍｉｘｔｕｒｅ　Ｍｏｄｅ１）算法　它是最大期望算法的　一种改进，基本思想在于元件具有保守性，且有对应的特征　矩阵，在不断迭代的过程中只有当两者适应时，最大似然函数值　才能达到最大。对于得到的保守序列、感知矩阵或者元件　特征模型，需要经过评估，确定其统计的显著性。（４）Ｇｉｂｂｓ采　样算法Ｇｉｂｂｓ采样算法是一种特殊的马尔柯夫链蒙特卡罗方法　ＭＣＭＣ（Ｍａｒｋｏｖ　Ｃｈｍｎ　Ｍｏｎｔｅ　Ｃａｄｏ），该算法最早是由Ｌａｗｒｅｎｃｅ　等引入蛋白质序列中的ｍｏｔｉｆ识别。后来Ｌｉｕ　等将Ｇｉｂｂｓ采样　整合进贝叶斯模型并应用于多重序列比较，获得了较好的结果。　目前，Ｇｉｂｂｓ采样算法以及一些改进算法被广泛应用于元件　的识别，并出现了一些较为成熟的软件以供用户在线和下载使　用，如ＭｏｔｉｆＳａｍｐｌｅｒ，ＡｌｉｇｎＡＣＥ　Ｊ，ＢｉｏＰｒｏｓｐｅｃｔｏｒ和Ｇｉｂｂｓ　Ｍｏｔｉｆ　Ｓａｍｐｌｅｒ　ｌ。。等。Ｇｉｂｂｓ采样算法识别元件的基本原理是通过　随机采样不断更新元件模型和在各条序列中的出现位置以　优化目标函数，当满足一定的迭代终止条件时就得到了最终的　候选元件。目前较为普遍的软件还有Ｃｏｎｓｅｎｓｕｓ，　ＭＥＭＥ…］，ＡＮＮ—Ｓｐｅｃ，ＰＲＯＪＥＣＴＩＯＮ，ＭＤＳｃａｎ，还有最近出现的　ＹＭＦ。　近年来，还有一些其他的算法¨　运用到预测元件　中，如统计分析、神经网络、聚类预测、字识别。随着各种技术的　发展和人们对分子生物学认识的深入，出现了越来越多的基于　生物学知识的其它方法来识别元件，如采用比较基因组学　来发现在进化过程中保守的结合位点，考虑元件之间的协　同作用而设计的元件模块识别方法等。　本文的工作主要集中在解决第二个问题：即从共表达的基　因序列中查找结合位点。对于采用计算的方法求解第二个问　题，有一个重要的假设：被同一个元件的基因，将具有　相同或者相似的基因表达模式。对基因芯片数据聚类，可以得　到共表达的基因，而我们就是要从这些共表达的基因的上游序　列中查找可能的转录因子的结合位点。所以问题可以定义为从　一个序列集合中查找一定长度的保守序列片段。为此本文提出　１．１　问题描述　为描述方便，假设所要解决的问题具有每类元件在每　条序列中出现且仅出现一次的特征。给定序列集Ｘ＝｛Ｘ。，　，　…，Ｘ　｝，每个序列由表示四种碱基的字母Ａ，　，Ｃ，Ｇ组成。每条　序列的长度分别为ｆ　，２：，…，ｆ　，目标是查找长度为　的ｍｏｔｉｆ所　在的保守序列片断集合Ｍ＝｛Ｍ。，Ｊｌ）ｆ２，…，Ｍ　｝，　是　的长度　为埘的子序列，其中』ｌｆ　ｃ　（ｉ＝１，２，…，ｎ）。　上面提到用计算的方法寻找保守序列片断结合位点首先要　解决的第一个重要问题是：用什么样的方法表示这些序列，即为　元件建立什么样的特征模型。本文的方法采用的是矩阵模　型，即用一个特征矩阵描述元件的分布，因此我们的目的就　是要找出该特征矩阵。　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　扣　１．２特征矩阵　定义１设模式长度为　，　：｛Ａ，Ｔ，Ｃ，Ｇ｝。则特征矩阵Ｍ　为一个４×　的矩阵，其第ｉ行第　列元素记为　，其中ｂ为第ｉ个　字符。Ｐ　表示∑中第ｉ个字符在模式的第Ｊ个位置出现的可能　性。　Ｃ　Ｃ　Ｃ　Ｃ　Ｃ　Ｃ　Ｃ　Ｇ　Ｇ　Ｇ　Ｇ　Ｇ　Ｇ　Ｇ　Ｔ　Ｔ　Ａ　Ｔ　Ａ　Ｔ　Ａ　我们可以首先构建出元件的矩阵模型如表１所示。　表１简单矩阵　１　２　３　４　５　６　Ａ　１０　Ｏ　Ｏ　０　０　３　１　０　Ｏ　０　０　９　Ｇ　０　０　ｌ２　Ｏ　ｌ２　０　Ｃ　１　１２　Ｏ　１２　０　Ｏ　表１中的矩阵元素为该位置上对应的碱基出现的数目，例　如矩阵的第一行第一列元素等于１０，说明字符“Ａ”出现在第一　个位置上的元件有１０个。将表１中的矩阵元素改成该位置　上对应的碱基出现的频率，我们可以进一步得到如表２所示的　Ｃ　Ｇ　Ｔ　２４　计算机应用与软件　２０１３免　守性。其值越大则表示样本问的差异性越小，保守性越高。　ＢＣ、ＤＨ、ＤＣ。经过一个时间单位后，在路径ＢＣＤ上的信息量是　从式（２）可以看出，当碱基ｂ在位置出现的频率Ｐ　越高于　．　路径ＢＨＤ上信息量的二倍。也就是说，在ｔ＝１时刻，将有２０只　蚂蚁由Ｂ和Ｄ到达Ｃ，有ｌ０只蚂蚁由Ｂ和Ｄ到达日。随着时间　的推移，蚂蚁将会以越来越大的概率选择路径ＢＣＤ，最终完全　选择路径ＢＣＤ，从而找到由蚁巢到食物源的最短路径。　出现在背景的频率Ｐ　时，两者的比值就越大，对信息含量，ｃ的　贡献就越大。反过来说，两者比值越大，碱基出现在位置　的概率　就越大，该点的保守性就越高。　与其他非编码序列相比，元件具有较高的保守性，其信　息含量，ｃ值也较高。因此我们要在所有Ｗ长的子序列组中找出　回Ｅ　胁协　回　，ｓ　＿ｓ　，ｃ最高者作为模体的特征矩阵。但是，一共有丌（Ｌｔ　　一　＋１）种　子序列组，如果要穷举它们，则计算量会特别大，显然，这个问题　是个ＮＰ完全问题。因此我们考虑采用优化算法来解决该问题，　本文提出用蚁群优化方法来求解模体的特征矩阵。　２蚁群算法简介　人们从仿生学的机理中受到启发，提出许多用于解决复杂　优化问题的新方法，统称为元启发算法，如遗传算法、进化策　略、模拟退火、蚁群算法、禁忌搜索算法等，并成功地应用于实际　问题。蚁群算法是模拟蚂蚁的群体的智能的一种新型模拟进化　算法。它是由意大利学者Ｍ．Ｄｏｒｉｇｏ等人受到人们对内然界真　实蚁群集体行为的研究成果的启发而首先提出来的。他们充分　利用蚁群搜索食物的过程与旅行商问题之间的相似性，通过人　Ａ　　一工模拟蚂蚁搜索食物的过程中个体之间的信息交流与相互协　＝　Ｃ．１ｊ　作，最终找到从蚁群到食物源的最短路径的原理解决ＴＳＰ问　题　，取得了很好的结果。随后，蚁群算法被用来求解ｊｏｂ—　ｓｈｏｐ调度问题、指派问题、地形测绘等ＮＰ完全问题，显示出蚁　群算法在求解复杂优化问题（特别是离散优化问题）方面的优　越性，证明了它是一种具有广阔发展前景的好方法。　生物学的研究表明，虽然单个蚂蚁的能力非常有限，但多　个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力。　这种能力是靠其在所经过的路径上留下的一种挥发性分泌物来　实现的。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的　分泌物选择其要走的路径，其选择一条路径的概率与该路经上　分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行　为实际上构成一种学习信息的正反馈现象：某一条路径走过的　蚂蚁越多，则后面的蚂蚁选择该路径的可能性就越大。蚂蚁的　个体之间通过这种信息的交流寻求通向食物的最短路径。这种　优化过程的本质在于：（１）选择机制，分泌物越多的路径，被选　择的概率越大；（２）更新机制，路径上的分泌物会随蚂蚁的经过　而增长，而且同时也随时间的推移逐渐挥发消失；（３）协调机　制，蚂蚁之间实际上是通过分泌物来互相通信、协同工作的。蚁　群算法正是充分利用了这样的优化机制，即通过个体之问的信　息交流与相互协作最终找到最优解，使它具有很强的发现较好　解的能力。　图２是Ｍ．Ｄｏｒｉｇｏ用来说明蚁群寻找最优路径原理的一个　例子：设Ａ是巢穴，Ｅ是食物源，ＨＣ为一障碍物。由于障碍物　存在，蚂蚁只能经由日或Ｃ从Ａ到达　，或从　到达Ａ，各点之　间的距离如图２所示。设每个时间单位有３０只蚂蚁由』４到达　曰，有３Ｏ只蚂蚁由　到达Ｄ点，蚂蚁过后留下的激素物质量（本　文称之为信息素强度或信息量强度）为１。为方便起见，设该物　质停留时间为１个单位时间长度。在初始时刻，由于路径ＢＨ、　ＢＣ、ＤＨ、ＤＣ上均无信息素存在，位于日和Ｅ的蚂蚁可以随机选　择路径。从统计学的角度可以认为它们以相同的概率选择ＢＨ、　Ｈ　Ｃ　Ｂ　…　。　㈣　ｉｆ３　ｓ　ｉＡ１’　ｓ…　图２人工蚁群的寻优过程　事实证明，这样的机制使得蚁群算法具有比遗传算法、模拟　退火算法、禁忌搜索等启发式方法更高效的优化能力，在一些特　定领域，该算法也被证明比神经网络算法更灵活。特别是近几　年来蚁群算法作为一种新型优化算法，被广泛应用于数值函数　优化、频率分配，网络路由、数据挖掘、芯片设计、生物信息学等　各个领域，取得了较好结果。　我们以ＴＳＰ问题为例，具体说明基本蚁群算法的框架。设　有ｎ个城市，ｄ　（ｉ，　＝１，２，…，ｎ）表示城市ｉ和　问的距离，ｒ　（ｔ）表示在ｔ时刻城市ｉ和　之间的信息量，用于模拟实际蚂蚁　的分泌物，设共有ｍ只蚂蚁，用Ｐ　（ｔ）表示在ｔ时刻蚂蚁　由城　市ｉ转移到城市．　的概率：　ｐ：　：ｆ（ｆ）＝＝｛【　０∑　。　　７．：（￡）叼　（￡）　…。ｔｅｈｅ　ｎｒｗｉ肌……‘。ｓ　ｅ　ｅｄ　（３）　其中ａｌｌｏｗｅｄ　表示蚂蚁ｋ下一步允许走过的城市的集合，Ｏｔ表示　路径上的信息量对蚂蚁选择路径所起的作用大小，　为由城市　ｉ转移到城市　的期望程度，可以取　＝Ｉ／ｄ　表示叩　的作　用。当　＝０时，算法就是传统的贪心算法；而当口＝０时，就成　了纯粹的正反馈的启发式算法。经过ｎ个时刻，蚂蚁可走完所　有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。　此时，要根据下式对各路径上的信息量作更新：　（ｔ＋１）＝（１一Ｐ）‘　（ｔ）＋△Ｊｒ　（４）　其中Ｐ　（０，１），表示信息量　（ｔ）随时间的推移而衰减的程度。　信息增量△　可表示为：　△　：　ａｒ：　（５）　其中△　ｒ　表示蚂蚁ｋ在本次循环中在城市ｉ和　之间留下的信　息量，它的计算公式根据计算模型而定，例如在最常用的ａｎｔ　ｃｉｒｃｌｅ　ｓｙｓｔｅｍ模型中：　：ｆＬ０　Ｑ／　ａｏｔｎｈｅｒｗｉｔ　ｓｅ　（　，　（６）　这里，Ｑ为常数，　为蚂蚁ｋ在本次循环中所走路径的长度。　在经过若干次循环以后，可以根据适当的停止条件来结束计算。　３算法的思想及其实现　３．１解的表示形式　设已知序列集为Ｘ＝（　。，Ｘ２，…，Ｘ　），其中序列　的长度　第１期　刘维等：一种识别基因元件的新型优化算法　２５　为ｌ　，ｍｏｔｉｆ所在的保守序列片断的长度为Ｗ。我们用一个蚂蚁　个体表示一个解，由于假设每个输入序列中包含了一个ｍｏｔｉｆ的　片段，所以可以用一个整数向量Ｊ＝｛　，　，…，　｝表示目标　其中　为第　只蚂蚁所得到的解的特征矩阵。，ｃ（　）为　的信息含量，可以由式（２）计算得到。　３．６算法框架　综上所述，该算法的总体框架如下：　算法ＡＣＲＲ（ａｎｔ—ｃｏｌｏｎｙ—ｒｅｇｕｌａｔｏｒｙ—ｒｅｃｏｇｎｉｔｉｏｎ）　ｍｏｔｉｆ。其中．　［１，ｆ　一　＋１］表示序列　中结合位点的起始点　（即模体的起始位置）。一个向量Ｉ，就代表了一个由ｎ个片段　组成的Ｗ长的子序列组。由此子序列组就可以计算它的特征　矩阵　（’，），从而也就可以得到其信息．含量　（Ｍ（ｔ，））。　输入：ｎ条序列Ｘ１，Ｘ２，…，　，迭代次数ｍｚ／￣ｕｍ，蚂蚁个数ｍ；　输出：子模体的特征矩阵肘　及起始位置Ｊ　＝｛　，，止，　３．２蚂蚁搜索的逻辑图　在蚂蚁搜索的逻辑图如图３所示。图有ｎ　４－１个节点，　分别标记为Ｘ　，Ｘ２，…，Ｘ　，Ｘ　，其中　表示第ｉ条序列（ｉ＝１，　２，…，ｎ），Ｘ　表示结束节点。由　到Ｘ…有Ｌｉ＝１　一Ｗ＋１条路　径，将其中的第　条记为ｃ　表示序列ｉ取位置　作为起始位置，　Ｇ　上的信息素记为ｒ　每个蚂蚁从　。出发，经由　，　，…至　，设其经由的路径为Ｃ　，Ｃ　，…，Ｃ　，则构成一个解Ｊ＝　｛　．，２，…，　．｝。　图３蚂蚁搜索的逻辑幽　３．３蚂蚁选择路径的概率公式　蚂蚁由节点Ｘ　到　时，选择边ｃ　的概率为：　尸　（　）：　且　（７）　∑　（ｔ）］　（　）］　这里Ｊｒ　（ｔ）为ｔ时刻Ｃ　上的信息素；叼　（　）为启发式信息，为选择　序列Ｘ　上的第　个位置为ｍｏｔｉｆ的开始位置的适合程度，它以蚂　蚁当前搜索到的最优模式为参考标准。　ｐ　￣ｔ，ｊ＋ｋ－Ｉ㈣　这里Ｍ（ｔ）为到ｔ时刻为止，蚂蚁所取得的历史最优解肘　所对　应的特征矩阵。为此，算法在各次迭代中要记录一个历史最优　解Ｍ　，并以此作为最优模式设置启发式信息７１　（ｔ）。　３．４解的适应度　对于蚂蚁所得到的解Ｊ＝｛　，止，…√　｝，我们可以由Ｗ长度　子序列组：　Ｘｌｊｌ，…，Ｘｌｊｌ＋　一ｌ　…，，　…　Ｘ　，…，　啦Ⅷ１　通过计算各个字符在每个位置上出现的次数来计算出其特　征矩阵肘（‘，），随后根据式（２）求得　（．，）的，ｃ值ＩＣ（　（Ｊ））作　为该解的适应度。　３．５信息素的更新公式　在每次迭代后，对每条边　上的信息素ｒ　用以下公式更新：　（　＋１）＝ｐｒ　（ｔ）＋（１一ｐ）∑△　ｒ　）　（９）　这里Ｐ∈（０，１）为衰减系数，ｍ为蚂蚁个数，ａｔｅ”．为蚂蚁　在边　Ｃｏ上的信息素增量，由下式定义：　△　（ｔ）：ｆ　ｃ（Ｍｋ）　ｉｆ　ａｎｔｋ的解中含有ｃ　（１０）　…，　｝。　Ｂｅｇｉｎ　１．　初始化，随机设置初始特征矩阵Ｍｂ。　计算背景模式Ｂ。　２．　ｆｏｒ　ｔ＝ｌ　ｔｏ　ｍａｘｎｕｍ　ｄｏ　３．　ｏｆｒ　ｋ＝１　ｔｏ　ｍ　ｄｏ　４．　ｏｆｒ　ｉ＝１　ｔｏ　ｎ　ｄｏ　５．　蚂蚁ｋ按公式（７）选择边Ｃ　６．　蚂蚁ｋ对所得的Ｘ。序列的起始位置ｊ作局部优化；　７．　ｅｎｄ　ｆｏｒ　ｉ　８．　蚂蚁ｋ对所得的子序列组作局部优化，设所得到的解为　Ｊ＝｛Ｊ１，ｊ２，…，Ｊ　｝；　９．　按公式（２）计算ＩＣ（Ｍ（Ｊ））；　１０．　ｉｆＩＣ（Ｍ（Ｊ））＞ＩＣ（Ｍｂ　）ｔｈｅｎ　１１．　Ｍｂ　。。＝Ｍ（Ｊ）；　１２．　Ｊｂ。　ｔ＝Ｊ　１３．　ｅｎｄｉｆ；　】４．　ｅｎｄｆｏｒ　ｋ　１５．按公式（９）更新各边上的信息素，按新的　计算－ｑ　（ｔ＋１）；　１６．　ｅｎｄ　ｆｏｒ　ｔ　１７．　输出Ｍｂ　Ｊ　Ｉ；　Ｅｎｄ　在算法ＡＣＲＲ的每次迭代过程中，每只蚂蚁都要经过搜索　逻辑图上的ｎ个顶点。在每一步中，进行路径选择的概率计算　需要花费的时间为ｌ　一　＋１，其中ｚ　为第ｉ条序列的长度，而　为模体的长度。由此，很明显地，我们可以得到算法ＡＣＲＲ的总　的时间复杂度为０（ｔｍｎＬ），其中ｔ为迭代次数，／－ｇ为基因序列的　条数，ｍ为算法中人工蚂蚁的个数，　是基因序列的最大长度。　３．７单序列局部优化策略　在算法ＡＣＲＲ的第６行，蚂蚁对于序列　所取的起始位置　作局部优化，在位置　的领域作局部搜索，找出更好的开始位　置。因这个局部优化只在序列墨中对所取的起始位置　进行优　化，故称为单序列局部优化。单序列局部优化的策略如下：　设Ｘ　＝　，　，…，　，｝，蚂蚁取　作为起始位置，　∈［１，２　一　＋１］，意味着仅片段　，　＋．，…，￣＂ｉ，ｊ＋ｗ－Ｉ作为模体。我们可　以同时分别观察以　一１为起始点的模体　一　，　…，　。＋　一　、　以　＋１作为起始点的模体　＋　，　：，…，　＋　，与Ｊ作为起始　点的模体进行比较。　我们可以参照历史最优解　，用式（１）计算出序列Ｘ　在　位置Ｊ上出现模体的概率尸（置ｌ　，Ｍｂｅｓｔ，Ｂ），同时也分别计算在　Ｊ一１，　＋１位置上出现模体的概率ＪＰ（置ｆＪ一１，Ｍｂｅｓｔ，Ｂ）和尸（置　ｌＪ＋１，Ｍ，曰），在三者中取最高的作为　序列的起始点。　３．８序列组的局部优化策略　在算法ＡＣＲＲ的第８行，对蚂蚁Ｊｊ｝在本次迭代中所取得的　解Ｊ＝｛　。，止，…，　｝作局部优化．由于这个局部优化是对一组子　序列构成的解的领域进行局部搜索，故称其为子序列组的局部　优化，优化策略如下：　２６　对于解Ｊ＝｛　…计算机应用与软件　，…　｝，考察另两个相邻的解Ｊ一＝｛　一　√２　ＴＦ　Ｓｉｚｅ　２０１３丘　表３啤酒酵母菌五个转录因子信息　Ｌｅｎｇｔｈ　Ｃｏｎｓｅｎｓｕｓ　Ｓｅｑｕｅｎｃｅ　√　｝和Ｊ　＝｛　＋。√２　…Ｊ　＋，｝的信息含量值，在解‘，、Ｊ一、Ｉ，　在计算Ｊｃ（Ｍ（Ｊ一））和ＩＣ（Ｍ（．，　））时，可以在Ｊｃ（Ｍ（＿，））　的三个中取信息含量值较大者作为蚂蚁ｋ在本次迭代中的解。　的基础上计算，不必再用式（２）重新计算。事实上，由式（２）我　ＧＡＩ４　ＲＡＰ１　ＲＥＢ１　６　１６　９　１７　７　７　ＣＣＧＮＮＮＮＮＮＮＮＮＮＮＣＣＧ　ＲＭＡＣＣＣＡ　ＹＹＡＣＣＣＧ　们可知：　，ｃ（　（’，））　Ｊ　１　ｂ　Ｅ　ｌ。ｇ［告Ｐｏ】　，　（　（　））　这里，１Ｃ（Ｍ（Ｊｊ））为Ｍ（Ｊ）的第　列元素的信息含量值。即：　，ｃ　驯＝　ｓ　０　Ｅ，　，Ｕ　由此可见，，Ｇ（　（Ｊ））是由各列的信息含量值求和而得到　的，而各列的信息含量值可以地求出。　对于解Ｊ＝｛　，…√　｝，它所含的一组子序列为：　１，Ｊｌ一１　Ｘ１，ｌ　１，Ｊｌ＋１　…Ｘｌ．，Ｊｌ　＂一３　１，Ｊ１＋ｗ－２　Ｘ２ｊ，一Ｉ　Ｎ２Ｊ２　Ｘ２４２＋１　…　２Ｊ２＋ｗ－３　Ｘ２，－Ｊ２＋ｗ－２　　，ｎ一１　，Ｊ“　ｎ．ＪＲ＋ｌ　ｎ，Ｊ“＋　一３　ｎ．，ｎ＋　一２　我们记向量Ｊｏ＝（　一　，　ｚ以　，…，　一ｔ）为第０列，向量　Ｊ　＝（ｘ　＋　，　Ｊ２＋　，…，Ｘ　＋　）为第　＋１列。因，ｃ［Ｍ（Ｉ，）］＝　∑，ｃ（　（　）），我们易知：　Ｊ　１　”一Ｉ　ＩＣ（Ｍ（Ｊ一））＝∑ＩＣ（Ｍ（Ｊｊ））　Ｊ　ｕ　＝ＩＣ（Ｍ（Ｊ））＋，Ｃ（　（Ｊｏ））一，Ｃ（　（Ｊ　））　＋ｌ　ＩＣ（Ｍ（Ｊ　））＝∑，ｃ（　（　））　Ｊ　＝ＩＣ（Ｍ（Ｊ））＋ＩＣ（Ｍ（Ｊ　＋１））一，Ｃ（　（　））　实际上，我们只要在，ｃ（Ｍ（　））一ＩＣ（Ｍ（Ｊ　）），０，ＩＣ（　（Ｊ　＋　））一ＩＣ（Ｍ（Ｊ，））三者中取最大者即可。　４实验结果及分析　我们用实验来验证本文所提出的基于蚁群优化的基因　元件识别算法ＡＣＲＲ的有效性，实验程序的运行计算机系统配　置为：Ｉｎｔｅｌ　Ｐｅｎｔｉｕｍ４　３．ＯＧＨｚ　ＣＰＵ，内存１ＧＢ，Ｗｉｎｄｏｗｓ　ＸＰ操作系　统，Ｖｉｓｕａｌ　Ｃ＋＋６．０的程序编辑、编译链接环境。所有的算法均　采用Ｃ＋＋语言实现。　本文的实验数据均采用了当前的标准测试数据来测试算法　的有效性，即啤酒酵母菌的几个典型的结合位点基因和大肠杆　菌中包含ＣＲＰ结合位点的１８条基因，这两组数据为检测程序　有效性的标准测试数据。　４．１　实验结果的质量分析　４．１．１　对啤酒酵母菌的结合位点分析　本文采用通用的数据库ＳＣＰＤ”　（ｈｔｔｐ：／／ｒｕｌａｉ．ｃｓｈｔ．ｅｄｕ／　ＳＣＰＤ／）中的关于啤酒酵母的数据。该数据库比诸如ＴＲＡＮＳ—　ＦＡＣ等其它同类数据库中关于转录因子的信息丰富得多，包含　了完整的啤酒酵母结合位点及其转录因子的信息。本文选用了　ＲＡＰ１，ＧＡｌＡ，ＲＥＢ１，ＭＣＢ和ＰＤＲ３等五组转录因子的结合位　点作为测试数据，具体的数据信息见表３。我们从ＳＣｐＤ上下载　了包含每一个转录因子的结合位点的、长度为５５０的若干条启　动子序列。　ＭＣＢ　６　６　ＷＣｅＣＧＷ　ＰＤＲ３　７　８　ＴＣＣＧＹＧＧＡ　我们对得到的结果用ｌｏｇｏ模型可视化表示。在该模型中，　横轴方向表示碱基在序列中的位置，所有出现在该位置的碱基　在这里进行堆叠，每个碱基在竖轴方向的高度对应于它在此位　置上的信息量。每个位置上，各碱基按照信息量大小自上而下　地排列，该位置上堆积的总高度即为该位置的信息总含量。由　于某一位置上碱基的保守性可以由该位置上的信息含量反映出　来，因而我们可以非常直观地从ｌｏｇｏ模型看出哪些位置上的哪　些碱基起着相对重要的作用，从而可以分析出各个结合位点的　保守程度。我们利用本文算法ＡＣＲＲ，我们对这些数据进行测　试，并将测试结果通过网站（ｈｔｔｐ：／／ｗｅｂｌｏｇｏ．ｂｅｒｋｅｌｅｙ．ｅｄｕ／ｌｏｇｏ．　ｃｇｉ）得到结果的可视化模型表示，如图４一图８所示，这些结果　与通过化学印记方法得到的结果全部相同。说明采用本文算法　ＡＣＲＲ是有效的。　ｍ　警　：＝Ｉ　图４　ＡＣＲＲ算法得到的ＧＡＬ４的运行结果　图５　ＡＣＲＲ算法得到的ＲＡＰ１的运行结果　图６　ＡＣＲＲ算法得到的ＲＥＢ１的运行结果　图７　ＡＣＲＲ算法得到的ＭＣＢ的运行结果　图８　ＡＣＲＲ算法得到的ＰＤＲ３的运行结果　４．１．２　大肠杆菌的结合位点实验结果分析　目前已有的大部分软件均采用大肠杆菌的ＣＲＰ结合位　点　作为测试数据，这组测试数据长度为１０５的、包含了受　第１期　刘维等：一种识别基因元件的新型优化算法　ＣＲＰ子结合位点的１８条序列，在其中，已知的ＣＲＰ结合位　有２条序列的识别结果错误，ＡｌｉｇｎＡＣＥ　也有２条序列的识别　点的有２３个，已经通过ＤＮＡ足印方法得到确认。对于ＣＲＰ结　错误。由于第１７条序列的结合位点的相似性程度比其它序列　合位点的测试，一般来说，如果找到的位点与已知位点有一半的　低，这三个软件均未能查找到第１７条序列的结合位点。而本文　序列能够重合，则认为此位点被找到。测试数据的全部信息如　算法ＡＣＲＲ从这１８条序列构成的集合中正确查找到了所有序　表４所示。一般的计算方法选取ＣＲＰ的结合位点的长度为１８　列的结合位点，尤其是第１７条序列，尽管它相应的偏差要比其　—２５，本文选取的长度为２２，如果找到的位点与已知点的差距　它序列大一些，但算法ＡＣＲＲ能够全部找到。主要原因是采用　在１０以内，则认为此位点被找到。表５显示了本文算法ＡＣＲＲ　ＡＣＲＲ算法利用了蚁群算法的优化能力，同时又使用了局部搜　与其余几种已有算法的实验结果比较。　索的方法，使所找到的结合位点的Ｍｏｔｉｆ的信息含量较大，这可　表４大肠杆菌ＣｌＩＰ结合位点的１８条序列　以由表６得知。由此可见，ＡＣＲＲ算法在ＣＲＰ测试数据上的准　名称　庠　列　确性要高于已有的常用算法，对解决该类问题是非常准确有效　的。　Ｃ　ｌＯＧ　＾Ｇ　口　ｎ了Ｇ蟠宅ＧＨｒｒｃ　Ｃ＾＾＾＾盟　ＧＧ　ａ　Ｃ＾搿ｅ掰＿Ｇ＾Ｃ＾Ｇ　表６不同软件找到的信息含量的值　Ｇ　Ｃ　ＬｃＧ暖　Ｉ　＾＾搿Ｇｆ｛葛柏＾＾　ｌｃＧＩＸ　Ｇ＾＾　Ｃｅ＾　Ｇ　ＥＣｏ＾Ｒ＾鼢　程序名称　信息量值　＾＝玎　ｒ了　０　ＧＧＯ皤Ｃ＾｜＝＾Ｃｎ　０ｃ】　∞　。ｃ黛豇幅。啦　蛆　巴＾∞　略　ＡＣＲＲ　１０．２７３　ＥＣＯ眦ｌ　Ｏ目．＾＾＾　ｃ｜　＾＾瞬曙　蠕　＾Ｃ　Ｇ内ＧＣ＾薯ａ　ｒｃ　瞄　ｎ　镊￡＾瑚ｒ　ＭＥＭＥ　９．５０８　Ｃ＾Ｉ　＾＾Ｉ　）Ｇ＾　口０∞－＾＾＾＾０　ａ　；Ｑ盯ＧＣ　ｌｃ＾Ｇｆ＾　Ｍ．ｃｍＣ　口　ＡｌｉｇｎＡＣＥ　９．７５２　ＥｅＯＣｌＩＰ　Ｇｉｂｂｓ　Ｓａｍｐｌｅｒ　９．２２９　＾ＣＧＧ　；ｃ馨　＾Ｃｎ　麓　）ＧＣ柏℃ｎ　ａ－ｒ　Ｃ０　Ｃ　盯ＣＡ昏　Ｕ棚　ＥＣＯＣ　４．２算法的运行速度分析　Ｅ００Ｉ）Ｉ　为了检验本文算法ＡＣＲＲ的运行速度，由于ＲＡＰ１的数据　ｒｒ‘：ｃｆ　ｎＧ　Ｇ霸　ｏＧ＾＾霹　扼　Ｔ１ｊ　。（　＾Ｇ翻　粗　ｒ　＿Ｇ姚　Ｇ０　巳　＿＾＾＾ＪＵ　ＣＧＧａ．＾＾阳　ａＷＧ．ｆ＾＾　０　ＴＯ　ｒＩ析ＣＣ　量最大，我们选用它的启动子结合位点进行检验。实验中，初始　ｌｌ口ｃＸ　Ｔ｜＇１　＾０　ｒ．１了ＯＧ０　ＨＴ｛瓠ｔ　ＣＷ０踟　掏日　ａｄ　匹　；０Ｃ　特征矩阵Ｍｂｅｓｔ由随机数构成，该特征矩阵包含了２０组初始　Ｍｏｔｉｆ，然后分别让ＡＣＲＲ算法和以Ｃｏｎｓｅｎｓｕｓ为代表的贪心算法　Ｂ０　癌Ｉ腿　Ｃ　巳ＵＬＴｎ∞。ｃ：ｃ　Ｇ＾　¨　ｎＴ　￡＾ⅡＧ戏　Ｏ０∞　．Ｉ＝　ｆ＾ＧＣｒＧｒ　以这２０组模体为初始模体，进行求解，表７所示为实验结果的　ＥＣ０Ｌ＾ｃ　比较。从表７可以看到，在这组数据上，本文算法ＡＣＲＲ的运行　盯。口１ｅＯＧＧＣ　０嗣　Ｇ矸ａ∞譬Ｋ为矗衄了Ｇ　赫　ＣＧＧ　＾Ｃ　蛭叮ＴＣ：＾Ｃ　＾Ｃ　广ｌ＾ＣＯ０ｏｃ：＾＾耵ａ奄ｒ从Ｃ　０＾Ｉ警静＝＾Ｃ＾ｃＩ　ＧｅＧ＾Ｏ　譬　ＧＧＢｃｃ式　速度是贪心算法的８—１２倍，充分说明本文算法在运行效率上　ＥＯ∞　’ＬＢ＾　ＧＧＧＣ＾＾Ｉ　ＧＧ　ＧＧ　Ｕ　＾ＧＧｎ＿ＧＣｃ（找艄　＾＾Ｉ麓　＾Ｉ奠ｈ＾　＿ｃｃＩ嚣ｒ酗．　的优越性。　ＥＣＤ】山吼Ｂ＾２　表７　ＡＣＲＲ与贪心法的运行时间比较　＾＾＝　ＣＧ飘　Ｔ　Ｘ　馥　＾　ＣＧｒ《粥船Ｇ　ｆ１Ｔ酗掰０Ｃ０Ｃ＾　编号　迭代次数　ＡＣＲＲ　贪心算法　Ｇ舡℃　戈　：ｃ　ｎ　Ｋ　嚣１Ｇ　＾　．＾＾ＡＧｘ　∞ａＧ　ＧＴｃ　￡＾ｃ＾Ｇ　￡００Ｍ札Ｔ　Ｔｏ　ｕ　Ｂ　￡＾１　＾＾｜　ｕＩｃ　ｃＧｃ玎　ｃ超　＾￡　＾＾ＧＧＪｎ　｛岛　单位：毫秒　单位：毫秒　ＧＣ　＾．＾　Ｕ　！ｊ　｜ｃ颤＾Ｃａ　醵＾ＧＵ　ＡＣ嚣蕾阿丁ｒＴ　孵Ｇ０Ｃｒ　１　４０　１８９　１８７５　Ｅｏ　∞－￡隧　Ｇ＾Ｉ　；ｃ　Ｇｎ℃＾Ｉ　ｇ　＾ＧｎＴ　＾Ｃ酗ｌｃＧｎＧ　执Ｃ玎Ｔ＾ｅ　。就　２　２２　１０７　１０３１　３　２６　１０３　１０７８　表５　ＡＣＲＲ与常用算法的实验结果比较　４　２２　９６　１０６２　卑列　馒点　ｏｉｂｂｌ差别　ＡＨｇｎＡｃＥ　差别　ＭＥＭＥ差别　ＡＣＲＲ差荆　５　２０　８７　８７５　Ｓａｍｐｌ￣　６　２３　１０１　ｌｏｏＯ　１　ｌ７．６ｌ　５９　．２　６３　２　６１　０　６３　２　２　ｌ　５５　５３　之　５７　２　５５　０　３７　２　７　２５　１０３　１２３５　３　７６　７｜　＿２　７５　２　７６　０　７８　２　８　３２　１６９　１６４０　－　４　６３　５９　．４　６５　２　６３　０　６５　２　９　２８　１３３　ｌ３１３　５　５ｏ　１１　－３９　Ｓ２　２　ｔ３　．３７　５２　２　１０　２８　１２５　１２５０　６　７．６ｏ　５　・２　９　２　７　Ｏ　９　２　１１　２２　９４　９８４　７　４２　４０　－２　２６　．１６　４２　０　４４　２　１２　２４　ｌ１９　１３１３　８　３９　３７　－２　４ｌ　２　３９　０　４１　２　９　９．８Ｏ　７　＿２　ｌｌ　２　９　０　１１　２　ｌ３　３０　１４０　１４８４　１０　ｌ４　ｌ２　－２　１６　２　１４　０　１６　２　１４　２４　１０７　１１４１　ｌｌ　６Ｉ　５９　－２　６３　２　３５　．】６　６３　２　１５　２５　１３０　１３２８　１２　４ｌ　４７　６　‘４３　２　３４　－７　４３　２　１６　２２　１０１　１０１６　ｌ３　４雹　４６　－２　５０　２　４８　０　５０　２　１７　２６　１０７　１１０９　ｌ４　７ｌ　６９　．２　７３　２　７ｌ　Ｏ　７３　２　１８　２５　１０７　１１０９　１５　ｌ７　ｌ５　．２　ｌ９　２　７５　５８　ｌ９　２　ｌ６　Ｓ３　４９　－４　５５　２　６　－４７　５５　２　１９　２８　１２４　１２３５　ｌ７　１．８４　２５　２４　６ｇ　．１６　２７　２６　９５　４　２０　２９　１２２　１２８１　ｌ８　７８　７４　－４　８Ｏ　２　ｌ６　．２　７８　０　我们还将结合算法ＡＣＲＲ与ＡｌｉｇｎＡＣＥ、ＭＥＭＥ、Ｇｉｂｂｓ　Ｓａｍ—　由表５可知，ＭＥＭＥ　（ｈｔｔｐ：／／ｍｅｍｅ．ｎｂｅｒ．ｎｅｔ／ｍｅｍｅ４—４一　ｐｌｅｒ等算法进行运行时间的比较，表８给出了各种算法对大肠　Ｏ／ｉｎｔｒｏ．ｈｔｍ１）有５条序列的识别结果是错误的，它们是第５、１１、　杆菌ＣＲＰ结合位点检测钓实验时间。从表８可以看到，本文算　ｌ５、１６、１７条，和已知位点的差距在１０以上。类似地，Ｇｉｂｂｓ　法ＡＣＲＲ的运行速度均比其他算法要快的多。例如，它比Ｇｉｂｂｓ　Ｓａｍｐｌｅｒ［１０］（ｈｔｔｐ：／／ｂａｙｅｓｗｅｂ．ｗａｄｓｗｏｒｔｈ．ｏｒｇ／ｇｉｂｂｓ／ｇｉｂｂｓ．ｈｔｍ１）　Ｓａｍｐｌｅｒ算法快１０倍以上，充分说明本文算法在运行效率上的　２８　计算机应用与软件　２０１３丘　优越性。　表８　ＡＣＲＲ与常用算法的实验时间比较　ＡｌｉｇｎＡＣＥ　ＭＥＭＥ　Ｇｉｂｂｓ　Ｓａｍｐｌｅｒ　ＡＣＲＲ　编号　迭代次数　单位：毫秒　单位：毫秒　单位：毫秒　单位：毫秒　１　４０　１５６５　１９ｌ２　１８９０　ｌ７９　２　２２　９４８　ｌ２３１　１０４８　１０１　３　２６　８９７　１３０４　１１Ｏ１　９９　４　２２　８４３　１２３９　１０７２　９２　５　２０　５２７　９８７　９０３　８３　６　２３　７２３　１１０５　１Ｏ２ｌ　９７　７　２５　１００１　１４０７　１３９５　９１　８　３２　１２１４　１８４２　１６４０　１５５　９　２８　９９８　１４７９　１２９８　ｌ１９　１０　２８　９９８　１２５０　１２５７　１１１　１１　２２　６２３　１０８４　９９２　８０　ｌ２　２４　１２２３　ｌ５ｌ２　１２７９　１０５　１３　３０　ｌ１００　１６２０　１３４８　ｌ２６　１４　２４　８４ｌ　１１４８　１０３７　９３　ｌ５　２５　１２３２　１４９１　１３８５　ｌ１６　１６　２２　７０４　１２３０　１０５４　８７　１７　２６　８１１　ｌ１５６　’ｌ０６３　９３　１８　２５　７９７　１００９　９８２　９１　本文算法ＡＣＲＲ比其他算法有较高的优化能力，是因为这　些算法解决元件的结合位点问题时大都采用局部搜索算　法，不能保证得到最优解，而且时间复杂度相当高。本文算法　ＡＣＲＲ利用蚁群算法强大的优化能力可以很好的避免过早陷入　局部最优，并且大大提高了运行效率。　５　结语　针对目前已有的基因元件识别算法大都存在得不到全　局最优解以及时间复杂度高等问题，本文提出了一种新型识别　算法ＡＣＲＲ，即基于蚁群算法来查找结合位点的计算方法。与　已有算法相比，该方法可以避免过早陷入局部最优，既保证了解　的质量，又大大降低了算法的时间复杂度。通过对当前通用的　两组标准测试数据，即啤酒酵母菌的五个典型的结合位点基因　和大肠杆菌中包含ＣＲＰ结合位点的１８条基因进行测试，结果　表明本文算法是非常有效的，对ＣＲＰ结合位点的预测准确度要　高于流行软件，且具有较高的识别速度。　参考文献　［１］马志强，崔颖，马雅楠，等．基因非编码区与转录元件的识别研　究［Ｊ］．生物物理学报，２００８（４）：４５—４７．　［２］候琳，钱敏平，朱云平，等．转录因子结合位点生物信息学研究进展　［Ｊ］．遗传，２００９，３１（４）：３６５—３７３．　［３］Ｑｉｕ　Ｐ．Ｒｅｃｅｎｔ　ａｄｖａｎｃｅｓ　ｉｎ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｐｒｏｍｏｔｅｒ　ａｎａｌｙｓｉｓ　ｉｎ　ｕｎｄｅｒ－　ｓｔａｎｄｉｎｇ　ｔｈｅ　ｔｒａｎｓｃｒｉｐｔｉｏｎａｌ　ｒｅｇｕｌａｔｏｒｙ　ｎｅｔｗｏｒｋ［Ｊ］．Ｂｉｃｏｈｅｍ　Ｂｉｏｐｈｙｓ　Ｒｅｓ　Ｃｏｍｍｕｎ，２００３，３０９：４９５—５０１．　［４］李婷婷，蒋博，汪小我，等．转录因子结合位点的计算分析方法　［Ｊ］．生物物理学报，２００８，２４（５）：３３４—３４７．　［５］Ｓａｕｒａｂｈ　Ｓｉｎｈａ，Ｍａｒｔｉｎ　Ｔｏｍｐａ．Ａ　ｓｔａｔｉｓｔｉｃａｌ　ｍｅｔｈｏｄ　ｆｏｒ　ｆｉｎｄｉｎｇ　ｔｒａｎ—　ｓｃｒｉｐｔｉｏｎ　ｆａｃｔｏｒ　ｂｉｎｄｉｎｇ　ｓｉｔｅｓ［Ｃ］／／Ｐｒｏｃ．Ｉｎｔ．Ｃｏｎｆ．Ｉｎｔｅｌ１．Ｓｙｓｔ．Ｍｏｌ　Ｂｉｏ１．，２０００．ＩＳＭＢ’００，８（２０００）：３４４—３５４．　［６］Ｃａｒｄｏｎ　Ｌ，Ｓｔｏｒｍｏ　Ｇ．Ｅｘｐｅｃｔａｔｉｏｎ　ｍａｘｉｍｉｚａｔｉｏｎ　ｆｏｒ　ｉｄｅｎｔｉｆｙｉｎｇ　ｐｒｏｔｅｉｎ—　ｂｉｎｄｉｎｇ　ｓｉｔｅｓ　ｗｉｔｈ　ｖａｒｉａｂｌｅ　ｌｅｎｇｔｈｓ　ｆｒｏｍ　ｕｎａｌｉｇｎｅｄ　ＤＮＡ　ｆｒａｇｍｅｎｔｓ［Ｊ］．　Ｊ．Ｍｏｌ　Ｂｉｏｌ，１９９２，２２３：１５９—１７０．　［７］Ｌａｗｒｅｎｃｅ　Ｃ，Ｒｅｉｌｌｙ　Ａ．Ａｎ　ｅｘｐｅｃｔａｔｉｏｎ　ｍａｘｉｍｉｚａｔｉｏｎ（ＥＭ）ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ａｎｄ　ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ｏｆ　ｃｏｍｍｏｎ　ｓｉｔｅｓ　ｉｎ　ｕｎａｌｉｇｎｅｄ　ｂｉｏ—　ｐｏｌｙｍｅｒ　ｓｅｑｕｅｎｃｅｓ［Ｊ］．Ｐｒｏｔｅｉｎｓ，１９９０，７：４１—５　１．　［８］Ｌｉｕ　Ｊ，Ｎｅｕｗａｌｄ　Ａ，Ｌａｗｒｅｎｃｅ　Ｃ．Ｂａｙｅｓｉａｎ　ｍｏｄｅｌｓ　ｆｏｒ　ｍｕｌｔｉｐｌｅ　ｌｏｃａｌ　ｓｅ—　ｑｕｅｎｃｅ　ａｌｉｇｎｍｅｎｔ　ａｎｄ　Ｇｉｂｂｓ　ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ［Ｊ］．Ｊ　Ａｍ　Ｓｔａｔ．Ａｓ—　ＳＯＣ．，１９９５，９０（４３２）：１１５６—１１７０．　［９］Ｒｏｔｈ　Ｆ　Ｐ，Ｈｕｇｈｅｓ　Ｊ　Ｄ，Ｅｓｔｅｐ　Ｐ　Ｗ，ｅｔ　ａ１．Ｆｉｎｄｉｎｇ　ＤＮＡ　ｒｅｇｕｌａｔｏｒｙ　ｎｏ—　ｔｉｆｓ　ｗｉｔｈｉｎ　ｕｎａｌｉｇｎｅｄ　ｎｏｎｃｏｄｉｎｇ　ｓｅｑｕｅｎｃｅｓ　ｃｌｕｓｔｅｒｅｄ　ｂｙ　ｗｈｏｌｅ—ｇｅｎｏｍｅ　ｕｔＲＮＡ　ｑｕａｎｔｉｔａｔｉｏｎ［Ｊ］．Ｎａｔ．Ｂｉｏｔｅｃｈｎｏｌ，１９９８，１６（１０）：９３９—９４５．　［１　０］Ｎｅｕｗａｌｄ　Ａ　Ｆ，Ｌｉｕ　Ｊ　Ｓ，Ｌａｗｒｅｎｃｅ　Ｃ　Ｅ．Ｇｉｂｂｓ　ｍｏｔｉｆ　ｓａｍｐｌｉｎｇ：ｄｅｔｅｃｔｉｏｎ　ｏｆ　ｂａｃｔｅｒｉａｌ　ｏｕｔｅｒ　ｍｅｍｂｒａｎｅ　ｐｒｏｔｅｉｎ　ｒｅｐｅａｔｓ［Ｊ］．Ｐｒｏｔｅｉｎ　Ｓｃｉ．，２００４，４　（８）：１６１８—１６３２．　［１　１］Ｂａｉｌｅｙ　Ｔ　Ｌ，Ｅｌｋａｎ　Ｃ．Ｆｉｔｔｉｎｇ　ａ　ｍｉｘｔｕｒｅ　ｍｏｄｅｌ　ｂｙ　ｅｘｐｅｃｔａｔｉｏｎ　ｍａｘｉｍｉｚａ—　ｔｉｏｎ　ｔｏ　ｄｉｓｃｏｖｅｒ　ｍｏｔｉｆｓ　ｉｎ　ｂｉｏｐｏｌｙｍｅｒｓ［Ｃ］／／Ｐｒｏｃ．Ｉｎｔ．Ｃｏｎｆ．Ｉｎｔｅｌ１．Ｓｙｓｔ．　Ｍｏ１．Ｂｉｏ１．１９９４，２：２８—３６．　［１２］周强．转录序列数据挖掘研究与实现［Ｄ］．上海：复旦大学，　２００８．　［１３］王红岩：基于图聚类的转录因子结合位点识别方法的研究ｌ　Ｄ］．　长春：东北师范大学，２０１０．　［１４］李群．基于基因表达谱数据预测转录因子和转录元件活　性［Ｄ］．上海：复旦大学，２０１０．　［１　５］Ｋｒｚｙｓｚｔｏｆ　Ｓｏｃｈａ，Ｍａｒｃｏ　Ｄｏｒｉｇｏ．Ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　ｃｏｎｔｉｎｕｏｕｓ　ｄｏｍａｉｎｓ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，２００８，１　８５　（３）：１１５５—１１７３．　［１　６］Ｚｈｕ　Ｊ，Ｚｈａｎｇ　ＭＱ．ＳＣＰＤ：ａ　ｐｒｏｍｏｔｅｒ　ｄａｔａｂａｓｅ　ｏｆ　ｔｈｅ　ｙｅａｓｔ　Ｓａｃｃｈａｒｏ—　ｍｙｃｅｓ　ｃｅｒｅｖｉｓｉａｅ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，１９９９，１５：６０７—６１１．　［１　７］Ｈｅｒｔｚ　Ｇ　Ｚ，Ｓｔｏｒｍｏ　Ｇ　Ｄ．Ｉｄｅｎｔｉｆｙｉｎｇ　ｐｒｏｔｅｉｎ・ｂｉｎｄｉｎｇ　ｓｉｔｅｓ　ｆｒｏｍ　ｕｎａ—　ｌｉｇｎｅｄ　ＤＮＡ　ｆｒａｇｍｅｎｔｓ［ｃ］／／Ｐｒｏｃ　Ｎａｔｌ　Ａｃａｄ　Ｓｃｉ　ＵＳＡ．１９８９，８６（４）：　ｌ１　８３一１］８７．　（上接第１５页）　［６］Ｃｈｅｎ　Ｙ，Ｃｈｅｎ　Ｈ，Ｃｌａｒｋ　Ｄ，ｅｔ　ａ１．Ｓｏｆｔｗａｒｅ　ｅｎｖｉｒｏｎｍｅｎｔｓ　ｆｏｒ　ｃｌｕｓｔｅｒ－ｂａｓｅｄ　ｄｉｓｐｌａｙ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｆｉｒｓｔ　ＩＥＥＥ／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｌｕｓｔｅｒ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　ｔｈｅ　Ｇｒｉｄ，２０１　１　Ｍａｙ．　［７］Ｃｈｅｎ　Ｈ，Ｓｕｋｔｈａｎｋａｒ　Ｒ，Ｗａｌｌａｃｅ　Ｇ，ｅｔ　ａ１．Ｓｃａｌａｂｌｅ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｌａｒｇｅ—　ｆｏｒｍａｔ　ｍｕｌｔｉ—ｐｒｏｊｅｃｔｏｒ　ｄｉｓｐｌａｙｓ　ｕｓｉｎｇ　ｃａｍｅｒａ　ｈｏｍｏｇｒａｐｈｙ　ｔｒｅｅｓ［Ｃ］／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　Ｖｉｓｕａｌｉｚａｔｉｏｎ，２００２：３３９—３４６．　［８］Ｒｅｎａｍｂｏｔ　Ｌ，Ｒａｏ　Ａ，Ｓｉｎｇｈ　Ｒ，ｅｔ　ａ１．ｔｈｅ　ｓｃａｌａｂｌｅ　ａｄａｐｔｉｖｅ　ｇｒａｐｈｉｃｓ　ｅｎｖｉ－　ｏｒｎｍｅｎｔ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＷＡＣＥ　２００４：２３—２４．　［９］Ｈｕｍｐｈｒｅｙｓ　Ｇ，Ｈｏｕｓｔｏｎ　Ｍ，Ｎｇ　Ｒ，ｅｔ　ａ１．Ｃｈｒｏｍｉｕｍ：ａ　ｓｔｒｅａｍ—ｐｒｏｃｅｓｓｉｎｇ　ｒｆａｍｅｗｏｒｋ　ｆｏｒ　ｉｎｔｅｒａｃｔｉｖｅ　ｒｅｎｄｅｒｉｎｇ　ｏｎ　ｃｌｕｓｔｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｓｉｇｇｒａｐｈ，２００２：６９３—７０２．　［１０］Ｄａｔａｔｏｎ　Ｉｎｃ【ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｄａｔａｔｏｎ．ｃｏｍ／．　［１　１］Ｌｉ　Ｃ，Ｌｉｎ　Ｈ，Ｓｈｉ　Ｊ．Ａ　ｓｕｒｖｅｙ　ｏｆ　ｍｕｌｔｉ－ｐｒｏｊｅｃｔｏｒ　ｔｉｌｅｄ　ｄｉｓｐｌａｙ　ｗａｌｌ　ｃｏｎ－　ｓｔｍｃｔｉｏｎ［Ｃ］／／Ｔｈｉｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　ａｎｄ　Ｇｒａｐｈｉｃｓ，　２００４：４５２—４５５．　［１２］Ｂｉｍｒａｎ　Ｋ　Ｐ．Ｒｅｌｉａｂｌｅ　Ｄｉｓｔｉｒｂｕｔｅｄ　Ｓｙｓｔｅｍ：Ｔｅｃｈｎｏｌｏｇｉｅｓ，Ｗｅｂ　Ｓｅｒｖｉｃｅｓ，　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｓｐｒｉｎｇｅｒ，Ｍａｒｃｈ　２５，２００５．　［１３］Ｍｉｃｒｏｓｏｆｔ　ＤｉｒｅｃｔＸ［ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｍｉｎ＇ｏｓｏｆｔ．ｅｏｍ／ｗｉｎｄｏｗｓ／ｄｉｒｅｃｔｘ．