High performance computing for haplotyping: models and platforms

Andrea Tangherloni, Leonardo Rundo, Simone Spolaor, Marco S. Nobile, Ivan Merelli, Daniela Besozzi, Giancarlo Mauri, Paolo Cazzaniga, Pietro Liò

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)


The reconstruction of the haplotype pair for each chromosome is a hot topic in Bioinformatics and Genome Analysis. In Haplotype Assembly (HA), all heterozygous Single Nucleotide Polymorphisms (SNPs) have to be assigned to exactly one of the two chromosomes. In this work, we outline the state-of-the-art on HA approaches and present an in-depth analysis of the computational performance of GenHap, a recent method based on Genetic Algorithms. GenHap was designed to tackle the computational complexity of the HA problem by means of a divide-et-impera strategy that effectively leverages multi-core architectures. In order to evaluate GenHap’s performance, we generated different instances of synthetic (yet realistic) data exploiting empirical error models of four different sequencing platforms (namely, Illumina NovaSeq, Roche/454, PacBio RS II and Oxford Nanopore Technologies MinION). Our results show that the processing time generally decreases along with the read length, involving a lower number of sub-problems to be distributed on multiple cores.

Original languageEnglish
Title of host publicationEuro-Par 2018
Subtitle of host publicationParallel Processing Workshops - Euro-Par 2018 International Workshops, Revised Selected Papers
EditorsGabriele Mencagli, Dora B. Heras
Number of pages12
ISBN (Electronic)978-3-030-10549-5
ISBN (Print)978-3-030-10548-8
Publication statusPublished - 1 Jan 2019
Externally publishedYes
Event24th International Conference on Parallel and Distributed Computing, Euro-Par 2018 - Turin, Italy
Duration: 27 Aug 201828 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11339 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Parallel and Distributed Computing, Euro-Par 2018


  • Future-generation sequencing
  • Genome Analysis Haplotype Assembly
  • High Performance Computing
  • Master-Slave paradigm


Dive into the research topics of 'High performance computing for haplotyping: models and platforms'. Together they form a unique fingerprint.

Cite this