Search

Phylogenetic trees represent the evolutionary relationships and ancestry of various species or groups of organisms. Comparing these trees by measuring the distance between them is essential for applications such as tree clustering and the Tree of Life project. Many distance metrics for phylogenetic trees focus on trees defined on the same set of taxa. However, some problems require calculating distances between trees with different but overlapping sets of taxa. This study reviews state‐of‐the‐art distance measures for such trees, covering six major approaches, including the constraint‐based Robinson–Foulds (RF) distance RF(−), the completion‐based RF(+), the generalized RF (GRF), the dissimilarity measure, the vectorial tree distance, and the geodesic distance in the extended Billera‐Holmes‐Vogtmann tree space. Among these, three RF‐based methods, RF(−), RF(+), and GRF, were examined in detail on generated clusters of phylogenetic trees defined on different but mutually overlapping sets of taxa. Additionally, we reviewed nine related techniques, including leaf imputation methods, the tree edit distance, and visual comparison. A comparison of the related distance measures, highlighting their principal advantages and shortcomings, is provided. This review offers valuable insights into their applicability and performance, guiding the appropriate use of these metrics based on tree type (rooted or unrooted) and information type (topological or branch lengths). [ABSTRACT FROM AUTHOR]

Let G be a k -uniform hypergraph with vertex set V (G) and edge set E (G). A connected and acyclic hypergraph is called a supertree. For 0 ≤ α < 1 , the α -spectral radius of G is the largest H -eigenvalue of α D (G) + (1 − α) A (G) , where D (G) and A (G) are the diagonal tensor of the degrees and the adjacency tensor of G , respectively. In this paper, we determine the unique supertrees with maximum α -spectral radius among all k -uniform supertrees with m edges and independence number β for ⌈ m (k − 1) + 1 k ⌉ ≤ β ≤ m , among all k -uniform supertrees with given degree sequences, and among all k -uniform supertrees with m edges and matching number μ for 1 ≤ μ ≤ ⌊ m (k − 1) + 1 k ⌋ , respectively. [ABSTRACT FROM AUTHOR]

Swine acute diarrhoea syndrome coronavirus (SADS-CoV; Coronaviridae, Rhinacovirus) was detected in 2017 in Guangdong Province (China), where it caused high mortality rates in piglets. According to previous studies, SADS-CoV evolved from horseshoe bat reservoirs. Here, we report the first five Rhinacovirus genomes sequenced in horseshoe bats from Vietnam and their comparisons with data published in China. Our phylogenetic analyses provided evidence for four groups: rhinacoviruses from Rhinolphus pusillus bats, including one from Vietnam; bat rhinacoviruses from Hainan; bat rhinacoviruses from Yunnan showing a divergent synonymous nucleotide composition; and SADS-CoV and related bat viruses, including four rhinacoviruses from Vietnam sampled in Rhinolophus affinis and Rhinolophus thomasi. Our phylogeographic analyses showed that bat rhinacoviruses from Dien Bien (Vietnam) share more affinities with those from Yunnan (China) and that the ancestor of SADS-CoVs arose in Rhinolophus affinis circulating in Guangdong. We detected sequencing errors and artificial chimeric genomes in published data. The two SADS-CoV genomes previously identified as recombinant could also be problematic. The reliable data currently available, therefore, suggests that all SADS-CoV strains originate from a single bat source and that the virus has been spreading in pig farms in several provinces of China for at least seven years since the first outbreak in August 2016. [ABSTRACT FROM AUTHOR]

Abstract Phylogenetic trees represent the evolutionary relationships and ancestry of various species or groups of organisms. Comparing these trees by measuring the distance between them is essential for applications such as tree clustering and the Tree of Life project. Many distance metrics for phylogenetic trees focus on trees defined on the same set of taxa. However, some problems require calculating distances between trees with different but overlapping sets of taxa. This study reviews state‐of‐the‐art distance measures for such trees, covering six major approaches, including the constraint‐based Robinson–Foulds (RF) distance RF(−), the completion‐based RF(+), the generalized RF (GRF), the dissimilarity measure, the vectorial tree distance, and the geodesic distance in the extended Billera‐Holmes‐Vogtmann tree space. Among these, three RF‐based methods, RF(−), RF(+), and GRF, were examined in detail on generated clusters of phylogenetic trees defined on different but mutually overlapping sets of taxa. Additionally, we reviewed nine related techniques, including leaf imputation methods, the tree edit distance, and visual comparison. A comparison of the related distance measures, highlighting their principal advantages and shortcomings, is provided. This review offers valuable insights into their applicability and performance, guiding the appropriate use of these metrics based on tree type (rooted or unrooted) and information type (topological or branch lengths).

