论文部分内容阅读
研究病毒准种单体型对了解病毒的基因序列,研制病毒疫苗以及制定有效的抗病毒治疗方法有着重要的实际意义。由于当前技术水平的限制,仅仅依靠生物学手段获取病毒准种单体型所需的金钱和时间成本很高。因此,利用计算方法来重建病毒准种单体型成为研究人员关注的热点问题。本文主要针对病毒准种单体型重建问题进行研究,设计并开发了一个系统软件包,具体工作如下:针对带有病毒准种单体型信息的测序片段来构造片段冲突图,引入模糊距离来衡量片段之间差异度,在带权冲突图模型下对单体型重建问题进行研究,提出了一种基于边权简约的改进重建算法IDsatur(Improved Dsatur)。IDsatur算法先根据阈值预处理片段冲突图;然后根据顶点的度及饱和度取值为图中顶点着色,着色遵循相邻顶点颜色相异的原则,直到着色完图中所有顶点;最终将同种颜色的顶点片段进行组装,从而获得准种单体型。实验采用模拟测序片段数据进行测试,比较分析算法IDsatur和Dsatur的重建性能和质量。实验结果显示,算法IDsatur能够获得更少的准种单体型种数和更高的重建性能,有效的处理并解决了当测序错误率增大时,重建数量过多的问题。针对准种单体型重建问题,提出了一种基于边权和着色的彩色编码算法CWSS(Coloring with Weight Sum and Saturation)。CWSS算法采用与IDsatur算法类似的算法流程,在冲突图着色时,利用边权和及饱和度来选定着色点。采用模拟测序片段数据对算法CWSS和Dsatur的重建性能和质量进行对比分析,实验结果显示,相对于算法Dsatur,算法CWSS能获得更准确的准种单体型种数和更高的重建性能,且其重建性能在测序错误率高的情况下仍表现良好。基于提出的重建算法IDsatur和CWSS,设计开发了病毒准种单体型重建的实用软件包。该软件包使用Python语言和装有wxpython库的JetBrains PyCharm Community Edition2016.2.3(64)作为开发工具,可以在任何安装了该开发工具的系统中运行。该软件包的功能包括参数设置、读入生物数据、重建准种、查看结果与帮助五大模块。参数设置模块可以根据实际情况,设置准种长度和边权和阈值的实验参数,读入生物数据模块可读入重建所需数据,在重建的过程中,可查看当前重建运行的进度,完成重建后可得到重建种数、重建包含的片段集和重建的基因序列以及根据重建指标得出的数值。综上所述,本文引入模糊距离,并使用阈值来预处理带权的片段冲突图,提出了一种一种基于边权简约的改进重建算法IDsatur和一种基于边权和着色的彩色编码算法CWSS。实验结果显示,两种算法都能获得更少的准种单体型种数,且其重建精度也更高,对于处理病毒准种单体型重建问题而言,两种算法都是行之有效的计算方法。为此,该相应软件包的开发也同样具有一定的实际应用价值。