生物高通量测序片段拼接与分子标记识别算法研究

发布时间：2017-05-25 08:25

  本文关键词：生物高通量测序片段拼接与分子标记识别算法研究，由笔耕文化传播整理发布。

【摘要】：快速准确的获取生物体的遗传信息是生命科学研究的基石,基因组是生物体全部遗传信息的载体。测序技术能够获得基因组的遗传信息,进而较全面的揭示生物体的复杂性和多样性,因而在生命科学研究中具有十分重要的作用。随着科学的进步,下一代测序技术迅速发展并广泛应用,使得生物序列数据的获取效率和费用成本的快速下降都达到了前所未有的程度,这些对基因组的深度测序和重测序研究产生了极大的推动作用。序列数据生产速度越来越快,由此产生了数量巨大的生物序列数据,而如何高效准确的对大数据量的生物序列数据进行分析和比较,成为了生物信息学领域的新挑战。近几年来计算机运算性能的增长趋于缓慢,为应对大数据时代的需求出现了Map Reduce、Spark等云计算技术,但目前生物信息领域的各种工具和方法还未能充分利用这些新技术。因此,本文以序列分析为基础,利用Map Reduce技术结合序列比对、串和图等算法,深入研究了高通量序列拼接与分子标记识别两方面的几个问题,主要内容如下。(1)提出了基于Map Reduce的高通量序列数据的聚类分析算法。生物序列聚类可以为下游序列分析工作提供基础,高通量测序也为序列聚类提出了新内容和新挑战。针对这一问题,本文提出了基于两种相似度的结合Map Reduce技术的贪心聚类方法。首先,从相似序列会共享一定数量k-mer这一事实出发,本文提出了基于窗口内非交叠共享k-mer计数的相似度计算方法,可以过滤掉不相关序列间的比对计算,从而大幅度提高比对效率;然后,对于相似序列的精确比对,本文提出了基于共享k-mer扩展块的块比对相似度计算方法。利用本文方法可对大规模序列数据如EST、高通量测序读片段等进行聚类分析。(2)提出了基于序列聚类和Seeds Graph的高通量测序片段拼接算法。全基因组高通量测序数据的拼接,主要困难在于高通量序列数据读长短、数量大和错误率高。本文针对这三方面的困难提出了基于Map Reduce和序列聚类的全基因组de novo拼接方法Seeds Graph。该方法利用云计算平台解决数据量大的问题,用序列聚类将短片段以簇表示,并定义可容错的seed结构来纠正测序错误。然后利用seed为顶点建立的SeedsGraph图来指导测序片段的拼接过程。最后,本文采用路径相容分析技术和双端读片段信息方式解决重复序列导致的复杂路径问题。实验表明Seeds Graph有良好的可扩展性,可处理较大规模基因组的拼接问题。(3)提出了多供体高通量测序数据的基因组结构变异分子标记识别算法。目前对生物个体重测序的研究普遍存在测序对象数量较多而测序深度不够的现象。在这种测序个体较多但深度都不大的数据中进行全基因组结构变异识别,往往因为深度不够而不能获得准确的结果。本文针对这一问题,提出了基于多供体高通量重测序数据的全基因组结构变异识别方法。该方法利用Map Reduce技术解决数据量巨大的问题,结合双端读片段和读片段分隔方法进行结构变异事件的识别;利用改进的仿射空位罚分的半全局序列比对算法,预测结构变异精确的断点位置。(4)综合本文在序列分析的算法成果,设计并实现了基于同源搜索和集成分类的mi RNA分子标记识别方法。该方法利用已知mi RNA为参考,对EST或高通量测序数据进行同源搜索,使用RNAfold软件分析发夹环结构,获得粗略的mi RNA前体候选集。为了解决该候选集中假阳性率过高的不平衡分类问题,本文提出了基于投票机制的集成学习分类方法。利用已知mi RNA作为正例和适当选择的反例以不平衡数据分类问题的策略训练多种分类器,再集成为一个单独的分类器,并对候选集进行分类。利用该方法可得到输入数据集中高可信度的miRNA候选,可以用于指导下游mi RNA识别和分析的研究工作。
【关键词】：序列比对 序列聚类 基因组拼接 结构变异 高通量测序
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.4
【目录】：

