  We present MLEHaplo, a maximum likelihood de novo assembly algorithm for
reconstructing viral haplotypes in a virus population from paired-end next
generation sequencing (NGS) data. Using the pairing information of reads in our
proposed Viral Path Reconstruction Algorithm (ViPRA), we generate a small
subset of paths from a De Bruijn graph of reads that serve as candidate paths
for true viral haplotypes. Our proposed method MLEHaplo then generates a
maximum likelihood estimate of the viral population using the paths
reconstructed by ViPRA. We evaluate and compare MLEHaplo on simulated datasets
of 1200 base pairs at different sequence coverage, on HCV strains with
sequencing errors, and on a lab mixture of five HIV-1 strains. MLEHaplo
reconstructs full length viral haplotypes having a 100% sequence identity to
the true viral haplotypes in most of the small genome simulated viral
populations at 250x sequencing coverage. While reference based methods either
under-estimate or over-estimate the viral haplotypes, MLEHaplo limits the
over-estimation to 3 times the size of true viral haplotypes, reconstructs the
full phylogeny in the HCV to greater than 99% sequencing identity and captures
more sequencing variation for the HIV-1 strains dataset compared to their known
consensus sequences.
