Terrace Aware Data Structure for Phylogenomic Inference from Supermatrices

Abstract

In phylogenomics the analysis of concatenated gene alignments, the so-called supermatrix, is commonly accompanied by the assumption of partition models. Under such models each gene, or more generally partition, is allowed to evolve under its own evolutionary model. Although partition models provide a more comprehensive analysis of supermatrices, missing data may hamper the tree search algorithms due to the existence of phylogenetic (partial) terraces. Here, we introduce the phylogenetic terrace aware (PTA) data structure for the efficient analysis under partition models. In the presence of missing data PTA exploits (partial) terraces and induced partition trees to save computation time. We show that an implementation of PTA in IQ-TREE leads to a substantial speedup of up to 4.5 and 8 times compared with the standard IQ-TREE and RAxML implementations, respectively. PTA is generally applicable to all types of partition models and common topological rearrangements thus can be employed by all phylogenomic inference software.

Keywords: Maximum likelihood; partial terraces; partition models; phylogenetic terraces; phylogenomic inference.

Figure 1.

The species tree $T$ and the two NNI neighboring trees $T_{NN{I}_1}$ and $T_{NN{I}_2}$, obtained by NNIs around the central edge $e$. NNI, nearest neighbor interchange.

Figure 2.

(a) Three adjacent edges on species tree $T$ and (b) their corresponding edges on partition tree $T|Y_i$.

Figure 3.

CPU time comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the runtime ratios for 10 runs between a comparing program and the mean runtime of ${\text{IQ-TREE}}_{\text{PTA}}$. Boxes below the horizontal line indicate instances where corresponding program is slower than ${\text{IQ-TREE}}_{\text{PTA}}$. EUL, Edge-Unlinked and EL, Edge-Linked.

Figure 4.

Log-likelihood comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the log-likelihood differences for 10 runs between a comparing program and the mean log-likelihood of RAxML standard (panels a and b) or IQ-TREE standard (panel c). Boxes below the horizontal line indicate that the corresponding program has a smaller log-likelihood than RAxML mean log-likelihood (panels a and b) or IQ-TREE mean log-likelihood (panel c). RAxML and ${\text{RAxML}}_{\text{optU}}$ have identical log-likelihoods given the same starting tree. We therefore omit ${\text{RAxML}}_{\text{optU}}$ in the plot.

Figure A.1.

Cases that do not change the topology of the partition tree under the EL models. Each tree is a species tree: before NNI ($T$, first row) and after NNI ($T_{NNI}$, second and third rows). The edges and the species sets leading to them are the same as in Figure 1 (e.g., on $T$ the upper left edge is $e_1$ with the species set $A$ and so on). Here, $f_i(.)$ of gray colored edges is equal to $ϵ$ and gray triangles correspond to taxa sets, which are absent on the considered partition tree: $T|Y_i,T_{NN{I}_1}|Y_i$ or $T_{NN{I}_2}|Y_i$. The black colored parts correspond to the topologies of these induced partition trees. The arrows show edges that were swapped during NNI around the central branch $e$ on $T$.

Figure A.2.

General representations of (a) SPR and (b) TBR, where the triangles denote the subtrees below the corresponding edges. SPR, subtree pruning and regrafting, TBR, tree bisection and reconnection.