Understanding the drivers of morphological convergence requires investigation into its relationship with behavior and niche space, and such investigations in turn provide insights into evolutionary dynamics, functional morphology, and life history. Mygalomorph spiders (trapdoor spiders and their kin) have long been associated with high levels of morphological homoplasy, and many convergent features can be intuitively associated with different behavioral niches. Using genus-level phylogenies based on recent genomic studies and a newly assembled matrix of discrete behavioral and somatic morphological characters, we reconstruct the evolution of burrowing behavior in the Mygalomorphae, compare the influence of behavior and evolutionary history on somatic morphology, and test hypotheses of correlated evolution between specific morphological features and behavior. Our results reveal the simplicity of the mygalomorph adaptive landscape, with opportunistic, web-building taxa at one end, and burrowing/nesting taxa with structurally modified burrow entrances (e.g., a trapdoor) at the other. Shifts in behavioral niche, in both directions, are common across the evolutionary history of the Mygalomorphae, and several major clades include taxa inhabiting both behavioral extremes. Somatic morphology is heavily influenced by behavior, with taxa inhabiting the same behavioral niche often more similar morphologically than more closely related but behaviorally divergent taxa, and we were able to identify a suite of 11 somatic features that show significant correlation with particular behaviors. We discuss these findings in light of the function of particular morphological features, niche dynamics within the Mygalomorphae, and constraints on the mygalomorph adaptive landscape relative to other spiders.

Chronograms—phylogenies with branch lengths proportional to time—represent key data on timing of evolutionary events, allowing us to study natural processes in many areas of biological research. Chronograms also provide valuable information that can be used for education, science communication, and conservation policy decisions. Yet, achieving a high-quality reconstruction of a chronogram is a difficult and resource-consuming task. Here we present DateLife, a phylogenetic software implemented as an R package and an R Shiny web application available at www.datelife.org , that provides services for efficient and easy discovery, summary, reuse, and reanalysis of node age data mined from a curated database of expert, peer-reviewed, and openly available chronograms. The main DateLife workflow starts with one or more scientific taxon names provided by a user. Names are processed and standardized to a unified taxonomy, allowing DateLife to run a name match across its local chronogram database that is curated from Open Tree of Life's phylogenetic repository, and extract all chronograms that contain at least two queried taxon names, along with their metadata. Finally, node ages from matching chronograms are mapped using the congruification algorithm to corresponding nodes on a tree topology, either extracted from Open Tree of Life's synthetic phylogeny or one provided by the user. Congruified node ages are used as secondary calibrations to date the chosen topology, with or without initial branch lengths, using different phylogenetic dating methods such as BLADJ, treePL, PATHd8, and MrBayes. We performed a cross-validation test to compare node ages resulting from a DateLife analysis (i.e, phylogenetic dating using secondary calibrations) to those from the original chronograms (i.e, obtained with primary calibrations), and found that DateLife's node age estimates are consistent with the age estimates from the original chronograms, with the largest variation in ages occurring around topologically deeper nodes. Because the results from any software for scientific analysis can only be as good as the data used as input, we highlight the importance of considering the results of a DateLife analysis in the context of the input chronograms. DateLife can help to increase awareness of the existing disparities among alternative hypotheses of dates for the same diversification events, and to support exploration of the effect of alternative chronogram hypotheses on downstream analyses, providing a framework for a more informed interpretation of evolutionary results. [ABSTRACT FROM AUTHOR]

