基因组中最大唯一匹配的查找算法研究

发布时间：2016-11-24 06:05

  本文关键词：基于Android的手机桌面搜索引擎研究与设计，由笔耕文化传播整理发布。

《西安电子科技大学》 2009年

基因组中最大唯一匹配的查找算法研究

王学  

【摘要】：最大唯一匹配在基因序列比对中有着重要的作用。它可以从相互重叠的序列片断中重构DNA的完整序列,可在各种试验条件下从探测数据中决定物理和基因图存贮,可遍历和比较数据库中的DNA序列来判断两个或多个序列的相似性。 本文首先简单介绍了国内外现有的部分研究成果,并在详细介绍后缀树和后缀数组的基础上,给出了一种基于后缀数组的最大唯一匹配(Maximal Unique Matches简写为MUM)查找及其排序的方法。算法首先构造出两条基因序列的后缀数组,然后通过两两比较后缀数组中相邻的后缀获得相邻后缀的最长公共前缀(Longest Common Prefixes简写为LCP)值,然后通过扫描满足MUM条件的LCP值求出MUM,最后利用最长递增子序列(Longest Increasing Subsequences简写为LIS)算法对获得的MUM进行排序。测试结果表明,在同等规模的数据量下,基于后缀数组的算法相比基于后缀树的算法在空间上具有显著优势,基于后缀数组的MUM查找及其排序方法可以节省28%的空间。

【关键词】：
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：TP301.6
【目录】：

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【共引文献】

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

1 周文鹃;刘自伟;陈昌平;;基于DC3算法的非编码区序列最大串联重复识别[J];兵工自动化;2009年03期

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

3 闫雷鸣;孙志挥;张柏礼;;一种时序数据局部相关对象聚类算法[J];东南大学学报(自然科学版);2007年05期

4 陈昌平;刘自伟;周文鹃;彭春艳;;串联重复序列识别方法研究[J];电脑知识与技术;2008年31期

5 陈虎;陈书明;陈胜刚;谷会涛;陈小文;;GISEES:面向嵌入式系统的扩展指令集自动产生方法[J];电子学报;2011年09期

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

7 柳渤;李建中;;基于广义后缀树的最长重复子模式算法[J];航天控制;2008年02期

8 闫雷鸣;孙志挥;吴英杰;张柏礼;;联合聚类非线性相关的时序基因表达数据[J];计算机研究与发展;2008年11期

9 胡海龙;孙晨;赫枫龄;左万利;;基于改进后缀树算法中英文聚类引擎的实现[J];吉林大学学报(理学版);2009年02期

10 刘燕兵;谭建龙;郭莉;;可动态增删关键词的串匹配算法[J];计算机工程与应用;2005年35期

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

1 ;A Chinese Web Page Clustering Algorithm Based on the Suffix Tree[A];Proceedings of the First Conference on Web Information System and Applications[C];2004年

2 龚才春;贺敏;张华平;许洪波;程学旗;;大规模语料的频繁模式快速发现算法[A];全国网络与信息安全技术研讨会论文集（上册）[C];2007年

3 曾依灵;许洪波;;网络热点信息发现研究[A];全国网络与信息安全技术研讨会论文集（下册）[C];2007年

4 郭莉;刘燕兵;谭建龙;;基于存储压缩的多模式串匹配算法[A];全国第八届计算语言学联合学术会议（JSCL-2005）论文集[C];2005年

