基于彩色编码技术的准种重建算法

摘要

求解病毒准种单体型有助于了解其基因结构特点,对疫苗的研制及抗病毒治疗具有重要意义.文中通过引入模糊距离,构造一种带权的片段冲突图,并提出了基于彩色编码技术的病毒准种单体型重建算法CWSS.CWSS算法先根据给定阈值对片段冲突图进行预处理;然后根据顶点的边权和及饱和度取值为图中顶点着色,着色遵循相邻顶点颜色相异的原则,直至所有顶点完成着色;最后将相同颜色的顶点片段进行组装,得到准种单体型.CWSS算法的时间复杂度为O(m2 n+mn).采用模拟测序片段数据进行实验测试,对CWSS算法和Dsatur算法的重建性能和质量进行对比分析.实验结果显示,相比于Dsatur算法,CWSS算法能获得更准确的准种单体型,具有更高的重建性能.