黄丹,吴璟莉.基于彩色编码技术的准种重建算法[J].计算机科学,2019,46(2):310-314
基于彩色编码技术的准种重建算法
Quasispecies Reconstruction Algorithm Based on Color Coding Technology
投稿时间:2017-11-23  修订日期:2018-02-21
DOI:
中文关键词:  准种,单体型,带权图,彩色编码,模糊距离
英文关键词:Quasispecies,Haplotype,Weighted graph,Color coding,Fuzzy distance
基金项目:本文受国家自然科学基金项目(61363035,61762015,61502111,7),广西自然科学基金项目(2015GXNSFAA139288),“八桂学者”工程专项,广西多源信息挖掘与安全重点实验室系统性研究基金项目(14-A-03-02,15-A-03-02),广西科技基地和人才专项(AD16380008)资助
作者单位E-mail
黄丹 广西师范大学计算机科学与信息工程学院 广西 桂林541004  
吴璟莉 广西师范大学计算机科学与信息工程学院 广西 桂林541004
广西师范大学广西多源信息挖掘与安全重点实验室 广西 桂林 541004
广西区域多源信息集成与智能处理协同创新中心 广西 桂林 541004 
wjlhappy@mailbox.gxnu.edu.cn 
摘要点击次数: 0
全文下载次数: 0
中文摘要:
      求解病毒准种单体型有助于了解其基因结构特点,对疫苗的研制及抗病毒治疗具有重要意义。文中通过引入模糊距离,构造一种带权的片段冲突图,并提出了基于彩色编码技术的病毒准种单体型重建算法CWSS。CWSS算法先根据给定阈值对片段冲突图进行预处理;然后根据顶点的边权和及饱和度取值为图中顶点着色,着色遵循相邻顶点颜色相异的原则,直至所有顶点完成着色;最后将相同颜色的顶点片段进行组装,得到准种单体型。CWSS算法的时间复杂度为O(m2n+mn) 。采用模拟测序片段数据进行实验测试,对CWSS算法和Dsatur算法的重建性能和质量进行对比分析。实验结果显示,相比于Dsatur算法,CWSS算法能获得更准确的准种单体型,具有更高的重建性能。
英文摘要:
      The reconstruction of viral quasispecies haplotypes contributes to know about the structure of viral gene-tic,and is of great significance for vaccine preparation and antiviral therapy.In this paper,a weighted fragment conflict graph was constructed by introducing fuzzy distance,and a viral quasispecies haplotypes reconstruction algorithm CWSS was proposed based on color coding technology.Firstly,the CWSS algorithm preprocesses the fragment conflict graph in accordance with a given threshold.Secondly,under the condition that adjacent vertices must have different colors,all vertices of the graph are colored according to their sum of edge weigh and saturation value.Finally,quasispecies haplotypes are obtained by assembling the fragment with the same color.The time complexity of the CWSS algorithm is O(m2n+mn).Simulated sequencing fragment were adopted to compare the reconstruction performance and quality of the CWSS algorithm and the Dsatur one.The experimental results show that CWSS algorithm can obtain more accurate quasispecies and higher reconstruction performance than Dsatur algorithm.
查看全文  查看/发表评论  下载PDF阅读器