Search

The Open Tree of Life (OToL) project produces a supertree that summarizes phylogenetic knowledge from tree estimates published in the primary literature. The supertree construction algorithm iteratively calls Aho’s Build algorithm thousands of times in order to assess the compatability of different phylogenetic groupings. We describe an incrementalized version of the Build algorithm that is able to share work between successive calls to Build. We provide details that allow a programmer to implement the incremental algorithm BuildInc, including pseudo-code and a description of data structures. We assess the effect of BuildInc on our supertree algorithm by analyzing simulated data and by analyzing a supertree problem taken from the OpenTree 13.4 synthesis tree. We find that BuildInc provides up to 550-fold speedup for our supertree algorithm.

The Open Tree of Life (OToL) project produces a supertree that summarizes phylogenetic knowledge from tree estimates published in the primary literature. The supertree construction algorithm iteratively calls Aho's Build algorithm thousands of times in order to assess the compatability of different phylogenetic groupings. We describe an incrementalized version of the Build algorithm that is able to share work between successive calls to Build. We provide details that allow a programmer to implement the incremental algorithm BuildInc, including pseudo-code and a description of data structures. We assess the effect of BuildInc on our supertree algorithm by analyzing simulated data and by analyzing a supertree problem taken from the OpenTree 13.4 synthesis tree. We find that BuildInc provides up to 550-fold speedup for our supertree algorithm., Competing Interests: The authors declare there are no competing interests., (2024 Redelings and Holder.)

Supertree methods enable the reconstruction of large phylogenies. The supertree problem can be formalized in different ways in order to cope with contradictory information in the input. Some supertree methods are based on encoding the input trees in a matrix; other methods try to find minimum cuts in some graph. Recently, we introduced Bad Clade Deletion (BCD) supertrees which combines the graph-based computation of minimum cuts with optimizing a global objective function on the matrix representation of the input trees. The BCD supertree method has guaranteed polynomial running time and is very swift in practice. The quality of reconstructed supertrees was superior to matrix representation with parsimony (MRP) and usually on par with SuperFine for simulated data; but particularly for biological data, quality of BCD supertrees could not keep up with SuperFine supertrees. Here, we present a beam search extension for the BCD algorithm that keeps alive a constant number of partial solutions in each top-down iteration phase. The guaranteed worst-case running time of the new algorithm is still polynomial in the size of the input. We present an exact and a randomized subroutine to generate suboptimal partial solutions. Both beam search approaches consistently improve supertree quality on all evaluated datasets when keeping 25 suboptimal solutions alive. Supertree quality of the BCD Beam Search algorithm is on par with MRP and SuperFine even for biological data. This is the best performance of a polynomial-time supertree algorithm reported so far. [ABSTRACT FROM AUTHOR]

We present a new supertree method that enables rapid estimation of a summary tree on the scale of millions of leaves. This supertree method summarizes a collection of input phylogenies and an input taxonomy. We introduce formal goals and criteria for such a supertree to satisfy in order to transparently and justifiably represent the input trees. In addition to producing a supertree, our method computes annotations that describe which grouping in the input trees support and conflict with each group in the supertree. We compare our supertree construction method to a previously published supertree construction method by assessing their performance on input trees used to construct the Open Tree of Life version 4, and find that our method increases the number of displayed input splits from 35,518 to 39,639 and decreases the number of conflicting input splits from 2,760 to 1,357. The new supertree method also improves on the previous supertree construction method in that it produces no unsupported branches and avoids unnecessary polytomies. This pipeline is currently used by the Open Tree of Life project to produce all of the versions of project’s “synthetic tree” starting at version 5. This software pipeline is called “propinquity”. It relies heavily on “otcetera”—a set of C++ tools to perform most of the steps of the pipeline. All of the components are free software and are available on GitHub.

Supertree methods combine a set of phylogenetic trees into a single supertree. Similar to supermatrix methods, these methods provide a way to reconstruct larger parts of the Tree of Life, potentially evading the computational complexity of phylogenetic inference methods such as maximum likelihood. The supertree problem can be formalized in different ways, to cope with contradictory information in the input. Many supertree methods have been developed. Some of them solve NP-hard optimization problems like the well-known Matrix Representation with Parsimony, while others have polynomial worst-case running time but work in a greedy fashion (FlipCut). Both can profit from a set of clades that are already known to be part of the supertree. The Superfine approach shows how the Greedy Strict Consensus Merger (GSCM) can be used as preprocessing to find these clades. We introduce different scoring functions for the GSCM, a randomization, as well as a combination thereof to improve the GSCM to find more clades. This helps, in turn, to improve the resolution of the GSCM supertree. We find this modifications to increase the number of true positive clades by 18% compared to the currently used Overlap scoring.

