A binning tool to reconstruct viral haplotypes from assembled contigs

Jiao Chen; Jiayu Shang; Jianrong Wang; Yanni Sun

Step 2: contig clustering based on relative abundance distribution Let the number of haplotypes estimated by step 1 be N . The problem can be defined as: given contigs C 0 , C 1 , ..., Cn assembled from viral quasispecies sequencing data, cluster the contigs into N groups so that each group contains contigs originating from the same haplotype. The relative haplotype abundance will be computed during the clustering process. The clustering algorithm we adopt is prototype-based clustering and is essentially an augmented K-means algorithm. In a standard K-means algorithm, the centroid of the objects in a cluster is the prototype of the cluster. In our algorithm, the prototype is a distribution that is derived from the contigs and empirically describes the relative abundance distribution.