Fast coalescent-based computation of local branch support from quartet frequencies

Introduction

• Support quantification remains under-addressed, while concatenation can assign high support to incorrect branches and underestimated support for true branches motivates better methods.The introduction identifies these limitations as reasons to improve support estimation for species trees.Source: Introduction · p. 2
• The proposed quartet-based support values are more precise and powerful than MLBS and much faster to compute.The authors report that very few highly supported branches are incorrect, most correct branches have high support with sufficient genes, and reliability persists when model assumptions are violated.Source: Introduction · pp. 2–3
• For each internal species-tree branch, the method assumes its four sides are correct and uses gene-tree quartet frequencies to calculate local posterior probabilities for three alternative topologies.It introduces an algorithm to compute quartet support for each alternative in Θ(nl) time, where l is the number of species and n is the number of genes.Source: Introduction · p. 3
• Quartet frequencies can also estimate internal branch lengths in coalescent units.The method uses quartet support for alternative topologies to derive the posterior probability that an alternative is the correct species topology.Source: Introduction · p. 3

New Approaches

• A branch’s quadripartition defines four clusters, and its surrounding quartets are enumerated by selecting one leaf from each cluster.The paper defines these clusters as the four groups created by an internal branch.Source: New Approaches · p. 4
• For an internal branch represented by quadripartition Q, the method targets both the probability that Q is in the species tree and its coalescent-unit length, assuming Q’s four clusters are correct.This locality assumption makes computation tractable for large datasets.Source: New Approaches · p. 4
• The model assumes tree-like evolution, MSC-generated gene trees, and an unbiased sample of true gene trees, whereas real-data analyses use estimated trees and may violate the sampling or MSC assumptions.The method is also tested using estimated gene trees and data that violate locality.Source: New Approaches · pp. 4–5

Calculation of local posterior probability

• Quartets around a branch are dependent even under the locality assumption, so treating them as independent m×n observations would inflate posterior confidence.The number of quartets m is at least l−3.Source: Calculation of local posterior… · p. 5
• To avoid that inflation, the method models a shared latent vector of true quartet frequencies from n trials and treats each quartet’s frequencies as a noisy estimate.A suitable noise model was unavailable, so the method does not marginalize over the latent vector.Source: Calculation of local posterior… · p. 6
• The expected latent quartet frequencies are estimated by averaging, and the resulting vector z can be computed in Θ(nl) time.The paper introduces this efficient algorithm for computing z.Source: Calculation of local posterior… · p. 6
• Under the MSC and a Yule-generated species-tree prior, Theorem 1 computes the local posterior probability for topology Q from its average quartet frequencies, assuming Q’s four clusters are present in the species tree.The posterior is conditional on the four clusters around Q being correct.Source: Calculation of local posterior… · p. 7
• With alternative topologies equally frequent, a branch present in 40% of gene trees has 66.1% pp with 50 genes, 93.0% with 200, and 99.7% with 500.Thus, a branch with 60% discordance can still be resolved with high confidence given enough genes.Source: Calculation of local posterior… · p. 7, Figure 2 · p. 8
• 1.90% pp is reported for the branch with 40% frequency (Fig. 2).Source: Calculation of local posterior… · p. 8

• For a correct branch, the section considers its length in coalescent units given the true parameter θ.Source: Calculation of branch length · p. 8
• Theorem 2 assumes the conditions of Theorem 1 and that the branch represented by Q is in the species tree.Source: Calculation of branch length · p. 8

• Explicitly enumerating quartets can be slow because as many as Θ(l^4) quartets may surround a single branch.Source: Calculation of quartet support · p. 8
• The algorithm counts matching quartet topologies by considering 12 cluster matchings and summing products of mapped cluster-intersection sizes.Source: Calculation of quartet support · p. 9

Other considerations

• The methods were implemented in ASTRAL, using Colt for numerical computations.Source: Other considerations · p. 9
• For missing data, the method uses the average number of observed quartets for m and counts genes containing at least one quartet for each branch’s n; unresolved trees are scored across tripartitions around each polytomy.The unresolved-tree procedure follows ASTRAL-II and considers all tripartitions around a polytomy of degree d.Source: Other considerations · p. 9

Datasets

• The study uses simulated and biological datasets; the simulations include 200-taxon A-200 data from Mirarab and Warnow (2015) and 48-taxon avian data from Mirarab et al. (2014c).Source: Datasets · p. 9, Simulated data · p. 9

