Data distribution for phylogenetic inference with site repeats via judicious hypergraph partitioning

I Baar, L Hübner, P Oettig, A Zapletal… - 2019 IEEE …, 2019 - ieeexplore.ieee.org
2019 IEEE International Parallel and Distributed Processing …, 2019ieeexplore.ieee.org
The so-called site repeats (SR) technique can be used to accelerate the widely-used
phylogenetic likelihood function (PLF) by identifying identical patterns among multiple
sequence alignment (MSA) sites, thereby omitting redundant calculations and saving
memory. However, this complicates the optimal data distribution of MSA sites in parallel
likelihood calculations, as the cost of computing the likelihood for individual sites strongly
depends on the sites-to-cores assignment. We show that finding a'good'sites-to-cores …
The so-called site repeats (SR) technique can be used to accelerate the widely-used phylogenetic likelihood function (PLF) by identifying identical patterns among multiple sequence alignment (MSA) sites, thereby omitting redundant calculations and saving memory. However, this complicates the optimal data distribution of MSA sites in parallel likelihood calculations, as the cost of computing the likelihood for individual sites strongly depends on the sites-to-cores assignment. We show that finding a 'good' sites-to-cores assignment can be modeled as a hypergraph partitioning problem, more specifically, a specific instance of the so-called judicious hypergraph partitioning problem. We initially develop, parallelize, and make available HyperPhylo, an efficient open-source implementation for this flavor of judicious partitioning where all vertices have the same degree. Using empirical MSA data, we then show that sites-to-core assignments computed via HyperPhylo are substantially better than those obtained via a previous naive approach for phylogenetic data distribution under SRs.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果