Skip to content

Review: Efficient Detection of Repeating Sites to Accelerate Phylogenetic Likelihood Calculations

Citation

  • Kobert, K., Stamatakis, A., & Flouri, T. (2017). Efficient detection of repeating sites to accelerate phylogenetic likelihood calculations. Systematic Biology, 66(2), 205–217.
  • DOI

Abstract

Site-repeats are groups of alignment sites that produce identical partial likelihood vectors at one or more internal nodes of the tree. Detecting and exploiting these repeats avoids redundant computation and can reduce runtime by up to an order of magnitude on typical biological datasets. An efficient detection algorithm and integration into RAxML are described.

The Felsenstein pruning algorithm computes a partial likelihood vector at each internal node for each alignment site (or site pattern). For two sites that have identical observed characters in all taxa, those vectors will be identical at every internal node from the leaves upward, until some difference in the tree makes them diverge. The key observation of Kobert et al. (2017) is that this redundancy extends beyond identical site patterns: even sites with different patterns can produce identical partial likelihood vectors at internal nodes further from the leaves, because the pruning recursion may "converge" to the same state after multiple levels of averaging.

The algorithm detects these site-repeats (groups of sites producing identical partial likelihood vectors at a given node) during a preprocessing pass over the alignment and tree. Sites in the same repeat group share their partial likelihood storage and computation at that node, reducing both memory and arithmetic operations. On empirical datasets the speedup can be 5-10x compared to per-pattern compression alone.

Hifuku's alignment compressor uses a site-pattern compression step (grouping identical columns) before passing the alignment to the GPU kernel. The site-repeat detection concept from this paper is a logical extension that is not yet implemented but is noted as a potential future optimization in the likelihood kernel design. The basic pattern compression achieves the most important gains (2-5x) for typical alignment sizes without the algorithmic complexity of full site-repeat detection.

Key result

Theorem 1 (Kobert et al.). Two alignment sites produce identical partial likelihood vectors at a node \( v \) if and only if they produce identical partial likelihood vectors at every descendant of \( v \) that has the same taxon subset. This locality property allows efficient bottom-up detection during a single postorder tree traversal.