Simulated data

• A-200 comprises 201 taxa (200 ingroups plus an outgroup) and three ILS levels, controlled by tree lengths of 500k, 2M, and 10M generations; species trees use all 1000 genes per replicate.The dataset tests accuracy under heterogeneous conditions with many species.Source: Simulated data · p. 10
• Avian simulations use 20 replicates of 1000 genes across four conditions with 250, 500, 1000, or 1500 sites per gene; average ASTRAL species-tree error ranges from 5% to 15%.The dataset has 48 taxa and models an avian-like species tree; its local posterior support is compared with MLBS.Source: Simulated data · pp. 10–11

Biological dataset:

• The biological analyses reanalyze four published datasets: plant (103 taxa, 424 genes), angiosperm (46 taxa, 310 genes), binned avian supergene trees (48 taxa, 2022 trees), and avian (201 taxa, 256 genes).Source: Biological dataset · p. 11

Evaluation procedure:

• For each scored species tree, the evaluation uses true or estimated gene trees and scores both each internal branch and its two alternative topologies.True species and gene trees meet the model assumptions; estimated gene trees violate the assumption that inputs follow MSC properties, while estimated species trees may violate locality because the four surrounding clusters can be incorrect.Source: Evaluation procedure · p. 11

Posterior:

• Posterior support is evaluated across thresholds using precision, recall, false positive rate, and ROC curves.Precision is the share of branches supported at least at the threshold that are correct; recall is the share of true branches meeting it, and FPR is the share of false branches meeting it.Source: Posterior · p. 12
• Because MLBS and posterior values are not directly comparable, their comparison uses ROC curves and was feasible only on the avian dataset.Gene bootstrapping was computationally infeasible on A-200, which had 300 replicates of 1,000 genes and 201 taxa.Source: Posterior · p. 12

Branch length:

• Branch-length accuracy is measured on the true species-tree topology using log error and root mean squared error; on avian datasets, ASTRAL is compared with MP-EST.Only correct branches can be used for branch-length accuracy.Source: Branch length · p. 12

A-200 dataset

• With true trees, precision is 100% at local pp ≥0.99 and at least 99.8% at 0.95; at 0.95, recall ranges from 98.7% to 55.0%.The recall endpoints correspond to low ILS with 1000 gene trees and high ILS with 50 gene trees, respectively; increasing ILS and reducing gene count lower recall while maintaining high precision.Source: A-200 dataset · pp. 12–13
• With estimated gene trees, precision falls from 100% to between 98.4% and 99.8%, while recall is reduced by as much as 10%.Gene-tree estimation error has a small impact on precision but a substantial impact on recall.Source: A-200 dataset · p. 13
• Lowering the threshold from 0.99 to 0.95 raises recall from 39% to 48% for high ILS with 50 genes, with precision reductions of at most 0.3%.The paper reports meaningful recall gains without substantially sacrificing precision.Source: A-200 dataset · pp. 13–14
• Compared with true species trees, ASTRAL trees change precision by at most 0.6% and raise recall by up to 2.9% with estimated gene trees; with true gene trees, precision falls by up to 1.4% and recall rises by up to 4.7%.The authors characterize these moderate locality-assumption violations as having minimal impact.Source: A-200 dataset · p. 14

Branch Length

• With 1000 true gene trees, branch-length logarithmic error ranges from 0.03 to 0.10; with fewer true gene trees it rises but never exceeds 0.25.Error is largely unbiased, except perhaps for very short or long branches that are difficult to estimate with limited genes.Source: Branch Length · pp. 14–15
• Estimated gene trees dramatically increase branch-length error: with 1000 estimated trees and low ILS, log error is 0.42, and error is biased toward underestimation, especially at low ILS.The reported log error corresponds to estimated branches that are on average 2.6 times too short or long.Source: Branch Length · p. 15

Avian

• The avian analysis compares local posterior probabilities with site-only MLBS support using estimated gene trees and ASTRAL species trees, while reducing sites per gene from 1500 bp.The passage describes the comparison and manipulation but supplies no avian results.Source: Avian · p. 15

Posterior and MLBS

• For a desired precision level, better recall can be obtained using local posterior support; the passage also reports 70% of correct branches.Source: Posterior and MLBS · p. 16, Figure 5 · p. 16

