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

doi:10.11896/j.issn.1002-137X.2019.02.046

Computer Science ›› 2019, Vol. 46 ›› Issue (2): 301-305.doi: 10.11896/j.issn.1002-137X.2019.02.046

• Interdiscipline & Frontier • Previous Articles Next Articles

Quasispecies Reconstruction Algorithm Based on Color Coding Technology

HUANG Dan¹, WU Jing-li^1,2,3

College of Computer Science and Information Technology,Guangxi Normal University,Guilin,Guangxi 541004,China¹
Guangxi Key Laboratory of Multi-source Information Mining & Security,Guangxi Normal University,Guilin,Guangxi 541004,China²
Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing,Guilin,Guangxi 541004,China³

Received:2017-11-23 Online:2019-02-25 Published:2019-02-25

Abstract

Abstract: 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 thefragment 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(m²n+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.

Key words: Color coding, Fuzzy distance, Haplotype, Quasispecies, Weighted graph

CLC Number:

TP301

HUANG Dan, WU Jing-li. Quasispecies Reconstruction Algorithm Based on Color Coding Technology[J].Computer Science, 2019, 46(2): 301-305.

References

[1]EIGEN M,SCHUSTER P.Hypercycle-principle of natural self-organization.a.emergence of hypercycle[J].Naturwissenschaften,1977,64(11):541-565.
[2]ANDINO R,DOMINGO E.Viral quasispecies[J].Virology, 2015,479-480(1):46-51.
[3]DOMINGO E,SHELDON J,PERALES C.Viral quasispecies evolution[J].Microbiology & Molecular Biology Reviews Mmbr,2012,76(2):159-216.
[4]COX R J,BROKSTAD K A,OGRA P.Influ-enza virus:immunity and vaccination strategies.Comparison of the immune response to inactivated and live,attenuated influenza vaccines[J].Scandinavian Journal of Immunology,2004,59(1):1-15.
[5]LAURING A S,ANDINO R.Quasispecies theory and the behavior of RNA viruses[J].Plos Pathogens,2010,6(7):e1001005.
[6]BU D,TANG H.Quasispecies reconstruction based on vertex coloring algorithms[C]∥IEEE International Conference on Bioinformatics and Biomedicine.Washington D.C:IEEE Co-mputer Society,2014:63-66.
[7]ERIKSSON N,PACHTER L,MITSUYA Y,et al.Viral popula- tion estimation using pyrosequencing[J].Plos Computational Bio-logy,2008,4(5):e1000074.
[8]MANCUSO N,TORK B,SKUMS P,et al.Viral Quasispecies Reconstruction from Amplicon 454 Pyrosequencing Reads[C]∥IEEE International Conference on Bioinformatics and Biomedicine Workshops.Washington D.C:IEEE Computer Society,2011:94-101.
[9]ZAGORDI O,BHATTACHARYA A,ERIKSSON N,et al. ShoRAH:estimating the genetic diversity of a mixed sample from next-generation sequencing data[J].Bmc Bioinformatics,2011,12(1):1-5.
[10]HUANG A,KANTOR R,DELONG A,et al.QColors:An algorithm for conservative viral quasispecies reconstruction from short and non-contiguous next generation sequencing reads[J].Silico Biology,2011,11(5-6):193-201.
[11]BRON C,KERBOSCH J.Algorithm 457:finding all cliques of an undirected graph[J].Communications of the Acm,1973,16(9):575-576.
[12]METZKER M L.Sequencing technologies－the next generation[J].Nature Review Genetic,2010,11(1):31-46.
[13]POH W T,XIA E,CHININMANU K,et al.Viral quasispecies inference from 454 pyrose-quencing[J].BMC Bioinformatics,2013,14(1):355.
[14]ALTSCHUL S F,GISH W,MILLER W,et al.Basic local alignment search tool[J].Journal of Molecular Biology,1990,215(3):403-410.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Quasispecies Reconstruction Algorithm Based on Color Coding Technology

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 0

[1]	LIU Sheng-jiu, LI Tian-rui, XIE Peng, LIU Jia. Measure for Multi-fractals of Weighted Graphs [J]. Computer Science, 2021, 48(3): 136-143.
[2]	ZHANG Qian and WU Jing-li. Triploid Individual Haplotype Reconstruction Algorithm Based on Enumeration Strategy [J]. Computer Science, 2017, 44(1): 75-79.
[3]	YAO Hua-chuan,WANG Li-zhen,CHEN Hong-mei and HU Xin. CP_SDD+RDS:An Algorithm Based on Row-divided Sorting and Single-direction Detecting for Finding Closest Pair of Points [J]. Computer Science, 2013, 40(7): 201-205.
[4]	. Subgraph Similarity Matching Based on Path Mapping [J]. Computer Science, 2012, 39(11): 137-141.
[5]	ZHOU Wei, WANG Jian-xin ,XIE Min-zhu ,CHEN Jian er （School of Information Science and Engineering, Central South University, Changsha 410083,China）. [J]. Computer Science, 2008, 35(11): 166-169.
[6]	NING Dan ,WANG Jian-Xin （School of Information Science and Engineering, Central South University, Changsha 410083）. [J]. Computer Science, 2007, 34(7): 222-224.