Haplotype inference

Many pathogens exist in their hosts as diverse ensembles of related, but genetically different individuals. Genetic diversity is the result of random mutation and natural selection and it plays an important role for the evolutionary success of the species in its environment. In HIV infection, for example, a diverse population is maintained in a single host so that the virus can more easily escape from the host's immune response. The high genetic heterogeneity of HIV also constitutes a major obstacle in the development of an effective vaccine. Other examples of diverse populations of medical interest include bacterial communities and tumor cells.

In recent years, a new generation of cost-effective DNA sequencing technologies has been introduced. Due to their high coverage, this approach is referred to as ultra-deep sequencing. We use ultra-deep sequencing data to detect genetic diversity in much greater depth than with traditional methods. Traditional Sanger sequencing can only infer the consensus sequence of a sample and polymorphic sites can only be detected if they are present in a substantial fraction of the sample. By contrast, with deep sequencing methods one can draw a very large number of relatively short and error-prone DNA reads from the population of interest.

We develop and apply mathematical and computational tools for correcting sequencing errors in the reads and for the assembly of reads into a set of diverse haplotypes. Our goal is to computationally reconstruct the genomic structure of the population from the observed set of reads. Our approach makes use of Bayesian inference, statistical learning theory, and combinatorial optimization. It is implemented in the software package ShoRAH.

Selected references

• Zagordi O, Klein R, Däumer M, Beerenwinkel N (2010). Error correction of next-generation sequencing data and reliable estimation of HIV quasispecies. Nucleic Acids Research, in press.
• Zagordi O, Geyrhofer L, Roth V, Beerenwinkel N (2009). Deep sequencing of a genetically heterogeneous sample: local haplotype reconstruction and read error correction. RECOMB 2009.
• Eriksson N, Pachter L, Mitsuya Y, Rhee S-Y, Wang C, Gharizadeh B, Ronaghi M, Shafer RW, Beerenwinkel N (2008). Viral population estimation using pyrosequencing. PLoS Computational Biology 4(5):e1000074.