面向三代测序的序列比对算法研究与优化

发布时间：2021-07-10 13:47

　　近年来,三代测序技术的发展为基因组学带来了重大变革和影响。但由于三代测序序列具有平均长度长、错误率高的特性,现有的三代测序序列比对算法在数据分析的工作流中占据了大量的时间。因此,如何快速、准确地将大规模的测序序列比对到参考基因组上是三代测序序列比对面临的一大挑战。目前主流算法大多采用种子扩展（seed-and-extend）方法,包括过滤出候选位置和进行比对验证两个阶段。过滤和验证是影响算法性能的关键环节,为了加快序列比对的速度,本文对过滤方法的特征选取和验证阶段的索引技术进行了较为深入的研究,主要工作和贡献如下:（1）过滤方法设计及优化对已有过滤方法进行分析,它们使用全部种子来过滤候选位置,如此要处理的种子数很多且针对性不强,导致过滤时间过长。我们的实验表明过滤时低频率的种子往往具有更高的区分度,同时低频种子也可以有效地减少计算量。基于此,本文提出了一种基于低频种子的过滤方法,根据基因组的规模动态地选取低频率的种子,使用低频种子进行投票定位候选区域。过滤得到的候选区域数目也是过滤方法的重要衡量标准。为了进一步减少候选区域的数目,我们对过滤方法进行了优化,提出了相邻窗口合并、候选窗口验... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：77 页

【学位级别】：硕士

【部分图文】：

图１．１种子扩展方法流程图??为了加速比对过程，大部分的序列比对算法都会采用辅助数据结构［１８］，即??

２．１．３．数据文件格式介绍??测序技术的不断发展，使得测序仪的吞吐量大幅提升，测序数据不断的，大量的数据需要处理和存储。这些数据既有直接通过测序获得的原始数有通过软件分析后得到的结果文件。在测序的研宄领域，有些大家公认的文式，作为序列比对算法输入／输出的标准文件格式。??１．?ＦＡＳＴＡ文件格式??ＦＡＳＴＡ格式是一种用于表示核酸序列或多肽序列的文本格式，又称Ｐｅａｒｓｏ式，主要发明人是威廉？皮尔森（Ｗｉｌｌｉａｍ?Ｒａｙｍｏｎｄ?Ｐｅａｒｓｏｎ）和戴维德．李（Ｄａｖｉｄ?Ｊ．Ｌｉｐｍａｎ）。随着时间的推移，这种格式己经成为生物信息学领域项标准。其中核酸（ＤＮＡ／ＲＮＡ）或氨基酸（Ａｍｉｎｏｒ?Ａｃｉｄ?ｓｅｑｕｅｎｃｅ）均以单母编码来表示，通常序列前会添加序列名及相应的注释。??一般情况下，参考基因组都存储在此类格式的文件中，单条染色体作为一

ＡＣＣＣＣＡＡＡＡＡＧＣＣＧＡＧＡＧＡＡＧＣＴＧＧＣＡＡＴＧＴＧＧＣＴＣＡＴＣＴＧＴＡＡＴＡＣＣＡＧＣＡＣＴＴＴＧＧＡＡＧＧＣＴＧＡＧＡＧＧＧＣＧＡＡＣＴＴＣＴＴＴＧＡＧＣＴＣ??＋??图２．３?ＦＡＳＴＱ格式文件示例??ＦＡＳＴＱ格式的序列一般每四行为一个单位，通常标题在第一行录入，必须??由’＠’开始，后面跟着唯一的序列标识符及可选的描述内容。第二行是核苷酸序??列，由Ａ、Ｃ、Ｇ、Ｔ、Ｎ构成；第三行以’＋’为起始符，后面可能会包含序列的??描述信息，或者没有信息，仅充当分隔符；第四行是测序序列的质量值，意指每??个碱基字符在相对位置上的可信度。与第二行的字符一一对应，所以长度跟第二??行是一致的。质量分数部分采用ＡＳＣＩＩ编码。图２．３是ＦＡＳＴＱ格式文件的一个示??例。??在ＦＡＳＴＱ格式文件中，质量值是非常重要的，它是一个碱基的错误率的对??数值。在测序过程中，可根据荧光信号的强弱得到一个参考的测序错误概率Ｐ值，??通过如下的Ｐｈｒｅｄ质量分数计算公式

【参考文献】：
期刊论文
[1]第三代测序技术及其应用[J]. 张得芳,马秋月,尹佟明,夏涛.  中国生物工程杂志. 2013(05)
[2]DNA测序技术的发展历史与最新进展[J]. 解增言,林俊华,谭军,舒坤贤.  生物技术通报. 2010(08)



本文编号：3276026