Viral Quasispecies Spectrum Reconstruction via Coloring the Vertex in the Weighted Read Conflict Graph

摘要

Viruses exist in their hosts as a collection of related viral haplotypes, called viral quasispecies. Since the composition of virus quasispecies is of clinical significance, assembling a group of viral quasispecies from a set of sequenced reads has become one of the most challenging problems in bioinformatics today. In this paper, a weighted read conflict graph is constructed by introducing fuzzy distance and a given threshold, and a viral quasispecies assembly algorithm CWSS is proposed based on color coding technology. The CWSS algorithm colors all vertices according to their sum of edge weight and saturation degree, so that all adjacent vertices must have different colors. The time complexity of the CWSS algorithm is O(m~2 n + mn). Simulated datasets of HIV quasispecies were adopted to compare the reconstruction performance of the CWSS algorithm and the Dsatur one, which resolves the reconstruction problem by coloring an unweighted read conflict graph. The experimental results show that algorithm CWSS can obtain much more accurate estimation of the number of quasispecies than the Dsatur algorithm and still performs well with reads (or read-pairs) of high error rates.