PaperlayerView exact revision on arXiv

Source-linked AI summary

Phylogenetic quantification of intra-tumour heterogeneity

Roland F Schwarz, Anne Trinh, Botond Sipos, James D Brenton, Nick Goldman, Florian Markowetz

arXiv:1306.1685v1q-bio.QMq-bio.PE

TL;DR

MEDICC addresses the need for algorithms targeting questions raised by multiple-sampling studies by reconstructing cancer evolutionary histories and quantifying heterogeneity. The authors report success in simulations and utility in a clinical example, with reconstruction accuracy attributed mainly to two factors.

  • Problem

    Few algorithms have been developed to target the specific questions raised by multiple-sampling studies, and ambiguity can prevent tracing individual events.

  • Method

    MEDICC reconstructs cancer evolutionary histories and proposes unbiased quantification of heterogeneity while modelling genomic events that change copy number and incorporating biological constraints.

  • Results

    The authors report success in simulations and utility in a clinical example, attributing increased reconstruction accuracy mainly to two factors.

  • Takeaways & Limitations

    MEDICC is presented as a contribution toward better reconstruction of cancer evolutionary histories and unbiased quantification of heterogeneity.

  • Takeaways & Limitations

    Future work will address reductions in algorithmic complexity and integration of SNP data.

Abstract

from arXiv · show

Background: Intra-tumour heterogeneity (ITH) is the result of ongoing evolutionary change within each cancer. The expansion of genetically distinct sub-clonal populations may explain the emergence of drug resistance and if so would have prognostic and predictive utility. However, methods for objectively quantifying ITH have been missing and are particularly difficult to establish in cancers where predominant copy number variation prevents accurate phylogenetic reconstruction owing to horizontal dependencies caused by long and cascading genomic rearrangements. Results: To address these challenges we present MEDICC, a method for phylogenetic reconstruction and ITH quantification based on a Minimum Event Distance for Intra-tumour Copynumber Comparisons. Using a transducer-based pairwise comparison function we determine optimal phasing of major and minor alleles, as well as evolutionary distances between samples, and are able to reconstruct ancestral genomes. Rigorous simulations and an extensive clinical study show the power of our method, which outperforms state-of-the-art competitors in reconstruction accuracy and additionally allows unbiased numerical quantification of ITH. Conclusions: Accurate quantification and evolutionary inference are essential to understand the functional consequences of ITH. The MEDICC algorithms are independent of the experimental techniques used and are applicable to both next-generation sequencing and array CGH data.

Background

MEDICC addresses the difficulty of reconstructing cancer evolution and quantifying intra-tumour heterogeneity from copy-number profiles, especially when rearrangements create phasing and locus-dependency challenges.

  • Background: Copy-number-driven heterogeneity complicates phylogenetic inference because parental-allele phasing, dependencies between adjacent loci, and suitable reference databases are often unavailable.These issues are particularly relevant in cancers where rearrangements and endoreduplications produce aberrant copy-number profiles.
  • Background: Existing heterogeneity quantification and tree inference have relied on ad-hoc thresholds or subjective procedures.Related approaches also have practical limitations, including dependence on detailed rearrangement annotation or failure to infer global within-patient evolutionary trees.
  • Background: The study aims to establish numerical, patient-level quantification of heterogeneity from copy-number profiles routinely acquired from clinical samples.The motivation is linked to understanding heterogeneity and its possible prognostic, predictive, and drug-resistance relevance.
  • Background: MEDICC infers phylogenetic trees from unsigned integer copy-number profiles while estimating optimal allele phasing and using complete genomic profiles rather than only breakpoints.The method addresses horizontal dependencies, overlapping events, ancestral-genome reconstruction, and summary statistics for evolutionary histories and heterogeneity.
  • Background: The authors developed MEDICC and applied it to 170 copy-number profiles from patients undergoing neoadjuvant chemotherapy for high-grade serous ovarian cancer.The paper also demonstrates the method on a real-world endometrioid cancer case and compares it with competing methods using simulations.

Results and Discussion

MEDICC represents copy-number profiles while retaining allele information and models rearrangement dependencies through weighted finite-state methods. Its reconstruction pipeline assigns alleles, estimates minimum-event distances, infers trees, and reconstructs ancestral genomes.

  • Results and Discussion: Copy-number profiles quantify DNA content relative to diploid normal in genomic windows, but the two parental alleles are usually not phased.The larger and smaller copy numbers are labeled major and minor, without establishing which values belong together on one allele.
  • Results and Discussion: Copy-number events overlap across adjacent genomic regions, creating horizontal dependencies that affect evolutionary-divergence estimation.This differs from models that treat sequence sites as independent and identically distributed.
  • Results and Discussion: MEDICC uses three minimum-evolution steps: allele-specific assignment, evolutionary-distance estimation with tree inference, and ancestral-genome reconstruction.The objective is to find a tree topology and ancestral states minimizing total genomic-event length.
  • Results and Discussion: The method models genomic profiles as finite-state automata and evolutionary transformations as weighted finite-state transducers.The transducer framework represents events transforming one copy-number sequence into another and supports minimum-event scoring.
  • Results and Discussion: MEDICC uses the tropical semiring to compute minimum-event distances while allowing the framework to transition to probabilistic calculations by changing semirings.The profile alphabet includes integer copy numbers up to K and a special character X; the default diploid maximum total copy number is 2K = 8.

