CPU和GPU协同并行加速多生物序列比对

将主库构建阶段的输入序列分成多个分主库、将主库扩展阶段的主库元素划分成多个计算窗口,使之符合GPU并行计算的线程结构特性,GPU以计算窗口为单位并行计算比对矩阵、并行约减主库及并行扩展比对矩阵,结合库优化思想优化主库构建过程,利用阈值cutoff控制主库约减程度,设计实现CPU和多个GPU协同计算并行比对多生物序列的高效可扩展算法OGM SA.实验结果表明,当cutoff≤0.20时,算法OGM SA的比对结果质量与算法G-M SA相同,计算速度是G-M SA算法的近4倍,内存容量需求比G-MSA算法也有所降低.

二级Hash全局和局部索引筛选的长序列比对并行算法

通过构建参考基因组的二级Hash索引,以快速筛选出测序长序列在参考基因组中可能匹配的候选区域;建立测序序列局部索引,以加速测序序列和参考基因组候选区域之间的映射定位;对每个候选区域里的k-mer与测序序列的索引命中进行左右扩展获得比对种子;采用等距离抽样方式对种子抽取多个位置,利用抽样结果建立判断依据来过滤掉那些不可能匹配的种子;建立处理包含“均聚物”类型错误的序列片段全局比对得分方程,并行填补比对骨架的空隙,并采取GPU显存预分配和后释放独立的并行比对策略,以提升序列片段全局并行比对效率.模拟与真实数据的实验结果表明,相较于已有同类的长序列比对并行算法,本文提出的并行算法获得整体上较高的比对敏感度、碱基层次灵敏度和准确度,且可有效处理第3代测序长序列含有的“均聚物”类型错误,显著加速了大规模长序列与参考基因组比对的完成.

融合信息量差异和聚类精炼的多Motif识别

采用信息量差异扩展采样Markov链的排斥力函数,使排斥力的值增加,推动两条相互靠近的采样Markov链向不同的区域探索,使motif位置概率矩阵元素值得到更新,避免motif识别算法过早陷入局部最优解,以发现更多的候选motif;利用信息量对motif聚类精炼,以减少假阳性motif对算法结果的影响,提高识别结果的精度和召回率.模拟启动子序列和真实数据集ENCODE TF Chip-seq上的实验结果表明,与同类的多motif识别算法相比,本文算法获得更高的召回率和精度、识别出保守性高的motif和匹配更多真实的motif.

时空高效的允许插入空位的short-read比对

short-read alignment(短序列比对)在下一代测序技术中得到广泛运用.精确识别测序序列中的gap(空位)是后续基因组解读的基础,而现有的允许空位的short-read比对算法效果并不理想或者不允许插入空位.对于查询序列和参考序列均为short reads的比对问题,通过采取训练查询序列样本数据寻找不同物种和不同read长度匹配的最优插入空位数量的策略,对大规模的short reads进行两两比对,以减少算法的迭代次数,从而减少算法所需的中间矩阵计算量,并用向量存储算法比对过程中的中间矩阵元素值,以降低存储空间需求,提出一种改进的short-read比对算法.数千万的short reads对准实验结果表明:与已有的有代表性的同类算法相比,本文算法在确保short-read比对精确度的前提下,降低了所需的运行时间和存储空间.

识别高质量重叠社区的高效算法

现实的社区结构通常具有相互重叠的现象,发现重叠社区结构有助于研究网络的特性、预测网络的变化趋势.通过改进非重叠社区发现算法LabelRank的后处理过程,以使得算法能够发现网络中重叠的社区结构;引入标签更新相似度作为标签更新的判别依据,给出一种能够消除标签震荡现象的迭代终止条件,以提升发现重叠社区结构的质量,同时显著减少社区识别算法的计算量和迭代次数.在人工生成网络数据集和真实网络数据集上的实验结果表明,与现有的重叠社区发现算法相比,给出的算法能够更加高效地发现更高质量的重叠社区.

通过DFT变换提取DNA序列特征聚类物种

利用离散傅里叶变换(Discrete Fourier Transformation,DFT)可以在不丢失信息的情况下揭示DNA序列隐藏信息的特性,通过挖掘DNA序列中子序列种类、含量和位置3种生物特征,将任意长度的DNA序列提取成等长的特征向量,使用欧式距离计算DNA序列相似度,给出一种改进的应用于物种聚类的无需比对的DNA序列相似度计算算法AFCS_DFT.实验结果表明:与已有的同类方法相比,AFCS_DFT算法计算得到了更准确的DNA序列相似度,利用此相似度对物种聚类,可以更准确地构建出反映物种聚类特征的系统进化树,揭示了进化水平越相近的物种的DNA序列越相近的特性.

高错误率长序列的高敏感度比对

将第三代测序平台产生的高错误率的长序列(long read)与参考基因组进行映射比对,需要高的编辑距离阈值.为此种求解长序列比对问题,将高错误率的长序列分割成较短的片段,借鉴全映射比对的思想,寻找所有满足编辑距离阈值的序列片段的候选位置;采用对高编辑距离更敏感的基于Hash索引的变长种子播种算法,定位序列片段在参考基因组上的候选位置,将连续“插入删除”相同碱基的编辑距离设置为1,使得算法可以处理第三代测序数据中新出现的“均聚物(homopolymer)”类型错误,以提升序列比对的敏感度;对片段侯选位置数量进行统计分析,求出片段候选位置质量分数,过滤掉质量不高的片段侯选位置;根据序列片段间的位置关系,动态连接片段的侯选位置,连接时对不同错误类型给予不同罚分,以去除假阳性的候选位置,确保比对的准确度.在模拟和真实数据集上的实验结果表明,与同类方法相比,本文方法在获得相同高的准确度的同时,提升了比对查全率和敏感度.

增强型稀疏后缀数组索引的高错误率reads比对

生物序列比对有助于定位序列之间的相似区域.测序技术的快速发展需要序列比对算法能够灵活地处理更长且错误率更高的reads序列.通过增强型稀疏后缀数组对参考序列建立索引,自适应地调整种子的最小长度,寻找参考序列与reads序列之间的最大精确匹配和超大精确匹配,以此进行种子扩展,提出一种改进的long-read比对算法.与已有代表性的算法相比,模拟和真实数据实验结果表明,本文算法在获得基本相同精确度的前提下,召回率明显提升,敏感度总体上更高,且能够识别更多的reads序列.

通过区域筛选和简洁de Bruijn图比对高重复短序列

下一代测序平台产生的大量短序列(short reads)包含许多重复的子序列,这给求解短序列比对(short-read alignment)问题带来了挑战.如何处理包含重复子序列的基因组区域将影响后续基因组的分析.现有的利用de Bruijn图的短序列比对算法效果并不理想或者未考虑重复子序列的影响.针对包含许多重复子序列的短序列比对问题,依据种子预定义由给定的shape布局中生成的关键字建立hash索引,通过采用基于空位种子(gapped seeds)搜索策略的区域选择方法,通过搜索索引筛选候选位置以减少待比对的候选位置个数、减少搜索空间;运用Hough变换分组操作将种子命中聚集为粗对准形式,以降低后续比对验证时间;采用简洁de Bruijn图结构压缩存储和索引长度为k的序列片段(k-mer),以降低比对所需的存储空间.分析与实验结果表明,与已有的代表性同类算法相比,本文的算法既保持或获得更高正确比对百分比,又降低了所需的运行时间和存储空间,尤其是对高重复率的序列进行比对,本文算法可获得更高的正确对准百分比.