INRIA Project-Team Virtual Plants, UMR, DAP, Montpellier, France.
IEEE/ACM Trans Comput Biol Bioinform. 2010 Oct-Dec;7(4):688-703. doi: 10.1109/TCBB.2009.29.
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.
在本文中，我们对通过具有特定自嵌套结构的树来逼近树的问题感兴趣。自嵌套树是指其所有给定高度的子树都是同构的。我们表明，这些树具有显著的压缩性质，具有很高的压缩率。为了衡量一棵树与自嵌套树的距离，我们研究如何量化任何树的自嵌套程度。为此，我们通过构建一个自嵌套树来定义树的自嵌套度的度量，该树使原始树与嵌入初始树的自嵌套树集合的距离最小。我们表明，该度量可以在多项式时间内计算，并描绘了相应的算法。然后，将到最近嵌入自嵌套树（NEST）的距离用于定义反映树可压缩性的压缩系数。为了说明这种方法，我们将这些概念应用于植物分支结构的分析。基于一个模拟理论植物的数据库，其中引入了不同水平的噪声，我们评估了该方法，并表明这种分支结构的 NEST 部分或完全恢复了原始的、无噪声的分支结构。然后，我们将整个方法应用于对一个真实植物（水稻穗）的分析，该植物的拓扑结构已被完全测量。我们表明，该植物的 NEST 可以用生物学术语来解释，并且可以用于揭示植物生长的重要方面。
