A scalable parallelization of the gene duplication problem

Phylogenetics is a branch of computational and evolutionary biology dealing with the inference of trees depicting evolutionary relationships among species and/or sequences. An important problem in phylogenetics is to find a species tree that is most parsimonious with a given set of gene trees, which are derived from sequencing multiple gene families from various subsets of species. The gene duplication problem is to compute a species tree that requires the minimum number of gene duplication events to reconciliate with the given set of gene trees. The best known heuristic algorithm for this NP-hard problem is a local optimization technique that runs in O(n2+kmn)O(n2+kmn) time per search step, where kk is the number of gene trees, nn is the size of the species tree, and mm is the maximum size of a gene tree. In this paper, we present a parallel algorithm for the gene duplication problem that runs in O(n2+kmnp) time for up to p=O(nklogk) processors. Our algorithm exploits multiple levels of parallelism by parallelizing both the exploration of the search neighborhood and reconciliating of the gene trees with species trees in the neighborhood. Due to the wide variance in the sizes of the gene trees, it is difficult to completely characterize the behavior of the algorithm analytically. We present experimental results on the Blue Gene/L to study both levels of parallelism and how best they should be combined to achieve overall minimum execution time. On a large problem that took about 62.5 h on a 3 GHz Pentium 4, our parallel algorithm ran in 7.7 min on a 1024 node Blue Gene/L.