串联重复序列比对的位置筛选方法

串联重复序列是基因组构建的困难片段,由于其重复单元之间的相似性与其拷贝数的不确定性,在序列比对时容易定位到多个候选位置,如何快速而准确地筛选出正确的比对位置是一项挑战。现有方法使用种子（从测序片段中选取的短序列）来定位并扩展候选比对位置,但挑选种子时未考虑串联重复序列特性。因此,提出了一种串联重复序列比对的位置筛选方法,其通过计算稀有kmer（长度为k的子序列）序列的相似性来筛选比对结果。此外,采用合并稀有kmer的策略加速计算,并利用基于编辑距离的模糊查找以提高过滤信息密度。实验结果表明,在模拟数据集上提高比对结果的召回率与准确率的同时,该方法比现有方法快约2倍,且具有良好的并行加速性能。     

一种基于低频种子的三代测序序列比对方法

随着测序技术的发展,三代测序已广泛应用于基因研究中。但是,由于三代测序序列具有平均长度长、错误率高的特性,如何快速、准确地将测序片段比对到参考基因组上成为严峻挑战。现有方法使用种子（从测序片段中挑选的短序列）来加速比对过程,但在挑选时未考虑频率特性,导致定位候选区域阶段时间消耗较大。因此,提出了一种基于低频种子的三代测序序列比对方法,该方法采用种子投票策略,使用低频种子进行投票,减少投票计数的时间消耗,并根据位置及票数关系对候选区域进行再过滤,进一步提高比对速度。实验结果表明,在确保敏感性和准确率的同时,本文方法比现有方法快3倍左右。     

基于新测序技术的比对与组装算法

针对新型超高通量测序仪Solexa测序仪所产生的测序片段read的比对与组装问题,提出一种短序列比对与组装算法SRMA,采用对参考序列进行hash的方法,将测序片段read分3段快速、准确地定位于参考序列,对不能定位的read采取从头（Denovo）组装的方法进行组装。测试结果表明SRMA算法具有较高的性能和敏感度,以及良好的应用前景。     

基于新一代测序数据的比对算法的研究

随着测序技术的发展,现在的高通量测序技术已经能在短时间内产生大量的数据.一个人类基因组的数据大约在3GB,而测序的数据集则往往是人类基因组的30倍以上(100GB).如此庞大的数据量,就为生物学家带来相对较大的挑战.基于新一代测序数据的比对通常是开展诸多分析工作的第一步,对于生物信息工作者深入研究极为重要,但是该类软件往往偏向计算机方向,其对比原理及使用方法对于生物信息工作者显得颇为晦涩.因此,就比对现有的主要算法进行了总结分析.     

基于区域过滤的测序序列比对算法研究

随着二代测序平台的发展,二代测序技术可短时间产生数以千万计长度在100位点左右的测序片段数据(read),如何快速、准确地将这些read比对到参考基因组上成为测序序列比对算法的严峻挑战。传统测序比对算法大多是使用种子进行细粒度过滤的方法,种子候选位置较多,造成算法验证时间过大。提出一种基于区域的粗粒度过滤方法,与细粒度过滤方法相结合来提高过滤效果,以提升测序序列比对算法处理速度,并将此过滤方法应用到找全比对Bit Mapper算法中。在线虫基因组和人类基因组上的实验结果表明,融合了区域过滤方法后的算法时间和过滤效果均有明显提升。     

基于长种子的二代测序序列找全比对算法

主流的二代测序序列找全比对算法采用种子扩展的方法,由于长种子索引存在空间开销大或检索时间长的问题,这类算法大多使用短种子而导致候选位置过多,增加了比对的时间成本.为此,提出一种基于长种子的找全比对算法,设计了一种空间开销低和检索时间适度的长种子哈希索引,其通过模运算限制哈希空间并使用布隆过滤器识别同一存储位置上的不同种子.长种子显著减少候选位置数量,从而降低验证阶段的时间开销.实验结果表明,在人类基因序列测序数据集上,该算法维持同等精度的同时比现有主流算法时间效率更高.     

