序列比对算法中的BW变换索引技术研究及其改进

面向大规模长序列的序列比对问题是生物信息学中最重要的基础问题之一。针对序列比对算法的主流索引技术BW变换(BWT)进行研究,提出一种新的二阶BWT索引方法。与传统BWT方法的逐位索引查找不同,改进后的BWT方法按双位索引查找。实验结果表明,改进后的方法减少了序列比对算法中的循环遍历和计算次数,降低了序列比对算法中索引方法的复杂度,提高了查找效率,尤其适合长序列和大规模序列的索引和查找。

基于长读数和多序列比对的间隙填充方法

间隙(gap)填充方法有助于获取更加完整和准确的基因组序列,可以促进基因表达与调控、结构变异分析和物种进化的研究。虽然已有较多填充gap的方法被提出,但是填充的准确性和完整性仍有待提高。设计一种基于长读数和多序列比对的gap填充方法GapLM。将包含gap的序列集合切割成不含gap的序列集合,基于长读数和序列之间比对位置的差异对结果进行修正。通过分析比对确定覆盖每个gap区域的左侧、右侧和跨过3个序列集合。针对1个gap和其相关联的3个序列集合,采用多序列比对方法分别对3个集合中的序列进行处理和融合,并生成一致序列对gap区域进行填充。将GapLM与GMcloser、PBjelly、LR_Gapcloser 3种填充方法在2个真实数据集上进行比较,实验结果表明,GapLM具有更加完整和准确的填充结果。

深度学习几何约束预测的蛋白质建模方法

蛋白质结构可以由残基间距离和主干二面角确定,精确预测残基间距离和二面角有助于蛋白质从头建模.为了提升蛋白质结构预测的精度,提出了距离约束和二面角优化的蛋白质结构预测方法.首先,基于HHblits和Jackhmmer搜索序列数据库以获取蛋白质多序列比对;进而,提取序列频率谱、位置熵、互信息、去除背景噪声的互信息、协方差矩阵、接触势能和CCMpred计算的耦合分数等特征;然后设计深度残差神经网络和长短时记忆网络,预测残基间距离和主干二面角;最后,开发了基于能量极小化的结构建模优化方法GCPFold.在80个测试蛋白上的实验结果表明,GCPFold方法可以有效折叠蛋白质结构.

水平聚类分簇和垂直分组的大规模长序列多比对

为解决现有算法在大规模长序列数据集上耗时过长的问题,提出一种融合水平聚类分簇和垂直分组的多序列比对方法.采用mBed方法和简并字母表方法将序列集编码为数值向量集,利用二分k-means算法聚类数值向量集并将序列集划分成多个水平簇;提出最长兼容链构建算法和簇内序列垂直分割方法,进而设计簇内序列垂直分组方法将每个水平簇划分为多个垂直分组,分别比对各垂直分组,以获得各个水平簇内序列的比对结果;设计针对水平簇集的簇间序列垂直分组方法和带有Gap类型推断的动态规划渐进比对方法,将长序列集垂直划分为多个簇间分组并分别进行对准,以实现大规模长序列的比对.实验结果表明,与同类算法相比,本文方法在维持较高比对精度的同时,显著地减少了比对的时间开销.