A heuristic algorithm for minimum-recombinant haplotyping in pedigrees: Implementation and parallelization

Haplotype inference based on pedigree data under the Mendelian law of inheritance and the minimum recombination principle is important for the construction of haplotype maps and the study of disease genes. But this problem has been proven to be NP-hard, exact algorithms previously known can´t be applied to handle large scale genotype datasets, so heuristic and parallel algorithms are imperative. This paper presents an algorithm named Zero recombinant block algorithm (ZRBA) based on a new strategy using zero recombinant blocks (ZRB) as intermediate structure to reconstruct the haplotype configurations, theoretical analysis shows that this strategy can reduce the possible haplotype configurations, and compared with the dynamical programming strategy used in existing rule-based algorithms, the using of zero recombinant blocks increases the parallelism enormously. Following experiments demonstrate the superiority of our algorithm in both serial and parallel performance.