（计算机科学与技术专业论文）基于频繁模式挖掘的双植入位点查找算法研究.pdf

摘要 随着计算机技术和生物医学的飞速发展，人类对于基因表达和遗传信息的传递 有了更高的认识，越来越多的学者开始关注d n a 序列中控制基因表达的植入位点 发现问题的研究。 本文对d n a 序列植入位点和数据挖掘技术等相关理论进行了深入的探讨，充 分总结归纳了目前植入位点发现问题研究领域的最新研究成果，并针对高等生物 中普遍存在的双植入位点查找问题，设计并实现了基于频繁模式挖掘算法思想的 d a p r i o r i 算法。首先，基于对d n a 单链中碱基序列具有“近似频繁模式”特性的 认识，本文重点分析了结合a p r i o r i 算法的下封闭特性和f p g r o w t h 算法的树型压 缩结构的b p r i o r i 算法，并将其成功应用于解决双植入位点查找问题中。其次，设 计并实现了d s p a c e 算法，实现单植入位点的拼接，从而有效地完成双植入位点 的查找工作。将d a p r i o r i 算法分别在人工合成数据集和真实数据集上进行了大量 的实验，实验结果表明：d a p r i o r i 算法在保证准确率的前提下，可以查找到所有 满足要求的并且模式长度未知的双植入位点结构。 本课题的研究成果不仅对于解决d n a 中查找双植入位点问题有着良好的性能 优势，并且还可以应用到数据挖掘领域中所有关于解决字符串查找问题的研究中。 对于进一步描绘和预测生物基因表达提供理论工具，为人类疾病的预防、发现及 治疗提供更直接有效的手段，从而更好地促进生物信息学和医学领域的发展。 关键词：双植入位点；数据挖掘；频繁模式；b p r i o r i 算法；d a p r i o r i 算法；d s p a c e 算法 分类号：t p l 8 2 = 竖塞銮道厶堂亟堂位论塞 旦墨! 垦王 a bs t r a c t w i t ht h eg r e a t d e v e l o p m e n to fn e wt e c h n o l o g y i n c o m p u t e r s c i e n c ea n d b i o m e d i c i n ei n d u s t r yd o m a i n ，t h es e c r e t so fh u m a ng e n ee x p r e s sa n dt h et r a n s l a t i o no f g e n e t i ci n f o r m a t i o nh a v eb e e nd i s c o v e r e do v e ra n do v e r , m o r ea n dm o r ef o r e s i g h t e d s c i e n t i s t sc o n c e n t r a t et h e i rr e s e a r c h e s o n s o l v i n g p l a n t e dm o t i f f i n d i n g p r o b l e m ( p m f p ) ，w h i c hc o n t r o l st h eg e n ee x p r e s si nd n al i n e i n t h i st h e s i s ，d n al i n ep l a n t e dm o t i f , d a t am i n i n gt e c h n o l o g y , a n ds o m eo t h e r r e l e v a n tt h e o r i e sw o u l db ef u l l yd i s c u s s e d w ea l s om a k eas u f f i c i e n ts u m m a r yo ft h e l a t e s tr e s e a r c hf i n d so np m f p u s i n gf r e q u e n tp a t t e r nm i n i n ga l g o r i t h mt os o l v e d o u b l e b l o c kp l a n t e dm o t i fp r o b l e m ( d b p m f p ) w h i c ha p p e a r e dm o r ef r e q u e n t l y a m o n gh i g h e ro r g a n i s m sn a m e dd - a p r i o r ia l g o r i t h mw o u l db ei n t r o d u c e di nd e t a i la s w e l l a sw ea l lk n o w , d n ab a s i cs e q u e n c eh a v i n g “a p p r o x i m a t ef r e q u e n tp a r e m c h a r a c t e r i s t i c si nt h ed n as i n g l e - c h a i n ，t h e r ea r et w oc l a s s i ca l g o r i t h m s ，a p r i o r i a l g o r i t h ma n df p g r o w t ha l g o r i t h m ，w h i c hu s ef r e q u e n tp a t t e r nt h e o r y , w o u l db e r e f e r r e da n da n a l y z e di no u rr e s e a r c h b a s e do nt h ea d v a n c e dc h a r a c t e r i s t i c ss u c ha s s e a l i n gp r o p e r t yo fa p r i o r ia l g o r i t h ma n dc o m p r e s s e ds t r u c t u r et r e ep r o p e r t yo f f p g r o w t ha l g o r i t h m ，w eu s eb p r i o r ia l g o r i t h mi nf i n d i n gp l a n t e dm o t i f if u r t h e r m o r e ， e f f i c i e n ts p l i c i n go fs i n g l e - b l o c kp l a n t e dm o t i f u s i n gd s p a c ea l g o r i t h mi sa p p r o v e dt o b ee f f i c i e n ti nf i n d i n gd o u b l e b l o c kp l a n t e dm o t i f u n d e rt h el a r g ea m o u n to fv a l i d a t e t e s t i n gb yu s i n gs y n t h e t i cd a t as e t sa n dr e a ld a t as e t sr e s p e c t i v e l y , t h ea l g o r i t h mw e p r o p o s e di sa p p r o v e db ye x p e r i m e n t st h a ti tc o u l dp r o v i d ea ns u c c e s s f u ls o l u t i o ni n f i n d i n gd o u b l e p l a n t e dm o t i f sw i t ht h e i rl e n g t h sb e i n gu n k n o w na n dm e e t i n ga l lt h e r e q u i r e m e n t s t h er e s u l t so ft h i st o p i cn o to n l yh a v eap e r f o r m a n c ea d v a n t a g eo fs o l v i n g p r o b l e m si nf i n d i n gd o u b l e b l o c kp l a n t e dm o t i fi nd n al i n e ，b u ta l s oc o u l db ea p p l i e d t oa l lo ft h er e s e a r c h e sa b o u tf i n d i n gas o l u t i o nt ot h ei s s u eo fs t r i n gi nd a t am i n i n ga r e a a sat h e o r e t i c a lt o o lf o rf u r t h e rd e s c r i b i n ga n dp r e d i c t i n gb i o l o g i c a lg e n ee x p r e s s i o nf o r h u m a nd i s e a s ep r e v e n t i o n ，d e t e c t i o na n dt r e a t m e n t ，t h e s er e s u l t sp r o v i d em o r ed i r e c t a n de f f e c t i v es o l u t i o n s a sar e s u l t ，t h i sp r o d u c t i o nc o u l da c c e l e r a t et h ed e v e l o p m e n ti n t h ef i e l do f b i o i n f o r m a t i c sa n dm e d i c a l k e y w o r d s ：d o u b l e - b l o c kp l a n t e dm o t i f ；d a t am i n i n g ；f r e q u e n tp a t t e r n ；b p r i o r i a l g o r i t h m ；d - a p r i o r ia l g o r i t h m ；d - - s p a c ea l g o r i t h m c l a s s n o ：t p l8 2 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：杨琳琳签字同期：2 0 0 9 年6 月1 6 同 栖琳抓 6 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：易钥朱抓 签字同期：7 叨净6 月形同 翩獬：梳 芝夕jf ? 1l 磐嗍下月歹同 i j 致谢 本论文的工作是在我的导师黄厚宽教授和贾彩燕老师的悉心指导下完成的， 黄教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响，黄教授对于 我的科研工作和论文都提出了许多的宝贵意见，在此向黄教授表示衷心的感谢! 同时，贾彩燕老师在整个论文研究过程给予了耐心的指导和帮助，帮我在研 究课题进行了详尽的介绍和分析，尤其是算法的实现过程给予了细致的指导，并 对本论文提出了许多的宝贵意见和建议，在此我对贾老师在研究课题中给予的帮 助表示诚挚的谢意! 在论文的写作过程中，瞿有利老师给予我很大的帮助和指导，让我对整个课 题有了深一步的把握和理解，在此表示深深地谢意! 在实验室工作及撰写论文期问，王智飞、邓瑞龙等同学对我论文中的结构和 格式等工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 序 本文是一篇研究性的论文，首先从总体上介绍了生物信息学中植入位点的概 念，查找植入位点算法的研究现状等，然后对现有的经典算法进行分析，提出了 解决查找d n a 中双植入位点的总体思想，并形成数据模型、实现算法，最后分别 利用生成的测试数据集和真实数据进行实验，并对实验结果进行分析比较。 生物信息学的快速发展推动了医学研究的发展，但是由于生物信息处理自身 的复杂性，现阶段国内外对于查找d n a 序列中植入位点的研究并不很理想，已有 的算法对于大规模的数据集的处理能力还很有限，结合已有的数据挖掘方法本身 多具有的高效性和扩展性，所以本文采用频繁模式的挖掘算法来解决更有普遍意 义的查找双植入位点的问题，并在相应的章节中详细介绍了数据模型以及两部分 核心算法，并自行设计、实现及优化。同时，进行了大量的数据测试，证明了算 法的扩展性和效率都在一定程度上达到了应用的水平。 本文旨在设计和实现一个有效的查找d n a 序列中双植入位点的算法模型，并 结合流程图、图表及实验结果等，对算法性能进行详细的阐述和分析，在设计和 实现过程中，利用了一些经典数据挖掘算法和已有的解决植入位点发现问题的算 法。 1 综述 1 1研究背景 长久以来，人类都在不断地探索我们所处的这个复杂的物质世界，科学技术 的每一次进步，都极大的带动了周围事物及相关学科水平的提高。上世纪5 0 年代 起，d n a 双螺旋结构模型的发现、人类基因组测序任务的完成揭丌了分子生物学 和生命科学历史的新篇章，标志着人类丌始进入改造、设计生命的征程。计算机 技术的迅猛发展，丌创了生物信息科学发展的新时代，为生物学和医学的研究带 来了前所未有的机遇和挑战。数据挖掘技术的发展，使海量的生物信息处理和发 现变成了可能，从此生物信息学便在计算机技术和生物学发展的基础上迅速成长， 通过对遗传信息载体d n a 和生命功能的体现者蛋白质进行研究，力图在大规模的 生物数据中提取有用的知识和原理，并希望预测和发现更复杂的生命信息，解读 与人类疾病相关的功能基因，从而可以更好的正确把握现代生命科学发展的规律 和方向。 植入位点发现问题作为信息科学的一个重要研究方向，它从最根本的基因功 能入手，采用高效的数据挖掘技术，在大规模的d n a 数据集中寻找控制基因表达 的植入位点模式，有利于寻找其与遗传疾病之间的对应关系，进而通过人为地改 变植入位点结果来控制基因的表达，从而干预或治愈疾病。 1 2研究现状及存在问题 从人类基因组计划开始，越来越多的研究关注于承载生命体遗传信息的d n a 序列的翻译和表达过程，而在这些研究中，在控制基因表达过程中起决定性作用 的植入位点的发现问题是整个生物信息学研究的主要内容之一。 目前，对于单植入位点发现问题的研究已经有很多，但在自然界中，对于和 我们关系更加密切的高等生物来说，基因的转录过程经常是由多个邻近的d n a 片 段共同作用来控制性状的表达，而其中某些特殊的二聚体是由两部分d n a 片段交 叉形成的螺旋结构，即双植入位点共同控制基因的表达，它在生物遗传过程中起 着非常重要的意义。因此，越来越多的学者开始关注查找长度已知的双植入识别 位点的发现问题上，并提出了一些可行的解决方案。然而，对于实际的生物学研 究，真实植入位点的长度事先很难被确定，如何在不确定植入位点长度的情况下 准确的查找隐藏在生物遗传信息中的双植入位点是本课题的研究重点。 现阶段用于解决植入点查找问题的算法，大部分算法都是采用从头算的思想， 根据对植入位点建模方法的不同将已有算法分为启发式枚举方法，如p e l l e r 口3 、 m i t r a n 3 算法和位置权重矩阵优化方法，如m e m e m l 、c o n s e n s u s t 2 3 】算法等。它 们将计算机技术很好的应用到解决生物信息学的实际问题中，并且预测结果显示 在识别m o t i f 的过程中精确度还比较高，但是由于背景序列的影响，对于不同的数 据集，预测结果准确度可能并不一样，对于变异点个数越多的植入位点，背景序 列的影响越大，查找过程越复杂，准确度也越低。因此，这一问题的研究还需要 很长的路要走。 现有的大量算法虽然在查找单个m o t i f 时的速度比较快，具有较低的计算复杂 度，适合在大空问中搜索解，但在实际应用中不具有普遍性意义，在查找复杂结 构的位点时有很大的局限性和约束性，可扩展性较差，并且容易陷入局部最优解 而找不到问题的精确解。而对于可用来查找多个m o t i f 的算法，虽然具有很好的普 遍性，但是对常规现象的针对性弱，算法的效率比较低，耗费的资源也比较大， 搜索到的假阳性结果较多。 本课题主要研究在生物中更为普遍的在模式长度未知的情况下查找双植入位 点问题，借助于数据挖掘中高效的频繁模式挖掘算法，将陆汝钤院士等人在2 0 0 5 年提出的b p r i o r i 5 】算法成功应用到解决双植入位点发现问题( d o u b l e b l o c kp l a n t e d m o t i f f i n d i n gp r o b l e m ，d b p m f p ) 中，因而具有普遍性和针对性等特点，算法的 时空效率较好，可扩展性较高。 1 3论文的主要工作及结构安排 1 3 1主要研究工作 在数据挖掘领域中，所要研究数据的特点会直接影响到将采用何种数据挖掘 算法和数学模型。本文主要研究如何高效和准确的发现隐藏在生物体d n a 序列中 位于基因上游的控制基因翻译的识别位点( m o t i f ) 问题。首先，生物体中存在大 量的不同结构的同源m o t i f , 并且这些同源的m o t i f 在各条d n a 序列中分布的位 置不尽相同；同时，由于d n a 序列中的脱氧核苷酸因子( a ，t ，gc ) 存在突变现 象，同源m o t i f 在各条d n a 序列中虽然基本上满足一定的突变概率出现，但实际 存在的情况却多种多样。因此，本文要在大量的d n a 序列中找到同源的m o t i f 的 同时，确定此m o t i f 在每条d n a 序列中发生突变后的实际植入m o t i f 以及其具体 位置分布。 2 首先，本文简要介绍了生物信息学和计算机科学的发展现状及相关理论基础， 分析当前本课题的研究意义及其实际的社会效益。生物信息学和计算机科学的良 好结合为医疗技术的发展提供了更为广阔的平台，从而更好地提高医疗技术水平。 其次，根据生物体d n a 序列在其单链中所表现的“近似频繁模式”特性，为 了使研究的问题更具有普遍性和应用性，设计和实现d n a 序列发生器，生成大量 可控的测试数据集，因而实验结果更具有普遍性。 第三，对目前现有的一些查找单植入位点和复杂的多植入位点的研究方法进 行分析和比较，包括s p e l l e r 、c e n s u s 、m i t r a 、b p r i o r i 等基于一致序列表达 的启发式枚举典型算法和c o n s e n s u s 、g i b b ss a m p l e r 等基于位置权重的局部优 化方法。部分算法将被用于与本文采用的频繁模式挖掘算法在效率和准确度上进 行比较，并通过实验证明频繁模式算法对于解决查找双植入位点问题的优越性， 也为进一步提高算法效率提供了参考依据。 第四，本文通过对关联数据挖掘算法中现有的经典算法和频繁模式挖掘思想 进行深入的分析和研究，充分分析了本文所提出d a p r i o r i 算法对于课题的研究意 义。这部分工作为本文算法的设计和实现提供了合理的依据和思想，同时也为实 验的i l i o n 进行提供了充分的理论准备。 第血，根据本课题的特点设计数据模型并完成高效的搜索算法和拼接算法， 从其时空复杂性能上进行理论分析，并与现有的算法进行比较，详细说明本论文 所提出的算法对于解决查找长度未知的双植入位点问题的优越性。这一部分是整 个文章的核心内容，为今后类似问题的学习和研究都提供了参考依据。 第六，在人工合成数据集和真实数据集上进行大量实验，并分别从算法参数 对效率的影响和相关算法的性能对比等两方面，通过实验数据进行详细的分析和 比较，从而证明采用频繁模式挖掘思想的优越性。 本文利用数据挖掘算法模型解决生物信息学中被普遍关注的双植入位点查找 问题，并通过实验进行验证和比较分析，对算法进行改进和提高，从而提出比现 有算法更有普遍意义的解决问题方案，即d a p r i o r i 算法。本文的贡献在于，将 b p r i o r i 算法中的频繁模式挖掘思想与d s p a c e 拼接算法相结合，成功的应用于解 决在模式长度未知情况下的双植入位点发现问题中，并通过大量的实验进行比较 分析，说明了d a p r i o r i 算法的合理性和有效性。 1 3 2 论文的结构安排 本文的组织和安排如下： 第一章主要介绍了植入位点查找问题的研究背景和内容，以及目前国内外的 研究现状与发展趋势、存在的问题及本文的创新点等。同时对论文的研究工作和 组织安排进行了必要的说明。 第二章主要阐述了本课题研究的理论基础，首先介绍了生物学中相关知识和 基本概念，之后重点探讨了植入位点发现问题( p l a n t e dm o t i ff i n d i n gp r o b l e m ， p m f p ) 的数据定义和特点，并讨论了频繁模式挖掘算法的思想及其对于本课题的 特殊性。 第三章深入分析了现阶段国内外p m f p 领域的研究现状，比较面向单个和复 杂植入位点问题的经典算法，并总结其各自的优缺点，为本课题算法的提出和实 现提供了充分的理论依据。 第四章是本文的核心部分，设计并实现了d a p r i o r i 算法，用于解决在模式长 度未知情况下的双植入位点发现问题，主要包括采用b p r i o r i 算法的搜索过程和 d s p a c e 算法实现的m o t i f 拼接过程，同时对算法的效率进行充分的理论推导。 第五章主要利用人工生成数据和真实数据集进行实验。首先设计人工合成 d n a 数据集合的发生器，包括了单植入位点和双植入位点两种。然后对大量不同 参数集合进行实验，并与相关算法性能进行必要的比较，给出实验结果，并对实 验结果进行了对比分析，阐明本课题在研究更普遍意义的双植入位点问题上存在 的优点和不足。 第六章总结全文，对本课题进行了全面的分析和总结，并指出了存在的一些 的问题，并给出了具体的研究思路和未来的发展方向。 4 2 理论基础 本章将简要介绍课题研究所涉及到的生物信息学和数据挖掘的相关知识和基 本概念。首先，引入植入位点发现问题( p m f p ) 的定义和特征：其次，重点阐述 数据挖掘的基本理论，尤其对关联规则和频繁模式数据挖掘的思想和典型算法进 行深入分析。 2 1生物学理论基础概述 1 生物学基本概念 d n a 分子记录了生物体基本的遗传信息，由两条多核苷酸链通过碱基的互补 配对相互缠绕形成一种双螺旋的结构。它存在4 种核苷酸碱基，分别是两种嘌呤 和两种嘧啶：腺嘌呤( a ) 和鸟嘌呤( g ) ，胸腺嘧啶( t ) 和胞嘧啶( c ) ，如表 2 1 所示。d n a 分子由两条多核苷酸链通过碱基的互补配对相互缠绕形成一种双螺 旋的结构，一个链上的嘌呤总是以氢键与另一个链上的嘧啶相结合，即腺嘌呤( a ) 与胸腺嘧啶( t ) 配对、鸟嘌呤( g ) 与胞嘧啶( c ) 配对。因而，d n a 序列可以 只用一条多核苷酸链上的4 种碱基( a ，t ，gc ) 所形成的线性序列来表示，以后 本文所指的d n a 序列均是这种线性序列。 表2 1d n a 中碱基含义 t a b l e2 1m e a n i n g so fd n ab a s e s 碱基符号d n a 中核苷酸碱基含义 a 腺嘌呤 t 胸腺嘧啶 g 鸟嘌呤 c 胞嘧啶 基因表达是一切生命研究的根本。基因表达是指基因通过不断的转录翻译以 及合成蛋白质的过程，这个过程中起到关键作用的是基因转录过程中的转录因子 结合到识别位点的能力。 转录因子( t r a n s c r i p t i o nf a c t o r ，t f ) 是转录起始过程中r n a 聚合酶所需的 辅助因子。真核生物基因在无转录因子时处于不表达状态，r n a 聚合酶自身无法 启动基因转录，只有当转录因子结合在其识别的d n a 序列上后，基因才开始表达。 5 转录因子结合位点( t r a n s c r i p t i o nf a c t o rb i n d i n gs i t e ，t f b s ) 是转录因子调节 基因表达时，与m r n a 结合的区域( m o t i f ) 。按照常识，转录因子的结合位点一 般应该分布在基因的前端( 如图2 1 ) ，与基因紧相邻接，结合r n a 聚合酶及其辅 助因子，形成r n a 聚合酶转录复合体，引导基因从j 下确的位置开始转录。 图2 1 转录冈子在d n a 中的位置 f i g u r e2 1t h ep o s i t i o no ft r a n s c r i p t i o nf a c t o ri nd n al i n e 植入位点( p l a n t e dm o t i f , p m ) 是指控制相同基因表达的转录因子结合位点 ( 同源m o t i f ) ，在不同的d n a 序列中，由于突变的原因表现出不同的状态。由于 生物自然选择的特性，承载生物体遗传信息的d n a 序列保持高度的一致性，单个 的脱氧核苷酸因子( a ，t gc ) 发生突变的频率很低并保持在一定的范围，使其 与同源的m o t i f 保持很大的相似性。 任何生命体的转录因子在引导基因表达的过程中，如何准确的找到p m 位置 问题，是决定基因能否从正确的位置开始转录的关键。而这些p m 本质上是一些 比较短的字符串序列，它们一般均处在受调控基因的上游区域，转录因子可通过 识别这些m o t i f 并与之结合，来调节d n a 的翻译和转录，由r n a 结合蛋白识别 并与之结合，从而影响r n a 的修饰、定位、翻译和降解。因此，如何准确的识别 和定位植入位点、了解由它们所控制的基因的表达特性，对于理解和解释生物的 遗传变异有着重大的意义。 生物学和计算机学者们一直希望为此找到一种有效的算法，可以方便地预测 并寻找这些隐藏在d n a 序列中，引导生物体基因表达的植入点的位置及序列信息， 这个过程称为植入位点发现问题( p l a n t e dm o t i f f i n d i n gp r o b l e m ，p m f p ) 。 2 植入位点发现问题( p m f p ) 描述 给定一组简单的d n a 序列，如表2 2 所示。这些序列具有如下特点：来自同 一类生物个体、控制相同性状的d n a 序列、每段序列长度相同、含有由同源m o t i f 经过若干变异产生的植入位点等。而p m f p 就是要在这些具有高度相似性的d n a 序列中找出位于基因上游的控制基因表达的重要d n a 序列片段。然而，什么样的 片段彳是包含有效信息的重要片断? 应该如何去界定? 等等这些问题则需要给予 明确的回答。下面本论文将对这些问题进行深入剖析。 6 表2 2 简单的生物d n a 序列 t a b l e2 2as e to fs i m p l ed n a s e q u e n c e s 1 c c t g u a g a c g c l l a t c t g g c l 7 a t c c a c g t a c g t a g g t c c t c t g t g c g a a t c l 7 a i t g c g l l t c c a a c c a t 2 a g l a c t g g t g t a c 戌r 兀g 汀a c g t a c g l a c a c c g g c a a c c t g a a a c a a a c g c t c a g a a c c a g a a g t g c 3 a a a c g l a c g t g c a c c c t c l - r r c t t c g t g g c t c t g g c c a a c g a g g g c t g a t g t 钮a a g a c g a a a a r r 兀 4 a g c c t c c g a t g t a a g t c a t a g c t g t a a c t k r r a c c t g c c a c c c c t a 丁t a c a t c l l a c g t a c g t a t a c a 5 c t g t l l a l a c a a c g c g t c a t g g c g g g g t a t g c g t l l t g g t c g t c g t a c g c t c g a t c g t 下a a c g t a c g t c 从纯算法角度来看，d n a 序列植入位点的预测问题可以转化为一个算法问 题。p e v z n e r 等人在2 0 0 0 年提出了p l a n t e d ( ，d ) m o t i ff i n d i n gp r o b l e m 1 2 】的假设模 型。该模型主要有两个受控因子：，和d 。，表示同源m o t i f 的长度，大量真核生物 种群的m o t i f 长度一般不超过1 5 ，即，1 5 。d 表示植入位点中允许变异核苷酸的 个数，也就是传统意义上的h a m m i n g 距离，现阶段所研究的问题模型中变异核苷 酸的数目一般控制在4 个以内，即d 4 。 h a m m i n g 距离定义如下：设形是由若干个固定字母组成的字符集合，设 口= a l 口2 a i 和b = b , b 2 b j 是两条字符串，其中a i 口2 ，a f ，6 l ，6 2 ，b j w ，若f = ， 这两组字符串之问的距离定义为： 虬 d n ( 口，b ) = 6 ( a i ，包) ( 2 1 ) i = i 其中 f 】x v 万( 训) 2 1 i 其在 ( 2 2 ) 经典p m f p 的描述是：将一个长度为，的d n a 片段( 源m o t i f ) 的个随机 小变异拷贝( d 个变异位点) ，分别植入到条长为三的d n a 序列中；目标是： 在给定参数z 和d ，寻找这个植入m o t i f 及其所有变异拷贝。 通常情况下，一个植入位点发现问题的解决过程主要有以下三个步骤： a 产生候选的同源m o t i f 。 ( 1 ) 给定条输入序列，为要寻找的数据集设计完善的数学模型，并提 供合理的算法参数( 主要有m o t i f 的长度，、植入位点与源m o t i f 相比可变 异的程度d 、m o t i f 的最低保守性阈值p 等) ： ( 2 ) 在输入序列集合中寻找所有高度相似性的、连续的d n a 片段，将每 个d n a 序列片段作为一个候选的同源m o t i f i ( 3 )记录同源m o t i f 在各个d n a 序列中的位置和变异情况。 b 估计每个候选的同源m o t i f 的统计显著性。 7 c 输出显著性最高的同源m o t i f 及其在条d n a 序列中所对应的植入位点 的具体信息。 2 2数据挖掘理论 2 2 1数据挖掘的基本概念 数据挖掘( d a t am i n i n g ，d m ) ，是从存放在数据库、数据仓库或其它信息库中 的大量数据中挖掘有用知识的过程，即从数据库中提取出隐含的、高水平的模式。 它既能查询和遍历过去的数据，又能探寻过去数据之间的潜在关系，从而进行信 息的传递，还可以根据过去的数据对将来进行预测和分类。数据挖掘以模式识别、 统计学、数据库和人工智能等众多学科为基础，是目前国际上数据库和信息决策 系统最前沿的研究方向之一。 作为一个年轻而又充满生机的领域，数据挖掘特别强调发现隐藏在大型数据 集中的有趣数据模式，并用于指导实际应用。近年来，数据挖掘引起了信息产业 界甚至整个社会的极大关注，其主要原因是社会的快速发展导致大量数据的产生， 如何将这些数据转换成有用的信息和知识，这是目前迫切需要解决的现实问题。 数据挖掘可分为两个方向：描述式数据挖掘和预测式数据挖掘。数据挖掘技 术主要有：关联分析、聚类分析、分类、预测等。关联规则是数据挖掘的一个重 要课题，目前已受到越来越多研究者的关注。 由于d n a 序列中的植入位点间保持高度的“近似频繁”特性，本课题将基于 关联挖掘算法中的频繁模式挖掘思想来解决双植入位点的查找问题。 2 2 2数据挖掘的实施步骤 数据挖掘的过程可以分为以下五个步骤，如图2 2 所示。 1 问题分析。清晰地定义问题研究的对象和研究的目的意义，确定要进行数 据挖掘的方法和设计过程等。 2 数据准备。本课题的数据准备过程包括： a 生成测试数据。构造序列发生器，有效的模拟d n a 单链的特点( a ，t q c 随机排列的字符串) ，并且设置不同的m o t i f 长度和允许变异个数d ，从 而生成大量高仿真的测试数据； b 数据预处理。进行数据再加工，包括检查数据的完整性及数据的致性、 去噪声、填补丢失的域、删除无效数据及数据离散化处理等。 3 数据挖掘：根据数据功能的类型和数据的特点选择相应的算法，在进行完 全预处理工作的数据集上进行数据挖掘。 4 结果分析：对数据挖掘的结果进行解释和评价，转换成为能够最终被用户 理解的信息和知识。 5 知识运用：将分析所得到的知识集成到实际应用的问题中去。 图2 2 数据挖掘的实施步骤 f i g u r e2 2s t e p so f d a t am i n i n g 2 3 关联规则挖掘算法 关联规则挖掘思想【2 9 】是由r a g r a w a l 等人在19 9 3 年首先提出并成功的应用到 实际问题中。它是在事务、关系数据库中的项集和对象中发现频繁模式、关联规 则、相关性和因果结构等( 如图2 3 所示) ，是数据挖掘中是一个重要的研究方向。 在关联规则挖掘算法中，一般用支持度和置信度两个阈值来度量关联规则的相关 性，在后来的研究中，不断引入兴趣度等参数，使得所挖掘的规则更符合需求。 9 预处理后数据 图2 3 关联数据挖掘流程 f i g u r e2 3f l o wo f a s s o c i a t ed a t am i n i n g 2 3 1算法的基本概念 关联规则挖掘算法的一个典型例子是购物篮分析。在这个例子中，关联规则 研究有助于发现交易数据库中不同商品( 项) 之间的联系，找出顾客购买行为模 式，如购买了某一商品对购买其它商品的影响等。分析结果可以应用于商品货架 布局、货存安排以及根据购买模式对用户进行归类等实际问题中。 设，= f l ，i 2 ，乙) 是由m 个不同项目组成的项集，其中( 七= 1 ，2 ，聊) 可以是 购物篮中的物品，也可以是保险公司的顾客。给定一个与任务相关的数据集d ， 该数据集是事务数据集，其中的每个事务丁是由，中的一组项目组成的集合，使得 r ，。 假设存在集合彳、b 是由，中的项目组成的事务，即爿，口g ，。关联规则 是蕴涵如下形式的逻辑：ajb ( asi ，bgi ，且a n b = o ) ，并有如下两个重 要属性： 支持度( s u p p o r t ) ：p ( a u a ) ，即a 和b 这两个项集在事务集d 中同时出 现的概率。 置信度( c o n g f i d e n c e ) ：p ( ba ) ，即在出现项集彳的事务集d 中，项集b 也同时出现的概率。 前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规 则的可信程度。支持度和置信度均高的规则才是有用的关联规则，同时满足最小 支持度阈值和最小置信度阈值的规则称为强关联规则。 2 - 3 2算法的基本思想 给定一个事务数据集d ，关联规则挖掘就是产生支持度和可信度分别大于用 户给定的最小支持度和最小可信度的关联规则，也就是产生强关联规则的问题【3 0 】。 目前大部分的关联挖掘算法采用“两步走 策略，如图2 4 所示，其核心部分 1 0 是频繁模式的产生。 1 频繁模式的产生。找到数据集合中所有的频繁项集，即频繁模式。所谓的 频繁模式是指那些支持度大于用户所制定的最小支持度阈值的项集； 2 关联规则的产生。利用找到的频繁模式产生关联规则。即在找到的频繁模 式中寻找满足用户制定的最小置信度阈值的规则。 数据集合酬瓣 m i n s u p p o r t 关联规则 生成锋泫 关联规则 集合 俞m 沁。n 触愀俞 图2 4 关联规则挖掘的基本模型 f i g u r e2 4t h eb a s i cm o d e lf o ra s s o c i a t ed a t am i n i n ga l g o r i t h m 不难看出，在“两步走”策略中，第二步的工作是比较简单直接的。具体来 说，若已知所有频繁项集的集合为，x 为f 中的任一频繁项集，设项集y 真包含 于z 测试c = 】，x 是否大于设定的最小置信度门限，若是，则规则x jy 是强 关联规则。按此方法即能将f 中所能构造的所有强关联规则找出来。因此，挖掘 关联规则算法的主要工作应集中在第一步，即设法高效地发现目标数据库中包含 的所有频繁项集，也就是采用何种频繁模式挖掘算法来实现的问题，这也是本课 题研究的重点。 为了测试某些特定项集是否是频繁项集，不可避免地需要扫描整个数据库。 如果目标数据库很大，则应设法尽可能减少扫描数据库的次数。考虑一种极端的 情况：只需扫描数据库一次，但要检测r 的所有子集( 若r 中包含m 个项，则共 有2 m 个子集) 。显然，这种指数级数据检测方法是不可行的，除非m 的值很小。 因而，如何更有效的减少扫描数据库的次数，并发现所有隐藏的频繁模式是提高 关联挖掘算法效率的关键。 从算法角度看，对于d n a 序列中基于一致序列表达的转录因子识别位点预测， 可以形式化表示为在特定字符集上( a ，t ，gc ) 的近似字符串的查找问题。因此， 首先要从近似串查找这一问题出发，研究与之相关的频繁模式挖掘算法，通过数 据挖掘中的频繁模式挖掘算法来预测和发现隐藏在d n a 序列中的植入位点，并对 它们的实际序列串和具体位置进行准确标记。 在下面的章节中，论文将对采用频繁模式挖掘思想的经典算法进行分析比较， 并在此基础上根据需要解决的实际问题的数据特征对算法进行有效的改进，力图 在类似d n a 序列这样的项目集较长的数据集中得到较好的性能。 2 4频繁模式挖掘 2 4 1频繁模式挖掘的概念 频繁模式挖掘是数据挖掘领域的一个基本问题，其研究内容一般包括项目集 合、项目序列和时间序列等各种数据。该方法被广泛应用于许多其它数据挖掘任 务中，并由于问题本身的基础性和内在复杂性，频繁模式挖掘方法成为许多研究 者关注的课题【3 6 1 。 作为关联规则挖掘算法的第一步，频繁模式挖掘是指找出数据集合中所有频 繁出现的项集的过程。通常，挖掘速度与准确率是一对矛盾体，也就是说，一些 算法在保证高效的时空复杂度或结果的准确性时，往往会造成另一方面的性能降 低，因此，力图在保证结果准确性的前提下，来提高算法的效率。 采用频繁模式挖掘思想的算法有很多，其中最经典的算法是：a p r i o r i 算法【3 3 】 和f p g r o w t h 3 1 1 算法。 a p r i o r i 算法使用频繁项集性质的先验知识，即频繁项集的所有非空子集必为 频繁项集( 称为下封闭特性，也称为a p r i o r i 特性) 。利用这一性质可以有效的压 缩搜索空间，使用一种称作逐层搜索的迭代方法，可以快速有效的挖掘出数据库 中蕴涵的用户感兴趣的频繁项集，完成频繁模式发现任务。然而，经典的a p r i o r i 算法需要的数据库扫描次数太多，寻找每层频繁项集都需要扫描一次数据库，由 于一般要处理的数据库都是大规模的数据库，这极大的限制了a p r i o r i 算法的可扩 展性。同时，当发现的最长频繁项集的长度，太长时，产生的候选项集的数目也很 庞大( 2 x 个) 。 f p g r o w t h 算法的核心是频繁模式树( f r e q u e n tp a t t e r nt r e e ，f p t r e e ) 的构建， 与a p r i o r i 算法相比，这个特殊的数据结构是f p g r o w t h 算法性能显著提高的原因 所在。它通过合并一些重复路径，实现了数据的压缩，从而使得将频繁项集加载 到内存中成为可能。f p g r o w t h 算法只需要两次扫描数据库就可以完成频繁模式发 现任务，同时生成频繁项集，它以树遍历的操作，替代了a p r i o r i 算法中最耗费时 间的事务记录遍历，从而有效地提升了算法的效率和可扩展性。 1 2 2 4 2 a p f i o f i 算法中频繁模式产生 a p r i o r i 算法采用“逐层搜索”的迭代方法，用k 项集生成( 斛1 ) 项集。首先， 扫描数据库计算出频繁1 项集的集合( 记为：厶) ：然后，执行下面的迭代过程计 算频繁k 项