Skip to Main content Skip to Navigation
Reports

Quantifying the degree of self-nestedness of trees. Application to the structural analysis of plants

Christophe Godin 1, 2, * Pascal Ferraro 3, 4
* Corresponding author
2 VIRTUAL PLANTS - Modeling plant morphogenesis at different scales, from genes to phenotype
CRISAM - Inria Sophia Antipolis - Méditerranée , INRA - Institut National de la Recherche Agronomique, UMR AGAP - Amélioration génétique et adaptation des plantes méditerranéennes et tropicales
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 re ect 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.
Complete list of metadatas

Cited literature [59 references]  Display  Hide  Download


https://hal.inria.fr/inria-00353645
Contributor : Christophe Godin <>
Submitted on : Friday, January 16, 2009 - 8:40:00 AM
Last modification on : Wednesday, July 8, 2020 - 5:24:03 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:24:14 PM

Files

RR-6800.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00353645, version 1
  • PRODINRA : 330770

Citation

Christophe Godin, Pascal Ferraro. Quantifying the degree of self-nestedness of trees. Application to the structural analysis of plants. [Research Report] RR-6800, INRIA. 2009, pp.42. ⟨inria-00353645⟩

Share

Metrics

Record views

866

Files downloads

620