KIT | KIT-Bibliothek | Impressum | Datenschutz

Data Distribution for Phylogenetic Inference with Site Repeats via Judicious Hypergraph Partitioning

Baar, Ivo; Hübner, Lukas; Oettig, Peter; Zapletal, Adrian; Schlag, Sebastian; Stamatakis, Alexandros; Morel, Benoit

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.

Open Access Logo

DOI: 10.1109/IPDPSW.2019.00038
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsmonat/-jahr 05.2019
Sprache Englisch
Identifikator ISBN: 978-1-7281-3511-3
KITopen-ID: 1000097566
HGF-Programm 46.12.02 (POF III, LK 01) Data Activities
Erschienen in IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Rio de Janeiro, Brazil, Brazil, 20-24 May 2019
Verlag Institute of Electrical and Electronics Engineers (IEEE)
Seiten 175–184
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page