（计算机软件与理论专业论文）生物序列模式挖掘方法研究及其应用.pdf

摘要 随着生物信息学的发展，生命科学数据呈爆炸式增长，迫使人们寻求强有力 的数据管理和分析工具。数据挖掘是目前最有效的数据分析手段，用于发现大量 数据所隐含的各种规律。在生物序列分析中，数据挖掘技术有着非常广阔的前景， 对于提高数据处理能力、产生有价值的生物学知识起着重要作用。生物序列模式 挖掘是生物序列数据挖掘的一项重要研究内容，它对指导基因的识别和功能注 释、非编码区功能元素的识别、蛋白质序列组成信息( 如功能域或结构域) 的识 别等具有重要的意义。 生物序列频繁模式挖掘和生物序列特定模式挖掘是生物序列模式挖掘中两 个重要的研究内容。针对传统生物序列频繁模式挖掘算法会在挖掘过程中产生大 量短的模式而导致的挖掘效率低下的问题，本文提出一种基于模式划分的生物序 列频繁模式挖掘算法m b i o p m 。m b i o p m 算法采用模式划分的方法，挖掘时能从一个 指定较长的模式长度开始挖掘，避免了产生大量的短的生物序列模式，明显提高 了挖掘的运行时间效率。实验和分析证明了该算法的有效性。 为了解决传统生物序列特定模式挖掘算法在挖掘过程中需要两两比较子序 列从而导致挖掘效率不高的问题，本文提出一种基于m d 索引结构的生物序列特定 模式挖掘算法m s a t r 。m s a t r 算法在挖掘过程中只需要比较相邻的模式，就可以得 到满足条件的生物序列特定模式。由于m s a t r 算法避免了不相关模式的比较，大 大提高了挖掘效率。实验和分析证明该算法是有效的。 关键词：生物序列；模式挖掘：模式划分 r e s e a r c ho nb i o l o g i c a ls e q u e n t i a lp a t t e r nm i n i n g a l g o r i t h m sa n dt h e f ta p p l i c a t i o n s a b s t r a c t w i t ht h ed e v e l o p m e n to fb i o i n f o r m a t i c s ，t h ed a t ao fb i o l o g i c a ls c i e n c ei se x p l o d i n g ， w h i c hf o r c ep e o p l et os e a r c hm o r ep o w e r f u lt o o l sf o ra d m i n i s t r a t i n ga n da n a l y z i n g d a t am i n i n gi st h em o s te f f e c t i v ew a yt oa n a l y z ed a t a , a n di tc a nb eu s e dt os e a r c ha l l k i n d so fk n o w l e d g eb e h i n dt h ed a t a i nt h ea n a l y s i so fb i o l o g i c a ls e q u e n c e s ，d a t a m i n i n gi su s e dw i d e l y i tc a ni m p r o v et h ea b i l i t yo fd e a l i n gd a t a , a n dp l a ya n i m p o r t a n tr o l eo np r o d u c i n gv a l u a b l eb i o l o g i c a lk n o w l e d g e b i o l o g i c a ls e q u e n t i a l p a t t e mm i n i n gi so n eo ft h ei m p o r t a n tr e s e a r c hf i e l d si nb i o l o g i c a ls e q u e n t i a ld a t a m i n i n g ，i ti si m p o r t a n t f o ri d e n t i f y i n gg e n e s ，e l e m e n ti n1 1 0c o d i n gf i e l da n d i n f o r m a t i o ni np r o t e i ns e q u e n c e s b o t hm i n i n gf r e q u e n tp a t t e m sa n ds e a r c h i n gt a n d e mr e p e a t sa r ei m p o r t r e s e a r c hf i e l d si nb i o l o g i c a l s e q u e n t i a lp a t t e r nm i n i n g t r a d i t i o n a lm i n gf r e q u e n t p a t t e m sa l g o r i t h m sw i l lg e n e r a t el o t so fp a t t e r n sw i t hs h o r tl e n g t hi nt h ep r o c e s so f m i n i n gw h i c hc a u s et h el o we f f i c i e n c yo fm i n i n g i no r d e rt oo v e r c o m et h el a c ko f t r a d i t i o n a la l g o r i t h m s ，t h ea l g o r i t h mm b i o p mw a $ p r o p o s e d w eu s e dam e t h o d c a l l e d “m o t i f - d i v i d e ”t os t a r tm i n i n gp a t t e r n s 、i mg i v e nl e n g t h , w h i c ha v o i d e d p r o d u c i n gl o t so fp a t t e r n s 、析t l ls h o r tl e n g t h t h et h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a l r e s u l t ss h o wm a tm b i o p mi m p r o v e st h ep e r f o r m a n c e t r a d i t i o n a ls e a r c h i n gt a n d e mr e p e a t sa l g o r i t h m sn e e dt oc o m p a r ep a t t e r n so i la l l o ft h e mw h i c ha f f e c tt h ep e r f o r m a n c eo fm i n i n g t oa t t a c kt h ep r o b l e mo ft r a d i t i o n a l a l g o r i t h r n s ，w ep r o p o s et h ea l g o r i t h mm s a t r i nt h ep r o c e s so fm s a t r , t a n d e m r e p e a t sc a nb em i n e dj u s t 谢n lc o m p a r i n gt h ep a t t e r n sn e x tt o e a c ho t h e r , a n d b e c a u s eo ft h a t ，m s a t ri m p r o v e st h ee f f i c i e n c yw h e nc o m p a r e dt ot r a d i t i o n a l a l g o r i t h m s t h ep e r f o r m a n c eo fm s a t r w a sp r o v e db yt h et h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t k e y w o r d s ：b i o l o g i c a ls e q u e n c e ；s e q u e n t i a lp a t t e mm i n i n g ；m o t i fd i v i d e 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 仉 邳日 )，lr，釉毕 釜 月 人 年 叭产期砷 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： 于 ) 1 经厦门大学保密委员会审查核定的保密学位论文， 月日解密，解密后适用上述授权。 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声眠 功叩年易月 年 第一章绪论 第一章绪论 生物信息学是生命科学、计算机科学、信息科学和数学等学科交汇融合所形 成的一门交叉学科，是当前的研究热点。生物序列数据是一类重要的生物数据， 生物序列数据挖掘技术对于提高数据处理能力、产生有价值的生物学知识具有重 要作用，其研究和应用是生物信息学最活跃的研究方向之一。这里我们将对这些 技术的研究现状以及存在的问题等进行阐述，最后对本文研究内容以及本文的结 构安排等进行总体概述。 1 1 研究背景及选题意义 1 9 5 6 年，在美国田纳西州盖特林堡召开首次“生物学中的信息理论研讨会”， 萌生了生物信息学概念1 。而后，研究者开始搜集大量的生物信息，并应用各种 方法进行计算和分析，试图发现这些信息反映生命现象的重要规律，从此，生物 学研究手段发生了由单纯的观察和实验研究转向与生物信息分析相结合的巨大 变革。2 0 世纪7 0 年代到8 0 年代初，计算机技术和数学统计方法飞速发展，研究者 开始应用计算机技术解决各种生物学上问题，初步形成生物信息学。1 9 8 5 年，人 类基因组计划( h u m a ng c n o m ep r o j e c t ，h g p ) 标志人类步入系统、全面解读和研 究人类遗传物质d n a ( d e o x y r i b o n u c l d ca c i d ) 的全球性合作时代卜1 。1 9 8 7 年，h w a a l i m 博士首次将这一学科命名为“b i o i n f o r m a t i c s ( 生物信息学) p 1 。2 0 0 0 年， r a s h i d i 等人给出了一个较为完整的生物信息学定义：生物信息学是指生命科学 与数学、计算机科学和信息科学等交汇融合所形成的一门交叉学科。它应用先进 的数据管理技术、数学分析模型和计算机软件对各种生物信息( 特别是分子生物 学信息) 进行提取、储存、处理和分析，旨在掌握复杂生命现象的形成模式与演 r 1 化规律r 1 。生物信息学的目标的是读懂基因组的遗传信息，揭示生物数据中蕴涵 的生物学知识和规律，指导生命科学研究p 1 。近年来，随着生物信息学的快速发 展，研究者收集的生物数据呈爆炸式增长，迫使人们寻求强有力的数据管理和分 生物序列模式挖掘方法及其心用 析工具。数据挖掘是目前最有效的数据分析手段，用于发现大量数据所隐含的各 种规律。由于复杂的生物数据特点、多样的生物学分析需求以及激增的生物数据 r 1 规模，数据挖掘在生物信息学中扮演着重要的角色一1 。 数据挖掘是从大量数据中寻找其规律的技术，主要有数据准备、规律寻找、 r 1 1 规律表示三个步骤1 。数据准备是从各种数据源中选取和集成用于数据挖掘的数 据；规律寻找是用某种方法将数据中的规律找出来；规律表示是用尽可能符合用 户习惯的方式( 如可视化) 将找出的规律表示出来。在具体实施数据挖掘应用时， 还要有一个结果评价步骤。这是因为数据挖掘算法寻找出来的是数据的规律，其 中有些是人们感兴趣的有用的，还有一些可能是不感兴趣的。这就需要对寻找出 的规律进行评估( 这是一个人工步骤，需要根据实际情况做出评估判断，还较难 以自动化) 。数据挖掘的主要内容包括模式挖掘、关联分析、聚类分析、分类分 析、异常分析和演变分析等，如图1 1 所示。生物序列数据挖掘为核酸与蛋白质 结构和功能的预测、基因组序列分析、功能基因组相关信息分析( 包括大规模基 因表达谱分析、基因组水平蛋白质功能综合预测等) 等提供了指导。数据挖掘技 r 0 1 术已成为生物信息学采用的主要数据分析技术p 1 。 图1 1 数据挖掘的主要内容 资料来源：参考熊赞，生物序列模式挖掘与聚类研剜2 1 ，2 0 0 7 1 0 第一章绪论 生物信息学的主要研究对象是生物序列，主要是指蛋白质和核酸序列( 包括 d n a 、r n a 序列) 等。蛋白质序列分析主要包括分析蛋白质间的相互作用、比较 蛋白质序列间的差异信息，用以指导蛋白质的结构和功能的预测、蛋白质在进化 中的作用的研究、蛋白质序列间相互关系的挖掘，分析蛋白质序列的组成信息( 如 功能域或结构域等等。核酸序列分析主要包括分析基因之间的相互作用、分析编 码区基因信息、比较不同物种的基因组序列、分析非编码区序列信息等等，用以 指导基因的识别和功能注释、基因问相互关系的挖掘、非编码区功能元素的识别、 基因在进化和特定生理过程中的作用的研究等等。生物序列数据挖掘的主要目的 是识别序列中的功能元素、预测序列功能、研究序列间的相互关系和相互作用等 等一。其中，生物序列模式挖掘是生物序列数据挖掘最重要的研究内容之一。 生物序列模式通常对应着生物序列中重要的功能( 或结构) 元素p 1 。例如，由 于进化等目的对基因进行复制产生大量的连续的重复序列称为重复片段( t r s ， t a n d e mr e p e a t s ) ，这种模式同它们的生物功能一样不能被完全理解，但是，它们 被确定在基因组织和进化上起着重要的作用1 0 1 ；同一个蛋白质家族中的所有序 列或大部分序列中包含着在进化过程中比较保守的区域，形成特定的序列模式， 它们对于蛋白质的结构和功能是非常关键的“；共表达基因序列上游区域包含着 在进化过程中表现更为保守的区域，形成特定的序列模式，它们是一类重要的功 能序列( 转录因子结合位点) ，能够调控基因的表达“。因此，发现这些重要的生 物序列模式对开展蛋白质家族分析、转录调控分析、基因组注释、非编码区功能 元素识别等研究具有重要的意义。生物序列模式挖掘的目的就是在生物序列中寻 找这样的序列模式，是识别基因及功能元素进而预测生物序列功能和解释序列间 相互关系等的一种关键技术。 1 2 研究现状及存在问题 序列模式挖掘问题最早a g r a w a l 和s r i k a n t 于1 9 9 5 年在分析交易序列数据的 基础上定义1 4 1 ，他们指出：给定一个序列集和用户指定的支持度阈值，序列模式 挖掘就是找到所有的频繁子序列，即在序列集中出现次数不低于最小支持度阈值 生物序列模式挖掘方法及其戍用 的子序列。19 9 6 年，s r i k a n t 等人提出基于a p d o f i 思想的c s p ( g e n e r a l i z e ds e q u e i l t i a l p a t t e r n sm i i l i n 曲算法“，算法引入时间和概念层次约束，采用自底向上宽度优先 策略挖掘所有频繁模式。但它的主要问题在于，当序列数据库规模很大时产生大 量的候选模式，需要频繁扫描序列数据库，尤其是在序列模式长度较长的情况下， 其对应的短的模式规模太大，导致算法难以处理，整体效率不高。为了解决这个 问题，2 0 0 0 年，p e i 等人提出了基于模式增长的p r e 6 x s p a n 算法引。该算法采用分 治思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库 上进行序列模式挖掘，算法无须产生候选模式，大幅度缩减了搜索空间，其主要 开销在于投影数据库的构造，性能优于类a 硼嘶算法。 然而，直接将传统的模式挖掘算法应用到生物序列数据的时，实验证实在可 伸缩性等方面存在问题“，因此，研究者设计了专门的生物序列模式挖掘算法。 例如，在d n a 序列中经常包含一些连续的重复模式称为重复片段( t a n d e m r e p e a t s ) ，这些重复的片段同它们的生物功能一样不能被完全理解，但是，它们 被确定在基因组织和进化上起着重要的作用1 8 1 9 1 。针对挖掘这种d n a 序列中特定 的模式出现了大量的算法：如早期的p t r 类算法2 0 2 1 1 ，a t r 类发现算法【2 2 之9 1 ， b e a s o n 的t r f i n d e r 算法3 0 1 ；而后，i 汕陀提出的基于后缀树的r e p u t e r 算法2 6 1 ，该 算法克服了输入序列大小限制，但它基于子序列两两比对，难以找至u d n a 序列中出 现次数较高的重复序列；2 0 0 7 年，w a n g 等人研究了相似性重复片段的查找问题 l aj l ，引入了新的相似性标准以及s a t r ( s e g m e n t s i m i l a r i t yb a s e da p p r o x i m a t e t a n d e mr e p e a t s ) 的概念，并在后继数组( s u a ) 的基础上设计了s u a _ s a t r 算法p “， 该算法在查找过程中不需要限制模式长度，在同样相似度要求下，对于相同的d n a 序列，算法查找时间低于其他同类方法，但是该算法的效率同样有待提高；2 0 0 7 年，x i o n g 等人提出的专门针对蛋白质序列的b i o p m 算法p 川，该算法引进多支持 度概念克服了传统算法的缺点，在性能和效率方面有显著改善，但是在支持度阈 值较低的情况下，该算法由于大量构建投影数据库，效率低下，而且该算法挖掘 过程中依然会产生大量不必要的短模式。 第一章绪论 总的说来，生物序列模式挖掘方法主要存在以下问题： 1 由于大多数的传统算法采用了自底向上宽度优先策略来挖掘所有频 繁模式，所以这些算法都需要进行多次的模式增长才能得到长度较 长的频繁模式，而太短的模式对生物序列没有多大意义，这使得这 些算法浪费了相当一部分时间来挖掘不必要的模式； 2 对类a p f i o f i 算法而言，挖掘生物序列中的频繁模式的时候，当要挖 掘的生物序列数据库规模很大时，将产生大量的候选模式，尤其在 需要挖掘的模式长度较长的情况下，将生成更多的候选模式，这导 致了整体效率很低； 3 对于建立投影数据库的算法而言，挖掘生物序列中的频繁模式的时 候，当要挖掘的生物序列模式支持度阈值较低时，需要多次地重新 构建投影数据库，这大大增加了这类算法的时间开销； 4 为挖掘出生物序列数据中相似的模式或者是具有相似模式的生物序 列，生物序列中的模式相似度度量以及序列间的相似度度量成为了 生物序列模式挖掘中的一个至关重要的问题，大多数传统算法采用 生物序列对比，计算匹配程度来反映相似度度量，然而这样的相似 度度量却不能反映这些生物序列、模式在生物学意义上的相似度； 5 为了挖掘生物序列中具有特定生物学意义的特殊模式，研究者们提 出了大量新的具有针对性的算法，主要包括了生物序列两两对比的 算法，采用基于特定索引结构的模式挖掘算法等。然而，这些算法 不仅在效率上有很大的提升空间，而且这些算法不能挖掘到所有生 物序列中的特定模式，它们挖掘的结果受到一定程度上的限制。 以上的这些问题可以归纳为如何提高算法效率以及如何定义相似度度量 这两大问题。一般说来，由于要处理的生物序列数据都是相当庞大的，所以， 生物序列模式挖掘算法的效率是一个很重要的问题。另外，生物序列模式挖 掘算法的目标是找出各种特定的、相似的模式或者序列，为生物序列功能预 测、蛋白质识别等等生物学研究提供基础，因此，如何定义出具有生物学意 义上的相似度度量显得尤为重要，这将直接影响到研究结果的好坏。 生物序列模式挖掘方法及其应用 1 3 主要研究内容及特色 本文主要针对生物序列频繁模式挖掘时产生大量不必要短的模式的问 题，如何在不产生候选模式的情况下进一步提高生物序列频繁挖掘效率的问 题，以及在生物序列特定模式挖掘中如何挖掘到更加完整的特定模式并进一 步提高挖掘效率的问题进行了深入的研究。研究的主要内容如下： 1 研究频繁模式挖掘算法：为了克服上面提到的传统频繁模式挖掘算 法的问题，首先介绍一种基于投影数据库的蛋白质序列频繁模式挖 掘算法b i o p m 。然后在该算法提出的多支持度概念的基础上，提出 一种新的基于模式划分的生物序列频繁模式挖掘算法m b i o p m ( m o t i f - d i v i d eb a s e db i o l o g ys e q u e n c ep a t t e r nm i n i n g ) ，来进一步提高 算法的挖掘效率； 2 研究d n a 序列特定模式挖掘算法：为了解决上面提到的生物序列特 定模式挖掘中的问题，首先介绍一种基于后继数组索引结构的挖掘 算法s u a s a t r 1 2 】。然后在该算法定义的模式相似度度量的基础上， 提出一种新的基于模式划分索引结构的d n a 序列特定模式挖掘算 法m s a t r ( m o t i f - d i v i d eb a s e ds e a r c ha p p r o x i m a t et a n d e mr e p e a t s ) ， 进一步提高了算法效率； 3 生物序列模式挖掘系统的设计：在以上理论研究的基础上，采用了 理论研究与系统相结合的方法，在有效理论研究的基础上设计开发 出应用系统。该系统对生物序列模式挖掘算法研究能起到辅助分析 和可视化的作用。另外，系统生成的生物序列模式能对进一步的生 物学研究如生物序列功能预测、蛋白质识别，蛋白质家族分析等等 提供一个基础。 本文研究的主要方法是通过分析传统的算法的问题，提出了模式划分的 方法，基于模式划分的索引结构，并把它应用于生物序列模式挖掘系统。主 要研究特色包括如下三个方面： 1 在生物序列频繁模式挖掘中，采用一种新的模式划分的方法，使得 挖掘生物序列频繁模式时，能从一个指定较长的模式长度开始挖掘， 第一章绪论 并在模式增长中不产生候选集，从而避免了产生大量不必要的短的 模式，进一步提高了挖掘效率； 2 在生物序列特定模式挖掘中，采用一种新的基于模式划分的索引结 构，通过该索引结构，能在线性时问内完成对生物序列特定模式的 挖掘，大大提升了挖掘效率，并且挖掘到的特定模式不像传统算法 挖掘到的结果那样受到限制； 3 根据以上提出的两种方法，设计生物序列模式挖掘系统，该系统既 能够高效挖掘生物序列中的频繁模式又能高效地够挖掘生物序列中 的特定模式。 1 4 本文结构安排 本文共分六章，主要研究了生物序列模式挖掘方法及其应用，各章的主要内 容如下： 第一章绪论，首先介绍了本文的选题背景、研究意义和当前国内外研究 现状，并对本文的研究方法、研究内容、研究特色及文章结构进 行了概述； 第二章系统地介绍生物序列模式挖掘相关技术，而后详细介绍了生物序 列频繁模式挖掘方法和生物序列特定模式挖掘方法这两种技术 的一般挖掘过程以及相关应用；最后，对本文的研究重点和框架 进行阐述； 第三章介绍频繁模式挖掘算法的核心思想以及两种生物序列频繁模式 挖掘算法。首先介绍一种基于投影数据库的蛋白质序列频繁模式 挖掘算法b i o p m 。然后在该算法提出的多支持度概念的基础上， 为解决传统频繁模式挖掘算法在挖掘过程中产生大量不必要的 短的模式导致效率低下的问题，提出了基于模式划分的生物序列 频繁模式挖掘算法m b i o p m ( m o t i f - d i v i d eb a s e db i o l o g ys e q u e n c e p a t t e r nm i n i n g ) ，能从一个指定较长的模式长度开始挖掘，提高 了挖掘的效率； 第四章介绍生物序列特定模式挖掘算法的核心思想以及两种d n a 序列特 生物序列模式挖掘方法及j 应用 定模式挖掘算法。首先介绍一种基于后继数组的d n a 序列特定模 式挖掘算法s u as a t r 。然后在该算法定义的模式相似度度量的基 础上，为进一步提高挖掘效率并解决传统算法挖掘结果受到限制 的问题，提出了基于模式划分索引结构的d n a 序列特定模式挖 掘算法m s a t r ( m o t i f - d i v i d eb a s e ds e a r c ha p p r o x i m a t et a n d e m r e p e a t s ) ，提高了挖掘效率； 第五章在前面章节的理论基础上，从应用方面进行实践，在e c l i p s e 集 成开发平台上设计开发出实际的应用系统； 第六章总结和展望。对本文的研究成果进行概括和总结，并提出了未来 的研究方向。 第二章生物序列模式挖掘技术及其应用 第二章生物序列模式挖掘技术及其应用 本章首先系统的介绍生物序列模式挖掘的相关技术。在此基础上，从生物序 列的频繁模式挖掘和生物序列的特定模式挖掘两方面进行讨论，分析生物序列模 式挖掘的过程，阐述了生物序列模式挖掘的研究意义和应用情况，最后，陈述本 文的研究重点。 2 1 模式挖掘的相关技术 如上所述，生物序列模式在进化过程中具有良好的保守性，对生物体的生存 具有至关重要的意义。因此，挖掘这些生物序列模式成为生物序列数据研究与分 析的重要内容，迄今为止，人们已经提出了大量的生物序列模式挖掘算法。模式 挖掘方法的分类如图2 1 所示。 图2 1 模式挖掘算法分类图 资料来源：参考朱扬勇，熊赞d n a 序列数据挖掘技术【6 】，2 0 0 7 生物序列模式挖掘方法及其应用 较为早期的生物序列模式挖掘方法可以分为以下几类【6 】： 1 启发式的方法：在挖掘过程中，不需要找到全局最优的生物序列模 式，只需要找到收敛到局部最优的模式。另外，为了进一步地缩小 搜索空间，采用限制序列模式的长度或者在模式增长时指定序列模 式的最大间隔的方法。但是，这种方法将有可能丢失一些很重要的 序列模式从而导致最终挖掘结果缺乏完整性。这类方法的典型算法 包括：g i b b s 3 4 1 算法，c o p i a 3 s 算法等等。 2 穷举搜索枚举所有模式方法：穷举方法可用于寻找频繁模式，统计 生物序列模式出现的频率等。它要穷举出所有解的情况，统计和比 较某一段生物序列片段出现的频率，并且不利用任何辅助信息。所 以算法运行的时间与空间随着模式长度的增长呈现指数级增长关 系。这种算法仅适用于在小规模数据库中搜索或统计较短的简单模 式。但是它的优点是能够找到所有所需要的结果。在实时性高的条 件下运用将会受到很大的限制。这类方法的典型算法包括：m o t i f p q 等。 3 采用剪枝策略的方法：由于在采用穷举方法进行搜索的过程中，要 搜索长度较长的序列模式的时候存在极大的困难，所以可以在搜索 过程中采用剪枝策略：从短的模式开始，进行短的模式连接扩展以 发现长模式，一旦模式不能再被扩展( 如支持度满足一定阂值) ，则 该模式即为最大模式。不能被扩展的模式即被剪枝。但该方法在最 坏情况下的运行时间仍然是指数级的。剪枝策略是优化搜索的一种 方法。顾名思义，就像剪掉无用树枝，在搜索中一旦发现有些搜索 步骤乃至以后的所有都是无用或已经做过，则可不再去执行这些步 骤。节约了空间与时间。在一些搜索算法可以利用剪枝策略，例如 穷举算法中，可以引入搜索策略提高搜索效率。代表性算法有 t e i r e s i a s l 3 刀，p r a t t 3 s 等。 4 建立随机模型的方法：由于某些序列模式不能用比较简单的决定性 模型来描述，所以需要采用一种随机的模型表达，例如建立h m m ，位 置权重矩阵等等。这种方法建立的模型只适合不需要找到全局最优 第_ 二章生物序列模式挖掘技术及其应用 的情况。这类方法的典型算法包括：m e m e 3 9 1 算法、e m 【删算法等。 5 借助附加信息的方法：为了使得挖掘到的结果模式更加符合生物学 的意义和应用，在挖掘过程中借助序列对比信息、序列全局特征信 息等来增强挖掘效果。这类方法的典型算法包括：e m o t i f 4 1 算法等。 在数据挖掘领域，研究者提出了适用于大规模数据的更高效的序列模式 挖掘算法，并受到广泛关注。自1 9 9 5 年，a g r a w a l 和s r i k a n t 给出序列频繁模 式挖掘的定义1 5 1 以来，出现了大量频繁模式挖掘算法，如a p r i o r i 15 1 ，g s p 16 1 ， p r e f i x s p 锄【用，f r e e s p 锄【4 2 】， s p a d e ( s e q u e n t i a lp a t t e r nd i s c o v e r yu s i n g e q u i v a l e n c ec l a s s e s ) 等。而后，研究者们设计了专门面向生物序列的模式挖 掘算法【6 】，其主要方法如下： 1 采用不同的搜索策略：通常的生物序列频繁模式挖掘采用的是自底 向上的模式搜索策略，即从短的频繁模式开始，不断扩展直到产生 不频繁模式。然而，由于频繁模式的子模式也是频繁的，该方法结 果集中会包含一定数量长度较短、在使用时可能不具备生物意义的 模式，这在一定程度上影响了生物序列模式的挖掘的效率。因此， 可以采取些额外扩展或剪枝方法，针对生物序列中长模式的进行 挖掘。另一种策略是自顶向下的搜索方法，这种方法在一定程度上 能够减少大量短的模式的分析，例如，e s t e r 等人在2 0 0 4 年提出一种 采用自项向下的模式搜索策略的算法t o m m s a 【州。首先，为了不丢 失某些可能的特定模式，算法设计一个自底向上的搜索函数，用于 确定频繁模式的最大长度值；然后，从所有具有指定最大长度的子 序列开始对每个模式进行缩减，直到其频繁为止缩减的方法是减少 子序列中的一个模式，或是利用概念图对其进行概化。该算法同样 会产生一定数量的候选集，但是其产生的候选模式数目远远小于自 底向上的方法； 2 挖掘具有约束限制的模糊匹配的生物序列模式：由于生物序列的特 点，要挖掘的生物序列模式间可能包含任意长度的间隔，所以生物 生物序列模式挖掘方法及其应用 序列模式间的匹配往往是包含间隔的模糊匹配。于是，研究者们在 考虑生物序列各种约束特征之后，特出了一些新的生物序列模式挖 掘方法。例如，w a n g 等人在2 0 0 4 年提出了一种有效挖掘包含任意长 度间隔生物序列模式的两阶段算法一“，其基本思想是，在第1 阶段搜 索所有称为片段的不包含间隔的短频繁模式；第2 阶段使用第l 阶段 得到的频繁模式，生成包含被可变长度间隔分割的多个片段连成的 长模式。不同于以往的方法，这个方法的优点在于能够从第一阶段 获得的局部模式信息来降低第二阶段全局模式的搜索时间。虽然根 据这种方法挖掘出的生物序列模式更加符合生物学上的意义，但是， 由于生物序列中的约束条件是十分复杂的，所以，这种挖掘方法的 研究依然是当前的一个重点和难点； 3 挖掘结果模式的压缩和优化：通常方法挖掘到生物序列模式，存在 许多冗余模式，并且由于要挖掘的序列集中包含的序列模式数量非 常大，往往需要耗费大量空间和时间，另外，由于大量的冗余模式， 使用者难以理解。为了减少结果模式的数量，去除冗余，常常取包 含大量一般模式的特定频繁子序列，如输出最大序列模式或闭合 ( c l o s e d ) 序列模式。闭合序列模式挖掘能够大量减少生成模式的数量， 并且这种压缩是无损的。y a n 等人提出一种基于p r e f i x s p a n 算法的闭 合序列模式挖掘算法：c l o s p a n 算、法m 1 ，定义闭合序列模式为：一个 序列模式s 是闭合的，如果在数据库中不存在任何与s 具有相同支持度 的s 的超序列。c l o s p a n 算法采用的基本思想是，在已挖掘的候选闭合 序列模式集上进行候选测试( c a n d i d m em m n t e n a n c e a n d t e s t ) 。使用这 个集合剪枝搜索空间，并判断是否新的序列模式可能是闭合模式。 由于大量闭合模式( 或候选模式) 占据内存并需要大量空间检测新的 模式，因此使用c l o s p a n 算法处理长序列数据时，所需的代价相当大。 之后，w a n g 等人提出b i d e ( b i - d i r e c t i o n a le x t e n s i o nb a s e d 台e q u e n t d o s e ds e q u e n c em i m n g ) 闭合序列模式算法一，采用一种称为 b i d i r e c t i o n a le x t e n s i o n 的闭合检测策略，算法不需要维护候选模式。 第一二章生物序列模式挖掘技术及其应用 实验证实，b i d e 比c l o s p a n 更为有效。相关的研究还有t z v e t k o v 等人 提出t 0 p 水闭合序列模式挖掘算法t s p ( t o p - kc l o s e ds e q u e n t i a lp a t t e r n s m i n i n 曲以及c o n g 等人提出并行闭合序列模式挖掘算法 p a r - c s p ( p a r a l l e ld o s e ds e q u e n t i a lp a t t e n lm “n 曲删等。这些方法的基 本思想和算法策略可以根据生物序列数据的特点进行改进并应用于 生物序列模式挖掘研究中。对结果模式的压缩可在一定程度上有效 去除冗余，提高模式集的可用性； 4 挖掘特定类型的序列模式：在生物繁殖、生长、进化过程中，往往 需要对基因进行复制而产生大量的重复序列。研究表明，研究表明， 重复序列并不是没有任何功能的，只是更多的功能目前尚未发现，并 且是非常重要的【1 引。这类序列称为串联重复序列，主要是指在某一 d n a 序列中重复出现次数超过一定数量、重复单位呈串状、首尾相连 排列的一段序列【1 9 】。针对这样的生物序列特定模式，研究者们提出 了一系列的相关挖掘算法。例如，2 0 0 5 年，w a n g 等人提出了针对精确 查找的新的重复片段的定义最大模式重复l p r ( 1 a r g e s tp a t t e r n r e p e t i t i o n ) ，并设计了索引结构后继数组( s u c c e e d i n gu n i ta r r a y ， 简称s u a ) 完成l p r 的查找h 明。然而，由于d n a 序列存在突变等情况，导 致这些重复成为非精确相等的。已有的p t r 发现，算法无法发现这样 的近似串联重复序列a t r 。于是，出现了大量a t r 发现算法2 2 。2 9 1 ，如 b e a s o n 设计的t r f i n d e r 算法是最有影响力的串联重复序列发现算法 3 0 1 ；k u r t z 等人提出的r e p u t e r 2 6 1 基于后缀树算法克服了输入序列大 小限制，但它基于子序列两两比对，难以找至w j d n a 序列中出现次数较 高的重复序列；2 0 0 5 年，l i 等人提出了一种新的投影拼接算法有效 识别重复序列5 0 1 ；2 0 0 5 年，y d ow e x e l 等人给出了关于评分函数的3 种类型a t r s 的定义，文中提出一种由扫描和候选验证两阶段组成的 a t r 发现算法，扫描阶段采用可变大小的滑动窗口检测相邻的子序列 是否相似，生成可能包含a t r s 的候选域列表，再由第2 阶段验证这些 生物序列模式挖掘方法及其心用 候选a t r s ，验证过程是首先将含有长度为t 模式的候选a t r 与下一个 长度为t 的子序列比对，计算评分是否大于给定阈值；然后扩展a t r 。 该算法还设计了一个统计框架来调整阈值、评分函数参数以及模式 r 1 间间隔等；w a n g 等人在2 0 0 7 年研究了相似性重发片段的查找问题p “， 针对重复片段查询的索引结构所需空间过大问题，引入了新的相似 性标准以及s a t r ( s e g m e n t s i m i l a r i t yb a s e da p p r o x i m a t et a n d e m r e p e a t s ) 的概念，并在后继数组( s u a ) 的基础上设计了s a t r 的查找算 法。算法在查找过程中不需要限制模式长度，在同样相似度要求下， 对于相同的待查序列，算法查找时间低于其他同类方法。然而，目 前的序列模式挖掘算法将支持度定义为包含序列模式的交易个数 ( 或百分比) 。对于一条序列，支持度仅为1 。因此，关于串联重复序 列模式的挖掘不同于以往的序列模式挖掘算法，是一项值得研究的 新内容。 在上述介绍的方法中，本文主要针对生物序列的频繁模式挖掘算法以及 生物序列特定类型模式挖掘算法进行深入研究，因此，接下来，我们将对这 两种方法进行具体的阐述。 2 2 频繁模式挖掘方法 生物序列的频繁模式挖掘是生物序列模式挖掘中的一种重要的方法，它作为 最常使用的一种生物序列数据处理技术，受到广泛的关注。生物序列频繁模式挖 掘方法主要可以分为两大类：第一类，主要是类a p r i o r i 的算法，但是这类算法 会在挖掘过程中产生大量的候选模式从而导致算法的运行时间效率低下；第二 类，主要是采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然 后在各个投影数据库上进行序列模式挖掘，由于算法不会产生大量候选模式，大 幅度缩减了搜索空间，其主要开销在于投影数据库的构造，性能优于类a p r i o r i 算法。 第二章生物序列模式挖掘技术及其应用 2 2 1 频繁模式挖掘的过程 生物序列频繁模式挖掘就是要挖掘出给定生物序列或者生物序列集合中出 现次数够频繁( 大于或者等于给定的支持度阈值) 的模式( 子序列) 。为了挖掘 出生物序列中所有频繁的模式，一般采用的是自底向上的搜索策略，先找出长度 较短的频繁模式，而后在短的模式上进行扩展产生长度较长的频繁模式，直到最 后找出所有生物序列中的频繁模式。在挖掘过程中，主要考虑的是挖掘的时间效 率问题。挖掘后得到的生物序列的频繁模式主要为进一步的生物序列数据分析提 供依据，例如，可以将其作为生物序列的特征描述作为生物序列聚类的依据；也 可以将其作为识别生物序列功能的基础等等。如上所述，虽然生物序列频繁模式 挖掘的两大类算法的基本思想不太一样，但是它们都包含几个阶段，如图2 2 所 示。 模式增长 图2 2 生物序列频繁模式挖掘过程 资料来源：参考x i o n gy u n ，a ne f f i c i e n ta l g o r i t h mf o rp r o t e i nm o t i fw i n i n g 3 3 1 ，2 0 0 7 具体步骤包括： ( 1 ) 生成频繁1 项集：由于是采用了自底向上的搜索策略，所以首先要挖掘出 长度最短即长度为l 的频繁序列。在这个过程中，需要扫描整个生物序列 数据库一遍，依次计算并记录所有长度为1 的子序列的频繁次数。最后， 根据支持度阈值这个设定的参数，对所有的子序列进行筛选，保留那些 频繁次数大于或者等于支持度阈值的子序列，即频繁1 项集； 生物序列模式挖掘方法及j e 心用 ( 2 ) 生成候选集合或者建立投影数据库：上述两大类方法的不同主要体现在 这个阶段中。类a p r i o r i 的方法，主要是根据前一阶段产生的频繁序列集 进行扩展，产生长度较长的候选频繁序列集。由于产生的候选集往往数 量很大，所以，一般会在产生候选集后进行剪枝操作来减少每次产生的 候选集的数量。剪枝操作一般根据频繁序列的子序列也是频繁序列这一 原理。而基于投影数据库的方法，主要是根据前一阶段产生的频繁序列 集，生成基于该频繁模式序列长度的投影数据库； ( 3 ) 生成频繁模式：类a p r i o r i 的方法，主要再次扫描一遍生物序列数据库， 计算并记录前一阶段得到的剪枝后的候选频繁集的频繁次数，而后根据 支持度阈值的筛选得到新的长度较长的频繁序列集合，进行存储。而基 于投影数据库的方法，由于在前一阶段生成了投影数据库，所以，只需 要扫描前一阶段建立的投影数据库，就能挖掘到长度较长的频繁模式并 进行存储，而不需要扫描整个大的生物序列数据库，这也是基于投影数 据库的方法性能要优于类a p r i o r i 方法的主要原因； ( 4 ) 迭代：不断重复2 ，3 步骤，直到挖掘出生物序列集中所有的频繁模式为 l e 。 2 2 2 生成频繁模式 在频繁模式挖掘过程中，如何产生频繁模式是一个