zbMATH — the first resource for mathematics

Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics. (English) Zbl 1452.55007
A Reeb graph is a connected set \({\mathbb X}\) together with a real valued map \(f :\ {\mathbb X} \ \rightarrow \ {\mathbb R}\) which is strictly monotone when restricted to edges. Reeb graphs arise in computational phylogenetics. The main results of this paper show that a Reeb graph can be thought of as a coproduct of partially ordered trees. The author obtains results on the complexity of Reeb graphs and shows that the isomorphism problem is in a reasonable sense tractable.
55N31 Persistent homology and applications, topological data analysis
18F99 Categories in geometry and topology
92B10 Taxonomy, cladistics, statistics in mathematical biology
Full Text: DOI
[1] Adámek, J.; Herrlich, H.; Strecker, GE, Abstract and Concrete Categories: The Joy of Cats (2004), New York: Wiley, New York
[2] Agarwal, PK; Edelsbrunner, H.; Harer, J.; Wang, Y., Extreme elevation on a 2-manifold, Discrete Comput. Geom., 36, 4, 553-572 (2006) · Zbl 1105.52010
[3] Bauer, U., Munch, E., Wang, Y.: Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In: Arge, L., Pach, J. (eds.) 31st International Symposium on Computational Geometry (SoCG 2015), Volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 461-475. Dagstuhl, Germany (2015). (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik) · Zbl 1382.58010
[4] Biasotti, S.; Giorgi, D.; Spagnuolo, M.; Falcidieno, B., Reeb graphs for shape analysis and applications, Theor. Comput. Sci., 392, 1-3, 5-22 (2008) · Zbl 1134.68064
[5] Billera, LJ; Holmes, SP; Vogtmann, K., Geometry of the space of phylogenetic trees, Adv. Appl. Math., 27, 4, 733-767 (2001) · Zbl 0995.92035
[6] Bjerkevik, H.B., Botnan, M.B.: Computational complexity of the interleaving distance. In: Speckmann, B., Tóth, C.D. (eds.) 34th International Symposium on Computational Geometry (SoCG 2018), Volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 13:1-13:15. Dagstuhl, Germany (2018). (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik)
[7] Bouland, A., Dawar, A., Kopczyński, E.: On tractable parameterizations of graph isomorphism. In: International Symposium on Parameterized and Exact Computation, pp. 218-230. Springer (2012) · Zbl 1350.68130
[8] Bubenik, P.; De Silva, V.; Scott, J., Metrics for generalized persistence modules, Found. Comput. Math., 15, 6, 1501-1531 (2015) · Zbl 1345.55006
[9] Cardona, G.; Rosselló, F.; Valiente, G., Extended newick: it is time for a standard representation of phylogenetic networks, BMC Bioinform., 9, 1, 532 (2008)
[10] Cardona, G.; Mir, A.; Rosselló, F.; Rotger, L.; Sánchez, D., Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf, BMC Bioinform., 14, 1, 3 (2013)
[11] Carlsson, G.; Zomorodian, A.; Collins, A.; Guibas, LJ, Persistence barcodes for shapes, Int. J. Shape Model., 11, 2, 149-187 (2005) · Zbl 1092.68688
[12] Chazal, F., Sun, J.: Gromov-hausdorff approximation of metric spaces with linear structure (2013). arXiv preprint arXiv:1305.1172
[13] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Extending persistence using Poincaré and Lefschetz duality, Found. Comput. Math., 9, 1, 79-103 (2009) · Zbl 1189.55002
[14] Cole-McLaughlin, K.; Edelsbrunner, H.; Harer, J.; Natarajan, V.; Pascucci, V., Loops in Reeb graphs of 2-manifolds, Discrete Comput. Geom., 32, 2, 231-244 (2004) · Zbl 1071.57017
[15] Crawley-Boevey, W., Decomposition of pointwise finite-dimensional persistence modules, J. Algebra Appl., 14, 5, 1550066 (2015) · Zbl 1345.16015
[16] De Silva, V.; Munch, E.; Patel, A., Categorified Reeb graphs, Discrete Comput. Geom., 55, 4, 854-906 (2016) · Zbl 1350.68271
[17] Dey, TK; Fan, F.; Wang, Y., An efficient computation of handle and tunnel loops via Reeb graphs, ACM Trans. Gr. (TOG), 32, 4, 32 (2013)
[18] Di Fabio, B.; Landi, C., The edit distance for Reeb graphs of surfaces, Discrete Comput. Geom., 55, 2, 423-461 (2016) · Zbl 1332.05038
[19] Dress, A.; Feng, J.; Jost, J., The category of x-nets, Networks: From Biology to Theory, 3-22 (2007), Berlin: Springer, Berlin · Zbl 1268.92048
[20] Edelsbrunner, H., Harer, J., Patel, A.K.: Reeb spaces of piecewise linear mappings. In: Symposium on Computational Geometry, pp. 242-250 (2008) · Zbl 1271.57059
[21] Escolano, F., Hancock, E.R., Biasotti, S.: Complexity fusion for indexing Reeb digraphs. In: International Conference on Computer Analysis of Images and Patterns, pp. 120-127. Springer (2013)
[22] Gasparovic, E., Munch, E., Oudot, S., Turner, K., Wang, B., Wang, Y.: Intrinsic interleaving distance for merge trees (2019). arXiv preprint arXiv:1908.00063
[23] Ge, X., Safa, I.I, Belkin, M., Wang, Y.: Data skeletonization via Reeb graphs. In: Advances in Neural Information Processing Systems, pp. 837-845 (2011)
[24] Harvey, W., Wang, Y., Wenger, R.: A randomized o (m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pp. 267-276. ACM (2010) · Zbl 1284.68600
[25] Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3D shapes. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pp. 203-212. ACM (2001)
[26] Huson, DH; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications (2010), Cambridge: Cambridge University Press, Cambridge
[27] Li, L.; Cheng, W-Y; Glicksberg, BS; Gottesman, O.; Tamler, R.; Chen, R.; Bottinger, EP; Dudley, JT, Identification of type 2 diabetes subgroups through topological analysis of patient similarity, Sci. Transl. Med., 7, 311, 311ra174-311ra174 (2015)
[28] Lokshtanov, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth, SIAM J. Comput., 46, 1, 161-189 (2017) · Zbl 1358.05284
[29] Mac Lane, S., Categories for the Working Mathematician (2013), Berlin: Springer, Berlin · Zbl 0232.18001
[30] Morin, MM; Moret, BME, Netgen: generating phylogenetic networks with diploid hybrids, Bioinformatics, 22, 15, 1921-1923 (2006)
[31] Morozov, D.; Beketayev, K.; Weber, G., Interleaving distance between merge trees, Discrete Comput. Geom., 49, 22-45, 52 (2013)
[32] Munch, E., Stefanou, A.: The \(\ell^\infty \)-cophenetic metric for phylogenetic trees as an interleaving distance (2018). arXiv preprint arXiv:1803.07609 · Zbl 1422.92099
[33] Nicolau, M.; Levine, AJ; Carlsson, G., Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival, Proc. Natl. Acad. Sci., 108, 17, 7265-7270 (2011)
[34] Reeb, G., Sur les points singuliers d’une forme de pfaff completement integrable ou d’une fonction numerique [on the singular points of a completely integrable pfaff form or of a numerical function], Comptes Rendus Acad. Sci. Paris, 222, 847-849 (1946) · Zbl 0063.06453
[35] Saitou, N., Phylogeny. In: Introduction to Evolutionary Genomics, 69-108 (2018), Cham: Springer, Cham
[36] Semple, C.; Steel, MA; Caplan, RA; Steel, M., Phylogenetics (2003), Oxford: Oxford University Press, Oxford · Zbl 1043.92026
[37] Singh, G., Mémoli, F., Carlsson, G.E.: Topological methods for the analysis of high dimensional data sets and 3D object recognition. In: SPBG, pp. 91-100 (2007)
[38] Sokal, RR; Rohlf, FJ, The comparison of dendrograms by objective methods, Taxon, 11, 33-40 (1962)
[39] Wood, Z.; Hoppe, H.; Desbrun, M.; Schröder, P., Removing excess topology from isosurfaces, ACM Trans. Gr. (TOG), 23, 2, 190-208 (2004)
[40] Yamazaki, K., Bodlaender, H.L., De Fluiter, B., Thilikos, D.M.: Isomorphism for graphs of bounded distance width. In: Italian Conference on Algorithms and Complexity, pp. 276-287. Springer (1997) · Zbl 0934.68071
[41] Yao, Y.; Sun, J.; Huang, X.; Bowman, GR; Singh, G.; Lesnick, M.; Guibas, LJ; Pande, VS; Carlsson, G., Topological methods for exploring low-density states in biomolecular folding pathways, J. Chem. Phys., 130, 14, 04B614 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.