This is an archived static version of the original phylobabble.org discussion site.

Tree comparison using Laplacian spectra

max

Dear babblers,

I stumbled across http://biorxiv.org/content/early/2015/09/09/026476 today. This paper attempts yet another method of summarising trees, this time using what the authors call “Spectral Density Profiles”, which are just [if I understood correctly] a transformation of the eigen values of the patristic distance matrix.

This seems to me like a principled way of introducing branch lengths in, for example, the [sprspace] (https://github.com/cwhidden/sprspace) framework: one could store the set of spectra for a particular topology in a hashmap and then use those to inform clustering on the SPR graph. The communities in the graph would then be not only a result of their proximity in the topological space, but also on “branch length space”. Their methods are even implemented as an R package, RPANDA.

I’m looking specially at you, @ematsen, @cwhidden, @mathmomike and @mtholder.

Cheers,

Luiz

ematsen

That’s an interesting paper, Max, and thanks for pointing it out.

It’s worth keeping in mind that any matrix-determinant-based methods are invariant to leaf relabeling, so this is a measure of tree shape rather than labeled topology. This could still be a useful key for a hash map, though I bet that we could cook up something using labels that would be even more informative.

The following paper does not have branch lengths as part of the definition of the spectra, but it shows some limitations of such an approach. Branch lengths will increase overlap.

ncbi.nlm.nih.gov

Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials.

FA Matsen and SN Evans, Algorithms for molecular biology : AMB, May 21 2012

There are several common ways to encode a tree as a matrix, such as the adjacency matrix, the Laplacian matrix (that is, the infinitesimal generator of the natural random walk), and the matrix of pairwise distances between leaves. Such representations involve a specific labeling of the vertices or at least the leaves, and so it is natural to attempt to identify trees by some feature of the associated matrices that is invariant under relabeling. An obvious candidate is the spectrum of eigenvalues (or, equivalently, the characteristic polynomial).We show for any of these choices of matrix that the fraction of binary trees with a unique spectrum goes to zero as the number of leaves goes to infinity. We investigate the rate of convergence of the above fraction to zero using numerical methods. For the adjacency and Laplacian matrices, we show that the a priori more informative immanantal polynomials have no greater power to distinguish between trees.Our results show that a generic large binary tree is highly unlikely to be identified uniquely by common spectral invariants.

dwbapst

Its interesting. I think, as a paleontologically-inclined person, one of the more intriguing things about this manuscript is its applications for analyzing diversification patterns on non-ultrametric phylogenies, which (as the paper points out) have been sorely lacking from the macroevolutionary toolbox.