Constructing the minimum-event distance for CN profiles

MEDICC constructs a symmetric minimum-event distance by composing event transducers and evaluating transformations through a closest possible last common ancestor. This distance supports tree inference under the modeled biological constraints.

  • Constructing the minimum-event distance for CN profiles: The one-step transducer models single amplification and deletion events, and repeated composition permits transformations requiring multiple events.Composition chains intermediate copy-number profiles and minimizes the accumulated event score.
  • Constructing the minimum-event distance for CN profiles: The tree transducer encodes biological constraints, including the prohibition of amplification from zero, but may not provide a valid path for every profile pair.Its directional structure reflects the modeled event rules.
  • Constructing the minimum-event distance for CN profiles: The final distance transducer combines the tree transducer with its inverse to measure events from one profile to a last common ancestor and back to another profile.This constructs the minimum evolutionary distance through the closest possible ancestor.
  • Constructing the minimum-event distance for CN profiles: The resulting minimum-event distance is symmetric and guaranteed to produce a valid distance for any pair of sequences.It counts the minimum number of modeled genomic events connecting the profiles through their last common ancestor.
  • Constructing the minimum-event distance for CN profiles: MEDICC infers a tree and ancestral states by minimizing total tree length, defined as the total number of genomic events along the tree.The computed distances also place samples in a high-dimensional evolutionary space suitable for exploratory analyses.

Step 1: Evolutionary phasing of major and minor CNs

MEDICC resolves major/minor copy-number phasing using evolutionary comparisons, then uses phased profiles for distance-based tree inference and ancestral genome reconstruction.

  • MEDICC chooses pairwise phasing scenarios that minimize evolutionary distances between diploid profiles while respecting separate allele histories.
  • A context-free grammar represents alternative allele-phasing choices, with each parse tree corresponding to one of the 2^L possible scenarios.
  • For joint optimization, MEDICC iteratively finds a geometric-median profile and phases each sample against that centre using shortest paths.
  • The joint phasing heuristic is not guaranteed to be globally optimal, although it has performed well in practice.
  • After phasing, MEDICC sums allele-specific distances, constructs trees with Fitch–Margoliash, and supports clock testing through MEDICCquant.
  • MEDICC reconstructs ancestral genomes by traversing a fixed tree and selecting parsimonious internal profiles, enabling investigation of cancer precursors and branch events.

MEDICC improves phylogenetic reconstruction accuracy

Simulations evaluated tree reconstruction from copy-number profiles across genomic rearrangement regimes. MEDICC improved reconstruction accuracy over Euclidean-distance BioNJ and TuMult, particularly when phylogenetic information was limited.

  • The simulations generated copy-number profiles from deletion, duplication, inverted duplication, inversion, and translocation events.
  • Accuracy was measured by quartet distance between true and reconstructed trees because branch lengths were not comparable across methods.
  • MEDICC outperformed BioNJ on Euclidean distances and TuMult in simulated copy-number tree reconstruction.
  • Reconstruction accuracies generally increased with increasing evolutionary rates, while MEDICC retained a significant advantage when phylogenetic information was limited.
  • The authors attribute MEDICC’s advantage to parental-allele phasing and efficient handling of horizontal dependencies from overlapping genomic events.

Temporal heterogeneity

MEDICCquant represents genomic profiles in a mutational landscape and quantifies temporal heterogeneity as the distance between average profiles from different time points.

  • Temporal heterogeneity is defined as the evolutionary distance between average genomic profiles from two time points.
  • Distances between time-point groups are computed between their centres of mass, allowing robust summaries that can ignore extreme points.
  • The same framework can compare arbitrary sample partitions, including samples from different organs or treatment time points.
  • Besag’s L and the clonal expansion index assess spatial clustering relative to complete spatial randomness; CE < 1 suggests CSR, whereas CE > 1 indicates local clustering.
  • MEDICCquant implements tests for tree-likeness and molecular-clock behaviour to guide evolutionary interpretation.

Progression and heterogeneity in a case of metastatic endometrioid adenocarcinoma

In a metastatic endometrioid ovarian carcinoma case, MEDICC revealed non-clock-like evolution, substantial clonal expansion, spatial and temporal heterogeneity, and ancestral copy-number events.

  • The molecular-clock test indicated strong non-clock-like behaviour (p = 2.89x10^-14).
  • The clonal expansion index was CE = 1.24, indicating strong spatial clustering of samples on the mutational landscape.
  • MEDICC counted a median of 204 genomic events relative to diploid and 146 events between pairwise sample comparisons.
  • Tree reconstruction supported omental and BL/VV subclades, suggesting strong spatial heterogeneity.
  • The temporal heterogeneity index was 3.78, reflecting large evolutionary distances between pre- and post-chemotherapy samples.
  • Spatial and temporal heterogeneity could not be distinguished cleanly because anatomical sampling locations coincided with treatment time points.
  • Ancestral reconstructions identified chromosome 17q loss of heterozygosity and amplifications on chromosomes 6, 8, 11, and 14 among clonal-expansion contributors.

