（计算机软件与理论专业论文）dna序列中基于后缀树的重复体识别算法.pdf

摘要 重复体识别是生物信息学中分析基因组序列的主要手段之一。在真核生物基 因中重复体d n a 占据了非常重要的地位。通过识别重复体可以发现基因组的进 化规则和许多疾病的遗传规律。许多转位子重复体序列作为可编码区域重复出现 在基因组序列中，识别这些重复体对基因组解码起到了很重要的作用。 通过考虑重复体序列的长度和发生频率，提出了一种基于后缀树的识别初级 重复体的r e p s e e k e r 算法。算法采用最低限制频率，并通过重叠性合并，最大程 度地扩展了重复体的长度。算法以d n a 序列所构造的后缀树作为输入，并以基 于后缀树的查询算法作为手段，最终生成输入的d n a 序列的初级重复体分类表。 为了进一步地提高r e p s e e k e r 算法的效率，我们对后缀树构造算法进行了适应性 改进。在构造后缀树时，给叶子节点编号，并在分支节点加入了叶子信息数组 l l ( l e a fl i s t ) 。在此基础上，改进了基于后缀树的查询算法，从而避免了r e p s e e k e r 算法进行高频度的子树遍历。 对u k k o r l e l l 后缀树构造算法的改进所带来的问题是对空间要求加大，而构造 后缀树算法的时间复杂度几乎没有受到影响。测试中使用了n c b i 中的几条典型 d n a 序列作为测试对象，并与改进u k k o n e n 前的重复体识别算法做了比较分析。 结果表明r e p s e e k e r 在没有损失精度的情况下很大程度地缩短了运行时间。 关键字：生物信息学复体识别后缀树r e p s e e k e r a b s t r a c t r e p e a ti d e n t i f i c a t i o ni so n eo fi m p o r t a n tm e a s u r e si nb i o i n f o r m a t i e st oa n a l y z e t h eg e n e s s e q u e n c e s r e p e t i t i v ed n as e q u e n c eo c c u p i e dac r u c i a lp o s i t i o ni n e u k a r y o t i cg e n e s t h r o u g hr e p e a ti d e n t i f i c a t i o n ，t h ee v o l u t i o nr u l e so fg e n o m ea n d g e n e t i cl a w so fm a n yd i s e a s e sc a l lb ef o u n d m a n yt r a n s p o s o n sw h i c hc 0 n t a i l lc o d i n g r e g i o n se x i s ti ng e n o m es e q u e n c e s i d e n t i f i c a t i o no ft h e s er e p e a t si s s i g n i f i c a n tt o d e c o d eg e n o m e t h i sp a p e rp r o p o s e sa l la l g o r i t h mn a m e dr e p s e e k e rw h i c hc a ni d e n t i f ye l e m e n t r e p e a t st h r o u g ht a k i n gt h el e n g t ha n df r e q u e n c yo fr e p e t i v es e q u e n c e si n t oa c c o u n t t h i sm e t h o da d o p t e dm i n i m u ml i m i tf r e q u e n c ya n de x t e n d e dr e p e a t sf u r t h e s tt h r o u g h m e r g eo fo v e r l a p p e dr e p e a t s ，s i m u l t a n e o u s l y u s i n gas u f f i xt r e ea si n p u tw h i c hi s c o n s t r u c t e db yd n a s e q u e n c e sa n das e a r c ha l g o r i t h mw h i c hi sb a s eo ns u f f i xt r e e sa s m e a s u r e ，t h i sm e t h o do u t p u t sac l a s s i f i e dt a b l eo fe l e m e n tr e p e a t sf i n a l l y i no r d e rt o e n h a n c et h e e f f i c i e n c yo ft h ea l g o r i t h mo fr e p s e e k e r , t h eu k k o n e na l g o r i t h mo f c o n s t r u c t i o no fs u f f i xt r e ew a si m p r o v e d t h el e a v e sa r en u m b e r e d 锄d1 e a f1 i s t sa r e s t o r e di nb r a n c hn o d e si nt h ep r o c e s so fc o n s t r u c t i o no fs u f f i xt r e e i nt h i sf o m l d a t i o n t h es e a r c ha l g o r i t h mb a s e do nt h i st y p eo fs u f f i x t r e ei s a d o p t e db yt h er e p s e e k e r , w h i c ha v o i ds u b t r e et r a v e r s a li nh i g hf r e q u e n c e t h ei m p r o v e m e n th a se n l a r g e dt h es p a c er e q u e s t ，b u th a sl i t t l ei n f l u e n c eo nt i m e c o m p l e x i t yo fu k k o n e na l g o r i t h r n r e p r e s e n t a t i v es e v e r a ld n a s e q u e n c e si nn c b i w a su s e da st e s to b j e e t ，a n dac o n t r a s tw a sm a d ew i t hb e f o r ei m p r o v e d t h er e s u l t s s h o wt h a tt h et i m eo fr e p s e e k e rw a sr e d u c e df u r t h e s tw i t hc o m p a r a b l ea c c u r a c y k e y w o r d ：b i o i n f o r m a t i c s r e p e a ti d e n t i f i c a t i o n s u f f i xt r e e r e p s e e k e r 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 竺：! ：氩 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子利技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名：日期呈呈盟三星 第一章绪论 第一章绪论 1 1 引言 随着生物测序技术迅猛发展，无论从数量上还是从质量上都极大地丰富了生 物学研究的数据资源，并迅速形成了巨量的生物信息库。例如，近年来，核酸库 的数据每1 0 个月左右就要翻一翻，2 0 0 0 年底，数据库数据则达到了创记录的1 0 0 亿个记录。面对着海量的生物信息数据，如何管理、分析、使用这些信息就成了 一个急需解决的问题。因此，在这些需求的基础上生物信息学就应运而生了。它 借助大型计算机的强大处理能力，通过计算机科学，信息科学，数学等多种手段 为人类破译遗传密码、揭示生物遗传和进化规律提供了高效的方法。它是人类能 够完全，清晰地认识自我和整个生物世界的重要途径。 生物信息学是研究生物信息的采集、处理、存储、传播、分析和解释等各方 面的一门学科，它通过综合利用生物学、计算机科学和信息技术而揭示大量而复 杂的生物数据所赋有的生物学奥秘。具体而言，生物信息学作为一门新的学科领 域，它是把基因组d n a 序列信息分析作为源头，在获得蛋白质编码区的信息后 进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行必要的药物设 计。基因组信息学、蛋白质空间结构模拟以及药物设计构成了生物信息学的3 个 重要组成部分。 从总体上讲，生物信息学的研究目的可以分为以下三个层次【1 】 第一层目的是对生物数据和知识进行有效管理，使研究者能快速得到己有的 信息并且便捷地提交试验获得的新数据。生物数据管理是开展其他研究的基础， 也是发展最为成熟的一个部分。目前，在互联网上己经建立了若干大型生物信息 学网站，其主要功能之一就是管理大型数据库，并提供数据收集、交换以及查询 等服务。国际上的三大核酸数据库分别是美国国家生物技术信息中心( n a t i o n a l c e n t e rf o rb i o t e e h n o l o g yh f o r m a t i o n , n c b i ) 维护的g e i l b a l l k 【2 】、欧洲生物信息学研 究所( e u r o p e a nb i o i n f o r m a t i c si n s t i t u t e e b i ) 维护的e m b l 3 】和日本信息生物学中 , l , ( c e n t e ro fi n f o r m a t i o nb i o l o g y c m ) 维护的d d b j 4 1 ，它们管理着全世界生物实 验室提交的原始核酸序列数据，并提供数据检索服务。这三者之间每天同步交换 数据，以保证数据的统一和完整，它们一起构成了国际核酸序列数据库 ( i n t e r n a t i o n a ln u c l e o t i d es e q u e n c ed a t a b a n k i n s d ) 。除核酸数据库以外，还有许 多针对其它生物数据的数据库，比如最大的e d n a 数据库t i g rd a t a b a s e 5 1 ，生物 大分子结构数据库p d b l 6 1 ( p r o t e i nd a t ab a n k ，其中9 0 是蛋白质的结构数据) 和 2 d n a 序列中基于后缀树的重复体识别算法 s w i s s p r o t a 蛋白质序列数据库( 7 】等等。总之，生物数据的管理和维护方面的研 究己经比较成熟，并且正在作为进一步研究的基础而发挥巨大的作用。 第二层目的是研究算法和开发新的工具。算法一直是生物信息学重点研究的 对象，而且对算法的研究涉及生物信息学的各个方面。生物数据的显著特点就是 数据量极为庞大，因此任何实用的算法都必须克服这一障碍，而这也正是生物信 息学算法研究的挑战性之所在【8 】。一些经典的算法以及在其基础上开发的应用程 序己经成为生物信息学中开展其它各项研究的基本工具，比如用于大规模d n a 序列测序的s t a d e n 程序包( 9 】，用于数据库相似性搜索的b l a s t t l 0 1 和f a s t a t l ， 以及用于显示生物分子三维结构的r a s m o l 1 2 】等等，而种类繁多的辅助性软件( 比 如数据格式转换、可视化显示等等) 更是己经成为了研究人员的日常工具。然而对 算法的需求是没有止境的，不仅是新的研究方向和内容需要新的算法，而且在很 多方面，已有的算法远远不能满足研究的需要，还需要更好的算法。可以说，生 物信息学的每一次飞跃，都伴随着一个经典的算法和一系列不成功的尝试，而算 法上的一个突破，也往往意味着生物信息学的一步进展。 第三层，也是生物信息学研究的最终目的，就是利用这些算法以及在其基础 上开发的应用程序对生物数据进行分析，最终理解各种生物数据的内涵，获得隐 藏在数据背后的生物学知识，认识生命现象的本质。目前，这一旨在理解生物数 据的研究包括：基因组d n a 序列分析、基因的识别和定位、基因功能分析、基因 表达与调控研究、d n a 一蛋白质的相互作用研究以及蛋白质序列分析和结构预测等 等，它们目前都还处于一个比较初级的研究阶段。 本文研究的主要内容是基因组中的重复序列识别，提出了一种新的基于后缀 树的重复体识别算法。重复序列研究属于基因组d n a 序列分析的范畴。关于重 复序列的识别、组成以及特点等方面的研究一直是基因组序列分析的重要组成部 分，它在基因组序列分析和比较中起着十分重要的作用。 真核生物的基因，由只有一个复制d n a 序列( 也称单一d n a ，u n i q u e s e q u e n c e ) 和具有多数反复存在的d n a 序列组成。称后者为重复序列。组成基因 组的d n a 序列，根据其重复的频度可分为三类。( 1 ) 高度重复序列：重复几百 万次，一般是少于1 0 个核苷酸残基组成的短片段。如异染色质上的卫星d n a 。 它们是不翻译的片段。在小鼠中约占基因组的1 0 。( 2 ) 中度重复序列：重复次 数为几十次到几千次。在小鼠中约占2 0 。如r r n a 基因、t r n a 基因和某些蛋 白质( 如组蛋白、肌动蛋白、角蛋白等) 的基因。( 3 ) 单一序列：在整个基因组 中只出现一次或少数几次的序列，在小鼠中约占基因组的7 0 。如珠蛋白基因、 卵清蛋白基因、丝心蛋白基因等。实验证明，所有真核生物染色体可能均含重复 序列而原核生物一般只含单一序列。高度和中度重复序列的含量随真核生物物种 的不同而变化。 第一章绪论 3 按照重复的排列方式，可将它分为串联重复序列( t a n d e mr e p e a t ) 和散在重 复序3 j t j ( i n t e r s p e r s e dr 印e a t ) 两大类【1 3 1 。串联重复序列是指重复单元呈现串状，首尾 相连的排列在一起形成聚集区的重复序列，一般成簇存在于染色体的特定区域。 散在重复序列是指重复单元并不相连，而是分散地分布在整个基因组中的重复序 列。散在重复序列根据转座方式的不同大致可以分为四类：l t r 元件、长散布元 件( l i n e ) 、短散布元件( s n e ) 和d n a 转座子。 重复序列在基因组中广泛存在，尤其是真核生物的基因组中存在大量的重复 序列，脊椎动物更是如此。例如，人类基因组中总数为3 2 1 0 9 1 0 p 的d n a 序列 构成，其中约有5 0 为各种类型的重复序列【1 4 】，拟南芥基因组中重复序列约占 1 1 ，秀丽线虫基因组中重复序列约占7 ，果蝇基因组中重复序列约占3 【l 5 1 。 这些重复序列种类繁多，其中大部分具体功能目前还不是十分清楚，然而已有的 研究显示一些特定的重复序列在基因表达、调控和遗传等方面起着十分重要的作 用。例如：染色体着丝点区域包含有大量被称为卫星d n a 的重复序列，它们可 以作为蛋白质结合点，在细胞分裂时帮助控制染色体移动【l6 1 。因此对重复序列的 研究可以促进基因表达与调控以及遗传等方面的研究。 另外，重复序列是基因组不稳定性的重要原因之一。基因组是一个动态结构， 在生物体的生命过程或是遗传过程中，基因组常常会发生变异、复制、倒置和退 化等各种改变【1 7 】。重复序列的再结合可以导致染色体组的重组，致使基因组发生 巨大的改变。这些重复序列短的只有几个碱基对( b a s ep a i r , b p ) ，长的可达上万个 碱基对。因此，对重复序列的研究可以加深对基因组整体结构的理解，这种理解 不仅可以推动基因组的完全标注，同时可以促进对生物进化的研究【l8 1 。更引人注 目的是：很多人类遗传病如脆性x 染色体综合症【l9 1 ( f r a g i l e xs y n d r o m e ) ，亨廷顿舞 蹈症【2 0 ( h u n t i n g t o n sd i s e a s e ) 以及弗兰德利克氏共济失调症【2 1 3 ( f r i e c t r e i e h sa t a x i a ) 等都与重复序列的副本数的异常有关。 如何快速有效地识别重复体己经成为生物信息学的一个非常重要的问题。 1 2 重复序列识别算法研究现状 关于重复序列识别算法的研究也很多，大体可以分为两类：一类是根据己有的 数据库中收集的重复序列模式进行搜索，另一类是无先验知识的。 第一类方法中最突出的是r e p e a t m a s k e r z 2 1 ，它定义重复序列为基因组中出现 十分频繁的子序列，因此它将已知的重复序列集合作为字典，用字典中的所有重 复序列相对于用户提交的序列进行准确或者近似匹配，并将检查到的重复序列用 n ( 或x ) 替代，以达到屏蔽重复序列的效果。这样做的目的是为了在分析基因结构 时减少由这些重复区域引入的噪声，提高基因预测的效率和准确率。它的不足之 4 d n a 序列中基于后缀树的重复体识别算法 处是只能确定重复体库中己有的少数特定类型的重复( 如某些微卫星) ，不能用于 所有的重复序列识别，特别当在你分析一个新的基因时，一个完整的重复体库几 乎是无从获取的。 第二类方法，无需任何先验知识，直接从核酸序列中查找重复序列。这类方 法中最简单的思路是考察序列的点阵图，重复序列在点阵图中表现为对角线的形 式。使用此类方法的程序有d o t t e r 程序】，它实际上是用点阵法进行双序列比对 的程序，也可以用于在一个序列中查找重复序列。其优点是形象化，缺点是只适 用于较短的序列，无法识别长序列中的重复片段。 从一个理论的观点，一个重复体通常被定义成一对相同或相似的子序列。例 如，在g u s f i e l d 的定义【矧中，目的在于找到最大的重复序列对。在r e p u t e r 2 5 2 6 1 中，结果是基于最大长度的相似序列列表。大多数的识别方法有一个共同的特点， 都是基于重复体的长度最大化，然而它们都忽略了重复频率( 出现次数) 的重要性。 在真实的生物序列中重复元素通常出现次数要大于两次的。例如，在复杂基 因中的转位子( t r a n s p o s o n ) 通常会出现成百上千次。因此，我们相信生物学意义上 的重复体定义应当将重复体的长度、频率和其他可能的因素都考虑进去。对于一 些研究者来说，明确生物学意义上的重复体定义不是一件容易的事情。有一些工 具当考虑重复体频率有可能大于2 时，只能找到短的或串联重复体，而不能找到 长的和散布的重复体。 b a o 、e d d y 2 7 1 和p e v z n c r 2 8 1 认识到仅与长度相关的重复体定义的缺陷，因此试 图将其他因素考虑进定义。一个严格的重复体长度和频率的定义还没有被明确地 提出。一旦放弃长度最大化的目标，对于重复体边界的计算将成为困难。 通过多序列比对的方法也是有问题的，因为重复体的嵌套结构有可能被忽略 了，而且多序列比对本身就是一个难题。p e v z n e r 等人提出了a b r u i j n 图来研究 重复体的镶嵌结构，然而当输入序列比较长且包含大量重复体时，a b r u i j n 图是 很复杂和难以分析的。另外，这种基于a b r u i j n 图的方法还要以输入串的局部双 序列比对结果作为输入，因此计算结果要受到双序列比对的影响。 探测重复体的边界也是一个方面，p r i c e 提出一种算法p e p e a t s c o u t 2 9 ， 通过种子的一致性扩展来识别重复体边界。r e d g a r 和e m y e r s 制作了工具 p i l e r 3 0 】，通过考虑知名的重复结构、末端重复何串联数组来发现具有可靠边界 的重复体。 以上介绍了现有的很多重复体识别算法，但是还没有一种能非常完善的解决 重复体的识别问题的算法。同时因为要处理的数据对象很大，因此需要在计算时 间和空间上都非常有效的算法。 第一章绪论 5 1 3 本文所做的工作 本文旨在对d n a 序列中重复体识别中的一些关键问题进行研究与探讨，重点 在于研究如何在不损失精度的情况下，降低算法的时间复杂度。 本文首先介绍了重复体识别领域相关的理论知识。分类介绍了当前比较流行 的重复体识别算法，分析了各类型算法的优缺点，说明了当前在重复体识别中存 在的问题。 接着本文根据初级重复体的概念，提出了一种基于后缀树的识别初级重复体 的r e p s e e k e r 算法。算法采用最低限制频率，并通过重叠性合并，最大程度地扩 展了重复体的长度。算法以d n a 序列所构造的后缀树作为输入，并以基于后缀 树的查询算法作为手段，最终生成输入的d n a 序列的初级重复体分类表。为了 进一步地提高r e p s e c k c r 算法的效率，通过对后缀树的构造过程以及对基于后缀 树的查询算法的研究，我们对后缀树构造算法进行了适应性改进。在构造后缀树 时，给叶子节点编号，并在分支节点加入了叶子信息数组l l ( 1 e a f l i s t ) 。从而避免 了r e p s e e k e r 算法进行高频度的子树遍历。 文章最后，使用了n c b i 中的几条典型d n a 序列作为测试对象，并与改进 u k k o n c n 后缀树前的重复体识别算法做了比较，验证了改进对r e p s e e k e r 算法的 时间效率的提高。 1 4 本文章节安排 针对当前国际上流行的重复体识别算法进行了细致分析和深入研究，根据初 级重复体的定义，提出了一种新的基于后缀树的初级重复体的识别算法。 论文内容具体安排如下： 第一章主要介绍重复体识别问题的背景知识，重复体识别的意义和研究现 状。 第二章对g k k o n e i l 后缀树构造算法的仔细深入分析，通过一个实例详细地 分析了u 妓o n e n 后缀树构造的全过程。对后缀树构造算法进行了适应性改进，加 入了l l 数组，并提出了基于改进的后缀树的查询算法。 第三章基于对初级重复体的定义，提出并实现了r 印s e e k e r 重复体识别算 法。分析了u k k o n c n 后缀树以及基于它的查询算法的缺点，在r e p s e e k e r 算法中 充分使用基于改进后缀树的查询算法，快速准确地在输入的d n a 序列中收集所 需信息。本章最后通过使用n c b i 中大小不等的d n a 序列作为测试对象，以识 别出的重复体个数、最大重复体及其长度、重复体的归类表作为结果，并与基于 6d n a 序列中基于后缀树的重复体识别算法 改进前后缀树的识别程序进行了时间性能上的对比。 第四章对整篇文章进行了总结，分析了方法中的不足，并指出了今后的研究 方向。 第二章后缀树 7 第二章后缀树 2 1 相关定义 定义2 1 设有字符集合，s + ；对于所有字符串b ，称b 是s 的后缀： i ( b = s i ，l s l 1 】) ，其中i = o ，1 ，l s l 1 ，i s l 为字符串s 的长度，特殊的，空串也是s 的后缀。实际上是任何字符串的后缀。 定义2 2 设有字符集合，s + ；对于所有字符串p ，称p 是s 的前缀： i ( p = s 0 ，i 】) ，其中i = 0 ，1 ，l s l 一1 ，l s i 为字符串s 的长度，特殊的，空串也是s 的前缀。实际上e 是任何字符串的前缀。 定义2 - 3 设字符串s l o m 】，s 2 o n + ，且m - - 1 1 ，若有s l o = s 2 i ， s l 1 = s 2 i + 1 ，s l m = s 2 i + m ，0 = i = n 一1 1 1 ，则有s l g s 2 ，称s l 是s 2 的一个子串。 2 2 后缀树 后缀树是字符串领域的一种非常重要的数据结构，由于其高效的索引能力， 它逐渐成为生物信息领域的主要研究工具。对后缀树的研究大概可以追溯到上个 世纪六十年代末。m o r r i s o n 在1 9 6 8 年提出了p a t r i c i a 树的概念，又称为后缀字典 树，这也就是后来的后缀树的原型【3 1 1 。所以在我们介绍后缀树的概念之前，我们 先介绍后缀字典树的概念。给定长度为n 的字符串s ，s 的后缀字典树是一颗高 度为1 1 并且含有n 个叶子的树。树中的每一条边都标识着字符串s 的一个字符。 任何由一个节点发出的两条边上的字符不允许相同。从根节点到任何一个叶子节 点的路径上的字符连接起来，都构成字符串s 的一个后缀。这样的一颗树就称为 字符串s 的后缀字典树。 例如，设s = ”a g a g a g c ”，其后缀字典树如图2 1 所示。 我们可以看到，树中将原字符串的所有后缀以树的形式索引起来。这样，原 字符串的任何一个子串都出现在树中由根节点开始的一条路径上。这就使得字符 串匹配问题变得非常简单，关于使用后缀树进行字符串匹配的问题将在后面进行 介绍。然而，后缀字典树并没有得到广泛的应用，这是因为构造后缀字典树需要 o ( n z ) 的时间和空间。 d n a 序列中基于后缀树的重复体识别算法 图2 1s = ”a g a g a g c ”后缀字典树 事实上，所谓后缀树就是一种压缩的后缀字典树，它将后缀字典树的边进行 压缩，使得树中只有一个孩子的节点与其孩子节点合并，并将指向孩子节点的边 上的标识连接到上一层的边上，从而使得树中边上的标识可以是原字符串的一个 子串。下面给出后缀树的定义： 定义3 4给定长度为m 的字符串s ，s 的后缀树是一颗有唯一根的有向的 树，树中有m 个叶子节点。每个分支节点也就是非叶子节点( 根节点除外) 都至少 有两个孩子。树中的每一条边上标识着s 的一个非空子串。任何两条由同一节点 发出的边上的标识的第一个字符不允许相同。若对1 1 1 个叶子进行顺序编号，从根 节点出发到叶子i 的路径上字符顺序串联就是字符串s 的第i 个后缀，即s i m 】。 例如，字符串”a g a g a g c ”的后缀树如图2 2 所示。从根节点到叶子0 的路径上 字符串联就是从s 第0 个字符开始的后缀”a g a g a g c 什，从根节点到叶子节点3 ，可 以串联成从s 第3 个字符开始的后缀”g a g c 。 基于以上后缀树的定义，不能够确保任意字符串s 的后缀树都存在。如果s 的一个后缀a 是s 的另一后缀b 的前缀，那么将无法通过从根出发到某个叶子节 点结束的方式来得到a ，这是因为后缀a 的路径将不会在叶子节点处终结。例如， 如果建立s = ”a g a g a g ”的后缀树，那么s 的后缀”a g a g ”是s 的另一后缀”a g a g a g ”的一 个前缀，那么从根开始串联出”a g a g ”的路径将不会终止于一个叶子节点。 为了避免出现这种情况，在s 的末尾增加一个s 中从来没有出现过的字符作 为s 的终结符号。程序中用”作为s 的终结符号。 第二章后缀树 9 图2 2 s = ”a g a g a g c ”的后缀树 后缀树将给定字符串的所有后缀以树的形式组织起来，从而使原字符串的任 何一个子串都出现在树中由根节点开始的某一路径上。这样，字符串匹配问题就 变得简单。 2 3 后缀树构造算法 后缀树构造方法大体上可以分为两种类型：经典的一次一个后缀的构造方法 ( o n e s u f f i x a t a - t i m e ) 和近年来采用的分治思想的构造方法( d i v i d e a n d c o n q u e r ) 。 1 9 7 3 年w e i n e r 第一次提出了线性时间的建树算法【3 2 】。几年后，m e c r e i g h t 提 出了更节约空间的算法【3 3 1 。直到1 9 9 5 年u k k o n e l l 提出了改进的线性时间建树算 法【3 4 】，它易于理解，由于它采用了路径压缩的方法，即每条边不只代表一个字符， 有可能是一个字符串，大大节省了构造此后缀树所花的时间与空间，而且具有在 线特性，即从左到右依次处理每个字符。 2 3 1u k k o n e n 后缀树构造 1 u k k o n e r l 后缀树的结构 u k k o n e l l 后缀树构造方法，对于给定的字符串s ，u k k o l l c l l 算法起始于一颗 空树，然后逐次将s 的i s l 个前缀的每一个加入到后缀树。例如，当为s = ”a g t g t g e 建立一个后缀树，如图2 3 ， a ”被插入到树中，然后是”a g ”，再是”孵”等等。当 ”a g t g t g e ”被最终插入，这颗后缀树创建完成。 o 日y 爿巴冷a l = 令 w - 盯p t yt r e l 图2 3 逐步建立后缀树 1 0 d n a 序列中基于后缀树的重复体识别算法 通过遍历后缀树和访问当前树的每一个后缀，从而增加一个新的前缀到树中。 我们从当前树中最长的后缀开始，一直到最短的后缀，通常是一个空串。每一个 后缀结束在下列节点中的一种： 叶子节点( 1 e a f n o d e ) ，后缀树中没有任何子孙节点的节点。 外部节点( i m p l i c i tn o d e ) ，也称为分支节点，即以它作为起点的边至少有两条。 内部节点( e x p l i c i tn o d e ) ，它们都是后缀字典树的节点，只是由于路径压缩而 去掉了。后缀树建立后，这些内部节点有时就有可能成为外部节点。 例如，输入序列为s = ”a g g c c t ”建立后缀树，当加入了”a g g c ”后，树中有5 个后 缀( 包括一个空串) ，如图2 4 中，节点1 ，2 ，4 和5 是叶子节点；”a g ，”a g g ” 和”g 都结束于一条边的中间，这些位置就是内部节点；非叶子节点0 和3 是外 部节点。 图2 4 建后缀树，输入序列是”a g g c e t ”，加入了”a g g c ”后 2 后缀树的更新过程 当加入下一个前缀”a g g c c ”到树中，就意味着访问当前树中的每一个后缀，同 时追加c 到这些后缀的尾部。前4 个后缀，a g g c ，”g g c ”，”g c 和”c ”都结束于叶 子节点。由于将路径压缩应用到后缀树，加入一个新的字符到一个叶子节点就将 仅仅是将其追加到尾部。当所有的叶子节点被更新后，我们仍然需要将”c ”追加到 以节点0 开始的空串后，形成当前前缀的后缀树，但如图2 5 中，当前前缀的最 后一个后缀”c ”始于节点0 ，同时终止于内部节点，该内部节点向下经过一个字符 导向节点5 。 图2 5 加入”a g g c c ”后产生的树 更新图2 4 中的树相对简单，我们进行了两种更新：第一种，简单地扩展边； 第二种，对内部节点的更新，没有动作。 我们加入”a g g c c t ”到图2 5 中的树中，引出了另外两种更新，第一种，在内 第二章后缀树 1 1 部节点处分裂一条现有的边，加入一个新的节点作为分支节点，接着在新节点下 加入一条新边。第二种，加入一条新边到分支节点。 图2 6 边的分裂和加入叶节点 当加入前缀”a g g c c t ”到图2 5 的树中时，首先从最长的后缀”a g g e e ”开始一直到 最短的空串。图2 5 中，结束于叶子节点的后缀有”a g g e c ”，”g g c e ”，”g e e ”和”c c ”。 更新较长的后缀就像更新叶子节点一样简单。图2 6 中的第一个树只是简单地扩 展了这四个后缀。 图2 5 中没有终止于叶子节点的第一个后缀是c ”。当更新一个后缀树时，我 们称第一个这样的字符在输入串中的位置为活动点。所有从活动点之前开始的后 缀都终止于某个叶子节点。”a g g c c ”的后缀”c ”终止于一个边 c o t 上的内部节点。当 测试到内部节点，我们需要看是否该节点下是否有与新加字符匹配的边。当加入 ”t ”时，很明显”e c t ”中的第一个”c ”只有一个后继”c ，这就意味着我们不得不加入 一个后继”t ”。这个过程分为两步：首先我们在第一个”c ”之后分裂当前的边，新加 人一个分支节点。图2 6 中间的树就是分裂后的状态。接着，在该分支节点下创 建一条新边”t ”和一个新叶子。当分裂一条边和加入一个新的节点后，我们就能看 到像图2 6 中的第三个树。 在更新了”a g g c c ”的后缀”c ”之后，我们还要更新”a g g c c 的一个更短的后缀即 空串。空串结束在外部节点0 ，我们要看节点o 是否有子边开始于字字符”t 。在 图2 6 中，我们可以看到节点0 下没有这样的边，因此如图2 7 所示，加入一个新 的叶子节点和表示”t ”的边。 图2 7 更新一个空串 3 u k k o n e l l 后缀树构造算法的概括及扩展 u k k o l l c l l 算法，对于输入串s 来说，后缀树的构造首先开始于一个空串并建 1 2 d n a 序列中基于后缀树的重复体识别算法 立根节点0 。从输入串s 左边开始，每次加入一个字符到当前更新的前缀p 中， 用p 的每一后缀串去更新后缀树。这样时间复杂度将会是o ( n 2 ) 。 根据后缀树的一些特点，我们生成了一个有相当效率的算法。最主要的特点： 一旦一个叶子节点被创建，那么它始终都是叶子节点。我们将指向该叶子节点的 边称为叶边。也就是说该节点下不会再创建任何边和子节点，叶边只能进行字符 串的扩展。更重要的是，每次我们加入一个新的前缀p 到树中，我们会将该新前 缀p 的最后一个字符追加到每一条叶边上。大多数情况扩展叶边要进行i p l 1 次。 在活动节点之前开始的后缀都会终止于某个叶子节点，所以为了省略扩展与 叶子相连边上的字符串的过程，每次我们创建一个新叶子，我们会自动让指向该 叶子的边代表从当前位置一直到输入串末尾的字符串。若是这样，当创建一个叶 子节点后，就可以忘掉它，也就是说不用再去扩展叶边，因为它已经是最终的扩 展结果了。如果要分裂一条边，只需要改变它的开始位置，而不需要去管它是否 能够到达输入串的末尾。我们按照新方法，图2 3 中的构造过程就对应的演变成 图2 8 中的过程。 e m p 。t yt r e e 日垂日 巴专訇匕冷 l j 图2 8 省略对叶子边的扩展 这样，每一次更新后缀树所要参照的字符串从空串开始，每次加入一个字符， 一直到整个输入串。由于内部节点的存在，有时当加入一个字符，该字符中止于 一个内部节点，这样使得在更新过程中暂时无法生成新的叶子和新边，因而要保 存这些未处理的字符串。该字符串的开始位置就是活动点。 下面是u k k o n e n 后缀树构造算法的一个类c 程序，整个构造过程就是不断更 新的过程。n e ws u f f i x 是每次用来更新后缀树的输入序列的一个新的前缀。 a c t i v ep o i n t 表示活跃点，c u r r e n ts u f f i x 就是上面提到的保留的字符串，即从活跃 点一直到上次更新到的位置的字符串。 u p d a t e ( n e w _ s u f f i x ) c u r r e n t s u f f i x = a c t i v e _ _ p o i n t t e s t c h a r = l a s t c h a ri nn e w s u f f i x d o n e = f a l s e ； w h i l e ( ! d o n e ) i fc u r r e n ts u f f i xe n d sa ta l le x p l i c i tn o d e 第二章后缀树 i ft h en o d eh a sn od e s c e n d a n te d g es t a r t i n gw i t ht e s t + c h a r c r e a t en e wl e a fe d g es t a r t i n ga tt h ee x p l i c i tn o d e e l s e d o n e = t r u e ； ) e l s e i ft h ei m p l i c i tn o d e sn e x te h a ri s n tt e s t c h a r s p l i tt h ee d g ea lt h ei m p l i c i tn o d e c r e a t en e wl e a fe d g es t a r t i n ga tt h es p l i ti nt h ee d g e ) e l s e d o n e = t r u e ； ) i fc u r r e n t s u f f i xi st h ee m p t ys t r i n g d o n e = t r u e ； e l s e e u r r e n t s u f f i x = n e x t _ s m a l l e r _ s u f f i x ( c u r r e n t s u f f i x ) ) a c t i v e _ p o i n t = c u r r e n t s u f f i x ) 4 加入后缀链( s u f f i xl i n k ) 上面的类c 程序基本上准确地描述了建立后缀树的一次更新过程。通过 n e x t _ s m a n e r s u m x o 在树上的导航，可以移动下一个更小的后缀节点处。这个子 过程将找到一个与指定后缀相对应内部节点或者外部节点。 如果通过简单地遍历后缀树来找到这个节点，那么该算法将不是一个线性时 间算法。为了使算法时间复杂度达到线性，在每一个分支节点加入一个指针，称 之为后缀指针，也叫后缀链。若每一个分支节点代表了一个由根节点到该节点路 径上的字符串，那么一个分支节点a 上的后缀指针指向另一个分支节点b ，若a 代表的字符串是从输入串的位置i 到n ，那么b 就代表输入串从位置i + l 到n 的 字符串。如图2 9 所示，节点3 的后缀指针指向节点5 ，节点3 代表字符串”a g a g ”， 节点5 代表字符串”g a g ”。 1 4 d n a 序列中基于后缀树的重复体识别算法 图2 9 有后缀链的后缀树 后缀指针的建立和建立后缀树是同时进行的。保存新建叶子的父节点序号， 每次建立一条新叶子，就建立一个从上次建立的叶子的父节点到当前叶子的父节 点。有了后缀指针，就可以很容易的从当前后缀到下一后缀，同时使得该后缀树 的构造算法从o ( n 2 ) 到了o ( n ) 。 2 3 2u k k o n e n 后缀树构造算法实现 a l g o r i t h m ：u k k o n e n ( s ) i n p u t ：s t r i n gs o fl e n g t hn o u t p u t ：n o d el i s ta n de d g el i s to ft h es u f f i x t r e eo fs 1 s t a r t n o d eo fe d g el i s t - - 一1 1 1 1 ei n i t i a le d g el i s t 2 a p f - - ( o ，( o ，一1 ) ，”) t h ei n i t i a la c t i v ep