title: PWHATSHAP: efficient haplotyping for future generation sequencing.
abstract: BACKGROUND
  Haplotype phasing is an important problem in the analysis of genomics information. Given a set of DNA fragments of an individual, it consists of determining which one of the possible alleles (alternative forms of a gene) each fragment comes from. Haplotype information is relevant to gene regulation, epigenetics, genome-wide association studies, evolutionary and population studies, and the study of mutations. Haplotyping is currently addressed as an optimisation problem aiming at solutions that minimise, for instance, error correction costs, where costs are a measure of the confidence in the accuracy of the information acquired from DNA sequencing. Solutions have typically an exponential computational complexity. WHATSHAP is a recent optimal approach which moves computational complexity from DNA fragment length to fragment overlap, i.e., coverage, and is hence of particular interest when considering sequencing technology's current trends that are producing longer fragments.
  
  
  RESULTS
  Given the potential relevance of efficient haplotyping in several analysis pipelines, we have designed and engineered PWHATSHAP, a parallel, high-performance version of WHATSHAP. PWHATSHAP is embedded in a toolkit developed in Python and supports genomics datasets in standard file formats. Building on WHATSHAP, PWHATSHAP exhibits the same complexity exploring a number of possible solutions which is exponential in the coverage of the dataset. The parallel implementation on multi-core architectures allows for a relevant reduction of the execution time for haplotyping, while the provided results enjoy the same high accuracy as that provided by WHATSHAP, which increases with coverage.
  
  
  CONCLUSIONS
  Due to its structure and management of the large datasets, the parallelisation of WHATSHAP posed demanding technical challenges, which have been addressed exploiting a high-level parallel programming framework. The result, PWHATSHAP, is a freely available toolkit that improves the efficiency of the analysis of genomics information.
authors.affiliation: Computer Science and Mathematics, School of Natural Sciences, Stirling University, Stirling, FK9 4LA, UK. abb@cs.stir.ac.uk.
authors.forename: Andrea
authors.initials: A
authors.lastname: Bracciali
authors.affiliation: Department of Computer Science, University of Torino, Torino, Italy.
authors.forename: Marco
authors.initials: M
authors.lastname: Aldinucci
authors.affiliation: Laboratoire de Biométrie et Biologie Evolutive, University Claude Bernard, Lyon, France.
authors.forename: Murray
authors.initials: M
authors.lastname: Patterson
authors.affiliation: Center for Bioinformatics, Saarland University, Saarland, Germany.|Max Planck Institute for Informatics, Saarbrücken, Germany.
authors.forename: Tobias
authors.initials: T
authors.lastname: Marschall
authors.affiliation: Department of Computer Science, University of Pisa, Pisa, Italy.|Erable Team, INRIA, Grenoble, France.
authors.forename: Nadia
authors.initials: N
authors.lastname: Pisanti
authors.affiliation: Institute of Biomedical Technologies, National Research Council, Milan, Italy.
authors.forename: Ivan
authors.initials: I
authors.lastname: Merelli
authors.affiliation: Department of Computer Science, University of Pisa, Pisa, Italy.
authors.forename: Massimo
authors.initials: M
authors.lastname: Torquati
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D005828:Genetics, Population; D015894:Genome, Human; D023281:Genomics / Q000379:methods; D006239:Haplotypes / Q000235:genetics*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*
keywords: Future generation sequencing; Haplotyping; High-performance computing