Paper Info
Title
The longest haplotype reconstruction problem revisited
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 2logδ nm for any constant δ poly log nm]. Finally, we give a fixed-parameter algorithm, where the parameter is the size of the reconstructed haplotypes.
Year
Venue
Keywords
2009
FCT
restricted case,longest haplotype reconstruction,reconstructed haplotypes,incomplete haplotype fragment,longest haplotype reconstruction problem,input matrix,approximation complexity,computational biology,fixed-parameter algorithm,poly log nm,lhr problem
Field
DocType
Volume
DTIME,Discrete mathematics,Combinatorics,Reconstruction problem,Matrix (mathematics),Haplotype,Time complexity,Mathematics
Conference
5699
ISSN
ISBN
Citations 
0302-9743
3-642-03408-X
0
PageRank 
References 
Authors
0.34
10
1
Name
Order
Citations
PageRank
Riccardo Dondi18918.42