Bootstrapping Phylogenies Inferred from Rearrangement Data

Yu Lin, Vaibhav Rajan, Bernard M. E. Moret

TL;DR

This paper introduces a novel bootstrapping method for assessing the reliability of phylogenetic trees built from whole-genome rearrangement data. Their approach, analogous to the standard bootstrap for sequence data, provides a much-needed tool for confidently inferring evolutionary relationships when analyzing large-scale genomic structural changes.

What Problem Does This Paper Address?

Inferring evolutionary relationships (phylogenies) between species is a cornerstone of biology. Traditionally, this has been done by comparing DNA sequences. However, with the advent of whole-genome sequencing, researchers can now also infer phylogenies based on the evolution of genome structure, such as rearrangements (inversions, translocations), duplications, and losses of gene blocks. While standard methods like bootstrapping are well-established for sequence-based phylogenies, they rely on resampling homologous characters (like individual DNA bases). In rearrangement data, the entire genome or large segments are treated as single characters, making direct application of traditional bootstrapping impossible. Existing methods for assessing the reliability of rearrangement-based phylogenies have been shown to be less accurate than the standard bootstrap for sequence data. This paper aims to bridge this gap by developing a robust bootstrapping method specifically for rearrangement data.

Methods

The authors propose a new bootstrapping approach that mimics the principles of the classic bootstrap for sequence data but is adapted for whole-genome rearrangement information. Their method is based on a distance-based phylogenetic inference framework, where genomes are represented by a distance matrix reflecting their evolutionary divergence.

The core of their innovation lies in how they generate "replicate" datasets for bootstrapping. Instead of resampling sequence columns, they adapt techniques to resample "adjacencies" (the connections between gene blocks) within genomes. They introduce several methods, including:

  • BC* (Bootstrap for Rearrangement Data): This is their direct analog to the classical bootstrap (BC) for sequence data. It involves sampling adjacencies with replacement to create replicate datasets.
  • PJ* (Parsimony Jackknife for Rearrangement Data): This method is analogous to parsimony jackknifing for sequences. It samples adjacencies with replacement but discards duplicate adjacencies, effectively mimicking the "delete-d" jackknife.
  • dJK* (d%-Jackknife for Rearrangement Data): This method randomly omits a percentage (d%) of adjacencies to create replicate datasets.

They also explore other methods like Gaussian noise addition (BGN*) and perturbation-based approaches (BP*), drawing parallels to their sequence-based counterparts. The key is that these methods generate replicate distance matrices, from which phylogenetic trees are then inferred.

Datasets

The authors evaluate their methods using both simulated and real datasets:

  • Simulated Datasets: They generate synthetic whole-genome data by evolving artificial genomes on model phylogenetic trees. These simulations allow them to control parameters like the number of syntenic blocks (gene groups) and the tree diameter (representing evolutionary distance). They use two main simulation settings:
  • Sequence data: 100 sequences, 10,000 characters each, tree diameter 20,000.
  • Rearrangement data:
  • 1,000 markers, tree diameter 2,000.
  • 5,000 markers, tree diameter 15,000.
  • Real Dataset: They use a dataset of 10 vertebrate genomes from the Ensembl Mercator/Pecan alignments, containing 8,380 common markers. This dataset includes some draft genomes that are not fully assembled, which they note has minimal impact on their adjacency-based distance estimator.

Key Insights and Ideas

  • Direct Analogs Work Best: The most striking insight is that the methods most directly analogous to established sequence-based bootstrapping and jackknifing (BC* and PJ*) perform significantly better than other approaches for rearrangement data. This suggests that the fundamental principles of these resampling techniques are transferable.
  • Duplicate Samples Don't Hurt: Their findings indicate that parsimony jackknifing (PJ*), which avoids overcounting resampled adjacencies, performs at least as well as, and sometimes better than, the classical bootstrap (BC*). This implies that the "overcounting" in BC* might not be detrimental and that simpler sampling strategies can be effective.
  • High Specificity is Crucial: The authors emphasize that a good bootstrapping method should maintain high specificity (correctly identifying non-existent branches) even at high confidence levels. Their top methods excel in this regard, providing reliable support values.
  • The "Rare Genomic Change" Hypothesis: The paper implicitly supports the idea that large-scale genomic rearrangements are "rare genomic changes" that can be informative for deep phylogenetic relationships, as they are using these events to build robust phylogenies.

