面向高通量测序序列的比对算法研究

发布时间：2023-02-16 08:28

　　在过去的数年中,高通量测序在极大的拓展了测序技术应用领域的同时也产生了海量的测序数据集。如何将这些海量的测序序列数据快速的比对到基因组上,准确的找出它们的原始位置是许多生物医学领域研究的前提和至关重要的一步,因此已有许多序列比对工具被开发出来专门用于短序列比对。然而随着高通量测序技术的不断发展,生成的序列长度已由最初的36bp增加到100¹50bp,一些针对短序列开发出的基于BWT索引结构的比对工具在使用回溯算法实现模糊比对时会带来候选解占用空间过大,搜索替换占用时间过长的问题。因此,一些后期开发的高通量测序比对软件普遍开始通过从序列中选取种子优先进行比对的策略来寻找整个序列在基因组上的比对位置。然而由于一般情况下种子的长度较短,在参考基因组上拥有大量的候选位置,因此或是需要耗费数倍于参考基因组大小的空间来存储这些数据或是需要相当的时间进行反复查找。为了更好的满足高通量测序序列比对的新要求,我们在BWT索引结构的基础上结合了哈希索引的策略,提出了一种基于改进索引结构的比对算法,能够很好的达到时间与空间的平衡。具体工作如下:(1)本文首先对近几年发布的,面向100<...

【文章页数】：64 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景
    1.2 研究的目的及意义
    1.3 国内外研究现状
        1.3.1 基于哈希索引的比对算法
        1.3.2 基于前缀/后缀索引的比对算法
    1.4 本文主要研究内容
        1.4.1 面向中长序列比对算法索引结构的研究及改进
        1.4.2 找最佳模式下种子选取及候选位置过滤的研究
        1.4.3 比对系统的实现
    1.5 论文组织结构
第二章 高通量测序序列比对相关介绍
    2.1 引言
    2.2 高通量测序平台
        2.2.1Roche454
        2.2.2 Illumina
        2.2.3 SOLiD
        2.2.4 PacBioRSII第三代测序
    2.3 序列比对中使用和生成的数据格式
        2.3.1 FASTA/FASTQ格式
        2.3.2 SAM格式
    2.4 序列比对的定义与基本方法
        2.4.1 精确匹配
        2.4.2 近似匹配
    2.5 序列比对算法的评价标准
    2.6 本章小结
第三章 面向中长序列比对算法的索引结构研究及改进
    3.1 引言
    3.2 基于Burrows-WheelerTransform(BWT)索引结构的搜索算法
        3.2.1 BWT的基本原理
        3.2.2 基于BWT的FM-Index搜索算法
    3.3 改进的索引结构设计与算法
        3.3.1 改进的索引结构总体设计
        3.3.2 改进的索引结构定位算法
        3.3.3 改进的索引结构算法性能分析
    3.4 实验结果与讨论
    3.5 本章小结
第四章 找最佳模式下种子选取及候选位置过滤的研究
    4.1 引言
    4.2 种子选取及候选位置过滤的研究
        4.2.1 固定长度种子的选取及过滤
        4.2.2 可变长度种子的选取及过滤
    4.3 找最佳模式下种子选取及候选位置过滤算法
        4.3.1 种子的选取
        4.3.2 最优覆盖链接算法
    4.4 比对系统的整体流程与实现
    4.5 系统测试
    4.6 本章小结
第五章 总结与展望
    5.1 本文工作总结
    5.2 后续工作展望
附录一 基于改进索引结构的分块定位算法伪代码
附录二 软件参数设置
附录三 部分核心代码
参考文献
致谢
在学期间的研究成果及学术论文情况



本文编号：3743884