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

摘要：

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

关键词：测序长序列、多比对、水平分簇、垂直分组、最长兼容链、Gap类型推断

所属期刊栏目：44

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金

在线出版日期：2023-10-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2353-2361