Bit-reproducible parallel phylogenetic tree inference
Bioinformatics · 2026
DOI: 10.1093/bioinformatics/btag044 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2026. Verfasst von Christoph Stelz und 2 weiteren Autor:innen. Beteiligte Einrichtung: Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Karlsruhe 76131, Germany. Hauptthemen laut MEDLINE: Phylogeny, Computational Biology. Die Arbeit nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Klaus Tschira Foundation, the European Union via European Research Council (ERC) Horizon 2020, EU ERA Chair.
Abstract (Originalsprache)
Motivation Phylogenetic trees describe the evolutionary history among biological species based on their genomic data. Maximum likelihood (ML) based phylogenetic inference tools search for the tree and evolutionary model that best explain the observed genomic data. Given the independence of likelihood score calculations between different genomic sites, parallel computation is commonly deployed. This is followed by a parallel summation over the per-site scores to obtain the overall likelihood score of the tree. However, basic arithmetic operations on IEEE 754 floating-point numbers, such as addition and multiplication, inherently introduce rounding errors. Consequently, the order by which floating-point operations are executed affects the exact resulting likelihood value since these operations are not associative. Moreover, parallel reduction algorithms in numerical codes re-associate operations as a function of the core count and cluster network topology, inducing different round-off errors. These low-level deviations can cause heuristic searches to diverge and induce high-level result discrepancies (e.g. yield topologically distinct phylogenies). This effect has also been observed in multiple scientific fields beyond phylogenetics. Results We observe that varying the degree of parallelism results in diverging phylogenetic tree searches (high-level results) for over 31% out of 10 179 empirical datasets. More importantly, 8% of these diverging datasets yield trees that are statistically significantly worse than the best-known ML tree for the dataset (AU-test, P < .05). To alleviate this, we develop a variant of the widely used phylogenetic inference tool RAxML-NG, which does yield bit-reproducible results under varying core-counts, with a slowdown of only 0%–12.7% (median 0.8%) on up to 768 cores. For this, we introduce the ReproRed reduction algorithm, which yields bit-identical results under varying core-counts, by maintaining a fixed operation order that is independent of the communication pattern. ReproRed is thus applicable to all associative reduction operations—in contrast to competitors, which are confined to summation. Our ReproRed reduction algorithm only exchanges the theoretical minimum number of messages, overlaps communication with computation, and utilizes fast base-cases for local reductions. ReproRed is able to all-reduce (via a subsequent broadcast) 4.1×106 operands across 48–768 cores in 19.7–48.61 μs, thereby exhibiting a slowdown of 13%–93% over a non-reproducible all-reduce algorithm. ReproRed outperforms the state-of-the-art reproducible all-reduction algorithm ReproBLAS (offers summation only) beyond 10 000 elements per core. In summary, we re-assess non-reproducibility in parallel phylogenetic inference, present the first bit-reproducible parallel phylogenetic inference tool, as well as introduce a general algorithm and open-source code for conducting reproducible associative parallel reduction operations. Availability and implementation ReproRed: https://doi.org/10.5281/zenodo.15004918 (LGPL)—Reproducible RAxML-NG version https://doi.org/10.5281/zenodo.15017407 (GPL)
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Karlsruhe 76131, Germany.
- Computational Molecular Evolution Group, Heidelberg Institute for Theoretical Studies, Heidelberg 69118, Germany.
- Biodiversity Computing Group, Institute of Computer Science, Foundation for Research and Technology - Hellas, Heraklion, Crete GR-730013, Greece.
ORCID-Profile: Lukas Hübner
Förderung
- Klaus Tschira Foundation
- the European Union via European Research Council (ERC) Horizon 2020
- EU ERA Chair
Zitieren
APA
Stelz, C., Hübner, L., & Stamatakis, A. (2026). Bit-reproducible parallel phylogenetic tree inference. Bioinformatics. https://doi.org/10.1093/bioinformatics/btag044
Vancouver
Stelz C, Hübner L, Stamatakis A. Bit-reproducible parallel phylogenetic tree inference. Bioinformatics. 2026. doi:10.1093/bioinformatics/btag044
BibTeX
@article{Stelz2026,
author = {Stelz, Christoph and Hübner, Lukas and Stamatakis, Alexandros},
title = {Bit-reproducible parallel phylogenetic tree inference},
journal = {Bioinformatics},
year = {2026},
doi = {10.1093/bioinformatics/btag044}
}
EUVIMED