{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:33:13Z","timestamp":1760239993818,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T00:00:00Z","timestamp":1551312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1444806"],"award-info":[{"award-number":["1444806"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study two problems in computational phylogenetics. The first is tree compatibility. The input is a collection    P    of phylogenetic trees over different partially-overlapping sets of species. The goal is to find a single phylogenetic tree that displays all the evolutionary relationships implied by    P   . The second problem is incomplete directed perfect phylogeny (IDPP). The input is a data matrix describing a collection of species by a set of characters, where some of the information is missing. The question is whether there exists a way to fill in the missing information so that the resulting matrix can be explained by a phylogenetic tree satisfying certain conditions. We explain the connection between tree compatibility and IDPP and show that a recent tree compatibility algorithm is effectively a generalization of an earlier IDPP algorithm. Both algorithms rely heavily on maintaining the connected components of a graph under a sequence of edge and vertex deletions, for which they use the dynamic connectivity data structure of Holm et al., known as HDT. We present a computational study of algorithms for tree compatibility and IDPP. We show experimentally that substituting HDT by a much simpler data structure\u2014essentially, a single-level version of HDT\u2014improves the performance of both of these algorithm in practice. We give partial empirical and theoretical justifications for this observation.<\/jats:p>","DOI":"10.3390\/a12030053","type":"journal-article","created":{"date-parts":[[2019,3,1]],"date-time":"2019-03-01T03:29:21Z","timestamp":1551410961000},"page":"53","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental Study"],"prefix":"10.3390","volume":"12","author":[{"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"first","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","article-title":"The complexity of reconstructing trees from qualitative characters and subtrees","volume":"9","author":"Steel","year":"1992","journal-title":"J. Classif."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Semple, C., and Steel, M. (2003). Phylogenetics, Oxford University Press.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Chimani, M., Rahmann, S., and B\u00f6cker, S. (2010, January 2\u20134). Exact ILP solutions for phylogenetic minimum flip problems. Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, Niagara Falls, NY, USA.","DOI":"10.1145\/1854776.1854800"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bininda-Emonds, O.R.P. (2004). Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, Springer.","DOI":"10.1007\/978-1-4020-2330-9"},{"key":"ref_5","unstructured":"Warnow, T. (arXiv, 2018). Supertree Construction: Opportunities and Challenges, arXiv."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"12764","DOI":"10.1073\/pnas.1423041112","article-title":"Synthesis of phylogeny and taxonomy into a comprehensive tree of life","volume":"112","author":"Hinchliff","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"e3058","DOI":"10.7717\/peerj.3058","article-title":"A supertree pipeline for summarizing phylogenetic and taxonomic information for millions of species","volume":"5","author":"Redelings","year":"2017","journal-title":"PeerJ"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","article-title":"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions","volume":"10","author":"Aho","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2453","DOI":"10.1007\/s00453-017-0330-4","article-title":"Fast compatibility testing for rooted phylogenetic trees","volume":"80","author":"Deng","year":"2018","journal-title":"Algorithmica"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/s13015-017-0099-7","article-title":"An efficient algorithm for testing the compatibility of phylogenies with nested taxa","volume":"12","author":"Deng","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.tcs.2005.10.033","article-title":"Compatibility of unrooted phylogenetic trees is FPT","volume":"351","author":"Bryant","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009268","article-title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","volume":"24","author":"Henzinger","year":"1999","journal-title":"Algorithmica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/S0097539702406510","article-title":"Incomplete directed perfect phylogeny","volume":"33","author":"Pupko","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1006\/jagm.1999.1033","article-title":"Decremental dynamic connectivity","volume":"33","author":"Thorup","year":"1999","journal-title":"J. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","article-title":"Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity","volume":"48","author":"Holm","year":"2001","journal-title":"J. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"10261","DOI":"10.1073\/pnas.96.18.10261","article-title":"Phylogenetic relationships among cetartiodactyls based on insertions of short and long interpersed elements: hippopotamuses are the closest extant relatives of whales","volume":"96","author":"Nikaido","year":"1999","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1142\/S0219720005001090","article-title":"The incomplete perfect phylogeny haplotype problem","volume":"3","author":"Kimmel","year":"2005","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","article-title":"An On-Line Edge-Deletion Problem","volume":"28","author":"Even","year":"1981","journal-title":"J. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/320211.320215","article-title":"Randomized fully dynamic graph algorithms with polylogarithmic time per operation","volume":"46","author":"Henzinger","year":"1999","journal-title":"J. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Thorup, M. (2000, January 21\u201323). Near-optimal fully-dynamic graph connectivity. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","DOI":"10.1145\/335305.335345"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., and Mountjoy, B. (2013, January 6\u20138). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611973105.81"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/945394.945398","article-title":"An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms","volume":"6","author":"Iyer","year":"2001","journal-title":"J. Exp. Algorithmics"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","article-title":"Randomized search trees","volume":"16","author":"Seidel","year":"1996","journal-title":"Algorithmica"},{"key":"ref_24","first-page":"277","article-title":"Molecular phylogeny of the \u201cTemperate Herbaceous Tribes\u201d of Papilionoid legumes: A supertree approach","volume":"Volume 9","author":"Herendeen","year":"2000","journal-title":"Advances in Legume Systematics"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1093\/auk\/119.1.88","article-title":"Seabird supertrees: Combining partial estimates of procellariiform phylogeny","volume":"119","author":"Kennedy","year":"2002","journal-title":"Auk"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Beck, R.M.D., Bininda-Emonds, O.R.P., Cardillo, M., Liu, F.G.R., and Purvis, A. (2006). A higher-level MRP supertree of placental mammals. BMC Evol. Biol., 6.","DOI":"10.1186\/1471-2148-6-93"},{"key":"ref_27","first-page":"742","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","year":"1918","journal-title":"Arch. Math. Phys."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S., and Skiena, S. (2003). Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica\u00ae, Cambridge University Press.","DOI":"10.1017\/CBO9781139164849"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/53\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:35:27Z","timestamp":1760186127000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,28]]},"references-count":28,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["a12030053"],"URL":"https:\/\/doi.org\/10.3390\/a12030053","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,2,28]]}}}