Abstract Background Genome-scale phylogenetic analysis based on core gene sets is routinely used in microbiological research. However, the techniques are still not approachable for individuals with little bioinformatics experience. Here, we present EasyCGTree, a user-friendly and cross-platform pipeline to reconstruct genome-scale maximum-likehood (ML) phylogenetic tree using supermatrix (SM) and supertree (ST) approaches. Results EasyCGTree was implemented in Perl programming languages and was built using a collection of published reputable programs. All the programs were precompiled as standalone executable files and contained in the EasyCGTree package. It can run after installing Perl language environment. Several profile hidden Markov models (HMMs) of core gene sets were prepared in advance to construct a profile HMM database (PHD) that was enclosed in the package and available for homolog searching. Customized gene sets can also be used to build profile HMM and added to the PHD via EasyCGTree. Taking 43 genomes of the genus Paracoccus as the testing data set, consensus (a variant of the typical SM), SM, and ST trees were inferred via EasyCGTree successfully, and the SM trees were compared with those inferred via the pipelines UBCG and bcgTree, using the metrics of cophenetic correlation coefficients (CCC) and Robinson–Foulds distance (topological distance). The results suggested that EasyCGTree can infer SM trees with nearly identical topology (distance 0.99) to those of trees inferred with the two pipelines. Conclusions EasyCGTree is an all-in-one automatic pipeline from input data to phylogenomic tree with guaranteed accuracy, and is much easier to install and use than the reference pipelines. In addition, ST is implemented in EasyCGTree conveniently and can be used to explore prokaryotic evolutionary signals from a different perspective. The EasyCGTree version 4 is freely available for Linux and Windows users at Github ( https://github.com/zdf1987/EasyCGTree4 ).

The extraordinary morphological diversity among extant mammals poses a challenge for studies of speciation, adaptation, molecular evolution, and reproductive isolation. Despite the recent wealth of molecular studies on mammalian phylogenetics, uncertainties remain surrounding both ancestral and more recent divergence events that have proven difficult to resolve. Multi-gene datasets, especially including genes that are highly divergent, often provide increased support for higher-level affinities within Mammalia; however, such analyses require vast amounts of genomic sequence data and at times, intensive, high-performance computational effort. Furthermore, despite the large-scale efforts dedicated to comprehensive, multi-gene phylogenetic analyses using a combination of mitochondrial, nuclear, and other sequences (e.g., tRNA, ultra-conserved elements, and transposable elements), many relationships across Mammalia remain highly controversial. To offer another approach and provide a phylogenetic solution to this longstanding issue, here we present a phylogenetic tool based on a single reproductive molecular marker, zonadhesin (gene: Zan), one of two known mammalian speciation genes, which encodes the rapidly evolving sperm protein zonadhesin that mediates species-specific adhesion to the egg and thereby promotes reproductive isolation among placental mammals (Eutheria). Topological comparison of Zan Maximum Likelihood phylogenies to a nearly complete mammalian supertree confirmed Zan's striking phylogenetic utility and resolution at both deeper and more terminal nodes in the placental mammalian phylogeny. This single gene marker yielded an equivalent and/or superiorly supported topology in comparison to a supertree generated using DNA sequences from a supermatrix of 31 genes from 5911 species (extinct and extant). Resolution achieved with this new phylogenetic approach provides unique insights into the divergence of both early and recent mammalian radiations. Finally, and perhaps most importantly, the utility of zonadhesin as a singular molecular marker was especially useful in clades where sufficient taxon sampling is impossible to achieve, and where only a subset of members of the mammalian species tree is available. The eutherian relationships presented here provide a foundation for future studies in the reconstruction of mammalian classifications, including reproductive isolation, hybridization, and biodiversification of species. [ABSTRACT FROM AUTHOR]

In phylogenomics, incongruences between gene trees, resulting from both artifactual and biological reasons, can decrease the signal-to-noise ratio and complicate species tree inference. The amount of data handled today in classical phylogenomic analyses precludes manual error detection and removal. However, a simple and efficient way to automate the identification of outliers from a collection of gene trees is still missing. Here, we present PhylteR, a method that allows rapid and accurate detection of outlier sequences in phylogenomic datasets, i.e. species from individual gene trees that do not follow the general trend. PhylteR relies on DISTATIS, an extension of multidimensional scaling to 3 dimensions to compare multiple distance matrices at once. In PhylteR, these distance matrices extracted from individual gene phylogenies represent evolutionary distances between species according to each gene. On simulated datasets, we show that PhylteR identifies outliers with more sensitivity and precision than a comparable existing method. We also show that PhylteR is not sensitive to ILS-induced incongruences, which is a desirable feature. On a biological dataset of 14,463 genes for 53 species previously assembled for Carnivora phylogenomics, we show (i) that PhylteR identifies as outliers sequences that can be considered as such by other means, and (ii) that the removal of these sequences improves the concordance between the gene trees and the species tree. Thanks to the generation of numerous graphical outputs, PhylteR also allows for the rapid and easy visual characterization of the dataset at hand, thus aiding in the precise identification of errors. PhylteR is distributed as an R package on CRAN and as containerized versions (docker and singularity). [ABSTRACT FROM AUTHOR]

Background: Genome-scale phylogenetic analysis based on core gene sets is routinely used in microbiological research. However, the techniques are still not approachable for individuals with little bioinformatics experience. Here, we present EasyCGTree, a user-friendly and cross-platform pipeline to reconstruct genome-scale maximum-likehood (ML) phylogenetic tree using supermatrix (SM) and supertree (ST) approaches. Results: EasyCGTree was implemented in Perl programming languages and was built using a collection of published reputable programs. All the programs were precompiled as standalone executable files and contained in the EasyCGTree package. It can run after installing Perl language environment. Several profile hidden Markov models (HMMs) of core gene sets were prepared in advance to construct a profile HMM database (PHD) that was enclosed in the package and available for homolog searching. Customized gene sets can also be used to build profile HMM and added to the PHD via EasyCGTree. Taking 43 genomes of the genus Paracoccus as the testing data set, consensus (a variant of the typical SM), SM, and ST trees were inferred via EasyCGTree successfully, and the SM trees were compared with those inferred via the pipelines UBCG and bcgTree, using the metrics of cophenetic correlation coefficients (CCC) and Robinson–Foulds distance (topological distance). The results suggested that EasyCGTree can infer SM trees with nearly identical topology (distance < 0.1) and accuracy (CCC > 0.99) to those of trees inferred with the two pipelines. Conclusions: EasyCGTree is an all-in-one automatic pipeline from input data to phylogenomic tree with guaranteed accuracy, and is much easier to install and use than the reference pipelines. In addition, ST is implemented in EasyCGTree conveniently and can be used to explore prokaryotic evolutionary signals from a different perspective. The EasyCGTree version 4 is freely available for Linux and Windows users at Github (https://github.com/zdf1987/EasyCGTree4). [ABSTRACT FROM AUTHOR]

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.

Despite the increasingly available phylogenetic hypotheses for multiple taxonomic groups, most of them do not include all species. In phylogenetic ecology, there is still a strong demand to have phylogenies with all species in a study included. The existing software tools to graft species to backbone megatrees, however, are mostly limited to a specific taxonomic group such as plants or fishes. Here, I introduce a new user-friendly R package, 'rtrees', that can assemble phylogenies from existing or user-provided megatrees. For most common taxonomic groups, users can only provide a vector of species scientific names to get a phylogeny or a set of posterior phylogenies from megatrees. It is my hope that 'rtrees' can provide an easy, flexible, and reliable way to assemble phylogenies from megatrees, facilitating the progress of phylogenetic ecology. [ABSTRACT FROM AUTHOR]

The extraordinary morphological diversity among extant mammals poses a challenge for studies of speciation, adaptation, molecular evolution, and reproductive isolation. Despite the recent wealth of molecular studies on mammalian phylogenetics, uncertainties remain surrounding both ancestral and more recent divergence events that have proven difficult to resolve. Multi-gene datasets, especially including genes that are highly divergent, often provide increased support for higher-level affinities within Mammalia; however, such analyses require vast amounts of genomic sequence data and at times, intensive, high-performance computational effort. Furthermore, despite the large-scale efforts dedicated to comprehensive, multi-gene phylogenetic analyses using a combination of mitochondrial, nuclear, and other sequences (e.g., tRNA, ultra-conserved elements, and transposable elements), many relationships across Mammalia remain highly controversial. To offer another approach and provide a phylogenetic solution to this longstanding issue, here we present a phylogenetic tool based on a single reproductive molecular marker, zonadhesin (gene: Zan), one of two known mammalian speciation genes, which encodes the rapidly evolving sperm protein zonadhesin that mediates species-specific adhesion to the egg and thereby promotes reproductive isolation among placental mammals (Eutheria). Topological comparison of Zan Maximum Likelihood phylogenies to a nearly complete mammalian supertree confirmed Zan’s striking phylogenetic utility and resolution at both deeper and more terminal nodes in the placental mammalian phylogeny. This single gene marker yielded an equivalent and/or superiorly supported topology in comparison to a supertree generated using DNA sequences from a supermatrix of 31 genes from 5911 species (extinct and extant). Resolution achieved with this new phylogenetic approach provides unique insights into the divergence of both early and recent mammalian radiations. Finally, and perhaps most importantly, the utility of zonadhesin as a singular molecular marker was especially useful in clades where sufficient taxon sampling is impossible to achieve, and where only a subset of members of the mammalian species tree is available. The eutherian relationships presented here provide a foundation for future studies in the reconstruction of mammalian classifications, including reproductive isolation, hybridization, and biodiversification of species.

Let H be an r -uniform hypergraph and A α (H) = α D (H) + (1 − α) A (H) be the convex linear combination of its degree diagonal tensor D (H) and its adjacency tensor A (H) , where r ≥ 3 and 0 ≤ α < 1. The α -spectral radius of H is the largest modulus of all the eigenvalues of A α (H). Let T (n , r) be the set of the r -uniform supertrees of order n , where r ≥ 3 and n ≥ 5. The number of the edges of the supertrees in T (n , r) is denoted by m = n − 1 r − 1 . Among T (n , r) with r ≥ 3 and m ≥ 7 , You et al. (2020) determined the supertrees with the first, the second and the third largest α -spectral radii and they gave two r -uniform supertrees which are the candidates for the supertree with the fourth largest α -spectral radius. You et al. (2020) proposed a conjecture concerning the supertrees with the fourth through the eighth largest α -spectral radii in T (n , r) , where m = n − 1 r − 1 ≥ 10. In this paper, we prove that this conjecture is correct when m ≥ 10 and 1 − 1 m − 2 ≤ α < 1. With our results, the supertrees with the fourth through the eighth largest α -spectral radii are determined among T (n , r). [ABSTRACT FROM AUTHOR]

A supertree is a connected and acyclic hypergraph. Let T m △ , △ be the set of the r-uniform supertrees with m edges and exactly two vertices of maximum degree ▵, where m ≥ 5 and 3 ≤ △ ≤ [ (m + 1) / 2 ]. We investigate the supertree with the minimum spectral radius among T m △ , △ . Several useful grafting operations are introduced for comparing the spectral radii of supertrees. The supertree with the minimum spectral radius among T m △ , △ is characterized. In addition, a new simple method is demonstrated to obtain the supertree with the minimum spectral radius among the set of r-uniform supertrees with m edges. [ABSTRACT FROM AUTHOR]

A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees. Quartet Compatibility is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for Quartet Compatibility for these systems. [ABSTRACT FROM AUTHOR]

Chronograms-phylogenies with branch lengths proportional to time-represent key data on timing of evolutionary events, allowing us to study natural processes in many areas of biological research. Chronograms also provide valuable information that can be used for education, science communication, and conservation policy decisions. Yet, achieving a high-quality reconstruction of a chronogram is a difficult and resource-consuming task. Here we present DateLife, a phylogenetic software implemented as an R package and an R Shiny web application available at www.datelife.org, that provides services for efficient and easy discovery, summary, reuse, and reanalysis of node age data mined from a curated database of expert, peer-reviewed, and openly available chronograms. The main DateLife workflow starts with one or more scientific taxon names provided by a user. Names are processed and standardized to a unified taxonomy, allowing DateLife to run a name match across its local chronogram database that is curated from Open Tree of Life's phylogenetic repository, and extract all chronograms that contain at least two queried taxon names, along with their metadata. Finally, node ages from matching chronograms are mapped using the congruification algorithm to corresponding nodes on a tree topology, either extracted from Open Tree of Life's synthetic phylogeny or one provided by the user. Congruified node ages are used as secondary calibrations to date the chosen topology, with or without initial branch lengths, using different phylogenetic dating methods such as BLADJ, treePL, PATHd8, and MrBayes. We performed a cross-validation test to compare node ages resulting from a DateLife analysis (i.e, phylogenetic dating using secondary calibrations) to those from the original chronograms (i.e, obtained with primary calibrations), and found that DateLife's node age estimates are consistent with the age estimates from the original chronograms, with the largest variation in ages occurring around topologically deeper nodes. Because the results from any software for scientific analysis can only be as good as the data used as input, we highlight the importance of considering the results of a DateLife analysis in the context of the input chronograms. DateLife can help to increase awareness of the existing disparities among alternative hypotheses of dates for the same diversification events, and to support exploration of the effect of alternative chronogram hypotheses on downstream analyses, providing a framework for a more informed interpretation of evolutionary results., (© The Author(s) 2024. Published by Oxford University Press on behalf of the Society of Systematic Biologists.)

A clade's evolutionary history is shaped, in part, by geographical range expansion, sweepstakes dispersal and local extinction. A rigorous understanding of historical biogeography may therefore yield insights into macroevolutionary dynamics such as adaptive radiation. Modern historical biogeographic analyses typically fit statistical models to molecular phylogenies, but it remains unclear whether extant species provide sufficient signal or if well-sampled phylogenies of extinct and extant taxa are necessary to produce meaningful estimates of past ranges. We investigated the historical biogeography of Primates and their euarchontan relatives using a novel meta-analytical phylogeny of over 900 extant (n= 419) and extinct (n = 483) species spanning their entire evolutionary history. Ancestral range estimates for young nodes were largely congruent with those derived from molecular phylogeny. However, node age exerts a significant effect on ancestral range estimate congruence, and the probability of congruent inference dropped below 0.5 for nodes older than the late Eocene, corresponding to the origins of higher-level clades. Discordance was not observed in analyses of extinct taxa alone. Fossils are essential for robust ancestral range inference and biogeographic analyses of extant clades originating in the deep past should be viewed with scepticism without them. [ABSTRACT FROM AUTHOR]

Supertree methods are tree reconstruction techniques that combine several smaller gene trees (possibly on different sets of species) to build a larger species tree. The question of interest is whether the reconstructed supertree converges to the true species tree as the number of gene trees increases (that is, the consistency of supertree methods). In this paper, we are particularly interested in the convergence rate of the maximum likelihood supertree. Previous studies on the maximum likelihood supertree approach often formulate the question of interest as a discrete problem and focus on reconstructing the correct topology of the species tree. Aiming to reconstruct both the topology and the branch lengths of the species tree, we propose an analytic approach for analyzing the convergence of the maximum likelihood supertree method. Specifically, we consider each tree as one point of a metric space and prove that the distance between the maximum likelihood supertree and the species tree converges to zero at a polynomial rate under some mild conditions. We further verify these conditions for the popular exponential error model of gene trees.

Abstract Dothideomycetes is the most diverse fungal class in Ascomycota and includes species with a wide range of lifestyles. Previous multilocus studies have investigated the taxonomic and evolutionary relationships of these taxa but often failed to resolve early diverging nodes and frequently generated inconsistent placements of some clades. Here, we use a phylogenomic approach to resolve relationships in Dothideomycetes, focusing on two genera of melanized, extremotolerant rock-inhabiting fungi, Lichenothelia and Saxomyces, that have been suggested to be early diverging lineages. We assembled phylogenomic datasets from newly sequenced (4) and previously available genomes (238) of 242 taxa. We explored the influence of tree inference methods, supermatrix vs. coalescent-based species tree, and the impact of varying amounts of genomic data. Overall, our phylogenetic reconstructions provide consistent and well-supported topologies for Dothideomycetes, recovering Lichenothelia and Saxomyces among the earliest diverging lineages in the class. In addition, many of the major lineages within Dothideomycetes are recovered as monophyletic, and the phylogenomic approach implemented strongly supports their relationships. Ancestral character state reconstruction suggest that the rock-inhabiting lifestyle is ancestral within the class.

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.)

Let S (m, d, k) be the set of k-uniform supertrees with m edges and diameter d, and S1 (m, d, k) be the k-uniform supertree obtained from a loose path u1, e1, u2, e2, ..., ud, ed, ud+1 with length d by attaching m–d edges at vertex u⌊d/2⌋+1. In this paper, we mainly determine S1 (m, d, k) with the largest signless Laplacian spectral radius in S (m, d, k) for 3 ⩽ d ⩽ m − 1. We also determine the supertree with the second largest signless Laplacian spectral radius in S (m, 3, k). Furthermore, we determine the unique k-uniform supertree with the largest signless Laplacian spectral radius among all k-uniform supertrees with n vertices and pendent edges (vertices). [ABSTRACT FROM AUTHOR]

A supertree is a connected and acyclic hypergraph. We investigate the supertrees with the extremal spectral radii among several kinds of r-uniform supertrees. First, by using the matching polynomials of supertrees, a new and useful grafting operation is proposed for comparing the spectral radii of supertrees, and its applications are shown to obtain the supertrees with the extremal spectral radii among some kinds of r-uniform supertrees. Second, the supertree with the third smallest spectral radius among the r-uniform supertrees is deduced. Third, among the r-uniform supertrees with a given maximum degree, the supertree with the smallest spectral radius is derived. At last, among the r-uniform starlike supertrees, the supertrees with the smallest and the largest spectral radii are characterized. [ABSTRACT FROM AUTHOR]

Let α be a real number with 0 ≤ α < 1 , G be a uniform hypergraph, and A α (G) = α D (G) + (1 − α) A (G) , where D (G) and A (G) are the diagonal degree tensor and the adjacency tensor of G , respectively. The spectral radius of A α (G) is called the α -spectral radius of G. In this paper, some properties for the α -spectral radius of connected k -uniform hypergraphs are investigated, the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with a given degree sequence is characterized, and the majorization theorem for k -uniform supertrees is obtained. By applying the majorization theorem, we determine the k -uniform supertrees obtaining the three largest α -spectral radius among all k -uniform supertrees with n vertices, give a new proof ordering the eight largest spectral radius among all k -uniform supertrees with n vertices, propose an open problem for further research, and characterize the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with given different parameters, e.g., the maximum degree △ , or the number of pendent vertices. [ABSTRACT FROM AUTHOR]

In this paper we show how the α -spectral radius changes under the edge grafting operations on connected k -uniform hypergraphs. We characterize the extremal hypertree for α -spectral radius among k -uniform non-caterpillar hypergraphs with given order, size and diameter. We also characterize the supertree with the second largest α -spectral radius among all k -uniform supertrees on n vertices. [ABSTRACT FROM AUTHOR]

Evolutionary relationships have remained unresolved in many well-studied groups, even though advances in next-generation sequencing and analysis, using approaches such as transcriptomics, anchored hybrid enrichment, or ultraconserved elements, have brought systematics to the brink of whole genome phylogenomics. Recently, it has become possible to sequence the entire genomes of numerous nonbiological models in parallel at reasonable cost, particularly with shotgun sequencing. Here, we identify orthologous coding sequences from whole-genome shotgun sequences, which we then use to investigate the relevance and power of phylogenomic relationship inference and time-calibrated tree estimation. We study an iconic group of butterflies—swallowtails of the family Papilionidae—that has remained phylogenetically unresolved, with continued debate about the timing of their diversification. Low-coverage whole genomes were obtained using Illumina shotgun sequencing for all genera. Genome assembly coupled to BLAST-based orthology searches allowed extraction of 6621 orthologous protein-coding genes for 45 Papilionidae species and 16 outgroup species (with 32% missing data after cleaning phases). Supermatrix phylogenomic analyses were performed with both maximum-likelihood (IQ-TREE) and Bayesian mixture models (PhyloBayes) for amino acid sequences, which produced a fully resolved phylogeny providing new insights into controversial relationships. Species tree reconstruction from gene trees was performed with ASTRAL and SuperTriplets and recovered the same phylogeny. We estimated gene site concordant factors to complement traditional node-support measures, which strengthens the robustness of inferred phylogenies. Bayesian estimates of divergence times based on a reduced data set (760 orthologs and 12% missing data) indicate a mid-Cretaceous origin of Papilionoidea around 99.2 Ma (95% credibility interval: 68.6–142.7 Ma) and Papilionidae around 71.4 Ma (49.8–103.6 Ma), with subsequent diversification of modern lineages well after the Cretaceous-Paleogene event. These results show that shotgun sequencing of whole genomes, even when highly fragmented, represents a powerful approach to phylogenomics and molecular dating in a group that has previously been refractory to resolution. [ABSTRACT FROM AUTHOR]

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q -MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q -MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q , and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees. [ABSTRACT FROM AUTHOR]

Collectively, ray-finned fishes (Actinopterygii) display far more diversity in many reproductive and genomic features than any other major vertebrate group. Recent large-scale comparative phylogenetic analyses have begun to reveal the evolutionary patterns and putative causes for much of this diversity. Several such recent studies have offered clues to how different reproductive syndromes evolved in these fishes, as well as possible physiological and genomic triggers. In many cases, repeated independent origins of complex reproductive strategies have been uncovered, probably reflecting convergent selection operating on common suites of underlying genes and hormonal controls. For example, phylogenetic analyses have uncovered multiple origins and predominant transitional pathways in the evolution of alternative male reproductive tactics, modes of parental care and mechanisms of sex determination. They have also shown that sexual selection in these fishes is repeatedly associated with particular reproductive strategies. Collectively, studies on reproductive and genomic diversity across the Actinopterygii illustrate both the strengths and the limitations of comparative phylogenetic approaches on large taxonomic scales. © 2006 The Authors.

In this paper, we introduce the operations of grafting an edge and subdividing an edge on hypergraphs, and consider how spectral radius of a hypergraph behaves by grafting an edge or subdividing an edge. As an application, we determine the unique hypergraphs with the maximum spectral radius among all the uniform supertrees and all the connected uniform unicyclic hypergraphs with given number of pendant edges, respectively. Moreover, we determine the unique uniform supertree which attains the maximum spectral radius among all the uniform supertrees with given number of pendant vertices. [ABSTRACT FROM AUTHOR]

Nuclear pore complex (NPC) is the largest multimeric protein assembly of the eukaryotic cell, which mediates the nucleocytoplasmic transport. The constituent proteins of this assembly (nucleoporins) are present in varying copy numbers to give a size from ~ 60 MDa (yeast) to 112 MDa (human) and share common ancestry with other membrane‐associated complexes such as COPI/COPII and thus share the same structural folds. However, the nucleoporins across species exhibit very low percentage sequence similarity and this reflects in their distinct secondary structure and domain organization. We employed thorough sequence and phylogenetic analysis guided from structure‐based alignments of all the nucleoporins from fungi to metazoans to understand the evolution of NPC. Through evolutionary pressure analysis on various nucleoporins, we deduced that these proteins are under differential selection pressure and hence the homologous interacting partners do not complement each other in the in vitro pull‐down assay. The super tree analysis of all nucleoporins taken together illustrates divergent evolution of nucleoporins and notably, the degree of divergence is more apparent in higher order organisms as compared to lower species. Overall, our results support the hypothesis that the protein–protein interactions in such large multimeric assemblies are species specific in nature and hence their structure and function should also be studied in an organism‐specific manner. [ABSTRACT FROM AUTHOR]

Graphical abstract Highlights • Dated phylogeny for babblers including 402 out of 452 currently recognized species. • Revealed the phylogenetic positions of some taxa previously not studied using newly generated sequences. • A new taxonomy for babblers with seven families and 64 genera, including one new family and one new genus. Abstract The babblers are a diverse group of passerine birds comprising 452 species. The group was long regarded as a "scrap basket" in taxonomic classification schemes. Although several studies have assessed the phylogenetic relationships for subsets of babblers during the past two decades, a comprehensive phylogeny of this group has been lacking. In this study, we used five mitochondrial and seven nuclear loci to generate a dated phylogeny for babblers. This phylogeny includes 402 species (ca. 89% of the overall clade) from 75 genera (97%) and all five currently recognized families, providing a robust basis for taxonomic revision. Our phylogeny supports seven major clades and reveals several non-monophyletic genera. Divergence time estimates indicate that the seven major clades diverged around the same time (18–20 million years ago, Ma) in the early Miocene. We use the phylogeny in a consistent way to propose a new taxonomy, with seven families and 64 genera of babblers, and a new linear sequence of names. [ABSTRACT FROM AUTHOR]

Transcriptome-based exon capture methods provide an approach to recover several hundred markers from genomic DNA, allowing for robust phylogenetic estimation at deep timescales. We applied this method to a highly diverse group of venomous marine snails, Conoidea, for which published phylogenetic trees remain mostly unresolved for the deeper nodes. We targeted 850 protein coding genes (678,322 bp) in ca. 120 samples, spanning all (except one) known families of Conoidea and a broad selection of non-Conoidea neogastropods. The capture was successful for most samples, although capture efficiency decreased when DNA libraries were of insufficient quality and/or quantity (dried samples or low starting DNA concentration) and when targeting the most divergent lineages. An average of 75.4% of proteins was recovered, and the resulting tree, reconstructed using both supermatrix (IQ-tree) and supertree (Astral-II, combined with the Weighted Statistical Binning method) approaches, are almost fully supported. A reconstructed fossil-calibrated tree dates the origin of Conoidea to the Lower Cretaceous. We provide descriptions for two new families. The phylogeny revealed in this study provides a robust framework to reinterpret changes in Conoidea anatomy through time. Finally, we used the phylogeny to test the impact of the venom gland and radular type on diversification rates. Our analyses revealed that repeated losses of the venom gland had no effect on diversification rates, while families with a breadth of radula types showed increases in diversification rates, thus suggesting that trophic ecology may have an impact on the evolution of Conoidea. [ABSTRACT FROM AUTHOR]

The supertree problem asking for a tree displaying a set of consistent input trees has been largely considered for the reconstruction of species trees. Here, we rather explore this framework for the sake of reconstructing a gene tree from a set of input gene trees on partial data. In this perspective, the phylogenetic tree for the species containing the genes of interest can be used to choose among the many possible compatible “supergenetrees”, the most natural criteria being to minimize a reconciliation cost. We develop a variety of algorithmic solutions for the construction and correction of gene trees using the supertree framework. A dynamic programming supertree algorithm for constructing or correcting gene trees, exponential in the number of input trees, is first developed for the less constrained version of the problem. It is then adapted to gene trees with nodes labeled as duplication or speciation, the additional constraint being to preserve the orthology and paralogy relations between genes. Then, a quadratic time algorithm is developed for efficiently correcting an initial gene tree while preserving a set of “trusted” subtrees, as well as the relative phylogenetic distance between them, in both cases of labeled or unlabeled input trees. By applying these algorithms to the set of Ensembl gene trees, we show that this new correction framework is particularly useful to correct weakly-supported duplication nodes. The C++ source code for the algorithms and simulations described in the paper are available at https://github.com/UdeM-LBIT/SuGeT. [ABSTRACT FROM AUTHOR]

An understanding of the balance of interspecific competition and the physical environment in structuring organismal communities is crucial because those communities structured primarily by their physical environment typically exhibit greater sensitivity to environmental change than those structured predominantly by competitive interactions. Here, using detailed phylogenetic and functional information, we investigate this question in macrofaunal assemblages from Northwest Atlantic Ocean continental slopes, a high seas region projected to experience substantial environmental change through the current century. We demonstrate assemblages to be both phylogenetically and functionally under-dispersed, and thus conclude that the physical environment, not competition, may dominate in structuring deep-ocean communities. Further, we find temperature and bottom trawling intensity to be among the environmental factors significantly related to assemblage diversity. These results hint that deep-ocean communities are highly sensitive to their physical environment and vulnerable to environmental perturbation, including by direct disturbance through fishing, and indirectly through the changes brought about by climate change. [ABSTRACT FROM AUTHOR]

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]

