A Graph Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction
This addresses the challenge of accurately assembling haplotypes and viral communities from sequencing data, which is crucial for applications like single individual haplotyping and viral studies, representing a strong domain-specific advancement.
The paper tackles the NP-hard problem of reconstructing genomic mixture components from DNA sequencing data, such as in haplotype assembly and viral quasispecies reconstruction, by proposing a graph auto-encoder framework that often significantly outperforms state-of-the-art techniques on realistic synthetic and experimental data.
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.