Key Results

  • Superior Performance: The proposed BC* and PJ* methods consistently outperform other tested methods (including BGN*, BP*, and JG*) in Receiver-Operator Characteristic (ROC) curve analyses, which measure sensitivity and specificity.
  • Comparable to Sequence Bootstrap: The performance of BC* and PJ* on rearrangement data is shown to be comparable to the classical bootstrap (BC) on sequence data, achieving high levels of accuracy.
  • Real-World Validation: On a dataset of vertebrate genomes, their BC* method correctly identified branches with historically uncertain phylogenetic placement as having the lowest bootstrap support, aligning with existing biological knowledge.
  • Efficiency: While not the primary focus, the paper notes that distance-based methods are generally more efficient than search-based methods like maximum parsimony or maximum likelihood.

Limitations and Future Work

  • Focus on Distance-Based Methods: The current work is primarily focused on distance-based phylogenetic inference. While the authors mention that extensions to search-based methods like Maximum Parsimony and Maximum Likelihood are possible, they require further testing.
  • Model Assumptions: The distance estimator used relies on certain assumptions about the genome evolution model (e.g., the double-cut-and-join model for rearrangements). The performance of the bootstrapping method might be affected if these assumptions are strongly violated.
  • Computational Cost: While distance-based methods are efficient, bootstrapping itself can be computationally intensive, especially for large datasets. The authors suggest that sampling half the characters (or adjacencies) might offer a computational shortcut without sacrificing accuracy.
  • Future Work: The authors suggest exploring the application of their bootstrapping approach to other inference methods and investigating more complex genome evolution models. They also hint at the potential for using their methods to assess the quality of phylogenetic reconstruction from gene order encodings.

Summary updated

Abstract

Background Large-scale sequencing of genomes has enabled the inference of phylogenies based on the evolution of genomic architecture, under such events as rearrangements, duplications, and losses. Many evolutionary models and associated algorithms have been designed over the last few years and have found use in comparative genomics and phylogenetic inference. However, the assessment of phylogenies built from such data has not been properly addressed to date. The standard method used in sequence-based phylogenetic inference is the bootstrap, but it relies on a large number of homologous characters that can be resampled; yet in the case of rearrangements, the entire genome is a single character. Alternatives such as the jackknife suffer from the same problem, while likelihood tests cannot be applied in the absence of well established probabilistic models. Results We present a new approach to the assessment of distance-based phylogenetic inference from whole-genome data; our approach combines features of the jackknife and the bootstrap and remains nonparametric. For each feature of our method, we give an equivalent feature in the sequence-based framework; we also present the results of extensive experimental testing, in both sequence-based and genome-based frameworks. Through the feature-by-feature comparison and the experimental results, we show that our bootstrapping approach is on par with the classic phylogenetic bootstrap used in sequence-based reconstruction, and we establish the clear superiority of the classic bootstrap for sequence data and of our corresponding new approach for rearrangement data over proposed variants. Finally, we test our approach on a small dataset of mammalian genomes, verifying that the support values match current thinking about the respective branches. Conclusions Our method is the first to provide a standard of assessment to match that of the classic phylogenetic bootstrap for aligned sequences. Its support values follow a similar scale and its receiver-operating characteristics are nearly identical, indicating that it provides similar levels of sensitivity and specificity. Thus our assessment method makes it possible to conduct phylogenetic analyses on whole genomes with the same degree of confidence as for analyses on aligned sequences. Extensions to search-based inference methods such as maximum parsimony and maximum likelihood are possible, but remain to be thoroughly tested.
BibTeX
@inproceedings{lin2011bootstrapping,
  author = {Yu Lin and Vaibhav Rajan and Bernard M. E. Moret},
  title = {{Bootstrapping Phylogenies Inferred from Rearrangement Data}},
  booktitle = {WABI},
  year = {2011},
  doi = {10.1007/978-3-642-23038-7\_16},
}

Loading related content...

Figure