（计算机应用技术专业论文）生物信息学中多序列比对算法的研究.pdf

v 7 钾与伫 中文摘要 中文摘要 生物信息学是在生命科学的研究中，以计算机为工具对生物信息进 行储存、检索和分析的科学。如何设计快速而有效的算法对生物数据进 行处理，从而发现蕴涵于其中的丰富生物知识，是生物信息学研究的重 要内容。 本文主要对适用于生物序列数据上的后缀树索引技术和生物信息学 中的多序列比对算法进行了分析和研究。在分析了后缀树在生物序列数 据上应用的主要问题的基础上，为了解决后缀树索引占用过多内存空间 的问题，提出了部分后缀树的索引技术，包括了索引的创建和在其上的 查询，理论分析和实验结果显示新方法有效的降低了存储空间的代价， 并且子部分非常适合分布处理。在部分后缀树的基础上提出了后缀树的 并行算法，解决了后缀树在应用上的内存瓶颈问题，因此更适合大规模 的序列分析。本文深入分析了多种多序列比对算法，把引入知识到序列 比对中的思想应用到采用渐进策略的c l u s t a i w 算法中，作为对算法的改 进，能够通过已有的知识得到更好的比对结果。 关键词：序列比对多序列比对索引后缀树部分后缀树 黑龙江大学硕士学位论文 a b s t r a c t b i o i n f o r m a t i c si st h es c i e n c eo fu s i n gc o m p u t e rt e c h n o l o g yt os t o r e ， r e t r i e v ea n da n a l y z eb i o l o g i c a li n f o r m a t i o ni nt h ef i e l do fl i f es c i e n c e s t o d e v e l o pr a p i da n de f f e c t i v ec o m p u t e ra l g o r i t h mt of i n dk n o w l e d g ef r o mv e r y l a r g eb i o l o g i c a ld a t ai st h em a i nr e s e a r c hw o r k t h i st h e s i sm a i n l yf o c u s e so nt h es t u d yo fs u f f i xt r e ei n d e xt e c h n i c a l d e a l i n gw i t hb i o s e q u e n c e sa n dm u l t i p l es e q u e n c e sa l i g n m e n tp r o b l e mi n b i o i n f o r m a t i c s t h et h e s i ss u r v e y so fa p p l i c a t i o na b o u tt h es u f f i xt r e e ， p r e s e n t sp a r t i a ls u f f i xt r e ei n d e xt e c h n i c a lt or e d u c em e m o r yu s a g e t h e n b a s e d o np a r t i a ls u f f i xt r e e ，p r e s e n t san e wp a r a l l e la l g o r i t h mo fs u f f i xt r e e ， w h i c hc a r lc o n s t r u c t i o nl a r g es u f f i xt r e ei nm e m o r ya n dm o r ep e r f e c tt ov e r y l a r g es e q u e n c e s i nt h ee n d ，t h et h e s i sa n a l y s i s d i v e r s ea l g o r i t h ma b o u t m u l t i p l es e q u e n c e sa l i g n m e n t ，i n o r d e rt og e tm o r eb i o l o g i c a l l yo p t i m a l a l i g n m e n tr e s u l t ，p r e s e n t sa ni m p r o v e m e n to fi n c o r p o r a t i n gu s e rk n o w l e d g e a b o u tf a m i l ys e q u e n c ei n t oc l u s t a l wp r o g r e s s i v em u l t i p l es e q u e n c e a l i g n m e n ta l g o r i t h m k e y w o r d s ：s e q u e n c ea l i g n m e n t ，m u l t i p l es e q u e n c e sa l i g n m e n t ，i n d e x ， s u 衢xt r e e p a r t i a ls u 师xt r e e 第1 章引言 1 1 研究背景 第1 章引言 随着人类基因组计划的实施，通过基因组测序、蛋白质序列测定和 结构解析等试验，分子生物学家得到了大量的有关生物分子的原始数据。 然而，面对如此丰富的数据，我们掌握的信息却很匮乏，产生分子遗传 学数据的能力大大超出了我们分析这些数据的能力。生物学而临的情况 是拥有了大量的数据却不能完全的理解、解析和利用这些数据。 现在人类基因组计划已于2 0 0 1 年提前完成，人们的注意力已从基因 组测序转向对基因组表达的分析，对蛋白质组结构与功能的预测。要解 决这个问题，必然需要强有力的计算机技术来协助完成对这些数据的分 析工作。在处理生物数据的同时对计算机技术也面临着挑战，一方面是 制造出运行更快，价格更便宜的硬件，一方面是设计出时间更优，运行 结果更好的算法。从而能从海量的生物数据中发现蕴涵于其中丰富的生 物知识。 在生物学的研究中，比较分析获取有用的信息和知识是一个常用的 方法。达尔文正是研究比较了加拉帕戈斯群岛上的鸟类的形态学特征， 从而提出了自然选择学说。现在的序列比对正是对基因和蛋白质序列进 行比较，从核酸和氨基酸的层次上去分析序列的相同点和不同点，以期 能够推测它们的结构、功能以及进化上的联系。 1 1 1 生物信息学介绍 生物信息学是8 0 年代末随着人类基因组计划的启动而兴起的门 黑龙江大学硕士学位论文 新的交叉学科，最初常被称为基因组信息学。生物信息学是在生命科学 的研究中，以计算机为工具对生物信息进行储存、检索和分析的科学。 它是当今生命科学和自然科学的重大前沿领域之一，同时也将是2 1 世纪 自然科学的核心领域之一。其研究重点主要体现在基因组学( g e n o m i c s ) 和蛋白组学( p r o t e o m i c s ) 两方面，具体说，是从核酸和蛋白质序列出发， 分析序列中表达的结构与功能的生物信息。 目前归入生物信息学领域大致有以下几个方面【i 】： 第一，各种生物数据库的建立和管理。这是一切生物信息学工作的 基础，通常要有计算机科学背景的专业人员与生物学者密切合作。 第二，数据库接口和检索工具的研制，数据库的内容来自万千生物 学者的日积月累，最终又为生物学所用，但不能要求一般生物学工资者 具有高深的计算机和网络训练。因此，必须发展查询数据库和向库里提 供数据的方便接口。 第三，研究新算法，发展方便适用的程序，是生物信息学的日常任 务。人类基因组计划的实施，配合大规模的d n a 自动测序，对信息的采 集和处理提出了空前的要求。从各种图谱的分析、大量序列片断的比对、 计算机克隆、寻找基因和预测结构与功能，到数据和研究结果的可视化， 无不需要高效率的算法和程序。 第四，生物信息学最重要的任务是从海量数据中提取新知识。这首 先要从d n a 序列中识别编码蛋白质的基因，以及调控基因表达的各种信 号。其次，从基因组编码序列翻译出的蛋白质序列的数目急剧增加，根 本不可能用实验的方法一一确定它们的结构和功能。 第五，d n a 芯片和微阵列的发展，把一定组织或生物体内力干基因 时空表达的研究提上日程。研究基因表达过程中的聚类关系，从中提取 调控网络和代谢途径的知识，进而从整体上掌握细胞内的全部巨相耦合 第1 章引言 的生化反应。这一切都要求发展新的算法，这是生物信息学刚刚揭开的 新篇章。 1 1 2 序列比对 比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找 对象可能具备的特性。在生物信息学研究中，比对是最常用的研究手段。 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过 比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化 关系。进一步的比对是将多个蛋白质或核酸同时进行比较，寻找这些有 进化关系的序列之间共同的保守区域、位点和p r o f i l e ，从而探索导致 它们产生共同功能的序列模式。此外，还可以把蛋白质序列与核酸序列 相比来探索核酸序列可能的表达框架：把蛋白质序列与具有三维结构信 息的蛋白质相比较，从而获得蛋白质折叠类型的信息 ”。 序列比对的理论基础是进化学说，如果两个序列之间具有足够的相 似性，就推测二者可能有共同的进化祖先，经过序列内残基的替换、残 基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。序 列相似和序列同源是不同的概念，序列之间的相似程度是可以量化的参 数，而序列是否同源需要有进化事实的验证。 早期的序列比对是全局的序列比较，但由于蛋白质具有的模块性质， 可能由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通 常用打分矩阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵 点记录两个维上对应的两个残基的相似性分数，分数越高则说明两个残 基越相似。因此，序列比对问题变成在矩箨里寻找最佳比对路径，目前 最有效的方法是n e e d l e m a n w i n c h 动态规划算法，在此基础上又改良产 生了s m i t h w a t e r m a n 算法和s i m 算法。 3 一 黑龙江大学硕士学位论文 在进行序列两两比对时，有两方面问题直接影响相似性分值：取代 矩阵和空位罚分。粗糙的比对方法仅仅用相同不同来描述两个残基的关 系，显然这种方法无法描述残基取代对结构和功能的不同影响效果。用 一个取代矩阵来描述氨基酸残基两两取代的分值会大大提高比对的敏感 性和生物学意义。虽然针对不同的研究目标和对象应该构建适宜的替换 矩阵，但国际上常用的替换矩阵有p a m 和b l o s u m 3 等。它们来源于不同 的构建方法和不同的参数选择。对于不同的对象可以采用不同的替换矩 阵以获得更多信息。 p a m 为可接受点突变( p o i n za c c e p t e dm u r a t i o n ) ，1 个p a m 的进化 距离表示1 0 0 个残基中发生一个残基突变的概率。对应于一个更大进化 距离间隔的突变概率矩阵，可以通过对初始矩阵进行适当的数学处理得 到，如常用的p a m 2 5 0 矩阵，p a m 2 5 0 相似性分数矩阵相当于在两个序列 之间具有2 0 的残基匹配。突变数据矩阵的产生基于相似性较高( 通常 为8 5 以上) 的序列比对，那些进化距离较远的矩阵( 如p a m 2 5 0 ) 是从 初始模型中推算出来而不是直接计算得到的，其准确率受到一定限制。 而序列分析的关键是检测进化距离较远的序列之问是否具有同源性，因 此突变数据矩阵在实际使用时存在着一定的局限性。 模块替换矩阵b l o s u m 以序列片段为基础，它是基于蛋白质模块数据 库b l o c k s 。h e n r i c o 夫妇从蛋白质模块数据库b l o c k s 中找出一组替换矩 阵，用于解决序列的远距离相关。 多序列比对就是把两条以上可能有系统进化关系的序列进行比对的 方法。目前对多序列比对的研究还在不断前进中，现有的大多数算法都 基于渐进的比对思想，在两两比对的基础上逐步得到多序列比对的结果。 多序列比对算法是生物信息学中的最基本算法，是生物体的进化分 析、蛋白质的分析和预测等生物体研究的基础，具有重要的理论意义和 第1 章引言 实用价值。 1 1 3 生物数据上的索引技术 随着大量生物学实验的数据积累，形成了当前数以百计的生物信息 数据库。它们各自按一定的目标收集和整理生物学实验数据，并提供相 关的数据查询、数据处理的服务。随着因特网的普及，这些数据库大多 可以通过网络来访问，或者通过网络进行文件下载。 这些生物信息数据库可以分为一级数据库和二级数据库。一级数据 库的数据都直接来源于实验获得的原始数据，只经过简单的归类整理和 注释；二级数据库是在一级数据库、实验数据和理论分析的基础上针对 特定目标衍生而来，是对生物学知识和信息的进一步整理。国际上著名 的一级核酸数据库有g e n b a n k 数据库、e m b l 核酸库和d d b j 库等：蛋白 质序列数据库有s w i s s p r o t 、p i r 等；蛋白质结构库有p d b 等。国际上 二级生物学数据库非常多，它们因为针对不同的研究内容和需要而各具 特色，如人类基因组图谱库g d b 、转录因子和结合位点库t r a n s f a c 、蛋 白质结构家族分类库s c o p 等等。 g e n b a n k 库包含了所有已知的核酸序列和蛋白质序列，以及与它们 相关的文献著作和生物学注释。它是由美国国立生物技术信息中心( n c b i ) 建立和维护的。它的数据直接来源于测序工作者提交的序列：由测序中 心提交的大量e s t 序列和其它测序数据；以及与其它数据机构协作交换 数据而来。到2 0 0 3 年8 月，g e n b a n k 中收集的序列数量达到2 7 2 万条， 3 3 9 百亿个碱基【4 】，而且数据增长的速度还在不断加快。 生物信息数据库的飞快增长，对生物信息数据的处理提出了挑战。 在数据库领域，可以通过建立索引的方式，在牺牲存储索引的存储空间 和耗费建立索引的时间开销的前提下来提高查询等数据处理的效率。 5 一 黑龙江大学硕士学位论文 i i i i i i i i i i 宣i i i i 宣i i i i i i i i i i i 蕾i i i i i i i i i 嗣i i i i i i i i i i | | i i i i i d n a 序列可以看成是由a 、c 、t 、g 四个字符组成的字符串序列，蛋 白质序列可以看成由2 0 个氨基酸组成的字符串。由于缺少结构信息，利 用传统的索引技术对这些字符序列的数据创建快速而有效的索引会很困 难。后缀树( s u f f i xt r e e ) 【5 】和后缀数组( s u f f i xa r r a y ) 1 6 1 是现在研 究比较活跃，且有效地应用于生物序列数据上的两种索引技术，这两种 索引技术也还广泛应用在数据信息检索等领域。 1 2 国内外的研究现状 序列比对算法是生物信息学中的基本算法，是对进步分析数据和 处理数据的不可缺少的工具。多序列比对算法的研究从上世纪8 0 年代末 开始，9 4 年后很多的多序列比对算法开始陆续提出。随着人们在生物信 息学领域的进一步研究，更多的技术和更先进的思想溶入到多序列比对 算法中，特别是索引技术和了解了越来越多的序列知识，对多序列比对 算法也提出了更高的要求。目前多序列比对算法的研究十分活跃，算法 从运行效率、结果的准确性和处理规模上不断有所改进和突破。 国外许多研究机构和大学都很重视对多序列比对算法的研究，其中 比较重要的有e m b l ( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y ) 欧洲 分子生物学实验室，他们提出了目前应用最为广泛的c l u s t a l w 多序列比 对算法，e b i ( 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 ) 欧洲生物信息研 究所和t i g r ( t h ei n s t i t u t eo fg e n o m icr e s e a r c h ) 等。由f 多序列比 对问题是n p 难问题，同时在生物界也不能明确肯定什么样的比对是最准 确的，以及在选择合适序列进行比对上都还有许多问题，导致目前还缺 乏快速而十分有效的多序列比对算法，需要做更进一步的研究工作。 我国目前有许多科研机构和大学从事生物信息学方面的研究，其中 有中国科学院计算所、武汉大学和中国农业大学等。但对多序列比对算 一r 一 第1 苹引言 法的研究不多。 由于生物序列数据的特殊性，在其上建立适当的索引方式的研究一 直都是研究的热点。其中后缀树是比较合适的一种索引方式，数据库、 生物信息学和信息检索等领域都有对后缀树索引技术的研究。基于后缀 树上的查找时间仅与要查找的字符串长度成正比，在后缀树的应用上， 如何高效地构造后缀树是问题的关键。虽然线性时间的创建算法最早在 1 9 7 3 年就提出了，但内存消耗过大一直是后缀树索引在应用上的障碍。 目前研究的重点主要集中在后缀树的并行算法、外存算法和更为有效的 内存算法上。 1 3 本文的贡献 本文是对应用于生物序列数据上的后缀树索引技术和多序列比对算 法的研究。在对后缀树索引技术进行深入分析后，提出了根据查询内容 只建立部分后缀树的思想，用来实现对规模较大数据的内存算法。 在部分后缀树的基础之上提出了后缀树的并行算法，该并行算法不 但实现了数据的分布，解决了目前后缀树在应用上的内存瓶颈问题，且 保持了后缀树在查洵上的高效性。 本文在深入分析了多种多序列比对算法的基础之上，提出了对 c l u s t a l w 算法的改进，把引入知识到序列比对中的思想应用到采用渐进 策略的c l u s t a l w 算法中，能够通过已有的关于序列的知识来得到更好的 比对结果。 黑龙江大学硕士学位论文 1 4 论文结构 本文主要分为五个部分。 第：二章介绍了应用于生物序列数据上的索引技术，包括有后缀树、 后缀数组等，重点介绍了后缀树的构造和查询算法。给出了本文提出的 建立部分后缀树的构造和查询算法。最后是对算法的实现和实验分析。 第三章介绍了现有的后缀树并行算法，比较了它们的特点。给出了 本文设计的基于部分后缀树的并行后缀树算法。最后对算法的实现和实 验分析进行了介绍。 第四章介绍了生物信息学中的多序列比对算法，重点介绍了采用渐 进策略的c l u s t a l w 算法、采用索引技术和用户介入思想的序列比对算 法。给出了本文对c 1 u s t a i w 算法进行改进的思想和实现。最后是对改进 后的算法的实验分析和总结。 最后，对本文进行了结论，给出了不足之处和未来的工作。 第2 章后缀树索引技术的研究 第2 章后缀树索引技术的研究 由于生物序列数据的特殊性，在其上缺少结构信息，利用传统的索 引技术对于这些字符序列并不适用。设计快速而有效的适合生物序列数 据的索引技术是目前索引技术研究的重点之一。本文在分析了适用于生 物序列数据的后缀树索引技术的基础之上，针对目前存在的主要问题， 提出了部分创建后缀树的算法。 2 1 各种索引技术的介绍 g e n b a n k 、e m b l 等基因序列数据库中所存的序列越来越多，而且还 在不断的快速增多中，对序列采用索引技术来实现快速处理变得越来越 重要。下面介绍其中主要的i n v e r t e di n d i c e s 7 ，8 ，9 1 、s u f f i xt r e e 和s u 踊x a x r a y 等索引技术。 2 1 1in v o r t e di n d o x 倒排索引是建立在每个词上 倒排索引的数据结构由两部分组成 应用于文档高效检索的索引技术。 一个为s e a r c hs t r u c t u r e ，用来记录 文档中出现的不同的词，另个是p o s t i n gl i s t s ，在s e a r c hs t r u c t u r e 中的 每一个词都有一个p o s t i n gl i s t 记录这个词在文档中出现的位置，词的 p o s t i n gl i s t 构成了整个的p o s t i n gl i s t s 。图2 1 是一个倒排索引的示例。 倒排索引在文档检索是一一个很好的索引技术，但由于d n a 序列不是 由字组成，仅仅是一串字符序列，所以倒排索引不能直接在d n a 序列上 应用。在论文 8 中提出把生物信息序列看成是由等长度的子序列组成， 黑龙江大学硕士学位论文 文中称为间隔( i n t e r v a l ) ，间隔中的字符可以相互覆盖，把序列中等长的 子序列，也就是间隔看成是文档中的字来处理。这样如果有长度为l 的 序列，每个间隔的长度为r l ，总的l 、日j 隔数就为( l 一1 1 + 1 ) 。图2 2 是l = 7 ，n = 3 的倒排索引的例子。 图2 1 文档中的倒排索g 0123 456 口丑亚圈 图2 2 在生物序列上的倒排索g 第2 章后缀树索引技术的研，e 从图2 2 我们可以得到序列a c f 在整个序列的第4 个位置出现，a g a 在第0 位和第2 位出现。通过这种方式可以得到长度为3 的子序列在整 个序列出现的次数和位置。 在生物序列上应用的倒排索引是一个简单的方法，对大量的间隔数 据可以采用哈希方法，分块存储在不同的桶中，从而提高查询速度。但 这种索引技术和n 的长度有关，对不同的查询需要有不同的索引。哈希 函数的选择也是一个难点，当数据量很大时容易发生冲突。 2 1 2s u f f l xt r e e s u f f i xt r e e 是用树的存储结构来存储字符串，从而能够实现快速的 字符串检索，检索的时间复杂度和被检索的字符串长度成线性关系。在 介绍s u f f i xt r e e 前先介绍s u f f i xt r i e ： 定义2 1 ：设r = t l t ：f 。是定义在字符集的字符串，正。= t i r f ，是 t 的子序列( 1 i j n ) ，字符串正= 正“= t i t 。t 。是字符串t 的一个后缀字符串，t = 正，= t ，t ，是字符串t 的一个前缀字符串。 表2 1 序列t = a g a g a c t $ 的后缀字符串 黑龙江大学硕士学位论文 t r i e 是一个树，具有下面的性质： 1 树中的每一个结点包含一个字符，根结点除外。 2 一个结点的各个子结点包含不同的字符。 s t ，( t ) 表示字符串t 对应的s u f f ixt r i e ，所有叶结点i 可以表示所 有t 的后缀字符串，s r ，( r ) 上的所有结点可以表示t 的所有子串。图2 4 是字符序列a g a g a c t $ 的t r i e 。 当要查询字符串a c t 时，从根结点出发，沿着边标记的字符，我们 可以找到叶结点，从叶结点可以定位a c t 在字符串的第四个位置上。图 2 3 是序列t = a g a g a c t $ 对应的s u f f i xt r i e ，从图中可以看出t r i e 很浪 费存储空间。 图2 3 序列a g a g a c t $ 对应的s u f f i xt r i e 第2 章后缀树索 3 1 技术的研冗 w e i n e r 在论文 5 中提出s u f f i xt r e e ，它是压缩的s u f f i xy r i e 。把其中 只包含一个子结点的结点合并成一个结点，从而压缩了1 竽储空间，得到 了更为实用s u f f i xt r e e 。 对于一个由m 个字符构成的字符串s ，其后缀树t 是一棵有i t l 个叶 子结点的树。树中的每个中间结点至少有两个儿子结点，每条边标记一 个非空字符串，并且是s 的子串。任意两条开始于同一个结点的边，它 们标记的是不同字符串。最重要的特性是从根结点沿着边一直到叶结点， 可以通过边上标记的字符串，得到叶结点对应的后缀字符串，从而通过 每个叶结点可以得到s 的所有后缀字符串。t 具有如下性质： 1 每条边标记了s 的子序列。 2 每个中间结点至少有两个子结点。 3 叶结点的个数为m 。 4 每个叶结点对应一条s 的后缀字符串。 图2 4 是序列t = a g a g a c t $ 对应的后缀树。 图2 4 序列t = a g a g a c t $ 对应的s u f f i xt r e e 黑龙江大学硕士学位论文 对于在后缀树上的查询，如设有序列s 的后缀树t ，在其上奄找p ， 长度为1 1 。可以从t 的根结点开始，沿着匹配的边往下查找，直到p 的 所有字符都匹配完毕，此时如果结点是叶结点，可以直接从叶结点中的 结点信息找到p 在序列s 上开始的位置，如果此时的结点不是叶结点， 那么从这个结点开始的子树中的所有叶结点对应的开始位置的m 长子序 列都和p 匹配。如果p 还没有匹配完全，在结点上也找不到和下一字符 匹配的边，那么p 在s 上不出现。 例如当t = a g a g a c t $ ，p = a g a 时，查询沿着图2 5 的根结点 一直走到叶结点0 和2 的父结点，此时对应结点不是叶结点，以此结点 为根结点的子树中所有叶结点记录的开始位置为0 和2 ，即在t 的第l 位和第3 位长度为3 的子序列和p 相等。 2 1 3s u f f ixa r r a y s u f f i xa r r a y 和后缀树样也是一种非常有效的索引技术，实现的功 能相似，在算法上可以互相转化。s u f f i xa r r a y 在存储上优于后缀树，但 仅仅采用基本的后缀树索引技术在查询的效率上不如后缀树索引，通过 增加一些辅助数据结构可以和后缀树上的查询相当 1 0 叫”。 设t = a o a a 。是长度为i n 的字符串，p o s 为t 的后级数组，在数 组中记录的值为0 到m l ，对应的是字符串t 在p o s 位对应的后缀字符 串按字母排序的顺序。图2 5 是一个序列t = a g a g a c t $ 对应的后缀数 鲴： ， p o s 0123 i 456 【2 o45 l 316 图2 5 序列a g a g a c t $ 对应的s u f f i xa r r a y 第2 章后缀树索引技术的研究 构造后缀数组的出发点是把t 所有的后缀字符串按字母顺序排列， 然后把排序的结果放入数组中，也就是p o s 0 是t 所有后缀子序列按字 母排序最小的子序列，如此类推，p o s k 上的字符串小于p o s k + 1 上对 应的字符串。$ 符合表示字符串的终止符号，在字母顺序中是最小的。图 2 6 是序列t = a g a g a c t $ 的后缀数组的存储。 i nm e m o r y gt a$ j g a c - r $ l n d i s k 图2 6 序列a g a g a c t $ 对应的s u f f i xa r r a y 的存储方式 后缀数组上的查询很容易处理，假设有字符串t 并建立了后缀数组 的索引，要查找字符串p 。查询算法的关键是如果p 是t 的子序列，由 于后缀数组是按字母顺序排序的，那么所有可能包含p 的后缀序列都是 相邻，中间没有断开的。例如当t = a g a g a c t $ ，p = a g a 时，查询得到 的开始位置为0 和4 ，在后缀数组中是相邻的。应此在后缀数组中可以 采用折半查找的办法用来查询。假设p 按字母顺序小于p o s m 2 ，那么 就可以继续在p o s 的前半部分继续采用折半查询，同理如果p 按字母顺 序大于p o s m 2 1 ，那么就可以继续在p o s 的后半部分继续采用折半查询。 这样如果查询匹配，那么此时在p o s 中的i 是最小的，继续从i 后再查找， 可以找到比i 更大的查询结果。 黑龙江大学硕士学位论文 2 2 后缀树的创建算法 在后缀树上进行查找的时间仅与要查找的模式字符串的长度成正 比，在应用后缀树解决问题时，如何高效地构造后缀树是问题的关键。 目前，对于串行的后缀树构造算法的研究已经非常成熟，人们提出了线 性时间和空间的算法，其中时间复杂度为o ( n ) 的创建后缀树算法中，具 有代表性的有w e i n e r 斟，u k k o n e n 4 11 5 , 1 6 0 和m c c r e i g h t t l ”。w e i n e r 的算 法是最早提出的线性时间算法，但该算法使用了较多的存储空间， u k k o n e n 算法使用后缀链接( s u f f i xl i n k ) 等技术束使该算法时间复杂度减 少到线性，其最大特点是它是一种在线( o n 1 i n e ) 算法，也就是说算法的 任何阶段都生成当前读取的部分字符串的后缀树。m c c r e i g h t 算法也是使 用了后缀链接技术来降低算法的时间复杂度，本文主要介绍u k k o n e n 算 法1 8 ，19 1 和m c c r e j i g h t 算法。 2 2 1u k k o n e n 算法 在介绍u k k o n e n 算法前需要先介绍一些必要的定义开始。 定义2 2 ( s u f f i x t r e e ) ：字符串s ( n = i sj ) 的后缀树t 的每条边都标记 为一个非空字符串，且此字符串为s 的子串，t 具有下面的性质： 1 除了根结点和叶结点，其它结点至少有两个子结点。 2 由同一结点发出的任何两条边，在其上标记的字符串中首字符不 允许相同。 3 ，把根结点开始到叶子结点的路径上所标记的字符串连接起来，构 成的字符串和s 的后缀字符串一一对应。 图2 7 是个序列s = a b a c 的后缀树的构造过程，在讨论构造算法前 还需要定义p o i n t 。 一】6 一 第2 章后缀树索引技术的研究 莹a 八。八 2 )b 、3 图27s = a b a c 后缀树按u k k o n e n 算法的 构造过程 当s 当前最后结尾的字符在之前没有出现过时，此时的后缀树满足 定义2 2 ，每一个叶结点对应一条后缀字符串，如图2 8 的第2 和第4 。 但当s 的当前结尾字符在前面的位置出现过，如图中第3 步，此时后缀 字符串a 没有对应在叶结点上，后缀个数和叶结点的个数不匹配，原因 为a 是后缀字符串a b a 的前缀，我们称此时的树为不完全后缀树( i m p l i c i t s u f f i xt r e e ) 。为了能够表示不和树中叶结点对应的后缀字符串，引入了 p o i n t 的定义。 定义2 3 ( p o i n t ) ：为了每个后缀字符串口和后缀树对应，定义p o i n t ( a ) 是一个三元组( v ，d ，c ) ，v 代表深度最深的，能够表达口的前缀卢的 结点，d = i d 卜i 卢j ，c 是口的第l l + l 位对应的字符。 通过在字符串s 的末尾增加一个特殊的字符$ ，可以确保每个叶结点 都对应一个唯一的后缀字符串。总之，对于字符串s $ 的后缀树有n 个叶 子结点，每个都对应一个非空后缀字符串。又由于在非叶结点垒少又2 个子结点，结点总数最多不会超过2 n 。 u k k o n e n 算法是一种o n 1 i n e 算法，按字符串从第一位到最后一位构 建后缀树。使得更容易实现数据的压缩，在这点上优于m c c r e i g h t 算法。 黑龙江大学硕士学位论文 这里从最简单的算法开始介绍，到最后如何通过降低主要过程的时问和 空间复杂度，使得都达到o ( n 1 。 u k k o n e n 算法构造后缀树的思想是从左到右读入字符串，每增加 个新字符串，在树中把所有可能的后缀都表示出来。也就是字符串 s = a a 。m = s f ，顺序读取字符串可以得到s 的前缀，前缀结尾在 s 吣f 从1 到m 。对每个前缀s 1 一i ，希望在树中找到后缀字符串 s j 卅，其中( 1 茎j s i ) 。最终可以在后缀树中得到s 的所有后缀字符串， 完成后缀树的建立。 算法：后缀树的简单算法： 输入：字符串： 功能：构造后缀树； 输出：后缀树； 算法描述： 1 ：f o r if r o mlt o m d o p r e f i x p h a s e 2 ： f o r jf r o m1t oid o s u f f i xp h a s e l 3 ： a = s u i 4 ：p = f i n d e n d o f p a t h p o r e r o o t ( a ) 5 ： a p p l y s a f f i x e x t e n s i o n r u l e s ( p ，s f 】) 6 ：e n d f o r 7 ：e n d f o r 后缀树的简单算法中的第4 和第5 步最坏的情况下其时间复杂度为 d 0 ) ，整个算法的时间复杂度为o ( n3 ) 。u k k o n e f l 算法从三方面对简单 算法做了改进，把算法的时间复杂度降为p ( n ) 。 第方面：对于第5 a p p l y s u f f i x e x t e n s i o n 一阳胁( ) 算法通过以 第2 章后缀树索引技术的 卅冗 下三条规则把时间复杂度降为常数。 1 如果在树中a 结束在叶结点上，那么s 【f 直接加在叶结点上。 2 如果在树中a 的后面不存在s 的路径，也就是a 后的字符没有 等于研i 的。 a 如果a 结束在一条边中，那么创建一个新的结点，把边分割 为两段。 b 否则，从a 结束处新建一个叶结点，叶结点边标记为研f 】。 3 如果在树中a 后存在和研f 】相同的字符，那么什么也不做。 第二方面：对于第4 步p = f i n d e n d o f p a t h f r o m r o o t ( a ) ， 对于每个a 需要从树的根开始搜索路径，增加了时间复杂度，算法通过 引入s u f f i xl i n k 避免每次从根结点开始搜索树来降低时间的复杂度。 定义2 4 ( s u f f i x l i n k ) ：设s 是一个字符串，后缀树s t r e e ( s ) = ( v ，e ) ， 其中v 是所有结点的有限集，v = v ，v ：v 。) ，e 是树中边的有限集。 设x 口为一个字符串，其中xe + ，a 是s 的子序列。设在树中的非叶子 结点v ( v 矿) 在树中边的路径对应为x g l ，如果有另一个结点s ( v ) v ， 且在树中边的路径对应为o t ，那么建立从结点v n s ( v ) 的指针就是s u f f i x l i n k ，记为( v ，5 ( v ) ) 。当x = s 时x 口的s u f f i x l i n k 指向根结点。 图2 8 是s u f f i x l i n k 的例子，其中s = b a b a c ，s u f f i x l i n k 有( 1 ，5 ) 和( 5 ，r o o t ) 。 1 9 黑龙江大学硕士学位论文 图2 8s = b 曲a c 后缀树中s u 用xl i n k 第三方面：对于第2 步s u f f i xp h a s e 阶段可以通过两方面来降低时间 的复杂度，使算法复杂度为常数时f h ，从而整个算法的时间复杂度降为 d ( 门) 1 树中叶结点始终是叶结点，叶结点不影响树的拓扑结构。在树的 创建过程中，不会从叶结点上创建子结点所有叶结点只需要修改对应 结束字符的位置，从而所有叶结点在这一过程只需要一个操作就可以修 改全部的叶结点。 2 控制树的修改范围。在树的创建过程中的每一阶段从最长子串对 应的不是叶结点的结点开始，下一步就可以按s u f f i xl i n k 进行下去，而 不需要整个树的搜索。同时如果满足扩充规则的第3 个条件，则可以跳 过s u f f i xp h a s e ，进入下一步的p r e f i xp h a s e 。 2 2 2m e t r e i g h t 算法 m c c r e i g h t 算法不是o n l i n e 算法，算法从字符串的第一位丌始，每 次把当前最长的后缀字符串放入后缀树中，然后移动到后一位，继续把 剩余序列中最大的后缀字符串放入后缀树中，直到到达字符串的术尾位 置结束。 算法：m c c r e i g h t 算法 2 0 第2 苹后缀耐粟引技术的研究 输入：字符串； 功能：构造后缀树； 输出：后缀树； 算法描述： l ：f o r ( i = 1 ；i i s l ；i _ r + ) 2 ： 取从i 开始的后缀字符串； 3 ： 查找在后缀树树中扩充的位置； 4 ：扩充后缀树； 5 ：e n d f o r 算法的第3 步也用到了s u f f i xl i n k ，使创建后缀树算法的时间复杂 度降为o ( n ) ，对后缀树的扩充部分和l l k k o n e l l 算法的处理过程基本相同。 2 3 部分后缀树算法 本文在分析了后缀树算法和在应用上的主要问题后，提出了部分后 缀树算法的思想，下面是对部分后缀树算法的介绍。 2 3 1 算法思想 后缀树在应用中遇到的最大问题是它所需要的存储空间问题，构造 一颗后缀树往往需要十几倍原序列大小的存储空间，而且d n a 序列数据 往往又很长，例如人类的基因组长度达到3 g b p ( b a s ep a i r s ，碱基对) ， 目前最长的达到1 5 g b p 。对于这样的大规模数据完全放入内存中是不可 能的。但如果把后缀树放入磁盘中又会消耗大量的时间，同时在其上的 查询也会因为频繁的读取磁盘数据而降低效率。针对这些后缀树算法的 问题，从减少后缀树的创建时间，尽量避免主存的限制，并且保持查询 黑龙江大学硕士学位论文 效率入手，本文提出了部分构造后缀树的算法。 从后缀树的查询特点可以发现，在后缀树上做准确查询只是查询后 缀树中的一部分，而且这部分可以从查询内容开始的前几个字符就可以 确定下来。图2 9 为一个在后缀树上查询的例子，在序列a g a g a c r $ 的后 缀树上查询a g a c ，箭头表示了在后缀树所走的路径。从图中可以看到查 询只用到部分后缀树，并且在这个例子中，查询需要的部分后缀树从查询 的字符串a g a c 的第一个字符a 就可以确定，通过查询字符串的前缀确定 了查询的范围。 图2 9 后缀树上的查询 根据查询字符串的前缀字符串，我们可以确定后缀树的查询范围。 那么，我们可以根据查询字符串的前缀字符串，构造出我们查询需要的 部分后缀树，其它查询不需遍历的子树就不考虑创建了。这样由于只是 创建部分的后缀树，在空间上可以节省大量的存储空间，在时间上i 可以 提高效率，同时也不影响精确查询的准确性。这就是本算法关键的思想。 图2 1 0 部分创建后缀树 图2 1 0 是在序列a g a g a c t $ 上查询a g a c ，如果前缀码取a 、c 、t 、g 划分后缀树，按查询序列的内容创建部分后缀树时，我们只需要构造所 有以a 开始的后缀字符串对应的后缀树，也就是树根下沿a 走的路径下 面的子树是需要建立的部分后缀树。下图是查询g a c t 需构造的部分后缀 树。可以看出，根据查询内容的不同，查询需要建立的部分后缀树也不 同，但在规模上都得到了减少。 2 3 2 部分后缀树的划分 本算法的关键思想是把整个后缀树划分为更小的部分后缀树，这样 就可以对规模更大的序列在内存中应用后缀树的索引技术。其中划分的 羹 黑龙江大学硕士学位论文 思想源于论文 2 0 ，2 1 ，2 2 中在创建硬盘索引时的分块思想，在此把它用 在了子树的划分上。 划分后的部分后缀树树在树中表现的特性是从树根结点开始在开始 阶段所经过的路径是相同的。对于序列本身就表现为具有相同前缀的后 缀字符串的集合，记为c ，在这个集合中的每一个字符串元素，可以找 到在树中对应的叶予结点。部分后缀树t 具有如下性质： 1 叶结点的个数为集合c 包含字符串元素的个数。 2 每个叶结点对应一个集合c 中的字符串元素。 从上面的分析我们可以得到我们所建立的部分后缀树，对应的是具 有相同前缀的所以后缀字符串的集合。原字符串的后缀字符串按前缀可 以划分在不同的集合中，通过控制前缀的长度可以控制集合个数的多少 和每个集合中元素的数量，从而划分合适大小的集合，能在内存中建立 对应集合的后缀树是我们的目标。 设字符序列s ，is i 表示字符串的长度，字符集合记为，p r e s t rj n g 定义为前缀字符串，那么按不同的前缀划分的集合个数满足公式： i l l = 刚9 一， 每个集合包含的后缀字符串的个数满足公式： n z 粤= 始 mi w ”+ 由于后缀树的大小可以从树的叶结点来估算，而后缀字符串的个数 和叶子结点是一样的，由后缀字符串的个数也就可以估算出后缀树的大 小，创建部分后缀树所需要的内存空间的估算公式为： a m a n 2 鹞 其中a 为一个系数，与不同算法采用的内部数据结构有关，可以通 过试验统计得到，如序列s 采用某种算法在内存创建后缀树需要1 8 is 1 的内存空间，可以令a 为1 8 。 在实际应用中，我们可以估算可用的内存空间大小a 。，从而可以确 定前缀的长度，确定不同的前缀，再去创建对应的可以在内存创建的部 分后缀树。 | p r 。s 噼忙i ：i 期叫咖爿。 1 0 ，n - l s l 爿。 如d n a 序列s ，字符符号集合= 一，c ，r ，g ，吲= 4 ，当is i 的大小为 2 0l ，机器可用内存为1 0 0j ，系数a 为1 8 ，此时由前面公式