A Graph Auto-Encoder for Haplotype Assembly and Viral Quasispecies
  Reconstruction
  Reconstructing components of a genomic mixture from data obtained by means of
DNA sequencing is a challenging problem encountered in a variety of
applications including single individual haplotyping and studies of viral
communities. High-throughput DNA sequencing platforms oversample mixture
components to provide massive amounts of reads whose relative positions can be
determined by mapping the reads to a known reference genome; assembly of the
components, however, requires discovery of the reads' origin -- an NP-hard
problem that the existing methods struggle to solve with the required level of
accuracy. In this paper, we present a learning framework based on a graph
auto-encoder designed to exploit structural properties of sequencing data. The
algorithm is a neural network which essentially trains to ignore sequencing
errors and infers the posteriori probabilities of the origin of sequencing
reads. Mixture components are then reconstructed by finding consensus of the
reads determined to originate from the same genomic component. Results on
realistic synthetic as well as experimental data demonstrate that the proposed
framework reliably assembles haplotypes and reconstructs viral communities,
often significantly outperforming state-of-the-art techniques.