• 摘要4-6
• ABSTRACT6-14
• 第1章 绪论14-30
• 1.1 课题背景及意义14-16
• 1.1.1 研究背景14-15
• 1.1.2 研究意义15-16
• 1.2 相关知识介绍16-24
• 1.2.1 序列分析技术简介16-17
• 1.2.2 测序技术简介17-22
• 1.2.3 基因组结构变异简介22
• 1.2.4 非编码RNA简介22-23
• 1.2.5 Map Reduce技术简介23-24
• 1.3 国内外研究现状24-28
• 1.3.1 高通量数据的聚类与拼接24-26
• 1.3.2 生物分子标记的识别26-28
• 1.4 本文主要工作28-30
• 第2章 基于MAPREDUCE的生物序列聚类算法30-54
• 2.1 引言30-34
• 2.1.1 问题描述31-32
• 2.1.2 相关算法32-34
• 2.2 基于共享k-mer计数的序列相似度计算方法34-38
• 2.2.1 基于共享k-mer计数的序列相似度34-35
• 2.2.2 基于Map Reduce的序列共享k-mer计数算法35-38
• 2.3 基于块比对的序列相似度计算方法38-47
• 2.3.1 全局比对和局部比对算法38-40
• 2.3.2 基于共享k-mers扩展块的局部块比对40-43
• 2.3.3 边加权有向无环图单源最长路径算法43-46
• 2.3.4 局部块比对的优化46-47
• 2.4 序列聚类算法47-49
• 2.5 实验与分析49-52
• 2.6 本章小结52-54
• 第3章 基于读片段聚类的高通量数据拼接算法54-79
• 3.1 引言54-59
• 3.1.1 拼接方法及相关算法55-57
• 3.1.2 问题描述57-59
• 3.2 NGS读片段聚类算法59-65
• 3.2.1 数据预处理59
• 3.2.2 生成k-mer群组59-61
• 3.2.3 读片段的聚类61-65
• 3.3 基于欧拉路径的contig建立算法65-69
• 3.3.1 Seeds Graph的构建65-66
• 3.3.2 Seeds Graph中重复路径的分析66-68
• 3.3.3 Contigs的生成方法68-69
• 3.4 基于mate-pair的scaffold建立方法69-72
• 3.4.1 Contigs间的相对方向70-71
• 3.4.2 Contigs的定位方法71-72
• 3.4.3 填充gap和生成scaffolds72
• 3.5 实验与分析72-77
• 3.6 本章小结77-79
• 第4章 基于高通量测序的多供体结构变异识别算法79-104
• 4.1 引言79-85
• 4.1.1 结构变异及其重要作用80-81
• 4.1.2 结构变异识别方法的研究现状81-82
• 4.1.3 问题描述82-85
• 4.2 基于Map Reduce的读片段定位方法85-89
• 4.2.1 不一致的读片段对86
• 4.2.2 基于Map Reduce的筛选算法86-89
• 4.2.3 合并多供体的候选读片段89
• 4.3 结构变异的识别算法89-97
• 4.3.1 小型indel事件的识别方法90-91
• 4.3.2 插入事件的识别方法91-92
• 4.3.3 缺失事件的识别方法92-93
• 4.3.4 倒位事件的识别方法93-94
• 4.3.5 易位事件的识别方法94-95
• 4.3.6 重复事件的识别方法95-96
• 4.3.7 识别算法96-97
• 4.4 断点精确预测算法97-100
• 4.4.1 基于split-read的断点预测方法97-99
• 4.4.2 基于soft clipping的断点预测方法99-100
• 4.5 实验与分析100-103
• 4.6 本章小结103-104
• 第5章 基于同源搜索与集成分类的MIRNA识别方法104-116
• 5.1 引言104-108
• 5.1.1 相关研究105-107
• 5.1.2 识别流程107-108
• 5.2 基于Map Reduce的同源序列搜索方法108-111
• 5.2.1 数据的预处理108
• 5.2.2 同源序列搜索108-111
• 5.3 基于集成学习的分类器111-113
• 5.3.1 样本集的选择111
• 5.3.2 集成分类器的构建111-113
• 5.4 实验与分析113-114
• 5.5 本章小结114-116
• 结论116-118
• 参考文献118-132
• 攻读博士学位期间发表的论文及其它成果132-136
• 致谢136-137
• 个人简历137

  本文关键词：生物高通量测序片段拼接与分子标记识别算法研究，，由笔耕文化传播整理发布。

本文编号：393192