DNA序列拼接中欧拉超路算法的新并行策略

序列拼接是全基因组测序的核心问题之一．基于“overlap-layout-consensus”的传统拼接软件虽然被人们应用于人类基因组拼接等项目,但它们始终不能有效解决全基因组重复序列的拼装问题．为了克服上述不足,Pevzner等提出了欧拉超路拼接算法．由于该算法要求构造一个复杂的de Bruijin图,因此用欧拉超路算法拼接大规模全基因组存在存储瓶颈问题．该文对欧拉超路拼接算法做了并行化研究并付诸实现,有效解决了欧拉超路算法中的存储瓶颈问题．测试结果表明,该并行算法具有良好的可扩缩性,能够解决较大规模全基因组的序列拼接．     

面向新一代基因测序数据的拼接算法综述*

随着新一代基因测序技术的不断发展,越来越多的物种通过全基因组鸟枪法拼接算法获得全序列。针对新一代DNA测序数据存在reads长度短,高覆盖度且存在错误数据等特点,研发满足实际应用的拼接软件,是序列拼接领域迫切的研究课题。本文探讨了全基因组序列拼接面临的挑战,研究了主流的几类拼接算法的拼接原理、操作流程,分析各种算法的优缺点和适用范围,其中包括：基于贪心图算法、基于OLC图算法,基于DeBruijn图算法等,并根据不同的标准列举了几类拼接算法之间的差异性,最后对基因拼接算法在未来的研究给出了建议。     

Phrap算法在DNA序列拼接中的应用与改进

介绍DNA序列拼接的背景与意义．详细介绍和分析Phrap算法在DNA序列拼接中的应用．并针对DNA序列拼接算法提出改进。     

DNA片段拼接中重复序列算法研究

本文主要研究DNA片断拼接中重复序列信息识别算法。包含大量重复信息的DNA序列,其重构是大规模DNA片段拼接所面临的实际困难之一。针对目前大多数拼接算法对于重复段的处理采用效率较低的反复迭代算法的特点,提出了基于k-mer子串的重复段分析方法,充分考虑了拼接中可能的分割点,设计与分析了识别重复序列并提高序列一致性的高效算法。     

面向下一代测序技术的de novo序列拼接工具综述

序列拼接是生物信息学的基础问题.全面总结了面向下一代测序技术的de novo DNA序列拼接工具,介绍下一代测序平台产生的数据特点以及de novo序列拼接算法所面临的挑战;给出序列拼接算法的形式化定义,总结目前最常用的拼接策略以及根据相应策略开发的拼接工具的特点和实现细节;对评估拼接性能的主要参数进行描述,并通过不同物种、不同规模的真实基因组序列数据对多个具有代表性的拼接工具进行测试,比较它们的拼接性能以验证相应的工具特点.为研究人员提供工具选择指导或改善拼接工具性能提供帮助;最后总结并阐述序列拼接工具存在的问题和发展趋势.     

一种视频序列的拼接算法

提出了一种视频序列的拼接算法。首先在同一镜头下的视频序列中提取若干关键帧，利用关键帧拼接表示序列的拼接；其次利用光流场算法计算出的运动位移量引导相邻关键帧间特征点的匹配,并结合随机抽样一致性（RANSAC）鲁棒估计算法和单映矩阵的级联性，得到相邻关键帧、非相邻关键帧间的对应矩阵；最后通过融合实现了序列的无缝拼接。实验验证了这种方法的有效性。     

改进的全景图拼接融合算法

在全景图像理论的基础上,对现有的拼接算法进行研究和改进,采用基于像素点颜色变化特征和序列相似性检测拼接算法相结合的图像拼接融合方法对柱面全景图进行拼接。实验表明,与原有的算法相比,采用改进后算法的全景图拼接效果得到了改进,对柱面全景图像的拼接融合能取得满意的视觉效果。     

序列模式挖掘的并行算法研究