高通量测序数据比对算法研究进展

高通量测序技术的出现在极大的改变了生命科学研究方式的同时也产生了海量的测序数据,如何将这些数据快速而准确的比对到参考基因组上是许多生物医学研究过程中的关键一步。为此自2007年以来,研究者们开发出了超过70种用于高通量测序序列比对的软件以解决这一问题。在本文中,我们将系统的回顾这些比对软件所运用的策略和算法,从它们的起源及发展进行比较,从而帮助生物信息工作者更好的理解和应用这些比对软件。     

面向新一代测序数据的病原微生物检测算法

病原微生物是导致交叉感染疾病甚至重大传染性疾病传播的重要因素之一,准确检测病原微生物对于感染或传染疾病的有效防御和精准诊疗具有十分重要的意义和价值。传统检测方法往往是采用培养手段进行观察和鉴别,但由于可培养的微生物种类有限,难以满足现代精准医疗中对病原微生物的准确且完备的检测要求。基于DNA分子水平上的病原微生物新型检测手段在当前得到发展和密切关注,其核心问题是如何利用被检样本的DNA测序数据,运用统计计算或机器学习方法判别样本中含有哪些病原微生物。以新一代测序数据为背景,以16S rDNA序列为分析对象,建立一种基于朴素贝叶斯的病原微生物精准检测算法,其核心思想在于：将16S rDNA序列的测序读段与病原微生物参考基因组序列进行比对,依据比对状态提取三种特征,以此构建基于朴素贝叶斯的分类模型,判别病原微生物库中每种微生物在被检样本中是否存在,从而达到病原微生物的精准检测。最后,通过仿真实验验证了所提算法的有效性,并与国际同行算法做了比较,表明该算法的优势。     

六倍体小麦基因组注释流程构建与优化

野生小麦是异源六倍体,基因组规模较大（约14 GB）,且包含大量重复序列.为了培育具有优良性状的新品种,首先要定位控制目标性状的基因,因此建立一个完整准确的基因组注释软件流程至关重要.传统的基因组注释方法基于数据库比对,具有三个明显的缺点：一是比对速度慢;二是难以发现新基因;三是软件选择没有统一标准.本文提出了一种新的生物信息学注释流程,结合了基因数据库比对、转录组高通量测序数据分析、全长转录组单分子测序数据分析等多种技术手段,实现了六倍体小麦科农9204基因组完整准确的注释,为揭示小麦生长发育规律和培育新品种提供了重要参考和软件技术支撑.     

当前RNA序列比对技术的分析

新一代测序技术的发展给DNA及RNA序列的分析带来了机遇和挑战,新一代测序技术产生的数据不同于传统测序技术产生的数据,高通量、低成本、信息量巨大的特点使得RNA序列的分析进入了一个全新的时代,以往的外显子芯片无法得到全基因组的完整信息,也无法观测到基因融合的问题,新一代测序技术使得对RNA序列的分析有了更深入的了解.文中简单介绍了DNA序列方法,以及当前主要的RNA序列比对工具的基本原理,分析了各种方法的优缺点.     

A high performance multiple sequence alignment system for pyrosequencing reads from multiple reference genomes

Genome resequencing with short reads generated from pyrosequencing generally relies on mapping the short reads against a single reference genome. However, mapping of reads from multiple reference genomes is not possible using a pairwise mapping algorithm. In order to align the reads w.r.t each other and the reference genomes, existing multiple sequence alignment(MSA) methods cannot be used because they do not take into account the position of these short reads with respect to the genome, and are highly inefficient for a large number of sequences. In this paper, we develop a highly scalable parallel algorithm based on domain decomposition, referred to as P-Pyro-Align, to align such a large number of reads from single or multiple reference genomes. The proposed alignment algorithm accurately aligns the erroneous reads, and has been implemented on a cluster of workstations using MPI library. Experimental results for different problem sizes are analyzed in terms of execution time, quality of the alignments, and the ability of the algorithm to handle reads from multiple haplotypes. We report high quality multiple alignment of up to 0.5 million reads. The algorithm is shown to be highly scalable and exhibits super-linear speedups with increasing number of processors.     

