title: SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming.
abstract: BACKGROUND
  The goal of haplotype assembly is to infer haplotypes of an individual from a mixture of sequenced chromosome fragments. Limited lengths of paired-end sequencing reads and inserts render haplotype assembly computationally challenging; in fact, most of the problem formulations are known to be NP-hard. Dimensions (and, therefore, difficulty) of the haplotype assembly problems keep increasing as the sequencing technology advances and the length of reads and inserts grow. The computational challenges are even more pronounced in the case of polyploid haplotypes, whose assembly is considerably more difficult than in the case of diploids. Fast, accurate, and scalable methods for haplotype assembly of diploid and polyploid organisms are needed.
  
  
  RESULTS
  We develop a novel framework for diploid/polyploid haplotype assembly from high-throughput sequencing data. The method formulates the haplotype assembly problem as a semi-definite program and exploits its special structure - namely, the low rank of the underlying solution - to solve it rapidly and with high accuracy. The developed framework is applicable to both diploid and polyploid species. The code for SDhaP is freely available at https://sourceforge.net/projects/sdhap .
  
  
  CONCLUSIONS
  Extensive benchmarking tests on both real and simulated data show that the proposed algorithms outperform several well-known haplotype assembly methods in terms of either accuracy or speed or both. Useful recommendations for coverages needed to achieve near-optimal solutions are also provided.
authors.affiliation: Department of ECE, The University of Texas at Austin, Austin, Austin, USA. shreedas@utexas.edu.
authors.forename: Shreepriya
authors.initials: S
authors.lastname: Das
authors.affiliation: Department of ECE, The University of Texas at Austin, Austin, Austin, USA. hvikalo@ece.utexas.edu.
authors.forename: Haris
authors.initials: H
authors.lastname: Vikalo
mesh_terms: D000465:Algorithms; D004171:Diploidy; D015894:Genome, Human; D006239:Haplotypes; D006720:Homozygote; D006801:Humans; D011123:Polyploidy; D012984:Software