高通量转录组测序片段快速比对算法研究

发布时间：2017-11-23 12:17

  本文关键词：高通量转录组测序片段快速比对算法研究

  更多相关文章： De Bruijn图 二维线段树 序列比对 动态规划

【摘要】：基因序列比对技术是基因序列数据分析的重要组成部分,也是人们深入了解生物的遗传特性,分析各种疾病,预防和抵御各种传染疾病的基础。新一代测序技术产生序列数据的速度更快,通量更高。因此出现了很多新型的RNA序列比对工具。然而,高速,精确地比对高通量RNA序列数据是一项非常具有挑战性的任务,当前新型的RNA序列比对工具在速度和准确率方面仍然有一定的不足。因此,开发一款速度快,准确率高的RNA序列比对工具是一项非常有意义的工作。本文提出了一个高通量转录组测序片段快速比对工具RNA-fat。RNA-fat利用种子在read和参考基因组上位置的关系识别种子间的剪切点和结构性变异,并且通过对种子构图,高效地寻找种子覆盖read的最优路径。由于选择出的最优路径对read具有很高的覆盖度,算法在序列比对阶段的计算量大幅降低。RNA-fat对参考基因组构建De Bruijn图,提取De Bruijn图中所有的单一路径并进行排序,最终生成RNA-fat的索引。该索引由三个相互关联的子索引构成,且具有非常高的查询效率。在剪切和结构性变异的影响下,read未覆盖区域的比对边界在read上会出现交叉,在参考基因组上会出现长空位。为了保证序列比对的准确性,RNA-fat对每一种情况进行判断,精确计算出read未覆盖区域在read和参考基因组上的比对边界,并采用不同的比对策略进行序列比对。通过实验数据,我们首先验证了最优覆盖路径的准确性,这就为未覆盖区域比对边界搜索的准确性打下了基础。通过对寻找最优路径的动态规划算法优化前后的效率对比,我们验证了二维线段树对RNA-fat性能优化的显著作用。最后,我们将RNA-fat和现有的RNA序列比对工具在相同的实验环境和实验数据下进行性能对比,我们发现RNA-fat具有高通量,速度快的优势,且在read比对的正确率和碱基比对的正确率方面与现有RNA序列比对工具相当。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4

【相似文献】

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

1 杨烨;刘娟;;第二代测序序列比对方法综述[J];武汉大学学报(理学版);2012年05期

2 涂俐兰;;两两序列比对的一种新方法[J];数学杂志;2006年01期

3 张涛涛;郭茂祖;邹权;;参数序列比对算法研究(英文)[J];生物信息学;2008年02期

4 李方洁;刘希玉;陈洁;;基于改进蚁群算法的DNA双序列比对[J];南京师大学报(自然科学版);2010年04期

5 杨洁;刘海;;生物序列比对算法的研究现状[J];中国科技信息;2011年09期

6 唐玉荣;生物信息学中的序列比对算法[J];计算机工程与应用;2003年29期

7 李小妹,王能超;生物序列比对算法的简述[J];云南民族大学学报(自然科学版);2004年01期

8 刘阳;王小磊;李江域;毛逸清;赵东升;;局部序列比对算法及其并行加速研究进展[J];军事医学;2012年07期

9 王非;杨欣;June Y.Liberamy;;生物序列比对算法的实现与集成[J];计算机与应用化学;2004年04期

10 李大卫;;基于动态规划的序列比对的并行算法研究[J];井冈山大学学报(自然科学版);2011年03期

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

1 王盛;吴长刚;孙慰迟;;带约束星形序列比对复杂性的研究[A];2006年全国理论计算机科学学术年会论文集[C];2006年

2 许龙飞;段敏;陈孝卫;冉丽;朱婵;;生物DNA序列比对算法研究[A];第二十一届中国数据库学术会议论文集（技术报告篇）[C];2004年

3 方慧生;陈凯先;;一个有效解决远距离同源蛋白质结构预测及序列比对的有效方法[A];中国化学会第26届学术年会化学信息学与化学计量学分会场论文集[C];2008年

4 陈婷婷;郭婷婷;李林;安冬;;基于生物信息学的功能蛋白基因序列分类研究[A];2011年全国通信安全学术会议论文集[C];2011年

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

1 陈科;最优化方法在生物序列比对中的应用与研究[D];电子科技大学;2010年

2 唐玉荣;生物信息学中的序列比对算法研究[D];中国农业大学;2004年

3 李玉岗;生物大分子序列比对和蛋白质结构分类算法[D];中国科学院研究生院（计算技术研究所）;2004年

4 康晓军;基因序列比对算法在SNP中的研究及应用[D];华中农业大学;2011年

5 夏飞;生物序列分析算法硬件加速器关键技术研究[D];国防科学技术大学;2011年

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

1 汪浩;基因序列比对算法的优化研究[D];中国农业科学院;2015年

2 卢山;高通量转录组测序片段快速比对算法研究[D];哈尔滨工业大学;2015年

3 李研;生物序列比对算法的并行优化设计与实现[D];哈尔滨工业大学;2015年

4 薛倩斐;DNA序列比对并行算法研究及应用[D];上海大学;2015年

5 曹金玲;基于种子的序列比对方法研究[D];吉林大学;2008年

6 黄宁;生物序列比对[D];苏州大学;2009年

7 吕艳萍;生物序列比对问题的研究[D];福州大学;2005年

8 刘淼;基于平衡分割的并行序列比对[D];西安电子科技大学;2007年

9 陈斐;蚁群算法在序列比对中的应用研究[D];湖南大学;2008年

10 尚婧;下一代测序短序列比对软件算法比较及评价[D];苏州大学;2013年

，

本文编号：1218436