  The computational problem of inferring the full haplotype of a cell starting
from read sequencing data is known as haplotype assembly, and consists in
assigning all heterozygous Single Nucleotide Polymorphisms (SNPs) to exactly
one of the two chromosomes. Indeed, the knowledge of complete haplotypes is
generally more informative than analyzing single SNPs and plays a fundamental
role in many medical applications. To reconstruct the two haplotypes, we
addressed the weighted Minimum Error Correction (wMEC) problem, which is a
successful approach for haplotype assembly. This NP-hard problem consists in
computing the two haplotypes that partition the sequencing reads into two
disjoint sub-sets, with the least number of corrections to the SNP values. To
this aim, we propose here GenHap, a novel computational method for haplotype
assembly based on Genetic Algorithms, yielding optimal solutions by means of a
global search process. In order to evaluate the effectiveness of our approach,
we run GenHap on two synthetic (yet realistic) datasets, based on the Roche/454
and PacBio RS II sequencing technologies. We compared the performance of GenHap
against HapCol, an efficient state-of-the-art algorithm for haplotype phasing.
Our results show that GenHap always obtains high accuracy solutions (in terms
of haplotype error rate), and is up to 4x faster than HapCol in the case of
Roche/454 instances and up to 20x faster when compared on the PacBio RS II
dataset. Finally, we assessed the performance of GenHap on two different real
datasets. Future-generation sequencing technologies, producing longer reads
with higher coverage, can highly benefit from GenHap, thanks to its capability
of efficiently solving large instances of the haplotype assembly problem.