基于动态规划的Needleman-Wunsch双序列比对算法的分析与研究

生物序列比对是生物信息学中最基础的研究课题之一.基于动态规划的Needleman-Wunsch双序列比对算法主要采用迭代算法及空位罚分规则对基因序列进行逐一比对,计算二者相似性得分,最后通过回溯分析得出序列之间的最佳比对.虽然该算法可以得到最佳比对结果,但是时间复杂度和空间复杂度较高.首先对原算法进行分析,对计算得分和...     

A new approach for displaying identities and differences among aligned amino acid sequences.

An algorithm is presented for computing degrees of sequence conservation found among aligned amino acid sequences. Sequence identities are calculated for each position of an alignment and average identity values of neighboring positions are figured. The average identity value of the whole alignment is chosen as a limit to discriminate between well and less conserved sequence sections. A second algorithm is given to calculate the degree of divergence of individual sequences compared to the other sequences of the alignment. The approach is easy to use on microcomputers and gives an exact picture of sequence identities and differences in order to determine, first, protein regions of high functional or structural importance among homologous proteins, and, second, significant differences of single sequences that may contribute to individual properties of the analysed protein. The method is illustrated by an example analysing a sequence alignment of higher plant nitrate reductases.     

事件日志的批量迹与过程模型的多视角对齐方法

在业务过程发现的一致性检测中,现有事件日志与过程模型的多视角对齐方法一次只能获得一条迹与过程模型的最优对齐;并且最优对齐求解中的启发函数计算复杂,以致最优对齐的计算效率较低。为此,提出一种基于迹最小编辑距离的、事件日志的批量迹与过程模型的多视角对齐方法。首先选取事件日志中的多条迹组成批量迹,使用过程挖掘算法得到批量迹的日志模型;进而获取日志模型与过程模型的乘积模型及其变迁系统,即为批量迹的搜索空间;然后设计基于Petri网变迁序列集合与剩余迹的最小编辑距离的启发函数来加快A*算法;最后设计可调节数据和资源视角所占权重的多视角代价函数,在乘积模型的变迁系统上提出批量迹中每条迹与过程模型的多视角最优对齐方法。仿真实验结果表明,相比已有工作,在计算批量迹与过程模型间的多视角对齐时,所提方法占用更少的内存空间和使用更少的运行时间。该方法提高了最优对齐的启发函数计算速度,可以一次获得批量迹的所有最优对齐,进而提高了事件日志与过程模型的多视角对齐效率。     

带变异算子粒子群算法在多序列比对中的应用

多序列比对(Multiple Sequence Alignment)是进行生物序列分析的最基本任务之一。在对已有的多序列比对算法进行对比分析的基础上,提出了一种新的多序列比对优化算法—带变异算子粒子群多序列比对算法。带变异算子的粒子群算法提高了原有算法跳出局部收敛的能力,将其应用于多序列比对问题中,提高了已有的基于粒子群算法的多序列比对方法的性能,拓展了粒子群算法在多序列比对研究领域中的应用。实验证明,带变异算子粒子群多序列比对算法是有效、可行的。     

基于Simhash的协议数据高频相似序列提取算法

在网络协议特征提取问题中,已有的基于频率统计和序列比对等算法在时间效率和准确率上有一定缺陷,因此提出了一种基于Simhash的高频相似序列提取方法。针对传统的Simhash算法一般用于文本处理领域的问题,根据二进制序列的特点将协议数据进行“分词”处理,并采用了减少哈希结果长度、降低比较次数等方法进一步提高算法效率,最终使Simhash适合于高频相似序列提取问题。实验结果表明,该算法的平均覆盖率达到74.28%,并且在此准确率的条件下时间效率较高。