Branch Length

• On the avian dataset, branch-length log error rose from 0.06 with true gene trees to 0.59 with 250bp genes, with estimates increasingly biased downward.The 0.06 error corresponds to branches about 14% shorter or longer than truth; the 0.59 error corresponds to branches on average 3.9 times too short or long.Source: Branch Length · pp. 16–17
• ASTRAL and MP-EST had similar branch-length log error with accurate gene trees, but ASTRAL performed better as gene-tree error increased.By RMSE, which emphasizes long branches, the methods were comparable, with MP-EST slightly better given accurate gene trees.Source: Table 4 · p. 16, Branch Length · p. 17

Biological datasets

• For the angiosperm dataset, ASTRAL recovered Amborella as sister to the remaining angiosperms with 75% bootstrap and 100% posterior support.The branch length was estimated at 0.160 coalescent units, close to the 1KP estimate of 0.156.Source: Biological datasets · p. 19
• The avian genome analysis supported very short branches at the Neoaves base, but gene-tree error made exact lengths difficult to quantify.The 1KP branch lengths were also cautioned to be lower bounds because gene-tree error can cause underestimation.Source: Biological datasets · pp. 19–20
• In the high-sampling avian dataset, the sister to parrots and passerines had 30% MLBS, 83% local posterior, and 0% collapsed posterior, amid little resolution of early Neoaves.Many relationships remained poorly supported overall, and the passage notes that this dataset provides little early Neoaves resolution because of insufficient gene count.Source: Biological datasets · p. 20
• As in avian genomic data, high ILS is reflected in a wall of short branches around the assumed rapid radiation of Neoaves.Source: Biological datasets · p. 20

• Computing posteriors took 10 seconds for 200 taxa and 1000 genes, and about three minutes for 1000 taxa and 1000 genes on a laptop.The method avoids extensive MCMC sampling or bootstrapping.Source: Discussions · pp. 20–21
• The speed depends on assuming true MSC-generated gene trees and locality, although real data can violate both assumptions.Simulations included gene-tree estimation error with average RF distance from 25% to 67%, as well as species-tree error.Source: Discussions · p. 21
• High support produced very few false positives even with high gene-tree estimation error; that error reduced recall but retained very high precision.The authors argue that underestimating support is less serious than assigning high support to false branches.Source: Discussions · p. 21
• Local posterior probabilities were less conservative than MLBS, and recall was generally high except with very few genes for a given amount of ILS.The discussion describes MLBS as the only viable alternative for large datasets.Source: Discussions · p. 21
• The commonly used 0.95 threshold gave very high precision with moderately high recall, while thresholds of 0.9 or 0.7 also gave high precision.The appropriate threshold depends on the desired false-positive rate and the amount of gene-tree error.Source: Discussions · p. 21

Gene tree estimation error

• With estimated gene trees, support at a given threshold was more precise under high than low ILS, potentially because estimation error adds more discordance under low ILS.This pattern was not observed with true gene trees.Source: Gene tree estimation error · p. 21
• Branch-length accuracy degraded more from true to estimated gene trees under low than high ILS, and estimated lengths can be underestimated under gene-tree error.The authors advise interpreting summary-method branch lengths with care when gene-tree estimation error is present.Source: Gene tree estimation error · pp. 21, 23
• Bootstrap gene trees had higher discordance than true or ML gene trees, and the authors propose this biased discordance explains MLBS underperformance.Site-resampled bootstrap gene trees can have increased discordance with the species tree and among themselves, especially when genes have limited phylogenetic signal.Source: Gene tree estimation error · pp. 21–22
• Despite not directly accounting for gene-tree uncertainty, the method remained precise with high estimation error and uses ML gene trees, which are better than bootstrapped trees.ML gene trees still tend toward increased discordance and reduced branch lengths.Source: Gene tree estimation error · p. 22
• Collapsing poorly resolved gene-tree branches can help account for estimation error, but aggressive filtering may introduce bias and its effects need further study.The authors describe collapsing branches with support below 33% as treating them as randomly resolved.Source: Gene tree estimation error · pp. 22–23

High support despite high discordance

