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

doi:10.1186/1748-7188-7-14

Algorithms Mol Biol. 2012; 7: 14.

Published online 2012 May 21. doi: 10.1186/1748-7188-7-14

PMCID: PMC3393622

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

Frederick A Matsen ¹ and Steven N Evans²

¹Program in Computational Biology, Fred Hutchinson Cancer Research Center, Seattle, Washington, USA

²Department of Statistics, University of California at Berkeley, Berkeley, California, USA

Corresponding author.

Frederick A Matsen : matsen/at/fhcrc.org; Steven N Evans: evans/at/stat.berkeley.edu

Received October 5, 2011; Accepted May 21, 2012.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Background

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).

Results

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.

Conclusion

Our results show that a generic large binary tree is highly unlikely to be identified uniquely by common spectral invariants.

Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of
BioMed Central