title: HapCol: accurate and memory-efficient haplotype assembly from long reads.
abstract: Haplotype assembly is the computational problem of reconstructing haplotypes in diploid organisms and is of fundamental importance for characterizing the effects of single-nucleotide polymorphisms on the expression of phenotypic traits. Haplotype assembly highly benefits from the advent of 'future-generation' sequencing technologies and their capability to produce long reads at increasing coverage. Existing methods are not able to deal with such data in a fully satisfactory way, either because accuracy or performances degrade as read length and sequencing coverage increase or because they are based on restrictive assumptions.
  
  
  
  By exploiting a feature of future-generation technologies-the uniform distribution of sequencing errors-we designed an exact algorithm, called HapCol, that is exponential in the maximum number of corrections for each single-nucleotide polymorphism position and that minimizes the overall error-correction score. We performed an experimental analysis, comparing HapCol with the current state-of-the-art combinatorial methods both on real and simulated data. On a standard benchmark of real data, we show that HapCol is competitive with state-of-the-art methods, improving the accuracy and the number of phased positions. Furthermore, experiments on realistically simulated datasets revealed that HapCol requires significantly less computing resources, especially memory. Thanks to its computational efficiency, HapCol can overcome the limits of previous approaches, allowing to phase datasets with higher coverage and without the traditional all-heterozygous assumption.
  
  
  
  Our source code is available under the terms of the GNU General Public License at http://hapcol.algolab.eu/
  
  
  
  bonizzoni@disco.unimib.it
  
  
  
  Supplementary data are available at Bioinformatics online.
authors: Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy.
authors: Yuri
authors: Y
authors: Pirola
authors: Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy.
authors: Simone
authors: S
authors: Zaccaria
authors: Dipartimento di Scienze Umane e Sociali, Univ. degli Studi di Bergamo, Bergamo, Italy.
authors: Riccardo
authors: R
authors: Dondi
authors: Life Sciences group, Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands, ERABLE Team, INRIA, Lyon, France and.
authors: Gunnar W
authors: GW
authors: Klau
authors: ERABLE Team, INRIA, Lyon, France and Dipartimento di Informatica, Univ. degli Studi di Pisa, Pisa, Italy.
authors: Nadia
authors: N
authors: Pisanti
authors: Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy.
authors: Paola
authors: P
authors: Bonizzoni
mesh_terms: D000465:Algorithms; D004171:Diploidy; D006239:Haplotypes; D020641:Polymorphism, Single Nucleotide; D017422:Sequence Analysis, DNA; D012984:Software