【作者】 张勇；

【导师】 徐云；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2016， 硕士

【摘要】 近些年,下一代测序技术获得了突飞猛进的发展,由此产生了越来越多的测序数据。如何处理这些测试数据一直以来都是生物信息学领域的一项重要研究内容,下一代测序技术应用到转录组研究领域产生了高通量转录组测序技术,简称为RNA-seq技术。RNA-seq数据分析软件的一项重要功能便是重构剪接之前的mRNA在细胞中的形态,此外,还应该能够评估每种剪接异构体的表达水平。但是,所有分析过程的第一步都是要把从RNA-seq中得到的测序片段比对到相应的参考序列上。因为内含子序列在DNA转录为成熟mRNA时会被剪切除去,所以与传统的序列比对问题相比,转录组序列比对有其固有的特殊之处,即需要将测序得到的序列分段比对到不同的外显子序列上,因此需要设计专门针对RNA-seq的序列比对算法。现有的RNA-seq序列比对算法基本上都是依赖于经典的剪接位点信号,而许多非经典的剪接信号位点具有重要的生物学功能,如GT-TG与人类腺苷酸环化酶刺激蛋白Gαs的形成有关。为此,我们设计了两个新的RNA-seq序列比对算法,用来发现多种类型的剪接位点。(])独立于剪接位点信号的转录组序列比对算法首先我们设计了一种采用重叠种子内部扩展策略的RNA-seq序列比对算法,命名为RNAMap o种子序列的重叠性能够保证由种子的比对信息能够组合出完整测序序列的定位信息。在扫描基因组时,RNAMap建立一个静态表和一个动态表来索引种子序列及其比对信息,寻找左右锚点序列之间的剪接位点,此时并不受经典剪接位点信号的限制。实验结果表明,对于含有多种类型的剪接位点的数据集,RNAMap的召回率和精确度分别达到了92.53%和97.01%,优于其它的转录组序列比对工具。(2)转录组序列比对算法改进之后我们又设计了一种采用非重叠种子之间扩展策略的RNA-seq序列比对算法,命名为RNAMap 2。该算法通过减少种子的数量来降低计算量,然后利用测序深度,即测序序列的重复性来进行比对。这在一定程度上弥补了RNAMap在运行速度方面的不足。实验结果表明,在测序序列的长度为300bp时,RNAMap2比RNAMap快将近40%。此外,RNAMap 2采用Needleman-Wunsch全局动态规划算法,能够处理编辑距离的误配情况,克服了RNAMap仅支持海明距离误配的缺点。实验结果表明,RNAMap 2的召回率比RNAMap高大约2%。更多还原

【Abstract】 Recently, next-generation sequencing (NGS) technologies have rapidly developed, which are producing increasingly many sequencing data. How to deal with such sequencing data is always a significant topic in bioinformatics. Next-generation sequencing technologies can be applied into related research of transcriptome, which is named high-throughput transcriptome sequencing (RNA-seq). One of the important functions of the software analyzing RNA-seq data is to reconstitute the pattern of RNA before splicing in cells. Moreover, it should be able to assess the expression level of every isoform. However, the first step of all analytical procedures is to align the sequences from RNA-seq onto the corresponding reference. Introns will be eliminated during transcription from DNA to mature mRNA. Therefore, compared with traditional sequence alignment, alignment of sequences from RNA-seq is very inherently special-that is to say, two parts of the sequence are expected to be aligned onto different exons. Consequently, there is need to design particular algorithms for RNA-seq alignment. Nearly all existing algorithms for RNA-seq alignment are dependent on the canonical signals of splice sites, but many splice sites with non-canonical signals have important biological functions. For example, the GT-TG splice site is related to the human adenylyl cyclase stimulatory G-protein Gαs. Therefore, we introduce two new algorithms designed for RNA-seq alignment in order to identify various splice sites.(1) the Algorithm Independent from Canonical Signals of Splice SitesThe algorithm designed for RNA-seq alignment adopts the extension strategy within overlapping seeds, and is named RNAMap. The overlapping property of seeds can guarantee that alignment information of seeds is able to result in alignment of reads. When scanning the genome, RNAMap builts a static table and a dynamic table in order to index seeds and their alignment information. It tries to identify splice sites between left anchors and right anchors without the limitation of canonical signals. The computational experiment of reads with a variety of splice sites indicates that the call rate and the precision of RNAMap reached 92.53% and 97.01%, respectively. RNAMap performed better than other tools for RNA-seq alignment.(2) the Improvement of the Algorithm for RNA-seq AlignmentBased on the extension strategy between non-overlapping seeds, the other algorithm is designed for RNA-seq alignment, named RNAMap 2. It reduces the amount of calculation through the decrease of the number of seeds. To some extent, RNAMap 2 makes up the disadvantage of RNAMap in speed. The computational experiment of reads of 300bp indicates that RNAMap 2 is faster than RNAMap by almost 40%. What’s more, RNAMap 2 adopts Needleman-Wunsch global dynamic programming to deal with mismatches of edit distance, which overcomes the shortcoming of RNAMap that only supports mismatches of hamming distance. Another computational experiment indicates that the call rate of RNAMap 2 is higher than that of RNAMap by nearly 2%.更多还原