Science

How to compare trees of clonal evolution?


Series on Tumor Evolution

While working on the BitPhylogeny paper, we stumbled on the problem of how to compare trees of clonal evolution.

Clonal evolution trees combine a clustering of molecular markers with tree inference. There are methods to compare clusterings and methods to compare trees, but how do you compare both at the same time?

Here is how we did it:

Idea 1: Consensus node-based shortest-path distance

The idea we published in the BitPhylogeny paper is to restrict the comparison to the nodes that appear in all trees under consideration. For example in the figure below, the node defined by marker ‘C’ only appears in two out of three trees and is thus not taken into account. On the consensus nodes, compare the pairwise shortest-path distances in each tree. Finally compare the distance matrices (or upper-/lower-triangular parts, because they are symmetric) and compute the distance by the sum of absolute values of differences between matrix entries. The following figure gives an overview:

ComparingClonalTrees-Idea1
Comparing Clonal Trees. The orange entries in the pairwise distance matrices indicate differences to the reference tree.

Idea 2: pairwise marker shortest-path distance

While the paper was in review, we came up with other ideas. Here is one that avoids using consensus nodes and uses pairs of markers instead:

  1. Start by only considering markers which are present in both trees you want to compare (if they both were computed from the same data, then this is generally all of them).
  2. For every pair of markers, compute their shortest-path distance in each tree: If two markers live in the same node, they have pairwise distance 0. If they live in separate nodes, count the number of edges (regardless of direction) between these nodes. This results in a symmetric marker-times-marker distance matrix for each tree.
  3. Finally, compare the marker-pair distance matrices by the sum of absolute values of all differences between matrix entries.

The following figure gives an overview of the procedure:

ComparingClonalTrees-Idea2
Comparing Clonal Trees. The orange entries in the pairwise distance matrices indicate differences to the reference tree.

This definition still has some shortcomings, which we plan to address in the future. In particular, it doesn’t take the length of edges (= evolutionary time) into account, which should be easily fixed by computing the pairwise distances on a weighted graph. Additionally, the distance is defined on the undirected graph, but it might be very important whether or not both trees represent the same order of events, so somehow the direction of edges needs to be included.

Distances are badly needed

I think a discussion on how to compare clonal evolution trees is important for everybody who works on how to infer them. How else will we ever be able to compare them with each other or to a `gold standard’ (if such a thing even exists for our problem).

The folks working on the DREAM challenge on tumor heterogeneity must face similar problems. I wonder what they have come up with …

Florian

References:
Yuan, K., Sakoparnig, T., Markowetz, F., & Beerenwinkel, N. (2015). BitPhylogeny: a probabilistic framework for reconstructing intra-tumor phylogenies Genome Biology, 16 (1) DOI: 10.1186/s13059-015-0592-6

Advertisements

2 thoughts on “How to compare trees of clonal evolution?

  1. Hi Florian,

    Nice blog!

    I enjoyed your last couple of entries about intra-tumor heterogeneity. I think that the
    Robinson-Foulds metric may do a good job for this, not sure if the clusters need special consideration. (Here’s a nice generalization: http://arxiv.org/pdf/1307.7824v1.pdf)

    Cheers,
    Mohammed El-Kebir

You gotta talk to me!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s