Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics

被引：0

作者：

Stefanou A. ^{[1
]}

机构：

[1] Mathematical Biosciences Institute, Department of Mathematics, The Ohio State University, Columbus, OH

来源：

Journal of Applied and Computational Topology | 2020年 / 4卷 / 2期

基金：

美国国家科学基金会;

关键词：

Betti number; Complexity; Coproducts; Decomposition; Phylogenetic networks; Reeb graphs;

D O I：

10.1007/s41468-020-00051-1

中图分类号：

学科分类号：

摘要：

Inspired by the interval decomposition of persistence modules and the extended Newick format of phylogenetic networks, we show that, inside the larger category of partially ordered Reeb graphs, every Reeb graph with n leaves and first Betti number s, can be identified with a coproduct of at most 2 s partially ordered trees with (n+ s) leaves. Reeb graphs are therefore classified up to isomorphism by their tree-decomposition. An implication of this result, is that the isomorphism problem for Reeb graphs is fixed parameter tractable when the parameter is the first Betti number. We propose partially ordered Reeb graphs as a model for time consistent phylogenetic networks and propose a certain Hausdorff distance as a metric on these structures. © 2020, Springer Nature Switzerland AG.

引用

页码：281 / 308

页数：27

共 41 条

[1]

Adamek J., Herrlich H., Strecker G.E., Abstract and Concrete Categories: The Joy of Cats, (2004)

[2]

Agarwal P.K., Edelsbrunner H., Harer J., Wang Y., Extreme elevation on a 2-manifold, Discrete Comput. Geom., 36, 4, pp. 553-572, (2006)

[3]

Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs, 31St International Symposium on Computational Geometry (Socg 2015), Volume 34 of Leibniz International Proceedings in Informatics (Lipics), Pp. 461–475. Dagstuhl, (2015)

[4]

Biasotti S., Giorgi D., Spagnuolo M., Falcidieno B., Reeb graphs for shape analysis and applications, Theor. Comput. Sci., 392, 1-3, pp. 5-22, (2008)

[5]

Billera L.J., Holmes S.P., Vogtmann K., Geometry of the space of phylogenetic trees, Adv. Appl. Math., 27, 4, pp. 733-767, (2001)

[6]

Computational complexity of the interleaving distance, 34Th International Symposium on Computational Geometry (Socg 2018), Volume 99 of Leibniz International Proceedings in Informatics (Lipics), Pp. 13:1–13:15. Dagstuhl, (2018)

[7]

Bouland A., Dawar A., Kopczynski E., On tractable parameterizations of graph isomorphism, International Symposium on Parameterized and Exact Computation, pp. 218-230, (2012)

[8]

Bubenik P., De Silva V., Scott J., Metrics for generalized persistence modules, Found. Comput. Math., 15, 6, pp. 1501-1531, (2015)

[9]

Cardona G., Rossello F., Valiente G., Extended newick: it is time for a standard representation of phylogenetic networks, BMC Bioinform., 9, 1, (2008)

[10]

Cardona G., Mir A., Rossello F., Rotger L., Sanchez D., Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf, BMC Bioinform., 14, 1, (2013)

← 1 2 3 4 5 →