A result-set-based algorithm for haplotype reconstruction

Most algorithms proposed in the literature for individual haplotyping problem try to generate a single pair of haploytpes with the highest accuracy in terms of certain specific optimization criteria. However, due to the limitations of models, the result produced by these algorithms may not be the real best one, which leads to a low reconstruction rate for the pair of constructed haplotypes. This paper starts with a thorough analysis on the reasons for how the real best result can be lost during a haplotyping process based on the minimum error correction (MEC) model. We propose a new idea to reduce the probability of losing the best result by generating a small set of optimal results (which will be called an optimal result set), instead of a single optimal result. Based on this idea, a practical parthenogenetic algorithm PGA-SET is presented to solve the MEC model. The short chromosome code and small size population of PGA-SET algorithm ensure that it can obtain a relatively small optimal result set. Experimental results indicate that the set contains no more than 7 results in general, and which contains at least a pair of haplotypes that has higher reconstruction rate than those generated by previous algorithms solving the MEC model. This strongly suggests that the idea of generating a small optimal result set may effectively avoid losing the real best result, and PGA-SET algorithm is a practical method based on this idea.