基于压缩后缀数组的空间高效短读比对算法

《基于压缩后缀数组的空间高效短读比对算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于压缩后缀数组的空间高效短读比对算法作者姓名李双江导师姓名、职务霍红卫教授一级学科计算机科学与技术二级学科计算机软件与理论申请学位类别工学硕士提交学位论文日期2014年11月学校代码10701学号1203121619分类号TP30密级公开西安电子科技大学硕士学位论文基于压缩后缀数组的空间高效短读比对算法作者姓名:李双江一级学科:计算机科学与技术二级学科:计算机软件与理论学位类别:工学硕士导师姓名、职务:霍红卫教授提交学位论文日期:2014年11月Space-efficientShortReadAlignmentwithCompressedSuffixArrayAthesissubmitte

2、dtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinComputerScienceandTechnologyByShuangjiangLiSupervisor:Prof.HongweiHuoNovember2014西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子

3、科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规

4、定）本学位论文属于保密，在年解密后适用本授权书。本人签名：日期导师签名：日期摘要摘要新一代基因测序技术(NGS)的出现使得测序成本飞速下降，随之而来的是大量的短读序列需要更快速准确的比对程序来处理。第一代基于散列表技术的序列比对算法如Bowtie等能够快速准确的完成比对工作，但其不支持gap比对的特性使得在短读序列(shortreads)过长导致indel出现频繁时，比对的精度也随之下降。另一方面，近年来压缩索引(BWT,CSA,FM-index)领域的相关研究使得在较小内存中索引人类基因组这样的大规模序列成为可能。这导致近年来出现了很多基于压缩索引的短读比对算法，如BWA,Bowtie

5、等。本文提出了一种基于压缩后缀数组和后向搜索实现近似匹配的算法来实现短读比对，在比对时间和空间以及比对精度上都取得了很好的效果。基于压缩后缀数组的短读比对算法(CSAA)，采用了压缩后缀数组来构建参考序列的索引，并使用后向搜索来做匹配。通过引入搜索树，CSAA实现了近似匹配算法，从而支持完全的gap比对。此外CSAA在搜索树上使用了一种类似堆的优先堆数据结构，大大减小了搜索空间。而且每一次的搜索方向都能保证是最优的。最后结合罚分机制以及difference距离，定义seed等方法，进一步降低搜索空间，提高了CSAA的比对速度和精度。CSAA的高效体现在三个方面。一是空间高效的索引方法；二

6、是基于后向搜索的高效的近似匹配方法；三是seed策略和多线程比对技术的利用。本文采用了增量法进行压缩后缀数组索引的构建，从而跳过后缀数组的构建，降低了对内存的需求。而在比对时，seed的引入使得在比对短读的前几十个核苷酸就可以放弃大部分无效的搜索方向。多个短读比对的相互独立使得并行化成为可能，使得CSAA使用多线程时可以获得数倍的加速优势，从而可以根据计算机的cpu核数指定多个线程，以取得最优的比对速度。CSAA支持单端和双端序列比对，以Fastq格式输入，输出为标准的SAM(Seq-uenceAlignmentMap)格式。关键词：短读比对，序列比对，压缩索引，压缩后缀数组论文类型:应

7、用基础研究i西安电子科技大学硕士研究生毕业论文iiABSTRACTABSTRACTNowadays,decreasingcostandbetteraccessibilityofnextgenerationsequencingmeth-odshaveproducedalargeamountofshortreadswhicarecallingforthedevelopmentoffastandaccuratereadalignmentp