Philodendron is the second most diverse genus of the Araceae, a tropical monocot family with significant morphological diversity along its wide geographic distribution in the Neotropics. Although evolutionary studies of Philodendron were conducted in recent years, the phylogenetic relationship among its species remains unclear. Additionally, analyses conducted to date suggested the inclusion of all American representatives of a closely-related genus, Homalomena, within the Philodendron clade. A thorough evaluation of the phylogeny and timescale of these lineages is thus necessary to elucidate the tempo and mode of evolution of this large Neotropical genus and to unveil the biogeographic history of Philodendron evolution along the Amazonian and Atlantic rainforests as well as open dry forests of South America. To this end, we have estimated the molecular phylogeny for 68 Philodendron species, which consists of the largest sampling assembled to date aiming the study of the evolutionary affinities. We have also performed ancestral reconstruction of species distribution along biomes. Finally, we contrasted these results with the inferred timescale of Philodendron and Homalomena lineage diversification. Our estimates indicate that American Homalomena is the sister clade to Philodendron. The early diversification of Philodendron took place in the Amazon forest from Early to Middle Miocene, followed by colonization of the Atlantic forest and the savanna-like landscapes, respectively. Based on the age of the last common ancestor of Philodendron, the species of this genus diversified by rapid radiations, leading to its wide extant distribution in the Neotropical region.

We present a new supertree method that enables rapid estimation of a summary tree on the scale of millions of leaves. This supertree method summarizes a collection of input phylogenies and an input taxonomy. We introduce formal goals and criteria for such a supertree to satisfy in order to transparently and justifiably represent the input trees. In addition to producing a supertree, our method computes annotations that describe which grouping in the input trees support and conflict with each group in the supertree. We compare our supertree construction method to a previously published supertree construction method by assessing their performance on input trees used to construct the Open Tree of Life version 4, and find that our method increases the number of displayed input splits from 35,518 to 39,639 and decreases the number of conflicting input splits from 2,760 to 1,357. The new supertree method also improves on the previous supertree construction method in that it produces no unsupported branches and avoids unnecessary polytomies. This pipeline is currently used by the Open Tree of Life project to produce all of the versions of project's "synthetic tree" starting at version 5. This software pipeline is called " propinquity ". It relies heavily on " otcetera "-a set of C++ tools to perform most of the steps of the pipeline. All of the components are free software and are available on GitHub., Competing Interests: The authors declare there are no competing interests.

Supertree methods combine a set of phylogenetic trees into a single supertree. Similar to supermatrix methods, these methods provide a way to reconstruct larger parts of the Tree of Life, potentially evading the computational complexity of phylogenetic inference methods such as maximum likelihood. The supertree problem can be formalized in different ways, to cope with contradictory information in the input. Many supertree methods have been developed. Some of them solve NP-hard optimization problems like the well-known Matrix Representation with Parsimony, while others have polynomial worst-case running time but work in a greedy fashion (FlipCut). Both can profit from a set of clades that are already known to be part of the supertree. The Superfine approach shows how the Greedy Strict Consensus Merger (GSCM) can be used as preprocessing to find these clades. We introduce different scoring functions for the GSCM, a randomization, as well as a combination thereof to improve the GSCM to find more clades. This helps, in turn, to improve the resolution of the GSCM supertree. We find this modifications to increase the number of true positive clades by 18% compared to the currently used Overlap scoring.

Philodendron is the second most diverse genus of the Araceae, a tropical monocot family with significant morphological diversity along its wide geographic distribution in the Neotropics. Although evolutionary studies of Philodendron were conducted in recent years, the phylogenetic relationship among its species remains unclear. Additionally, analyses conducted to date suggested the inclusion of all American representatives of a closely-related genus, Homalomena, within the Philodendron clade. A thorough evaluation of the phylogeny and timescale of these lineages is thus necessary to elucidate the tempo and mode of evolution of this large Neotropical genus and to unveil the biogeographic history of Philodendron evolution along the Amazonian and Atlantic rainforests as well as open dry forests of South America. To this end, we have estimated the molecular phylogeny for 68 Philodendron species, which consists of the largest sampling assembled to date aiming the study of the evolutionary affinities. We have also performed ancestral reconstruction of species distribution along biomes. Finally, we contrasted these results with the inferred timescale of Philodendron and Homalomena lineage diversification. Our estimates indicate that American Homalomena is the sister clade to Philodendron. The early diversification of Philodendron took place in the Amazon forest from Early to Middle Miocene, followed by colonization of the Atlantic forest and the savanna-like landscapes, respectively. Based on the age of the last common ancestor of Philodendron, the species of this genus diversified by rapid radiations, leading to its wide extant distribution in the Neotropical region.