• A branch found in only 40% of gene trees can still be resolved with high confidence when enough genes are available, around 500 in the example.This illustrates that high discordance does not preclude confidence in a correctly inferred relationship.Source: High support despite high discordance · p. 23
• In the 1KP tree, branches appearing in 49% and 50% of collapsed gene-tree quartets both had posterior probabilities of 1.0.These were the Zygnematales sister to land plants and Bryophytes monophyletic branches, respectively.Source: High support despite high discordance · p. 23

Limitations and future work

• Gene-tree uncertainty could be incorporated by weighting quartets with SH-like or bootstrap support, or concordance measures (Ané et al., 2007).The authors also identify comparison with Bayesian co-estimation methods on small datasets as future work.Source: Limitations and future work · p. 23
• The study did not vary prior parameter λ or explore alternative priors such as Dirichlet distributions or birth-death processes.These prior choices are left for future work.Source: Limitations and future work · p. 23
• Simulations and inference used GTR+Γ, but compositional bias in real data can bias gene-tree estimates.The experiments therefore did not cover all model violations relevant to real data.Source: Limitations and future work · pp. 23–24
• Simulated discordance came only from ILS and estimation error, so future work should test reliability under other biological sources, including undetected paralogy and horizontal gene transfer.Source: Limitations and future work · p. 24

MBE Advance Access published April 15, 2016

• The supplementary material identifies Erfan Sayyari and Siavash Mirarab as its authors and presents additional figures, tables, and methods for their paper.Source: MBE Advance Access published April 15,… · p. 29, Table S1 · p. 30

1 Supplementary Figures and Tables

• Supplementary figures document A-200 dataset discordance and gene-tree error, and evaluate local posterior accuracy with true species trees, NJST trees, and concatenation.A-200 simulations vary ILS; the caption notes that higher ILS datasets also tend to have higher gene-tree error.Source: Figure S1 · p. 31, Figure S2 · p. 32, Figure S3 · p. 33
• Avian supplementary figures compare precision and recall of local posterior probability with MLBS across site-count conditions, and include branch-length accuracy plots.The branch-length plots cover A-200 low- and high-ILS datasets and the avian dataset; the avian summary also plots MPEST and ASTRAL estimates against true lengths.Source: Figure S5 · p. 35, Figure S6 · p. 36, Figure S7 · p. 37

2 Supplementary methods

• The supplementary frequency algorithm takes gene trees and a quadripartition of species clusters as input and returns frequencies for the three quartet topologies around a branch.The pseudocode represents clusters as species-indexed bitsets and calculates the frequencies from gene-tree counts.Source: §1 · p. 43, Figure S14

3.1 Proof of Lemma 1

• Lemma 1 derives the posterior probability that θ1 > 1/3 from quartet-count frequencies using Bayes’ rule and equal lower multinomial parameters.The proof treats the average quartet counts as multinomial observations conditional on θ1.Source: §3.1 · p. 45

3.2 Proof of Theorem 1

• Theorem 1 gives local posterior support for a quartet topology from average quartet frequencies when n gene trees follow the MSC and the species tree follows a Yule process.The proof uses the result that an unrooted quartet lacks anomaly zones, so Q is in the species tree exactly when θ1 > 1/3.Source: §3.2 · pp. 45–46

3.3 Proof of Theorem 2

• For an in-tree branch, the ML length estimate is −ln[3/2(1−z1/(n+2λ))] when 3z1 ≥ n; otherwise, both ML and MAP estimates are zero.The MAP estimate assumes branch lengths are exponentially distributed with rate 2λ under the Yule process.Source: §3.3 · pp. 47–48

3.4 Proof of Lemma 2

• Under the Yule process, branch lengths are exponentially distributed with rate 2λ, while an uninformative prior assigns equal probability to each topology being dominant.The proof then transforms the branch-length distribution to the corresponding quartet parameter.Source: §3.4 · p. 48

4.1 ASTRAL

• ASTRAL 4.9.1 scored trees and estimated branch posterior probabilities, 4.9.8 computed MAP branch lengths, and 4.10.0 was used for scoring and computing branch lengths and local posterior probabilities.The commands used options -t 4 with 4.9.1, -t 2 with 4.9.8, and -t 3 with 4.10.0.Source: §4.1 · pp. 48–49

4.2 MP-EST

• MP-EST 1.5 estimated branch lengths on a fixed topology, with a custom script running two seeds and selecting the tree with the highest likelihood.The script is available in the authors’ global repository.Source: §4.2 · p. 49