序列模式在许多领域都有着重要的应用,大量的数据和模式需要高效的、可扩展的并行算法.针对目前序列模式挖掘算法存在的普遍问题,提出了一个适合无共享并行环境下的算法PMSP,有效地解决了存储受限以及时效性问题,并将它与当前相对较优的并行算法HPSPM做了比较,实验表明PMSP是有效的.     

CuMen：基于最大频繁序列模式的聚类算法及其在基因拼接中的应用

基因组序列拼接的主流方法是将整条序列随机打断成小片段,然后根据片段间重叠关系连接成长序列.由于较多噪音存在,算法复杂度高,加之生物数据的海量增长,序列拼接处理导致巨大的时空开销而无法完成.本文提出一种基于最大频繁序列模式的聚类算法,将整个数据集分成若干个子集,分别高效地处理,实现了一个基因拼接网格系统、透明动态的资源管理,大大扩展了基因拼接计算能力.基于最大频繁序列模式聚类算法及挖掘算法,针对生物数据的特性做出了优化.     

CGDNA:基于簇图的基因组序列集成拼接算法

基因组测序的目的是获取一个生物体完整的DNA序列信息,而DNA信息是进行遗传学研究和疾病诊断的基础。通常而言,完整的基因组测序分为两个步骤:第一步通过实验手段测定DNA序列片段,第二步通过计算方法把DNA片段拼接为完整的基因组。尽管桑格测序技术成功解析了包括人类在内的多个基因组,但其由于成本过高,目前逐渐被新一代测序技术所取代。新一代测序技术的特点为高通量、高覆盖率、低成本,随之而来的缺点体现为短读长、更多类型的错误。这些特点也给基因拼接算法带来了更大的挑战。鉴于目前的数十种基因拼接算法中并没有一种算法显著优于其它算法,且一些分析表明不同算法的拼接结果具有互补性,提出了CGDNA算法框架,它把不同算法的拼接结果整合到一起,使得整合的结果超越任何单个算法的结果。提出了一种基于簇图的基因组序列集成拼接算法,它通过构建索引、读长映射、重叠群聚簇、构建簇图等步骤将重叠群拼接成更长的序列。实验结果表明,相对于目前最优的算法Velvet、ABySS、SOAPdenovo,CGDNA在N50与最长拼接序列这两项指标上的增长比例高达50%以上,并且达到了较高的覆盖度。当更多的基本算法集成到本算法时,性能可进一步提高。提出的方法大幅提高了基因拼接的长度,为下一步的遗传分析降低了难度,并加快了生物基因组研究的步伐。     

基于成本和并行装配的装配序列有向图求解

针对虚拟装配中装配序列规划问题,引入了有向图来描述装配过程中的零件以及零件间的装配约束关系。结合装配成本、并行装配、装配经验优化了装配关系有向图的拓扑排序算法。提出了将装配方向变化次数作为衡量装配成本的一项重要指标。提出了将单次可装配的零件数量作为装配优先方向的参考依据。文章最后给出了装配序列生成的具体算法。     

生物序列拼装欧拉路径算法的Gamma描述及其并行化研究

序列拼装是生物基因测序的一个重要环节,也是生物信息学重要的研究内容．[2]中将Eulerian路径的方法应用于序列拼接,较好地解决传统序列拼装软件中存在的repeat问题,从而提高序列拼装的精度,但对于该方法的研究目前还只有串行化的实现,拼装速度不够理想．在本文中,我们采用了并行化Gamma模型形式化地描述了用于序列拼装的Eulerian方法,并给出了Gamma程序的并行化实现方案．     

Why greed works for shortest common superstring problem

The shortest common superstring problem (SCS) has been extensively studied for its applications in string compression and DNA sequence assembly. Although the problem is known to be Max-SNP hard, the simple greedy algorithm performs extremely well in practice. To explain the good performance, previous researchers proved that the greedy algorithm is asymptotically optimal on random instances. Unfortunately, the practical instances in DNA sequence assembly are very different from the random instances.     

