基于外存后缀树的top-k局部比对算法

发布时间：2017-09-28 15:23

  本文关键词：基于外存后缀树的top-k局部比对算法

  更多相关文章： 局部比对 top-k 外存后缀树 叉子区域

【摘要】：局部比对是一种衡量字符串间相似程度的技术,它在生物信息学领域具有十分重要的作用.介于此,许多学者已对其进行了深入的研究.然而,随着数据规模的扩大,常规的内存算法已不适用于支持大规模文本数据的局部比对.为解决上述问题,该文研究了基于外存后缀树的top-k局部比对算法.它从根本上消除了内存空间对算法的束缚.为了提高算法的性能,该文首先将经典内存算法中的过滤策略引入该文.通过适当的修改,这些策略可以基于外存后缀树有效地降低计算开销.其次,该文提出一种巧妙的算法支持top-k局部比对查询.该算法通过引入启发式策略有效规避了TA算法的固有问题.具体地,它一方面可以提高算法的过滤能力,另一方面可以降低候选对象的维护代价.再次,该文对外存后缀树和磁盘的工作原理进行了研究.基于此,该文提出一种槽的结构支持查询.该结构既可以实现磁盘的顺序访问,又可以降低磁盘的访问次数.因此,它可以有效提高算法的查询效率.最后,大量的实验验证了该文所提出算法的有效性.
【作者单位】： 东北大学信息科学与工程学院;
【关键词】： 局部比对 top-k 外存后缀树 叉子区域
【基金】：国家“九七三”重点基础研究发展规划项目基金(2012CB316201) 国家自然科学基金(61572122,61173031,61129002,61532021,U1401256) 国家优秀青年科学基金(61322208)资助~~
【分类号】：TP391.1
【正文快照】： 1引言 局部比对是在两条文本串之间寻找近似子串的过程.它在生物信息学领域具有重要应用[1-2].具体来说,它有助于研究人员分析不同基因片段的功能,确定它们在遗传学上的意义[3-4].和常规文本数据相比,基因数据的规模较大.常规PC机的内存往往无法容纳这些数据[5-8],更无法容纳

【相似文献】

中国期刊全文数据库 前10条

1 黄影;;一种有效的后缀树建立方法[J];电子科技;2013年10期

2 赵杰文;原娇杰;;数据挖掘中后缀树算法的应用研究[J];焦作大学学报;2007年03期

3 黄影;;一种有效的后缀树建立方法[J];中国电子教育;2013年03期

4 乔百友,葛健,王国仁,韩东红;并行后缀树的构造及查询算法[J];东北大学学报;2004年03期

5 彭静;翟英;冯爽;;后缀树算法在舆情聚类中的应用[J];河北科技大学学报;2012年01期

6 葛健;王国仁;于戈;;后缀树的并行构造算法[J];计算机科学;2004年05期

7 曲文龙;杨炳儒;张克君;;基于广义后缀树的事件序列频繁情节挖掘算法[J];北京科技大学学报;2006年05期

8 王秉政;苏晓珂;张素智;;一种基于后缀树的简洁关联规则挖掘有效剪枝方法[J];郑州轻工业学院学报(自然科学版);2011年03期

9 董云耀;李笑;;基于后缀树的知识点间关联规则挖掘算法[J];杭州电子科技大学学报;2006年01期

10 师鸣若;姜中华;赵明茹;;基于概率后缀树的宏观网络报警事件序列分析[J];电脑开发与应用;2009年01期

中国重要会议论文全文数据库 前1条

1 务孟庆;高军;王腾蛟;杨冬青;;WD-STC：一种基于网络词典的WEB新闻文档后缀树聚类算法[A];全国网络与信息安全技术研讨会论文集（上册）[C];2007年

中国硕士学位论文全文数据库 前10条

1 李双江;基于压缩后缀数组的空间高效短读比对算法[D];西安电子科技大学;2014年

2 郭海涛;用加强的后缀数组查找MUM[D];西安电子科技大学;2007年

3 王学;基因组中最大唯一匹配的查找算法研究[D];西安电子科技大学;2009年

4 王坚;基于后缀数组的滑动窗口匹配压缩改进算法研究[D];华中科技大学;2012年

5 陈月妥;一种新型后缀数组构造外存算法的性能优化技术[D];中山大学;2014年

6 荣元媛;改进后缀树的中文检索结果聚类系统[D];北京林业大学;2013年

7 董丽霞;基因组比对中若干改进算法研究[D];西安电子科技大学;2009年

8 唐德昌;基于串核的蛋白质分类算法的研究与实现[D];哈尔滨工业大学;2008年

9 张任文;生物序列索引结构的研究与实现[D];哈尔滨工业大学;2006年

10 张吉;基于后缀树模型的流文本表示研究及其应用[D];中国科学院研究生院（计算技术研究所）;2005年

，

本文编号：936596