Haplotype assembly of autotetraploid potato using integer linear programming

Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods are not delivering satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short sequencing reads. Our method is based on a generalization of the existing minimum fragment removal (MFR) model to the polyploid case and on new integer linear programs (ILPs) to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and real data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on real data confirm a sensible improvement over the state of the art. Binaries for Linux are available at: http://github.com/ComputationalGenomics/HaplotypeAssembler .