基于Pthreads的并行DSRC压缩算法设计与实现

高通量测序仪产生大量的DNA数据,FASTQ是被广泛使用的存储DNA数据的数据格式.对FASTQ格式的数据进行压缩处理,能有效地节省存储空间.DSRC算法具有压缩比高的优点,因此对DSRC算法进行并行能提高压缩FASTQ格式的DNA数据的效率.基于Pthreads,实现了并行DSRC算法.测试结果表明,当使用4线程时加速比达到3.5.     

基于图划分的全基因组并行拼接算法

提出了一种基于图划分的全基因组并行拼接算法．该算法巧妙地将数据划分问题转化成图划分的问题,解决了传统数据划分算法中存在的节点负载不平衡的问题．同时,算法在建立关系图时有效地利用了WGS测序中所提供reads之间的长度信息和配对信息,使reads关系图能更准确地反映出数据之间的关系特性,从而提高了数据划分的准确性．实验结果表明,该算法可以准确地划分各种模拟数据、真实数据的数据集,相对于传统数据划分算法划分质量有了明显改善．     

"天河二号"上一种DNA序列denovo拼接方法的并行优化策略

基于String Graph理论的序列拼接工具SGA是当前国际上的一种新型序列拼接工具.首先,形式化证明了SGA的序列拼接问题是一个NP完全问题,然后对SGA的拼接效率进行了分析,发现与业界同类拼接软件相比,SGA在内存开销方面具有优势,但却有更大的时间开销,其中构建索引占了60%~70%的比例.基于此,设计了一种并行优化策略,并实现了面向天河二号体系结构的并行策略来解决这一问题.分别在普通机群和天河二号上进行性能测试,针对小规模数据,优化后的索引构建时间比之前的最佳性能提高了3.06倍,中等规模数据提高了1.60倍,实验结果表明,其优化效果明显,且并行构建局部索引过程具有良好的线性扩展性.其中用到的优化方法和策略对相关问题的研究有一定的借鉴意义.这也表明,天河二号的超级计算能力能够很好地助力生命科学领域的相关研究.     

A molecular solution for minimum vertex cover problem in tile assembly model

Self-assembly is a generalization of the crystal growth, which has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computation. In the same context, tile assembly model is a highly distributed parallel model of natural self-assembly. In this paper, we propose a tile assembly system to tackle a well-known NP-complete problem known as Minimum Vertex Cover problem. The proposed algorithm requires Θ(n×m) types of tiles, and each parallel assembly executes in a linear time, where n is the number of vertices and m is the number of edges. Furthermore, the experimental results proved the simplicity and the efficiency of the proposed algorithm to solve the Minimum Vertex Cover, and reduce the overall complexity to find the solution.     

Scalable parallel word search in multicore/multiprocessor systems

This paper presents a parallel algorithm for fast word search to determine the set of biological words of an input DNA sequence. The algorithm is designed to scale well on state-of-the-art multiprocessor/multicore systems for large inputs and large maximum word sizes. The pattern exhibited by many sequential solutions to this problem is a repetitive execution over a large input DNA sequence, and the generation of large amounts of output data to store and retrieve the words determined by the algorithm. As we show, this pattern does not lend itself to straightforward standard parallelization techniques. The proposed algorithm aims to achieve three major goals to overcome the drawbacks of embarrassingly parallel solution techniques: (i) to impose a high degree of cache locality on a problem that, by nature, tends to exhibit nonlocal access patterns, (ii) to be lock free or largely reduce the need for data access locking, and (iii) to enable an even distribution of the overall processing load among multiple threads. We present an implementation and performance evaluation of the proposed algorithm on DNA sequences of various sizes for different organisms on a dual processor quad-core system with a total of 8 cores. We compare the performance of the parallel word search implementation with a sequential implementation and with an embarrassingly parallel implementation. The results show that the proposed algorithm far outperforms the embarrassingly parallel strategy and achieves a speed-up’s of up to 6.9 on our 8-core test system.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。