Quantifying the degree of self-nestedness of trees:
Application to the structural analysis of plants
Christophe Godin1 and
Pascal Ferraro2
1 INRIA Virtual Plants
2 University of Bordeaux
Abstract
In this paper, we are interested in the problem of approximating trees
by trees with a particular self-nested structure. Self-nested trees
are such that all their subtrees of a given height are isomorphic. We
show that these trees present remarkable compression properties, with
high compression rates. In order to measure how far a tree is from
being a self-nested tree, we then study how to quantify the degree of
self-nestedness of any tree. For this, we define a measure of the
self-nestedness of a tree by constructing a self-nested tree that
minimizes the distance of the original tree to the set of self-nested
trees that embed the initial tree. We show that this measure can be
computed in polynomial time and depict the corresponding
algorithm. The distance to this nearest embedding self-nested tree
(NEST) is then used to define compression coefficients that reflect
the compressibility of a tree. To illustrate this approach, we then
apply these notions to the analysis of plant branching
structures. Based on a database of simulated theoretical plants in
which different levels of noise have been introduced, we evaluate the
method and show that the NESTs of such branching structures restore
partly or completely the original, noiseless, branching
structures. The whole approach is then applied to the analysis of a
real plant (a rice panicle) whose topological structure was completely
measured. We show that the NEST of this plant may be interpreted in
biological terms and may be used to reveal important aspects of the
plant growth.
Reference
Christophe Godin and Pascal Ferraro.
Quantifying the degree of self-nestedness of trees:
Application to the structural analysis of plants.
Transactions on Computational Biology and Bioinformatics
7(4), p. 688-703, October 2010.
Download PDF here (3.5 Mb), or from the publisher's site.