The Longest Haplotype Reconstruction Problem Revisited
Riccardo Dondi
Abstract
The Longest Haplotype Reconstruction (LHR) problem has been introduced
in Computational Biology for the reconstruction of the haplotypes of an
individual, starting from a matrix of incomplete haplotype fragments. In
this paper, we reconsider the LHR problem, proving that it is NP-hard
even in the restricted case when the input matrix is error-free. Then,
we investigate the approximation complexity of the problem, showing that
it cannot be approximated within factor $2^(log^delta nm) for any
constant delta<1, unless NP-class is subset DTIME[2^(poly log nm)].
Finally, we give a fixed-parameter algorithm, where the parameter is the
size of the reconstructed haplotypes.