Graphical models such as Bayesian networks have many applications in computational biology, numerous algo- rithmic improvements have been made over the years. Yet many practical problem instances remain infeasible as technology advances and more data becomes available, for instance through SNP genotyping and DNA se- quencing. We therefore suggest a scheme to parallelize a graphical model search algorithm on a computational grid, with applications to finding the most likely haplotype configuration in general pedigrees. Through this we can obtain faster solution times than sequential algorithms and solve previously infeasible problem instances.