SUFFIX TREE 文件生成器.docVIP

SUFFIX TREE 文件生成器 　　摘要：后缀树是一个功能强大的数据结构，可以用于计算机科学执行字符串后处理操作。使用树结构的一个挑战是，随着树的生长、树的结构变得难以想象。该文的项目就是针对后缀树的这一问题，通过使用三维空间来改善树的呈现效果。项目的目的将允许用户在没有重叠显示的情况下，大幅增加从屏幕上获得的数据量。这个项目将着眼于渲染定向图，如在双曲空间的后缀树。 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）13-0077-03 　　1目标 　　这个项目是为了在屏幕上通过提供一个有效的数据管理方法，从而改善当前DNA字符串后缀树结构的可视化水平。为了实现这个项目，从输入DNA字符串样本和翻译获得结构到LibSea图格式都使用BioJava生物信息学库来构造后缀树结构。这种格式是为了使处理资源消耗最小化，并且可以在双曲空间里用作海象源工具来显示和导航指示图。 　　2 介绍 　　在过去的几年中，可用的生物数据结构体积，如DNA和蛋白质序列大大增加。计算机硬件的不断发展使得它可以处理和分析越来越多从生物中检索到的数据信息。这种增长使生物信息学领域得到提升和发展。随着领域的发展，要求新数据结构能有效的存储和分析，从而获得所需信息。 　　后缀树是一个有向图的数据结构，在生物信息学领域被用于支持高效和强大的运作。[1] 例如，模式匹配， 近似模式匹配， 寻找共同的子字符串， 文本压缩等。所有这些都可以应用于研究和分析显示为字符串的DNA序列。[2-3]然而，当后缀树被用于构造信息结构图的时候，是非常大的，例如DNA序列，加工信息的大小为显示结果创造了一个重大的困难。就是数据显示可能因过大而不可读。 　　3 后缀树 　　字符串S的符号m的后缀树T是一个带根节点的有向树。这样一个后缀树具有精确的m叶子被标记为从1到m的值（图1）。后缀树的每一个内部节点都至少有两个子节点，每一个树的边缘都包含了一个非空的S子串。同一个节点不同边缘的符号不能拥有相同的标签。一个后缀树结构的关键特性是每一个叶节点i， 根点到i的标签串联通常会返回从节点i位置开始的S的准确后缀。这意味着，这个路径写为S[i...m]。[2，10] 　　通常终止符号$被加到S的末尾，并被用于防止S最后一个后缀与另外一个给定的字符串的后缀的前缀相配。在这类事例当中，树可能无法满足上述结构的定义。为了防止S最后一个后缀与终止符的给定输入串的前缀匹配。终止符$被添加到了开始符列。 　　3.1 Ukkonen后缀树算法 　　Ukkonen算法构建了一个后缀树的简化版本，之后转变成了S字串的真实后缀树。一串字符简化的后缀树，是一种从没有树边缘终止符存在，并消除了无标签边缘，以及没有满足关键特性，且子节点2个以下的节点的S$中得到的后缀树[10]。Ukkonen的算法是构成了每个S[1…i]前缀的Ti的简化后缀树，以T1开始，增加值到i，直到树Tm完整。完整的后缀树S是根据O（m）时间内的Tm而构造的[10]（图2）。 　　3.2 BioJava 　　BioJava平台下的一个开源工程项目，旨在为处理和分析生物学数据提供程序库。BioJava项目的目的是推进生物信息学应用程序的发展[11]。这个项目使用了BioJavaAPI版本1.7.1。尽管从来没有BioJava库的版本，必威体育精装版版本的数据库中没有本项目所必须的类别。Ukkonen后缀树和前缀树不属于BioJava更新的管理类别当中。 　　3.3 LibSea 　　概述：LibSea是由CAIDA团队开发的图表文件格式，从而以一种有弹性，可扩展并可以储存的方式去呈现大量的数据结构。通过这种格式，用户可以使用节点，边缘和路径链环元素等对需要的定向图的拓扑结构进行定义。在图表所有元素当中会有额外的数据，作为其属性特征。图表格式在可提供的属性数量上没有限制，且可以为这些属性接收不同的数据类型[17]。LibSea以图表扩展名形式储存为文本文件。图表文件的结构由5部分组成：元数据，结构数据，属性数据，可视化提示和界面提示[17]。 　　3.3.1 LibSea元数据 　　这个部分包含了关于图表的信息，比如图表名字，提供的描述，节点数量，边缘数量，路径数量，和路径链环数量等。每个节点，每个边缘和路径都含有指定的指标，这些指标可用于连接文件中的字符实体。编号以0开始，所以整个字符实体给定的下标也是从0到特定实体-1。 　　[Graph 　　{### metadata ### 　　@name = “OurSuffixTree”； 　　@description=”Description of the suffix tree”； 　　@numNodes=6；