Finding most likely haplotypes in general pedigrees through parallel search with dynamic load balancing.
General pedigrees can be encoded as Bayesian networks, where the common MPE query corresponds to finding the most likely haplotype configuration. Based on this, a strategy for grid parallelization of a state-of-the-art Branch and Bound algorithm for MPE is introduced: independent worker nodes concurrently solve subproblems, managed by a Branch and Bound master node. The likelihood functions are used to predict subproblem complexity, enabling efficient automation of the parallelization process. Experimental evaluation on up to 20 parallel nodes yields very promising results and suggest the effectiveness of the scheme, solving several very hard problem instances. The system runs on loosely coupled commodity hardware, simplifying deployment on a larger scale in the future.
Bren School of Information and Computer Sciences, University of California, Irvine, CA 92697, USA. lotten@ics.uci.edu
Lars
L
Otten
Rina
R
Dechter
D000465:Algorithms; D001499:Bayes Theorem; D019295:Computational Biology; D005260:Female; D006239:Haplotypes; D006801:Humans; D008297:Male; D008957:Models, Genetic; D010375:Pedigree