Conclusions

MEDICC was developed to improve cancer evolutionary-history reconstruction and provide unbiased quantification of tumour heterogeneity and clonal expansion. Simulations and clinical analysis supported improved reconstruction accuracy, while the method accommodates multiple data platforms.

  • MEDICC targets the limited availability of algorithms for reconstructing cancer evolution in multiple-sampling studies.
  • MEDICC reconstructs within-patient evolutionary histories and quantifies heterogeneity and clonal expansion without relying on a specific data-collection platform.The method can use SNP-array, sequencing-based, or other absolute-copy-number data.
  • Simulations demonstrated the method’s success, and a clinical example illustrated its utility for studying clonal expansion and heterogeneity.Further clinical examples were reported as elaborating the connection between clonal expansion, heterogeneity, and patient outcome.
  • MEDICC showed higher reconstruction accuracy than naive approaches and TuMult in the reported comparisons.The authors attribute the improvement mainly to two factors, while noting TuMult was designed for fewer leaf nodes.
  • MEDICC phases parental alleles using a minimum-evolution criterion and models genomic copy-number events with biological constraints including loss of heterozygosity.
  • Future work includes reducing algorithmic complexity and integrating SNP data into the reconstruction process.The authors describe a future extension toward a full probabilistic model once sufficient curated training data are available.

Methods

The study used simulated genome evolution and clinical SNP-array data to evaluate MEDICC and related reconstruction methods. Simulations represented copy-number-changing genomic events across evolving genomes, and analyses were implemented with dedicated software packages.

  • Clinical SNP-array data for the OV03/04 example were accessed through NCBI Gene Expression Omnibus accession GSE40546.
  • Genome-evolution simulations used APE, custom SimCopy code, and modified PhyloSim processes to model genomic events on abstract regions.Simulated events included deletion, duplication, inversion, inverted duplication, and translocation.
  • SimCopy represented genomic regions as signed integer sequences and reported copy-number profiles for leaf and internal nodes after evolution was simulated.Event lengths were modeled with truncated Geometric+1 distributions.
  • The simulations used 15 leaf nodes, a root size of 100 segments, and an average event length of 12 segments.
  • Event-rate experiments covered rates from 0.02 to 0.2, with event-specific modifiers for deletions, duplications, inverted duplications, inversions, and translocations.The listed modifiers were 0.3, 1.0, 0.1, 0.2, and 0.2, respectively.
  • Simulated copy-number distributions were selected to resemble those observed in the clinical study.
  • FST and FSA used OpenFST, MEDICC was written in Python with time-critical parts in C, and tree reconstruction used Phylip for Fitch-Margoliash implementations.
  • Quantitative analyses used R, MEDICCquant, spatstat, and kernlab, while MEDICC was released for Windows and UNIX-based systems.

Authors contributions

The project divided responsibilities across algorithm development, simulations, clinical study design, and supervision of phylogenetic, machine-learning, and manuscript work.

  • RFS designed and implemented MEDICC and wrote the manuscript.
  • AT implemented comparisons with TuMult, while BS designed and implemented genome simulations.
  • JDB designed the clinical study and supervised clinical-data analysis.
  • NG and FM supervised the phylogenetic and machine-learning aspects of the project.
  • NG, FM, and JDB edited the manuscript, and all authors approved the final version.

Figures

The figures present MEDICC as a three-stage framework for reconstructing evolutionary copy-number trees, computing minimum-event distances, resolving allele phasing, and quantifying intra-tumour heterogeneity.

  • Figure 1: MEDICC phases major and minor alleles, reconstructs tree topology from pairwise genome distances, and infers ancestral genomes to determine event-based branch lengths.The three reconstruction stages are shown in sequence.
  • Figure 2: A transducer architecture models overlapping rearrangements and composes one-step edit operations to obtain a symmetric minimum-event distance.The asymmetric evolutionary transducer is composed with its inverse to calculate the symmetric distance.
  • Figure 3: Context-free grammars represent possible parental-allele phasing choices, with each parse tree corresponding to one possible phasing.The selected consecutive segments minimize pairwise distance between profiles.
  • Figure 4: Simulations show improved reconstruction accuracy over BioNJ clustering on Euclidean copy-number distances and TuMult, while clonal expansion indices distinguish induced long branches from neutral evolution.The figure compares MEDICC with both a naive method and a competing algorithm.
  • Figure 5: MEDICC quantifies ITH by locating genomes on a mutational landscape and estimating subgroup separation using robust centres of mass before and after chemotherapy.The robust centres omit each subgroup’s single most distant point, reducing sensitivity to outliers.
  • Figure 6: In an endometrioid cancer case, MEDICC reconstructs ancestral copy-number profiles and identifies four clonal expansions across three Omentum groups and the Bl/VV group.The figure combines an evolutionary tree, kPCA ordination, and Circos plots of phased parental alleles.
Loading 1306.1685v1…