Visualizing phylogenetic tree landscapes

Wen Huang, James C. Wilgenbusch, Wen Huang 0001, Kyle A. GallivanBMC Bioinformatics 2017 · DOI

TL;DR

This paper introduces and evaluates novel dimensionality reduction techniques for visualizing the complex relationships among thousands of competing phylogenetic trees derived from genomic data. By moving beyond simple consensus trees, the authors enable a more nuanced understanding of evolutionary processes and potential issues in phylogenetic inference, particularly highlighting the benefits of 3D visualizations.

What Problem Does This Paper Address?

Inferring evolutionary history from genomic data often results in a vast number of potential phylogenetic trees, especially when analyzing different gene partitions or codon positions within a single alignment. Traditional methods, like creating a single consensus tree, discard valuable information about the diversity of these trees and can mask underlying problems. This loss of information makes it difficult to diagnose issues with evolutionary models or tree reconstruction methods. The authors aim to address this by developing and testing methods to visualize the "phylogenetic tree landscape" – the relationships and similarities among these competing trees – in a low-dimensional space (2D or 3D). This visualization can help researchers gain a better perspective on evolutionary processes and identify potential methodological problems.

Methods

The core of this paper lies in applying and evaluating various Nonlinear Dimensionality Reduction (NLDR) techniques to visualize phylogenetic tree landscapes. The process involves:

  1. Tree Generation: Generating thousands of bootstrap trees for individual gene partitions from mitochondrial DNA (mtDNA) alignments.
  2. Distance Calculation: Computing pairwise Robinson-Foulds (RF) distances between all generated trees to quantify their topological differences. This creates a high-dimensional distance matrix.
  3. Dimensionality Reduction: Applying several NLDR methods, each consisting of a stress function (e.g., Kruskal-1, Normalized, NLM, CCA) and an optimization algorithm (e.g., Majorization, Gauss-Seidel, SGD, MCMC), to project the RF-distance matrix into 2D and 3D space.
  4. Evaluation: Assessing the performance of these NLDR methods using:
  5. Goodness-of-fit measures: 1-Nearest Neighbor (1NN), Continuity, and Trustworthiness to quantify how well the projected distances preserve the original RF-distances.
  6. Intrinsic dimensionality estimation: Determining the minimum number of dimensions required to represent the data without significant distortion.
  7. Visual comparison: Subjectively evaluating the clarity and interpretability of the resulting tree landscapes.

The authors specifically highlight Curvilinear Components Analysis (CCA) combined with Stochastic Gradient Descent (SGD) as a promising approach. They also introduce methods for comparing landscapes, such as using convex hulls to group related trees and Procrustes analysis to compare projections.

Datasets

The study utilizes three publicly available, aligned whole mitochondrial DNA (mtDNA) genome datasets:

  • Fishes: 90 sequences
  • Mammals: 89 sequences
  • Salamanders: 42 sequences

Additionally, a "Shuffled" test dataset was created by randomly selecting characters from the Salamander alignment to match the size of the original gene partitions. This shuffled dataset serves as a null model to distinguish patterns arising from biological signal versus those due to sampling error or partition size.

Key Insights and Ideas

  • Beyond Consensus: Simple consensus trees are insufficient for understanding the complexity of phylogenetic signal from large genomic datasets. Visualizing the "tree space" is crucial.
  • Dimensionality Matters: The choice of dimensionality reduction method significantly impacts how phylogenetic relationships are perceived. Not all NLDR methods are created equal for this task.
  • 3D is Better: For mtDNA data, intrinsic dimensionality estimates suggest that 3D projections are warranted to minimize information loss and better capture the relationships among trees compared to 2D.
  • CCA + SGD Shines: The combination of Curvilinear Components Analysis (CCA) as the stress function and Stochastic Gradient Descent (SGD) as the optimization algorithm consistently performed best across multiple goodness-of-fit metrics for visualizing these phylogenetic landscapes.
  • Partition Size and Tree Diversity: Shorter gene partitions tend to yield more bootstrap trees and exhibit greater variation (higher mean RF-distance), suggesting they may contain less phylogenetic signal or be more susceptible to noise.
  • Visualizing Outliers and Clusters: Techniques like convex hulls can effectively group related trees and help identify outliers, aiding in the interpretation of complex landscapes.

Key Results

  • CCA + SGD Outperforms: The CCA + SGD method provided the best representation of the original tree-to-tree RF-distances, as judged by 1NN, Continuity, and Trustworthiness measures.
  • 3D Improves Fit: For all three mtDNA alignments, 3D projections significantly increased the fit between projected distances and original RF-distances, facilitating interpretation.
  • Intrinsic Dimensionality: Estimates for the intrinsic dimensionality of the mtDNA tree-to-tree distance matrices ranged from 3 to 15 dimensions, supporting the use of 3D visualizations.
  • Convergence Speed: The SGD optimization algorithm generally converged faster than other tested algorithms, making it practical for large datasets.
  • Visual Clarity: Projections using CCA + SGD showed better continuity and discrimination among related groups of trees compared to other tested methods.

Limitations and Future Work

  • Subjectivity in Interpretation: While objective measures are used, the final interpretation of the visualized landscapes still involves a degree of subjective evaluation.
  • Statistical Rigor of Convex Hulls: The authors acknowledge that convex hulls are not strictly statistically interpretable, but they offer a practical visual aid.
  • Future Work: The authors suggest that this framework can be extended to evaluate other tree-to-tree distance metrics and to assess the performance of different tree reconstruction methods, nucleotide substitution models, and other phylogenetic analyses. Further development of parallel NLDR implementations is also mentioned as a path to improve computational efficiency.

Summary updated

BibTeX
@article{huang2017visualizing,
  author = {Wen Huang and James C. Wilgenbusch and Wen Huang and Kyle A. Gallivan},
  title = {{Visualizing phylogenetic tree landscapes}},
  journal = {BMC Bioinformatics},
  year = {2017},
  doi = {10.1186/s12859-017-1479-1},
}
Figure