{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,7]],"date-time":"2026-09-07T22:50:47Z","timestamp":1788821447706,"version":"build-2803163510"},"reference-count":11,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T00:00:00Z","timestamp":1567036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in 2010. The procedure consists of computing a self-nested approximation, called the nearest embedding self-nested tree, that both embeds the plant and is the closest to it. In this paper, we propose a new algorithm that computes the nearest embedding self-nested tree with a smaller overall complexity, but also the nearest embedded self-nested tree. We show from simulations that the latter is mostly the closest to the initial data, which suggests that this better approximation should be used as a privileged measure of the degree of self-similarity of plants.<\/jats:p>","DOI":"10.3390\/a12090180","type":"journal-article","created":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T11:26:22Z","timestamp":1567077982000},"page":"180","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Nearest Embedded and Embedding Self-Nested Trees"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5234-1822","authenticated-orcid":false,"given":"Romain","family":"Aza\u00efs","sequence":"first","affiliation":[{"name":"Laboratoire Reproduction et D\u00e9veloppement des Plantes, Univ Lyon, ENS de Lyon, UCB Lyon 1, CNRS, INRA, Inria, F-69342 Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.ic.2014.12.012","article-title":"Tree compression with top trees","volume":"243","author":"Bille","year":"2015","journal-title":"Inf. Comput."},{"key":"ref_2","first-page":"1322","article-title":"XML Compression via Directed Acyclic Graphs","volume":"57","author":"Lohrey","year":"2014","journal-title":"Theory Comput. Syst."},{"key":"ref_3","unstructured":"Buneman, P., Grohe, M., and Koch, C. (2003, January 9\u201312). Path Queries on Compressed XML. Proceedings of the 29th International Conference on Very Large Data Bases, VLDB\u201903, Berlin, Germany."},{"key":"ref_4","unstructured":"Frick, M., Grohe, M., and Koch, C. (2003, January 22\u201325). Query evaluation on compressed trees. Proceedings of the 18th Annual IEEE Symposium of Logic in Computer Science, Ottawa, ON, Canada."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1109\/TCBB.2009.29","article-title":"Quantifying the degree of self-nestedness of trees. Application to the structural analysis of plants","volume":"7","author":"Godin","year":"2010","journal-title":"IEEE Trans. Comput. Biol. Bioinform."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","article-title":"Efficient Memory Representation of XML Document Trees","volume":"33","author":"Busatto","year":"2008","journal-title":"Inf. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2006.07.024","article-title":"The Complexity of Tree Automata and XPath on Grammar-compressed Trees","volume":"363","author":"Lohrey","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1142\/S0129054196000130","article-title":"Subtree Isomorphism is in DLOG for Nested Trees","volume":"7","author":"Greenlaw","year":"1996","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.21105\/joss.01351","article-title":"treex: A Python package for manipulating rooted trees","volume":"4","author":"Cerutti","year":"2019","journal-title":"J. Open Source Softw."},{"key":"ref_10","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc.. [1st ed.]."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01975866","article-title":"A constrained edit distance between unordered labeled trees","volume":"15","author":"Zhang","year":"1996","journal-title":"Algorithmica"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/180\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:14:56Z","timestamp":1760188496000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,29]]},"references-count":11,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090180"],"URL":"https:\/\/doi.org\/10.3390\/a12090180","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,29]]}}}