方小永[1]2003年在《DNA序列拼接的分布式并行处理》文中提出生物信息学是一门综合利用生物学、计算机科学、数学等学科知识的新兴交叉学科，其主要任务是揭示海量生物学数据中蕴含的生物学意义、探索生命活动的奥秘。全基因组DNA序列拼接是生物信息学研究的重要课题。在大规模DNA测序中普遍使用的Shotgun方法中，片段序列的拼接是一个关键而又费时的过程，如何提高序列拼接的速度是本课题研究的重点。 本文在深入分析现有拼接算法及其实现软件的基础上，针对分布式并行计算环境，提出DNA序列拼接的一种新的并行算法，分别对序列拼接中的Overlap、Layout和Consensus阶段的串行处理过程和并行算法进行了探讨，通过分析数据集的划分方法和串行处理过程的可并行性，提出了多种不同的并行处理策略并加以比较。 基于本文算法，实现了拼接软件PL_Nphrap，本文对该软件的数据结构、拼接过程的实现原理以及通信优化等作了较为详实的阐述。其中，拼接过程主要包括：首尾比较、寻找Match，以形成Read Pairs；Smith_Waterman比对；LLR分值计算；动态输出Overlap；计算片段偏移量，以形成片段间的组合关系；片段投票过程，以获得Consensus序列；通信与并行优化。 最后，给出了本文算法及其拼接软件的测试结果，试验数据表明算法是高效可行的。
高进[2]2012年在《基于MapReduce的DNA序列拼接算法研究》文中指出生物信息学是集生物、数学和计算机等领域的综合学科,主要研究内容是生物信息的处理。生物信息学通过研究生物数据中蕴藏的生物学意义来揭示其对生物体活动的影响。生物体基因组控制着生物体遗传、成长、衰老等生命过程,因此基因组测序是生物信息学中的重要课题之一。但是限于现有测序设备,大部分生物体的基因组无法直接测出,普遍使用的是鸟枪法测序。鸟枪法测序中最重要的过程是序列拼接。目前,序列拼接算法主要分为基于Hamilton路径和基于欧拉(Euler)超路两种。基于Hamilton路径的算法利用的是"overlap-layout-consensus"方法,这种方法时间复杂度较高,且并没有很好克服重复序列的影响。基于欧拉超路的DNA序列拼接算法的提出,给出了DNA序列拼接的一种全新方法,克服了传统"overlap-layout-consensus"方法在拼接工作中的不足。但欧拉超路算法在拼接过程中需要生成de Bruijin图,对于序列较大的拼接工作,该图所维护的数据量十分庞大,这使存储和效率成为瓶颈问题。目前已经有基于MapReduce的拼接算法提出,但是基于seed-and-extend技术,需要参照序列。2011年,也有了一些利用MapReduce解决de Bruijin图的探讨,但大都要进行图的划分,且这一思路也仅限探讨,没有任何软件的发布。本文在研究欧拉超路算法的基础上,寻求一种基于MapReduce且避免图划分的并行策略,并在集群上进行实现。实验结果表明,使用并行策略,很好地克服了存储和效率的问题,同时在不对图进行划分的情况下,获得了更好的拼接结果。
方小永, 骆志刚[3]2005年在《DNA序列拼接的分布式并行处理》文中提出针对分布式存储环境,本文提出一种DNA序列拼接的并行算法,分别对序列拼接中OVERLAP、LAYOUT 和CONSENSUS阶段的串行处理过程和并行算法进行了描述,并给出了算法复杂性分析。数值试验结果表明,算法是高 效的。
潘旭[4]2017年在《基于Spark的DNA序列拼接算法研究》文中进行了进一步梳理生物信息学是对生物信息进行处理的交叉学科,DNA序列拼接问题是其研究的主要内容之一。DNA序列长度少则几千,多则数十亿,但目前测序仪的平均读长仅在500bp左右,无法直接测得生物体的基因组。所以,DNA序列拼接算法应运而生。该算法首先将目标序列打断成小片段,然后对这些小片段进行分别测序,最后利用计算机技术根据片段间的重迭关系进行拼接。目前,序列拼接算法主要分为Overlap-Layout-Consensus拼接算法和de-Bruijin graph 拼接算法。Overlap-Layout-Consensus 拼接算法运用 "overlap-layout-consensus"方法基于read片段进行拼接处理,虽能保留片段的完整信息,但却不能有效克服重复序列的问题。de-Bruijin graph拼接算法将read片段进行进一步拆分,然后基于更小的片段单元进行拼接处理,一定程度上克服了重复序列问题,但同时产生大量的k-mer片段,并且需要生成deBruijin图,所以,这类算法存在着很大的存储和时间上的开销。另外,对于实现平台而言,大多数研究在于单机环境下实现的串行算法,这种算法的瓶颈是空间和时间的消耗。还有人在MapReduce并行环境下进行研究。但是,基于MapReduce的计算引擎通常会将中间结果输出到磁盘上,进行存储和容错,有着费时的读写硬盘操作。效率上虽然有明显提高,但依然存在一定的时间开销。针对以上问题,本文在de-Bruijin graph拼接算法研究的基础上,提出了拆分read片段时依次右移两位碱基的策略,将改变k-mer获取方法的思想融入拼接算法中,降低了 deBruijin图的复杂度。同时,将该算法在Spark并行环境下进行了实现。仿真实验数据表明,论文所提出的基于Spark并行环境下的拼接算法在时间效率上比单机串行以及基于MapReduce环境下的并行算法得到了提高。
张丽君[5]2015年在《基于de bruijn图的并行de novo拼接技术研究》文中进行了进一步梳理随着人类基因组计划的顺利完成,基因组学也随之进入了对于基因结构和功能分析的后基因组时代。与此同时,基因组的测序技术也向着更加快速、准确和经济的目标发展。如何快速、高通量以及低消耗地实现基因组的测序仍然是基因组学中一个基础而又十分重要的环节。新一代测序技术的序列数据(read)具有数据量大、序列长度短和准确性相对较低等特点,已有的序列拼接算法并不适应上述的数据特点。因此,适应新一代测序技术的序列拼接算法的进一步研究势在必行。目前,基于deBruijn图的序列拼接算法是基因组de novo测序拼接算法中的主要方法。该类方法利用deBruijn图来存储基因序列,具有节省内存开销、高准确性和高覆盖率等特点。本文针对基于新一代测序技术的基因组de novo测序拼接问题进行了较深入的研究,并取得了一些研究结果,具体归纳如下:首先,深入调研了生物信息学的产生、定义和发展过程;调研了基因组测序和DNA序列拼接中的主要技术;深入研究了基于de Bruijn图序列拼接算法的原理和对应的算法的计算流程。其次,针对新一代DNA测序数据的短序列、高通量、数据量大等特点,引入了决策表的概念以及用四叉树进行后继k-mer的选取方法,优化了基于deBruijn图序列拼接算法。再次,深入调研了基于MapReduce模型的deBruijn图序列拼接算法。并且,基于该模型提出了避免deBruijn图分块的具体方法和并行化方法,采用变化的K值构建de Bruijn图,实现了基于de Bruijn图的并行de novo拼接程序,并获取了拼接效率最高的拼接结果序列,最后,进行了大量的实验,并将实验结果和现有的算法的结果相比较。本文提出的基于deBruijn图的序列拼接算法的优化技术能够在一定程度上提高序列拼接的效率和准确率。基于MapReduce模型的de Bruijn图的序列拼接算法的并行化研究提高了 denovo算法的扩展性,大大提高了序列拼接的速度。基因组de novo拼接方法不利用任何参考序列,直接地基于基因组测序序列(reads)推导DNA序列,对于没有DNA参考序列的物种的基因组测序是唯一的方法。本文的研究结果对于更加准确、快速和高通量地DNA新一代测序具有一定的理论价值和实用价值。
邱风[6]2013年在《基于de Bruijn图的短序列拼接算法的优化及并行化》文中研究说明基因组测序一直是基因组学的核心内容,随着测序技术的产生和发展,人们能在较短时间内获得大量测序数据。测序技术朝着高通量、低成本、高精度的方向发展,积累的测序数据也随之越来越多。如何快速、准确地处理海量测序数据已成为DNA测序发展的瓶颈。本文通过对现有基于de Bruijn图算法的新一代测序技术优缺点的深入分析和研究,针对得到的read片段长度短、数量多以及通量高的特点,研究设计了基于de Bruijn图的优化算法。在序列拼接的过程中引入决策表的概念,通过决策表中的信息更新来优化de Bruijn图中最优路径的选择,缩小后继k-mer的选择范围,从而达到缩短序列拼接时间,提高contig准确率的目的。在优化算法的基础上,提出了算法的并行化处理方案,通过分别对I/O读取和存储的并行化以及拼接过程中的并行化设计,达到进一步缩短拼接时间,减少单机上存储压力,提高计算性能的目的。仿真实验结果表明,本文提出的基于de Bruijn图算法的短序列拼接算法的优化及并行化设计与新一代测序技术中的基于de Bruijn图算法相比,有效提高了序列拼接的运算速度,降低了单机运行的内存压力。在拼接数据量为20G的C.elegans基因组,处理器为8个时,其加速比达到6倍,且具有良好的可扩展性。
苑建蕊[7]2012年在《基于双向de Bruijn图的序列拼接并行化研究与实现》文中认为DNA序列拼接是生物信息学领域研究的重要课题。随着高通量、短序列测序科技的出现,测序覆盖度进一步提高,这给原有的序列拼接技术带来了严峻的挑战。高效的适用于大规模基因组的拼接技术成为处理DNA测序数据的关键。如何结合并行计算技术从而提高序列拼接处理速度成为本文研究的重要课题。通过对已有的基于de Bruijn图的序列拼接技术的研究与分析,将序列拼接问题抽象为多步-双向de Bruijn图的结构(本文简称为双向deBruijn图),建立数学模型,并对其性质进行推导与论证。根据该图的性质,设计基于双向de Bruijn图结构的并行序列拼接方法,该方法通过融合半扩展单步-双向边得到全扩展多步-双向边集合,即DNA序列拼接过程中contig结构的集合,最终完成序列拼接。通过对基于双向deBruijn图结构的并行序列拼接方法的每一个执行步骤的确切分析,将该方法划分为四大功能模块进行实现,主要包括：并行I/O模块的设计与实现、单步-双向de Bruijn子图的构建、单步-双向de Bruijn图的分布式存储与构建以及单步-双向de Bruijn图的邻边融合模块的设计与实现。其计算复杂度为O(n/p),通讯复杂度为O(n/p),单机节点的通讯量为O(nlog(n)/p),其中n为DNA序列read的数量,p为CPU个数。实验测试表明,基于双向de Bruijn图的并行序列拼接有效提高了序列拼接的运算速度,降低了单机运行的内存消耗。在拼接数据量20G的C.elegans基因组时,其可从10个CPU扩展到640,加速比达到20倍,具有良好的可扩展性。
孟光伟[8]2017年在《基于MapReduce的DNA序列k-mer频次统计算法研究》文中指出随着“人类基因组计划”的完成,生命科学研究进入了信息共享与分析的“后基因组”时代。在探索和分析生物基因数据的过程中,DNA序列是研究的重点之一。DNA序列k-mer及其频数在基因序列拼接、序列比对、错误序列检测中有着重要的应用。由于高通量测序技术的发展以及DNA序列研究工作的迅速开展,各研究机构产生了大量数据,带来了对数据可靠存储、高效计算和分析的迫切需求,这就要求研究新的DNA序列数据存储与计算模式解决DNA序列数据的激增问题。本文首先做了理论调研工作,详细阐述了DNA序列及k-mer基本概念、特征及其应用范围,其次分析了DNA序列k-mer频次算法的国内外研究现状。同时深入研究MapReduce并行编程模型的特点和应用,并研究Hadoop分布式处理平台的特性和设计原理,得出在海量生物基因序列数据存储和计算问题上,MapReduce编程模型和Hadoop框架的优势所在。然后本文重点研究后序遍历k-mer频次统计算法(BTKC),详细分析算法原理和优缺点,针对其存在的问题,提出了一种改进算法。改进算法由用户指定可用内存和Hash表装载因子,将序列数据分区加载进Hash表进行迭代计算;同时设计了一种排序策略,对Hash表结果进行排序后输出。实验表明了算法能够在有限内存下处理任意大小的数据集,同时对Hash结果排序输出可以在数据集很大的情况下,节约合并中间结果的时间,算法效率得到有效提升。最后针对大规模DNA序列数据存储和计算问题,从理论和实践两方面分析了Hadoop框架及MapReduce编程模型的适用性。之后对改进后的算法进行并行化应用研究,提出一种基于MapReduce的DNA序列k-mer频次统计算法,并在Hadoop集群上进行实验,验证并行算法的有效性。
颜珂, 何威, 徐勇, 张健[9]2016年在《面向新一代基因测序数据的拼接算法综述》文中指出针对新一代DNA测序数据存在reads长度短、高覆盖度且存在错误数据等特点,研发满足实际应用的拼接软件,是序列拼接领域迫切的研究课题。探讨了全基因组序列拼接面临的挑战,研究了主流的几类拼接算法的拼接原理、操作流程,分析各种算法的优缺点和适用范围,其中包括基于贪心图算法、基于OLC图算法、基于De Bruijn图算法等,并根据不同的标准列举了几类拼接算法之间的差异性,最后对基因拼接算法在未来的研究给出了建议。
徐魁[10]2015年在《高效的分布式大规模基因组序列组装》文中研究表明在基因组序列组装算法中,一个最基本的问题就是如何合适的选择上下游的短序列用于组装成一个长序列。当单独从一个种子序列进行扩展的时候,大量的重复的区域将会导致非常多的扩展的候选,从而导致序列组装问题非常的复杂。目前通用的方法就是选择一个基于短序列(双端序列)之间的重迭信息然后进行组装的。然而当所组装的基因组序列是非常高重复的复杂数据的时候,这种方法将面临巨大的挑战,尤其是序列数据中还包含有错误、高重复的序列以及不均衡的测序深度导致基因组中某些区域只有少量的序列覆盖或者大量的序列覆盖。所有的这些原因导致了现在的组装程序得不到最完美的组装基因组数据。本文提出了通过原始读长信息寻找基于多个无参考序列的拼接算法产生的重迭群之间的重迭信息,来进行再组装。算法通过首先将重迭群建立k-mer位置索引,然后进行读长映射、潜在重迭群聚类、可组装重迭群聚类等步骤进行搭支架。整个算法流程能高效率便捷的运行.我们将整个算法流程设计为基于Hadoop的分布式平台,并在多个部分使用MapReduce算法,且在较小的内存机器上就可以运行。在大肠杆菌的基因组数据集上运行结果表明,本文提出的算法在组装的多项指标上据表现出良好的性能,在N50指标上有将近46%的提高,整体的组装覆盖度更加接近参考序列,并且算法能在Hadoop平台上高效的运行。
参考文献：
[1]. DNA序列拼接的分布式并行处理[D]. 方小永. 国防科学技术大学. 2003
[2]. 基于MapReduce的DNA序列拼接算法研究[D]. 高进. 北京交通大学. 2012
[3]. DNA序列拼接的分布式并行处理[J]. 方小永, 骆志刚. 计算机工程与科学. 2005
[4]. 基于Spark的DNA序列拼接算法研究[D]. 潘旭. 内蒙古农业大学. 2017
[5]. 基于de bruijn图的并行de novo拼接技术研究[D]. 张丽君. 东北大学. 2015
[6]. 基于de Bruijn图的短序列拼接算法的优化及并行化[D]. 邱风. 中南大学. 2013
[7]. 基于双向de Bruijn图的序列拼接并行化研究与实现[D]. 苑建蕊. 中南大学. 2012
[8]. 基于MapReduce的DNA序列k-mer频次统计算法研究[D]. 孟光伟. 重庆邮电大学. 2017
[9]. 面向新一代基因测序数据的拼接算法综述[J]. 颜珂, 何威, 徐勇, 张健. 计算机应用研究. 2016
[10]. 高效的分布式大规模基因组序列组装[D]. 徐魁. 天津工业大学. 2015
标签：计算机软件及计算机应用论文; 基因组论文; 并行处理论文; 高通量测序论文; 序列模式论文; 分布式算法论文; 测序深度论文; 科学论文; dna序列论文; 科普论文; 算法论文; dna测序论文;