基于Edlib的启发式生物序列聚类算法  

A heuristic biological sequence clustering algorithm based on Edlib

作　　者：卫泽刚 陈旭 张小丹 胡婉靖 刘飞 WEI Ze-gang;CHEN Xu;ZHANG Xiao-dan;HU Wan-jing;LIU Fei(Institute of Physics and Optoelectronics Technology,Baoji University of Arts and Sciences,Baoji 721016,Shaanxi,China)

机构地区：[1]宝鸡文理学院物理与光电技术学院,陕西宝鸡721016

出　　处：《宝鸡文理学院学报（自然科学版）》2024年第3期50-55,共6页Journal of Baoji University of Arts and Sciences(Natural Science Edition)

基　　金：国家自然科学基金青年项目(62402010);宝鸡文理学院校级研究生创新科研项目(YJSCX23YB37);陕西省科技厅项目(2024SF-YBXM-134);陕西省教育厅项目(23JK0287);陕西基础科学(数学、物理学)研究院科研计划项目(23JSQ051);2023年教育部产学合作协同育人项目(230705211175618);宝鸡文理学院第十七批校级本科教学改革研究项目(22JGYB37);宝鸡文理学院2023年大学生创新创业训练计划项目(S202310721033)。

摘　　要：目的提出一种基于Edlib的启发式序列聚类算法:EdClust,以降低目前启发式序列聚类算法普遍存在的聚类数量过估计和聚类种子序列质量低的问题。方法EdClust首先读取第一条序列并作为第一个聚类单元的种子;然后读取下一条序列,通过Edlib计算序列与种子序列的相似性,如果相似性大于给定阈值,则对其进行聚类,否则,创建一个新的聚类单元并作为其种子序列;重复以上步骤,直到所有序列完成聚类。结果2组实验测试表明,EdClust在聚类数量和种子序列质量上均取得较好效果。结论EdClust采用Edlib进行序列比对,可以快速得到待比对序列与种子序列间的相似性,提高了聚类种子质量,降低了聚类数量过估计。Purposes—To develop a new heuristic sequence clustering heuristic(EdClust)based on Edlib,with the aim of addressing overestimation of inferred clusters and low seed quality in numerous heuristic clustering algorithm.Methods—In EdClust,the first input sequence becomes the seed for the first cluster.The next input sequence is compared against all existing seeds by using the Edlib C/C++library of sequence alignment.If the similarity is greater than the given threshold,this sequence is added to the corresponding cluster.Otherwise,a new cluster is created,and the sequence becomes the seed.The previous processes are repeated until all the sequences are clustered.Results—EdClust is tested on two widely used databases,demonstrating that EdClust can obtain fewer clusters and achieve higher clustering sensitivity.Conclusions—In EdClust,Edlib is used to perform pairwise alignment,which can find the most similar region at any part of the seed for a query sequence.It's demonstrated that EdClust improves the seed quality and reduces the overestimation of clusters.

关 键 词：序列聚类 启发式聚类 聚类质量 高通量测序 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]