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 条

[21]

Escolano F., Hancock E.R., Biasotti S., Complexity fusion for indexing Reeb digraphs, International Conference on Computer Analysis of Images and Patterns, pp. 120-127, (2013)

[22]

Gasparovic E., Munch E., Oudot S., Turner K., Wang B., Wang Y., Intrinsic interleaving distance for merge, Trees, (2019)

[23]

Ge X., Safa I.I., Belkin M., Wang Y., Data skeletonization via Reeb graphs, 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, Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pp. 267-276, (2010)

[25]

Hilaga M., Shinagawa Y., Kohmura T., Kunii T.L., Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28Th Annual Conference on Computer Graphics and Interactive Techniques, pp. 203-212, (2001)

[26]

Huson D.H., Rupp R., Scornavacca C., Phylogenetic Networks: Concepts, Algorithms and Applications, (2010)

[27]

Li L., Cheng W.-Y., Glicksberg B.S., Gottesman O., Tamler R., Chen R., Bottinger E.P., Dudley J.T., Identification of type 2 diabetes subgroups through topological analysis of patient similarity, Sci. Transl. Med., 7, 311, (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, pp. 161-189, (2017)

[29]

Mac Lane S., Categories for the Working Mathematician, 5, (2013)

[30]

Morin M.M., Moret B.M.E., Netgen: generating phylogenetic networks with diploid hybrids, Bioinformatics, 22, 15, pp. 1921-1923, (2006)

← 1 2 3 4 5 →