5 张龙;周傲英;郑仕辉;梁宇奇;;一种可行的层次型XML仓库索引结构[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

6 包小源;宋再生;唐世渭;杨冬青;王腾蛟;;SuffIndex——一种基于后缀树的XML索引结构[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

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

1 李炳龙;文档碎片取证关键技术研究[D];解放军信息工程大学;2007年

2 陈曦;基于子串的文本分割与主题标注研究[D];武汉大学;2009年

3 刘玉国;基于内容的互联网舆情信息挖掘关键技术研究[D];山东大学;2011年

4 杨瑞龙;基于短语特征的Web文档聚类方法研究[D];重庆大学;2010年

5 陈虎;面向应用的指令集处理器关键技术研究[D];国防科学技术大学;2011年

6 赵基;基于数据挖掘的银行客户分析管理关键技术研究[D];浙江大学;2005年

7 刘洁;对等网络环境下基于语义的异构数据管理模型[D];中国科学院研究生院（计算技术研究所）;2005年

8 梁作鹏;面向Web的XML检索关键技术研究[D];东南大学;2005年

9 何丽;基于Web挖掘的决策支持系统模型研究[D];天津大学;2005年

10 滕伟;面向Web信息集成的Web信息抽取中若干关键问题的研究[D];上海交通大学;2007年

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

1 李英斌;模体发现问题中投影算法的研究[D];西安电子科技大学;2009年

2 王敬艳;DNA序列中串联重复体查找算法研究[D];西安电子科技大学;2009年

3 黄影;生物序列索引结构构造算法研究[D];西安电子科技大学;2009年

4 王洋;高效的motif识别方法研究[D];北京交通大学;2011年

5 赵颖;基于Ontology的Web文本聚类研究[D];西华大学;2011年

6 公衍磊;跨站脚本漏洞与攻击的客户端检测方法研究[D];大连理工大学;2011年

7 陈飞;聚类搜索引擎关键技术的研究[D];北京邮电大学;2011年

8 丁溪源;基于大规模语料的中文新词抽取算法的设计与实现[D];南京理工大学;2011年

9 肖鹏;基于Android的手机桌面搜索引擎研究与设计[D];电子科技大学;2011年

10 张维华;基于聚类的中文元搜索引擎技术研究[D];南京邮电大学;2011年

【相似文献】

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

1 丁四成;;C语言程序—指针算法分析[J];宿州教育学院学报;2011年02期

2 杜素芳;韩利娟;;C#索引器教学法探讨[J];濮阳职业技术学院学报;2011年03期

3 何晓敏;关于C语言教学中指针的探讨[J];长沙大学学报;1999年04期

4 杨风暴,王召巴;在实模式下编程使用扩充内存[J];山西电子技术;1999年01期

5 陈琦;C程序设计中常见问题辨析[J];燕山大学学报;2000年03期

6 荆霜雁,车紫辉;C语言中多维数组指针处理技术及应用[J];保定师专学报;2001年02期

7 李娜;仁庆道尔吉;曹军;;一种求第K个元素新算法的实现[J];阴山学刊(自然科学版);2005年01期

8 冯林;邹继军;;非接触式ID卡浴室收费系统设计[J];微计算机信息;2008年23期

9 陈新一;唐文玲;;二分搜索排序的算法研究[J];科技信息(学术研究);2008年27期

10 沙胜贤,谭振江;Turbo-Prolog程序设计的某些方法[J];吉林师范大学学报(自然科学版);1993年01期

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

1 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会——2004年学术年会论文集[C];2004年

2 郝军军;郝五零;;Levy飞行查找算法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

3 许晓峰;金澈清;高明;周傲英;;面向大型数据集合的关键分类查找算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

4 骆雄武;万小军;杨建武;吴於茜;;基于后缀树的Web检索结果聚类标签生成方法[A];第四届全国信息检索与内容安全学术会议论文集（上）[C];2008年

5 张常有;秦晓静;李文清;曹元大;;一种面向对等网络的Web服务快速查找算法[A];2009年全国开放式分布与并行计算机学术会议论文集(上册)[C];2009年

6 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会2004年学术年会论文集[C];2004年

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

8 涂锟;顾乃杰;董万利;;分布存储环境下的基于后缀数组的串匹配算法[A];2005年“数字安徽”博士科技论坛论文集[C];2005年

9 尚凤军;;一种IP数据包快速分类算法[A];第十七届全国过路控制会议论文集[C];2006年

10 尚凤军;唐红;潘英俊;;一种串行IP分类算法研究[A];第九届全国青年通信学术会议论文集[C];2004年

中国重要报纸全文数据库 前10条

1 高军;[N];中国电脑教育报;2008年

2 曾;[N];计算机世界;2002年

3 魏伟;[N];电脑报;2009年

4 马严;[N];中国电脑教育报;2003年

5 蔡昌;[N];中国会计报;2009年

6 曹悟尔;[N];网络世界;2005年

7 广安职业技术学院 杨志伦;[N];广安日报;2008年

8 山东莱芜钢城双泉路学校 张志国;[N];中国电脑教育报;2008年

9 艾缇;[N];中国电子报;2009年

10 符闻;[N];国防时报;2010年

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

1 梁作鹏;面向Web的XML检索关键技术研究[D];东南大学;2005年

2 龚才春;短文本语言计算的关键技术研究[D];中国科学院研究生院（计算技术研究所）;2008年

3 高茂庭;文本聚类分析若干问题研究[D];天津大学;2007年

4 王振兴;NGI高性能路由器转发处理算法与实现[D];南京理工大学;2004年

5 余小高;电子商务环境中分布式数据挖掘的研究[D];武汉理工大学;2007年

6 杨瑞龙;基于短语特征的Web文档聚类方法研究[D];重庆大学;2010年

7 赵华;多模型下的近似字符串匹配算法研究[D];华中科技大学;2013年

8 何丽;基于Web挖掘的决策支持系统模型研究[D];天津大学;2005年

9 程胜;移动Ad hoc网络中虚拟骨干网技术的研究[D];北京邮电大学;2003年

10 尹传环;结构化数据核函数的研究[D];北京交通大学;2008年

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

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

2 赵丽红;后缀数组在维、哈、柯搜索引擎中的应用[D];新疆大学;2012年

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

4 解洋;ATN中信任证关键技术的研究[D];哈尔滨工程大学;2010年

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

6 王智强;高速路由查找算法研究[D];中国人民解放军信息工程大学;2003年

7 谢可心;P2P网络中分类数据查找算法的研究与实现[D];东北大学;2008年

8 李欢;利用领域特性扩展的kd-tree及其查找算法[D];河北大学;2011年

9 李建祥;智能网页推荐系统的相关技术研究[D];西南交通大学;2004年

10 史庆庆;基于后缀数组的克隆代码检测研究[D];内蒙古师范大学;2013年

  本文关键词：基于Android的手机桌面搜索引擎研究与设计，由笔耕文化传播整理发布。

，

本文编号：189981