Quartet trees displayed by larger phylogenetic trees have long been used as inputs for species tree and supertree reconstruction. Computational constraints prevent the use of all displayed quartets in many practical problems with large numbers of taxa. We introduce the notion of an Efficient Quartet System (EQS) to represent a phylogenetic tree with a subset of the quartets displayed by the tree. We show mathematically that the set of quartets obtained from a tree via an EQS contains all of the combinatorial information of the tree itself. Using performance tests on simulated datasets, we also demonstrate that using an EQS to reduce the number of quartets in both summary method pipelines for species tree inference as well as methods for supertree inference results in only small reductions in accuracy. [ABSTRACT FROM AUTHOR]

A supertree is a connected and acyclic hypergraph. Let S ( m , d , k ) be the set of k -uniform supertrees with m edges and diameter d . In this paper, we determine the supertrees with the first two largest spectral radii among all supertrees in S ( m , d , k ) for 3 ≤ d ≤ m − 1 . [ABSTRACT FROM AUTHOR]

In [8] , Hu and Qi studied the normalized Laplace tensors and normalized Laplace spectra of k -uniform hypergraphs. They also mentioned the question about whether or not 2 is also an H-eigenvalue of the normalized Laplace tensor of a k -uniform hypergraph, when 2 is an eigenvalue of the normalized Laplace tensor (in this case, k is necessarily even). In this paper, we use an expression for the normalized Laplace tensor in terms of the tensor product, together with the diagonal similarity of tensors, the Perron–Frobenius Theorem for nonnegative tensors and nonnegative weakly irreducible tensors, and the concept and properties of odd-colorable hypergraphs introduced in [13] , to give a complete answer to this question. We show that: (i). When k ≡ 2 ( mod 4 ) , then the answer to this question is affirmative. (ii). When k ≡ 0 ( mod 4 ) , then the answer to this question is negative, and in this case, we give an infinite family of counterexamples. We also study the signless normalized Laplace spectra and the signless normalized Laplace H-spectra of hypergraphs. We give structural characterizations of the hypergraphs having the same normalized Laplace spectrum and signless normalized Laplace spectrum, or having the same normalized Laplace H-spectrum and signless normalized Laplace H-spectrum, or both. Finally, we determine the first two k -uniform supertrees of order n with the largest Laplace spectral radii, and also determine the unique k -uniform hypertree of order n with the smallest Laplace spectral radii, in the case when k is even. [ABSTRACT FROM AUTHOR]

Phylogenetics is an intrinsic part of many analyses in evolutionary biology and ecology, and as the amount of data available for these analyses is increasing rapidly the need for automated pipelines to deal with the data also increases. Phylommand is a package of four programs to create, manipulate, and/or analyze phylogenetic trees or pairwise alignments. It is built to be easily implemented in software workflows, both directly on the command prompt, and executed using scripts. Inputs can be taken from standard input or a file, and the behavior of the programs can be changed through switches. By using standard file formats for phylogenetic analyses, such as newick, nexus, phylip, and fasta, phylommand is widely compatible with other software.

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.