Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction

Reply to Abrantes et al. Recombination-Based Perspectives on Lagovirus Classification, Phylogenetic Patterns, and Evolutionary Dynamics. Comment on "Shah et al. Genetic Characteristics and Phylogeographic Dynamics of Lagoviruses, 1988-2021. Viruses 2023, 15, 815"

Recently, Abrantes et al [...].

Order of amino acid recruitment into the genetic code resolved by Last Universal Common Ancestor's protein domains

The current "consensus" order in which amino acids were added to the genetic code is based on potentially biased criteria such as absence of sulfur-containing amino acids from the Urey-Miller experiment which lacked sulfur. Even if inferred perfectly, abiotic abundance might not reflect abundance in the organisms in which the genetic code evolved. Here, we instead exploit the fact that proteins that emerged prior to the genetic code's completion are likely enriched in early amino acids and depleted in late amino acids. We identify the most ancient protein-coding sequences born prior to the archaeal-bacterial split. Amino acid usage in protein sequences whose ancestors date back to a single homolog in the Last Universal Common Ancestor (LUCA) largely matches the consensus order. However, our findings indicate that metal-binding (cysteine and histidine) and sulfur-containing (cysteine and methionine) amino acids were added to the genetic code much earlier than previously thought. Surprisingly, even more ancient protein sequences - those that had already diversified into multiple distinct copies in LUCA - show a different pattern to single copy LUCA sequences: significantly less depleted in the late amino acids tryptophan and tyrosine, and enriched rather than depleted in phenylalanine. This is compatible with at least some of these sequences predating the current genetic code. Their distinct enrichment patterns thus provide hints about earlier, alternative genetic codes.

Accurate, scalable, and fully automated inference of species trees from raw genome assemblies using ROADIES

Inference of species trees plays a crucial role in advancing our understanding of evolutionary relationships and has immense significance for diverse biological and medical applications. Extensive genome sequencing efforts are currently in progress across a broad spectrum of life forms, holding the potential to unravel the intricate branching patterns within the tree of life. However, estimating species trees starting from raw genome sequences is quite challenging, and the current cutting-edge methodologies require a series of error-prone steps that are neither entirely automated nor standardized. In this paper, we present ROADIES, a novel pipeline for species tree inference from raw genome assemblies that is fully automated, easy to use, scalable, free from reference bias, and provides flexibility to adjust the tradeoff between accuracy and runtime. The ROADIES pipeline eliminates the need to align whole genomes, choose a single reference species, or pre-select loci such as functional genes found using cumbersome annotation steps. Moreover, it leverages recent advances in phylogenetic inference to allow multi-copy genes, eliminating the need to detect orthology. Using the genomic datasets released from large-scale sequencing consortia across three diverse life forms (placental mammals, pomace flies, and birds), we show that ROADIES infers species trees that are comparable in quality with the state-of-the-art approaches but in a fraction of the time. By incorporating optimal approaches and automating all steps from assembled genomes to species and gene trees, ROADIES is poised to improve the accuracy, scalability, and reproducibility of phylogenomic analyses.

Complexity of avian evolution revealed by family-level genomes

Despite tremendous efforts in the past decades, relationships among main avian lineages remain heavily debated without a clear resolution. Discrepancies have been attributed to diversity of species sampled, phylogenetic method and the choice of genomic regions1-3. Here we address these issues by analysing the genomes of 363 bird species4 (218 taxonomic families, 92% of total). Using intergenic regions and coalescent methods, we present a well-supported tree but also a marked degree of discordance. The tree confirms that Neoaves experienced rapid radiation at or near the Cretaceous-Palaeogene boundary. Sufficient loci rather than extensive taxon sampling were more effective in resolving difficult nodes. Remaining recalcitrant nodes involve species that are a challenge to model due to either extreme DNA composition, variable substitution rates, incomplete lineage sorting or complex evolutionary events such as ancient hybridization. Assessment of the effects of different genomic partitions showed high heterogeneity across the genome. We discovered sharp increases in effective population size, substitution rates and relative brain size following the Cretaceous-Palaeogene extinction event, supporting the hypothesis that emerging ecological opportunities catalysed the diversification of modern birds. The resulting phylogenetic estimate offers fresh insights into the rapid radiation of modern birds and provides a taxon-rich backbone tree for future comparative studies.

Auto-phylo v2 and auto-phylo-pipeliner: building advanced, flexible, and reusable pipelines for phylogenetic inferences, estimation of variability levels and identification of positively selected amino acid sites

The vast amount of genome sequence data that is available, and that is predicted to drastically increase in the near future, can only be efficiently dealt with by building automated pipelines. Indeed, the Earth Biogenome Project will produce high-quality reference genome sequences for all 1.8 million named living eukaryote species, providing unprecedented insight into the evolution of genes and gene families, and thus on biological issues. Here, new modules for gene annotation, further BLAST search algorithms, further multiple sequence alignment methods, the adding of reference sequences, further tree rooting methods, the estimation of rates of synonymous and nonsynonymous substitutions, and the identification of positively selected amino acid sites, have been added to auto-phylo (version 2), a recently developed software to address biological problems using phylogenetic inferences. Additionally, we present auto-phylo-pipeliner, a graphical user interface application that further facilitates the creation and running of auto-phylo pipelines. Inferences on S-RNase specificity, are critical for both cross-based breeding and for the establishment of pollination requirements. Therefore, as a test case, we develop an auto-phylo pipeline to identify amino acid sites under positive selection, that are, in principle, those determining S-RNase specificity, starting from both non-annotated Prunus genomes and sequences available in public databases.

Xanthomonas rydalmerensis sp. nov., a non-pathogenic member of Group 1 Xanthomonas

Five bacterial isolates were isolated from Fragaria × ananassa in 1976 in Rydalmere, Australia, during routine biosecurity surveillance. Initially, the results of biochemical characterisation indicated that these isolates represented members of the genus Xanthomonas. To determine their species, further analysis was conducted using both phenotypic and genotypic approaches. Phenotypic analysis involved using MALDI-TOF MS and BIOLOG GEN III microplates, which confirmed that the isolates represented members of the genus Xanthomonas but did not allow them to be classified with respect to species. Genome relatedness indices and the results of extensive phylogenetic analysis confirmed that the isolates were members of the genus Xanthomonas and represented a novel species. On the basis the minimal presence of virulence-associated factors typically found in genomes of members of the genus Xanthomonas, we suggest that these isolates are non-pathogenic. This conclusion was supported by the results of a pathogenicity assay. On the basis of these findings, we propose the name Xanthomonas rydalmerensis, with DAR 34855T = ICMP 24941 as the type strain.

Genetic and functional enrichments associated with Enterococcus faecalis isolated from the urinary tract

IMPORTANCE

Urinary tract infection (UTI) is a global health issue that imposes a substantial burden on healthcare systems. Women are disproportionately affected by UTI, with >60% of women experiencing at least one UTI in their lifetime. UTIs can recur, particularly in postmenopausal women, leading to diminished quality of life and potentially life-threatening complications. Understanding how pathogens colonize and survive in the urinary tract is necessary to identify new therapeutic targets that are urgently needed due to rising rates of antimicrobial resistance. How Enterococcus faecalis, a bacterium commonly associated with UTI, adapts to the urinary tract remains understudied. Here, we generated a collection of high-quality closed genome assemblies of clinical urinary E. faecalis isolated from the urine of postmenopausal women that we used alongside detailed clinical metadata to perform a robust comparative genomic investigation of genetic factors that may be involved in E. faecalis survival in the urinary tract.

QR-STAR: A Polynomial-Time Statistically Consistent Method for Rooting Species Trees Under the Coalescent

We address the problem of rooting an unrooted species tree given a set of unrooted gene trees, under the assumption that gene trees evolve within the model species tree under the multispecies coalescent (MSC) model. Quintet Rooting (QR) is a polynomial time algorithm that was recently proposed for this problem, which is based on the theory developed by Allman, Degnan, and Rhodes that proves the identifiability of rooted 5-taxon trees from unrooted gene trees under the MSC. However, although QR had good accuracy in simulations, its statistical consistency was left as an open problem. We present QR-STAR, a variant of QR with an additional step and a different cost function, and prove that it is statistically consistent under the MSC. Moreover, we derive sample complexity bounds for QR-STAR and show that a particular variant of it based on "short quintets" has polynomial sample complexity. Finally, our simulation study under a variety of model conditions shows that QR-STAR matches or improves on the accuracy of QR. QR-STAR is available in open-source form on github.

Phylogenomic branch length estimation using quartets

MOTIVATION

Branch lengths and topology of a species tree are essential in most downstream analyses, including estimation of diversification dates, characterization of selection, understanding adaptation, and comparative genomics. Modern phylogenomic analyses often use methods that account for the heterogeneity of evolutionary histories across the genome due to processes such as incomplete lineage sorting. However, these methods typically do not generate branch lengths in units that are usable by downstream applications, forcing phylogenomic analyses to resort to alternative shortcuts such as estimating branch lengths by concatenating gene alignments into a supermatrix. Yet, concatenation and other available approaches for estimating branch lengths fail to address heterogeneity across the genome.

RESULTS

In this article, we derive expected values of gene tree branch lengths in substitution units under an extension of the multispecies coalescent (MSC) model that allows substitutions with varying rates across the species tree. We present CASTLES, a new technique for estimating branch lengths on the species tree from estimated gene trees that uses these expected values, and our study shows that CASTLES improves on the most accurate prior methods with respect to both speed and accuracy.

AVAILABILITY AND IMPLEMENTATION

CASTLES is available at https://github.com/ytabatabaee/CASTLES.

Inter-species diversity and functional genomic analyses of closed genome assemblies of clinically isolated, megaplasmid-containing Enterococcus raffinosus Er676 and ATCC49464

Enterococcus raffinosus is an understudied member of its genus possessing a characteristic megaplasmid contributing to a large genome size. Although less commonly associated with human infection compared to other enterococci, this species can cause disease and persist in diverse niches such as the gut, urinary tract, blood and environment. Few complete genome assemblies have been published to date for E. raffinosus . In this study, we report the complete assembly of the first clinical urinary E. raffinosus strain, Er676, isolated from a postmenopausal woman with history of recurrent urinary tract infection. We additionally completed the assembly of clinical type strain ATCC49464. Comparative genomic analyses reveal inter-species diversity driven by large accessory genomes. The presence of a conserved megaplasmid indicates it is a ubiquitous and vital genetic feature of E. raffinosus . We find that the E. raffinosus chromosome is enriched for DNA replication and protein biosynthesis genes while the megaplasmid is enriched for transcription and carbohydrate metabolism genes. Prophage analysis suggests that diversity in the chromosome and megaplasmid sequences arises, in part, from horizontal gene transfer. Er676 demonstrated the largest genome size reported to date for E. raffinosus and the highest probability of human pathogenicity. Er676 also possesses multiple antimicrobial resistance genes, of which all but one are encoded on the chromosome, and has the most complete prophage sequences. Complete assembly and comparative analyses of the Er676 and ATCC49464 genomes provide important insight into the inter-species diversity of E. raffinosus that gives it its ability to colonize and persist in the human body. Investigating genetic factors that contribute to the pathogenicity of this species will provide valuable tools to combat diseases caused by this opportunistic pathogen.

Functional and genetic adaptations contributing to Enterococcus faecalis persistence in the female urinary tract

Enterococcus faecalis is the leading Gram-positive bacterial species implicated in urinary tract infection (UTI). An opportunistic pathogen, E. faecalis is a commensal of the human gastrointestinal tract (GIT) and its presence in the GIT is a predisposing factor for UTI. The mechanisms by which E. faecalis colonizes and survives in the urinary tract (UT) are poorly understood, especially in uncomplicated or recurrent UTI. The UT is distinct from the GIT and is characterized by a sparse nutrient landscape and unique environmental stressors. In this study, we isolated and sequenced a collection of 37 clinical E. faecalis strains from the urine of primarily postmenopausal women. We generated 33 closed genome assemblies and four highly contiguous draft assemblies and conducted a comparative genomics to identify genetic features enriched in urinary E. faecalis with respect to E. faecalis isolated from the human GIT and blood. Phylogenetic analysis revealed high diversity among urinary strains and a closer relatedness between urine and gut isolates than blood isolates. Plasmid replicon (rep) typing further underscored possible UT-GIT interconnection identifying nine shared rep types between urine and gut E. faecalis . Both genotypic and phenotypic analysis of antimicrobial resistance among urinary E. faecalis revealed infrequent resistance to front-line UTI antibiotics nitrofurantoin and fluoroquinolones and no vancomycin resistance. Finally, we identified 19 candidate genes enriched among urinary strains that may play a role in adaptation to the UT. These genes are involved in the core processes of sugar transport, cobalamin import, glucose metabolism, and post-transcriptional regulation of gene expression.

IMPORTANCE

Urinary tract infection (UTI) is a global health issue that imposes substantial burden on healthcare systems. Women are disproportionately affected by UTI with >60% of women experiencing at least one UTI in their lifetime. UTIs can recur, particularly in postmenopausal women, leading to diminished quality of life and potentially life-threatening complications. Understanding how pathogens colonize and survive in the urinary tract is necessary to identify new therapeutic targets that are urgently needed due to rising rates of antimicrobial resistance. How Enterococcus faecalis , a bacterium commonly associated with UTI, adapts to the urinary tract remains understudied. Here, we generated a collection of high-quality closed genome assemblies of clinical urinary E. faecalis isolated from the urine of postmenopausal women that we used alongside detailed clinical metadata to perform a robust comparative genomic investigation of genetic factors that may mediate urinary E. faecalis adaptation to the female urinary tract.

DISCO+QR: rooting species trees in the presence of GDL and ILS

Motivation

Genes evolve under processes such as gene duplication and loss (GDL), so that gene family trees are multi-copy, as well as incomplete lineage sorting (ILS); both processes produce gene trees that differ from the species tree. The estimation of species trees from sets of gene family trees is challenging, and the estimation of rooted species trees presents additional analytical challenges. Two of the methods developed for this problem are STRIDE, which roots species trees by considering GDL events, and Quintet Rooting (QR), which roots species trees by considering ILS.

Results

We present DISCO+QR, a new approach to rooting species trees that first uses DISCO to address GDL and then uses QR to perform rooting in the presence of ILS. DISCO+QR operates by taking the input gene family trees and decomposing them into single-copy trees using DISCO and then roots the given species tree using the information in the single-copy gene trees using QR. We show that the relative accuracy of STRIDE and DISCO+QR depend on the properties of the dataset (number of species, genes, rate of gene duplication, degree of ILS and gene tree estimation error), and that each provides advantages over the other under some conditions.

Availability and implementation

DISCO and QR are available in github.

Supplementary information

Supplementary data are available at Bioinformatics Advances online.

Population Structure and Genomic Characteristics of Australian Erysipelothrix rhusiopathiae Reveals Unobserved Diversity in the Australian Pig Industry

Erysipelothrix rhusiopathiae is a bacterial pathogen that is the causative agent of erysipelas in a variety of animals, including swine, emus, turkeys, muskox, caribou, moose, and humans. This study aims to investigate the population structure and genomic features of Australian isolates of E. rhusiopathiae in the Australian pig industry and compare them to the broader scope of isolates worldwide. A total of 178 isolates (154 Australian, seven vaccine isolates, six international isolates, and 11 of unknown origin) in this study were screened against an MLST scheme and publicly available reference isolates, identifying 59 new alleles, with isolates separating into two main single locus variant groups. Investigation with BLASTn revealed the presence of the spaA gene in 171 (96%) of the isolates, with three main groups of SpaA protein sequences observed amongst the isolates. Novel SpaA protein sequences, categorised here as group 3 sequences, consisted of two sequence types forming separate clades to groups 1 and 2, with amino acid variants at positions 195 (D/A), 303 (G/E) and 323(P/L). In addition to the newly identified groups, five new variant positions were identified, 124 (S/N), 307 (Q/R), 323 (P/L), 379 (M/I), and 400 (V/I). Resistance screening identified genes related to lincomycin, streptomycin, erythromycin, and tetracycline resistance. Of the 29 isolates carrying these resistance genes, 82% belonged to SpaA group 2-N101S (n = 22) or 2-N101S-I257L (n = 2). In addition, 79% (n = 23) of these 29 isolates belonged to MLST group ST 5. Our results illustrate that Australia appears to have a unique diversity of E. rhusiopathiae isolates in pig production industries within the wider global context of isolates.

Genomic remnants of ancestral methanogenesis and hydrogenotrophy in Archaea drive anaerobic carbon cycling

Anaerobic methane metabolism is among the hallmarks of Archaea, originating very early in their evolution. Here, we show that the ancestor of methane metabolizers was an autotrophic CO₂-reducing hydrogenotrophic methanogen that possessed the two main complexes, methyl-CoM reductase (Mcr) and tetrahydromethanopterin-CoM methyltransferase (Mtr), the anaplerotic hydrogenases Eha and Ehb, and a set of other genes collectively called "methanogenesis markers" but could not oxidize alkanes. Overturning recent inferences, we demonstrate that methyl-dependent hydrogenotrophic methanogenesis has emerged multiple times independently, either due to a loss of Mtr while Mcr is inherited vertically or from an ancient lateral acquisition of Mcr. Even if Mcr is lost, Mtr, Eha, Ehb, and the markers can persist, resulting in mixotrophic metabolisms centered around the Wood-Ljungdahl pathway. Through their methanogenesis remnants, Thorarchaeia and two newly reconstructed order-level lineages in Archaeoglobi and Bathyarchaeia act as metabolically versatile players in carbon cycling of anoxic environments across the globe.

Sharks Provide Evidence for a Highly Complex TNFSF Repertoire in the Jawed Vertebrate Ancestor

Cytokines of the TNF superfamily (TNFSF) control many immunological processes and are implicated in the etiology of many immune disorders and diseases. Despite their obvious biological importance, the TNFSF repertoires of many species remain poorly characterized. In this study, we perform detailed bioinformatic, phylogenetic, and syntenic analyses of five cartilaginous fish genomes to identify their TNFSF repertoires. Strikingly, we find that shark genomes harbor ∼30 TNFSF genes, more than any other vertebrate examined to date and substantially more than humans. This is due to better retention of the ancestral jawed vertebrate TNFSF repertoire than any other jawed vertebrate lineage, combined with lineage-specific gene family expansions. All human TNFSFs appear in shark genomes, except for lymphotoxin-α (LTA; TNFSF1) and TNF (TNFSF2), and CD70 (TNFSF7) and 4-1BBL (TNFSF9), which diverged by tandem duplications early in tetrapod and mammalian evolution, respectively. Although lacking one-to-one LTA and TNF orthologs, sharks have evolved lineage-specific clusters of LTA/TNF co-orthologs. Other key findings include the presence of two BAFF (TNFSF13B) genes along with orthologs of APRIL (TNFSF13) and BALM (TNFSF13C) in sharks, and that all cartilaginous fish genomes harbor an ∼400-million-year-old cluster of multiple FASLG (TNFSF6) orthologs. Finally, sharks have retained seven ancestral jawed vertebrate TNFSF genes lost in humans. Taken together, our data indicate that the jawed vertebrate ancestor possessed a much larger and diverse TNFSF repertoire than previously hypothesized and oppose the idea that the cartilaginous fish immune system is “primitive” compared with that of mammals.

Early divergence of translation initiation and elongation factors

Protein translation is a foundational attribute of all living cells. The translation function carried out by the ribosome critically depends on an assortment of protein interaction partners, collectively referred to as the translation machinery. Various studies suggest that the diversification of the translation machinery occurred prior to the last universal common ancestor, yet it is unclear whether the predecessors of the extant translation machinery factors were functionally distinct from their modern counterparts. Here we reconstructed the shared ancestral trajectory and subsequent evolution of essential translation factor GTPases, elongation factor EF-Tu (aEF-1A/eEF-1A), and initiation factor IF2 (aIF5B/eIF5B). Based upon their similar functions and structural homologies, it has been proposed that EF-Tu and IF2 emerged from an ancient common ancestor. We generated the phylogenetic tree of IF2 and EF-Tu proteins and reconstructed ancestral sequences corresponding to the deepest nodes in their shared evolutionary history, including the last common IF2 and EF-Tu ancestor. By identifying the residue and domain substitutions, as well as structural changes along the phylogenetic history, we developed an evolutionary scenario for the origins, divergence and functional refinement of EF-Tu and IF2 proteins. Our analyses suggest that the common ancestor of IF2 and EF-Tu was an IF2-like GTPase protein. Given the central importance of the translation machinery to all cellular life, its earliest evolutionary constraints and trajectories are key to characterizing the universal constraints and capabilities of cellular evolution.

Quintet Rooting: rooting species trees under the multi-species coalescent model

Motivation

Rooted species trees are a basic model with multiple applications throughout biology, including understanding adaptation, biodiversity, phylogeography and co-evolution. Because most species tree estimation methods produce unrooted trees, methods for rooting these trees have been developed. However, most rooting methods either rely on prior biological knowledge or assume that evolution is close to clock-like, which is not usually the case. Furthermore, most prior rooting methods do not account for biological processes that create discordance between gene trees and species trees.

Results

We present Quintet Rooting (QR), a method for rooting species trees based on a proof of identifiability of the rooted species tree under the multi-species coalescent model established by Allman, Degnan and Rhodes (J. Math. Biol., 2011). We show that QR is generally more accurate than other rooting methods, except under extreme levels of gene tree estimation error.

Availability and implementation

Quintet Rooting is available in open source form at https://github.com/ytabatabaee/Quintet-Rooting. The simulated datasets used in this study are from a prior study and are available at https://www.ideals.illinois.edu/handle/2142/55319. The biological dataset used in this study is also from a prior study and is available at http://gigadb.org/dataset/101041.

Contact

warnow@illinois.edu

Supplementary information

Supplementary data are available at Bioinformatics online.

Accounting for errors in data improves divergence time estimates in single-cell cancer evolution

Single-cell sequencing provides a new way to explore the evolutionary history of cells. Compared to traditional bulk sequencing, where a population of heterogeneous cells is pooled to form a single observation, single-cell sequencing isolates and amplifies genetic material from individual cells, thereby preserving the information about the origin of the sequences. However, single-cell data is more error-prone than bulk sequencing data due to the limited genomic material available per cell. Here, we present error and mutation models for evolutionary inference of single-cell data within a mature and extensible Bayesian framework, BEAST2. Our framework enables integration with biologically informative models such as relaxed molecular clocks and population dynamic models. Our simulations show that modeling errors increase the accuracy of relative divergence times and substitution parameters. We reconstruct the phylogenetic history of a colorectal cancer patient and a healthy patient from single-cell DNA sequencing data. We find that the estimated times of terminal splitting events are shifted forward in time compared to models which ignore errors. We observed that not accounting for errors can overestimate the phylogenetic diversity in single-cell DNA sequencing data. We estimate that 30-50% of the apparent diversity can be attributed to error. Our work enables a full Bayesian approach capable of accounting for errors in the data within the integrative Bayesian software framework BEAST2.

An Evaluation of Phylogenetic Workflows in Viral Molecular Epidemiology

The use of viral sequence data to inform public health intervention has become increasingly common in the realm of epidemiology. Such methods typically utilize multiple sequence alignments and phylogenies estimated from the sequence data. Like all estimation techniques, they are error prone, yet the impacts of such imperfections on downstream epidemiological inferences are poorly understood. To address this, we executed multiple commonly used viral phylogenetic analysis workflows on simulated viral sequence data, modeling Human Immunodeficiency Virus (HIV), Hepatitis C Virus (HCV), and Ebolavirus, and we computed multiple methods of accuracy, motivated by transmission-clustering techniques. For multiple sequence alignment, MAFFT consistently outperformed MUSCLE and Clustal Omega, in both accuracy and runtime. For phylogenetic inference, FastTree 2, IQ-TREE, RAxML-NG, and PhyML had similar topological accuracies, but branch lengths and pairwise distances were consistently most accurate in phylogenies inferred by RAxML-NG. However, FastTree 2 was the fastest, by orders of magnitude, and when the other tools were used to optimize branch lengths along a fixed FastTree 2 topology, the resulting phylogenies had accuracies that were indistinguishable from their original counterparts, but with a fraction of the runtime.

Completing gene trees without species trees in sub-quadratic time

MOTIVATION

As genome-wide reconstruction of phylogenetic trees becomes more widespread, limitations of available data are being appreciated more than ever before. One issue is that phylogenomic datasets are riddled with missing data, and gene trees, in particular, almost always lack representatives from some species otherwise available in the dataset. Since many downstream applications of gene trees require or can benefit from access to complete gene trees, it will be beneficial to algorithmically complete gene trees. Also, gene trees are often unrooted, and rooting them is useful for downstream applications. While completing and rooting a gene tree with respect to a given species tree has been studied, those problems are not studied in depth when we lack such a reference species tree.

RESULTS

We study completion of gene trees without a need for a reference species tree. We formulate an optimization problem to complete the gene trees while minimizing their quartet distance to the given set of gene trees. We extend a seminal algorithm by Brodal et al. to solve this problem in quasi-linear time. In simulated studies and on a large empirical data, we show that completion of gene trees using other gene trees is relatively accurate and, unlike the case where a species tree is available, is unbiased.

AVAILABILITY AND IMPLEMENTATION

Our method, tripVote, is available at https://github.com/uym2/tripVote.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Chlamydia pecorum Ovine Abortion: Associations between Maternal Infection and Perinatal Mortality

Chlamydia pecorum is a common gastrointestinal inhabitant of livestock but infections can manifest in a broad array of clinical presentations and in a range of host species. While C. pecorum is a known cause of ovine abortion, clinical cases have only recently been described in detail. Here, the prevalence and sequence types (STs) of C. pecorum in ewes from a property experiencing high levels of perinatal mortality (PNM) in New South Wales (NSW), Australia, were investigated using serological and molecular methods. Ewes that were PNM+ were statistically more likely to test seropositive compared to PNM− ewes and displayed higher antibody titres; however, an increase in chlamydial shedding from either the rectum, vagina or conjunctiva of PNM+ ewes was not observed. Multilocus sequence typing (MLST) indicated that C. pecorum ST23 was the major ST shed by ewes in the flock, was the only ST identified from the vaginal site, and was the same ST detected within aborted foetal tissues. Whole genome sequencing of C. pecorum isolated from one abortion case revealed that the C. pecorum plasmid (pCpec) contained a unique deletion in coding sequence 1 (CDS1) that was also present in C. pecorum ST23 shed from the ewes. A further unique deletion was noted in a polymorphic membrane protein gene (pmpG) of the C. pecorum chromosome, which warrants further investigation given the role of PmpG in host cell adherence and tissue tropism.This study describes novel infection parameters in a sheep flock experiencing C. pecorum-associated perinatal mortality, provides the first genomic data from an abortigenic C. pecorum strain, and raises questions about possible links between unique genetic features of this strain and C. pecorum abortion.

Ultra-Conserved Elements and morphology reciprocally illuminate conflicting phylogenetic hypotheses in Chalcididae (Hymenoptera, Chalcidoidea)

Recent technical advances combined with novel computational approaches have promised the acceleration of our understanding of the tree of life. However, when it comes to hyperdiverse and poorly known groups of invertebrates, studies are still scarce. As published phylogenies will be rarely challenged by future taxonomists, careful attention must be paid to potential analytical bias. We present the first molecular phylogenetic hypothesis for the family Chalcididae, a group of parasitoid wasps, with a representative sampling (144 ingroups and seven outgroups) that covers all described subfamilies and tribes, and 82% of the known genera. Analyses of 538 Ultra-Conserved Elements (UCEs) with supermatrix (RAxML and IQTREE) and gene tree reconciliation approaches (ASTRAL, ASTRID) resulted in highly supported topologies in overall agreement with morphology but reveal conflicting topologies for some of the deepest nodes. To resolve these conflicts, we explored the phylogenetic tree space with clustering and gene genealogy interrogation methods, analyzed marker and taxon properties that could bias inferences and performed a thorough morphological analysis (130 characters encoded for 40 taxa representative of the diversity). This joint analysis reveals that UCEs enable attainment of resolution between ancestry and convergent/divergent evolution when morphology is not informative enough, but also shows that a systematic exploration of bias with different analytical methods and a careful analysis of morphological features is required to prevent publication of artifactual results. We highlight a GC content bias for maximum-likelihood approaches, an artifactual mid-point rooting of the ASTRAL tree and a deleterious effect of high percentage of missing data (>85% missing UCEs) on gene tree reconciliation methods. Based on the results we propose a new classification of the family into eight subfamilies and ten tribes that lay the foundation for future studies on the evolutionary history of Chalcididae.

Exploring systematic biases, rooting methods and morphological evidence to unravel the evolutionary history of the genus Ficus (Moraceae)

Despite many attempts in the Sanger sequencing era, the phylogeny of fig trees remains unresolved, which limits our ability to analyze the evolution of key traits that may have contributed to their evolutionary and ecological success. We used restriction-site-associated DNA sequencing (c. 420 kb) and 102 morphological characters to elucidate the relationships between 70 species of Ficus. To increase phylogenetic information for higher-level relationships, we targeted conserved regions and assembled paired reads into long loci to enable the retrieval of homologous loci in outgroup genomes. We compared morphological and molecular results to highlight discrepancies and reveal possible inference bias. For the first time, we recovered a monophyletic subgenus Urostigma (stranglers) and a clade with all gynodioecious Ficus. However, we show, with a new approach based on iterative principal component analysis, that it is not (and will probably never be) possible to homogenize evolutionary rates and GC content for all taxa before phylogenetic inference. Four competing positions for the root of the molecular tree are possible. The placement of section Pharmacosycea as sister to other fig trees is not supported by morphological data and considered a result of a long-branch attraction artefact to the outgroups. Regarding morphological features and indirect evidence from the pollinator tree of life, the topology that divides Ficus into monoecious versus gynodioecious species appears most plausible. It seems most likely that the ancestor of fig trees was a freestanding tree and active pollination is inferred as the ancestral state, contrary to previous hypotheses. However, ambiguity remains on the ancestral breeding system. Despite morphological plasticity, we advocate restoring a central role to morphology in our understanding of the evolution of Ficus, as it can help detect systematic errors that appear more pronounced with larger molecular datasets.

Assessing Confidence in Root Placement on Phylogenies: An Empirical Study Using Non-Reversible Models for Mammals

Using time-reversible Markov models is a very common practice in phylogenetic analysis, because although we expect many of their assumptions to be violated by empirical data, they provide high computational efficiency. However, these models lack the ability to infer the root placement of the estimated phylogeny. In order to compensate for the inability of these models to root the tree, many researchers use external information such as using outgroup taxa or additional assumptions such as molecular clocks. In this study, we investigate the utility of nonreversible models to root empirical phylogenies and introduce a new bootstrap measure, the rootstrap, which provides information on the statistical support for any given root position. [Bootstrap; nonreversible models; phylogenetic inference; root estimation.]

Root Digger: a root placement program for phylogenetic trees

BACKGROUND

In phylogenetic analysis, it is common to infer unrooted trees. However, knowing the root location is desirable for downstream analyses and interpretation. There exist several methods to recover a root, such as molecular clock analysis (including midpoint rooting) or rooting the tree using an outgroup. Non-reversible Markov models can also be used to compute the likelihood of a potential root position.

RESULTS

We present a software called RootDigger which uses a non-reversible Markov model to compute the most likely root location on a given tree and to infer a confidence value for each possible root placement. We find that RootDigger is successful at finding roots when compared to similar tools such as IQ-TREE and MAD, and will occasionally outperform them. Additionally, we find that the exhaustive mode of RootDigger is useful in quantifying and explaining uncertainty in rooting positions.

CONCLUSIONS

RootDigger can be used on an existing phylogeny to find a root, or to asses the uncertainty of the root placement. RootDigger is available under the MIT licence at https://www.github.com/computations/root_digger .

HIV Care Prioritization Using Phylogenetic Branch Length

BACKGROUND

The structure of the HIV transmission networks can be dictated by just a few individuals. Public health intervention, such as ensuring people living with HIV adhere to antiretroviral therapy and remain virally suppressed, can help control the spread of the virus. However, such intervention requires using limited public health resource allocations. Determining which individuals are most at risk of transmitting HIV could allow public health officials to focus their limited resources on these individuals.

SETTING

Molecular epidemiology can help prioritize people living with HIV by patterns of transmission inferred from their sampled viral sequences. Such prioritization has been previously suggested and performed by monitoring cluster growth. In this article, we introduce Prioritization using AnCesTral edge lengths (ProACT), a phylogenetic approach for prioritizing individuals living with HIV.

METHODS

ProACT starts from a phylogeny inferred from sequence data and orders individuals according to their terminal branch length, breaking ties using ancestral branch lengths. We evaluated ProACT on a real data set of 926 HIV-1 subtype B pol data obtained in San Diego between 2005 and 2014 and a simulation data set modeling the same epidemic. Prioritization methods are compared by their ability to predict individuals who transmit most after the prioritization.

RESULTS

Across all simulation conditions and most real data sampling conditions, ProACT outperformed monitoring cluster growth for multiple metrics of prioritization efficacy.

CONCLUSION

The simple strategy used by ProACT improves the effectiveness of prioritization compared with state-of-the-art methods that rely on monitoring the growth of transmission clusters defined based on genetic distance.

Assessing Uncertainty in the Rooting of the SARS-CoV-2 Phylogeny

The rooting of the SARS-CoV-2 phylogeny is important for understanding the origin and early spread of the virus. Previously published phylogenies have used different rootings that do not always provide consistent results. We investigate several different strategies for rooting the SARS-CoV-2 tree and provide measures of statistical uncertainty for all methods. We show that methods based on the molecular clock tend to place the root in the B clade, whereas methods based on outgroup rooting tend to place the root in the A clade. The results from the two approaches are statistically incompatible, possibly as a consequence of deviations from a molecular clock or excess back-mutations. We also show that none of the methods provide strong statistical support for the placement of the root in any particular edge of the tree. These results suggest that phylogenetic evidence alone is unlikely to identify the origin of the SARS-CoV-2 virus and we caution against strong inferences regarding the early spread of the virus based solely on such evidence.

Log Transformation Improves Dating of Phylogenies

Phylogenetic trees inferred from sequence data often have branch lengths measured in the expected number of substitutions and therefore, do not have divergence times estimated. These trees give an incomplete view of evolutionary histories since many applications of phylogenies require time trees. Many methods have been developed to convert the inferred branch lengths from substitution unit to time unit using calibration points, but none is universally accepted as they are challenged in both scalability and accuracy under complex models. Here, we introduce a new method that formulates dating as a nonconvex optimization problem where the variance of log-transformed rate multipliers is minimized across the tree. On simulated and real data, we show that our method, wLogDate, is often more accurate than alternatives and is more robust to various model assumptions.

Assessing the accuracy of phylogenetic rooting methods on prokaryotic gene families

Almost all standard phylogenetic methods for reconstructing gene trees result in unrooted trees; yet, many of the most useful applications of gene trees require that the gene trees be correctly rooted. As a result, several computational methods have been developed for inferring the root of unrooted gene trees. However, the accuracy of such methods has never been systematically evaluated on prokaryotic gene families, where horizontal gene transfer is often one of the dominant evolutionary events driving gene family evolution. In this work, we address this gap by conducting a thorough comparative evaluation of five different rooting methods using large collections of both simulated and empirical prokaryotic gene trees. Our simulation study is based on 6000 true and reconstructed gene trees on 100 species and characterizes the rooting accuracy of the four methods under 36 different evolutionary conditions and 3 levels of gene tree reconstruction error. The empirical study is based on a large, carefully designed data set of 3098 gene trees from 504 bacterial species (406 Alphaproteobacteria and 98 Cyanobacteria) and reveals insights that supplement those gleaned from the simulation study. Overall, this work provides several valuable insights into the accuracy of the considered methods that will help inform the choice of rooting methods to use when studying microbial gene family evolution. Among other findings, this study identifies parsimonious Duplication-Transfer-Loss (DTL) rooting and Minimal Ancestor Deviation (MAD) rooting as two of the most accurate gene tree rooting methods for prokaryotes and specifies the evolutionary conditions under which these methods are most accurate, demonstrates that DTL rooting is highly sensitive to high evolutionary rates and gene tree error, and that rooting methods based on branch-lengths are generally robust to gene tree reconstruction error.

From pairs of most similar sequences to phylogenetic best matches

BACKGROUND

Many of the commonly used methods for orthology detection start from mutually most similar pairs of genes (reciprocal best hits) as an approximation for evolutionary most closely related pairs of genes (reciprocal best matches). This approximation of best matches by best hits becomes exact for ultrametric dissimilarities, i.e., under the Molecular Clock Hypothesis. It fails, however, whenever there are large lineage specific rate variations among paralogous genes. In practice, this introduces a high level of noise into the input data for best-hit-based orthology detection methods.

RESULTS

If additive distances between genes are known, then evolutionary most closely related pairs can be identified by considering certain quartets of genes provided that in each quartet the outgroup relative to the remaining three genes is known. A priori knowledge of underlying species phylogeny greatly facilitates the identification of the required outgroup. Although the workflow remains a heuristic since the correct outgroup cannot be determined reliably in all cases, simulations with lineage specific biases and rate asymmetries show that nearly perfect results can be achieved. In a realistic setting, where distances data have to be estimated from sequence data and hence are noisy, it is still possible to obtain highly accurate sets of best matches.

CONCLUSION

Improvements of tree-free orthology assessment methods can be expected from a combination of the accurate inference of best matches reported here and recent mathematical advances in the understanding of (reciprocal) best match graphs and orthology relations.

AVAILABILITY

Accompanying software is available at https://github.com/david-schaller/AsymmeTree.

TreeSwift: A massively scalable Python tree package

Phylogenetic trees are essential to evolutionary biology, and numerous methods exist that attempt to extract phylogenetic information applicable to a wide range of disciplines, such as epidemiology and metagenomics. Currently, the three main Python packages for trees are Bio.Phylo, DendroPy, and the ETE Toolkit, but as dataset sizes grow, parsing and manipulating ultra-large trees becomes impractical for these tools. To address this issue, we present TreeSwift, a user-friendly and massively scalable Python package for traversing and manipulating trees that is ideal for algorithms performed on ultra-large trees.

Fast speciations and slow genes: uncovering the root of living canids

Despite ongoing efforts relying on computationally intensive tree-building methods and large datasets, the deeper phylogenetic relationships between living canid genera remain controversial. We demonstrate that this issue arises fundamentally from the uncertainty of root placement as a consequence of the short length of the branch connecting the major canid clades, which probably resulted from a fast radiation during the early diversification of extant Canidae. Using both nuclear and mitochondrial genes, we investigate the position of the canid root and its consistency by using three rooting methods. We find that mitochondrial genomes consistently retrieve a root node separating the tribe Canini from the remaining canids, whereas nuclear data mostly recover a root that places the Urocyon foxes as the sister lineage of living canids. We demonstrate that, to resolve the canid root, the nuclear segments sequenced so far are significantly less informative than mitochondrial genomes. We also propose that short intervals between speciations obscure the place of the true root, because methods are susceptible to stochastic error in the presence of short internal branches near the root.

Evolution of the Genes Encoding Effector Candidates Within Multiple Pathotypes of Magnaporthe oryzae

Magnaporthe oryzae infects rice, wheat, and many grass species in the Poaceae family by secreting protein effectors. Here, we analyzed the distribution, sequence variation, and genomic context of effector candidate (EFC) genes in 31 isolates that represent five pathotypes of M. oryzae, three isolates of M. grisea, a sister species of M. oryzae, and one strain each for eight species in the family Magnaporthaceae to investigate how the host range expansion of M. oryzae has likely affected the evolution of effectors. We used the EFC genes of M. oryzae strain 70-15, whose genome has served as a reference for many comparative genomics analyses, to identify their homologs in these strains. We also analyzed the previously characterized avirulence (AVR) genes and single-copy orthologous (SCO) genes in these strains, which showed that the EFC and AVR genes evolved faster than the SCO genes. The EFC and AVR repertoires among M. oryzae pathotypes varied widely probably because adaptation to individual hosts exerted different types of selection pressure. Repetitive DNA elements appeared to have caused the variation of some EFC genes. Lastly, we analyzed expression patterns of the AVR and EFC genes to test the hypothesis that such genes are preferentially expressed during host infection. This comprehensive dataset serves as a foundation for future studies on the genetic basis of the evolution and host specialization in M. oryzae.

TreeCluster: Clustering biological sequences using phylogenetic trees

Clustering homologous sequences based on their similarity is a problem that appears in many bioinformatics applications. The fact that sequences cluster is ultimately the result of their phylogenetic relationships. Despite this observation and the natural ways in which a tree can define clusters, most applications of sequence clustering do not use a phylogenetic tree and instead operate on pairwise sequence distances. Due to advances in large-scale phylogenetic inference, we argue that tree-based clustering is under-utilized. We define a family of optimization problems that, given an arbitrary tree, return the minimum number of clusters such that all clusters adhere to constraints on their heterogeneity. We study three specific constraints, limiting (1) the diameter of each cluster, (2) the sum of its branch lengths, or (3) chains of pairwise distances. These three problems can be solved in time that increases linearly with the size of the tree, and for two of the three criteria, the algorithms have been known in the theoretical computer scientist literature. We implement these algorithms in a tool called TreeCluster, which we test on three applications: OTU clustering for microbiome data, HIV transmission clustering, and divide-and-conquer multiple sequence alignment. We show that, by using tree-based distances, TreeCluster generates more internally consistent clusters than alternatives and improves the effectiveness of downstream applications. TreeCluster is available at https://github.com/niemasd/TreeCluster.

A Two-State Model of Tree Evolution and Its Applications to Alu Retrotransposition

Models of tree evolution have mostly focused on capturing the cladogenesis processes behind speciation. Processes that derive the evolution of genomic elements, such as repeats, are not necessarily captured by these existing models. In this article, we design a model of tree evolution that we call the dual-birth model, and we show how it can be useful in studying the evolution of short Alu repeats found in the human genome in abundance. The dual-birth model extends the traditional birth-only model to have two rates of propagation, one for active nodes that propagate often, and another for inactive nodes, that with a lower rate, activate and start propagating. Adjusting the ratio of the rates controls the expected tree balance. We present several theoretical results under the dual-birth model, introduce parameter estimation techniques, and study the properties of the model in simulations. We then use the dual-birth model to estimate the number of active Alu elements and their rates of propagation and activation in the human genome based on a large phylogenetic tree that we build from close to one million Alu sequences.

A phylogenetic examination of host use evolution in the quinaria and testacea groups of Drosophila

Adaptive radiations provide an opportunity to examine complex evolutionary processes such as ecological specialization and speciation. While a well-resolved phylogenetic hypothesis is critical to completing such studies, the rapid rates of evolution in these groups can impede phylogenetic studies. Here we study the quinaria and testacea species groups of the immigrans-tripunctata radiation of Drosophila, which represent a recent adaptive radiation and are a developing model system for ecological genetics. We were especially interested in understanding host use evolution in these species. In order to infer a phylogenetic hypothesis for this group we sampled loci from both the nuclear genome and the mitochondrial DNA to develop a dataset of 43 protein-coding loci for these two groups along with their close relatives in the immigrans-tripunctata radiation. We used this dataset to examine their evolutionary relationships along with the evolution of feeding behavior. Our analysis recovers strong support for the monophyly of the testacea but not the quinaria group. Results from our ancestral state reconstruction analysis suggests that the ancestor of the testacea and quinaria groups exhibited mushroom-feeding. Within the quinaria group, we infer that transition to vegetative feeding occurred twice, and that this transition did not coincide with a genome-wide change in the rate of protein evolution.

TreeShrink: fast and accurate detection of outlier long branches in collections of phylogenetic trees

BACKGROUND

Sequence data used in reconstructing phylogenetic trees may include various sources of error. Typically errors are detected at the sequence level, but when missed, the erroneous sequences often appear as unexpectedly long branches in the inferred phylogeny.

RESULTS

We propose an automatic method to detect such errors. We build a phylogeny including all the data then detect sequences that artificially inflate the tree diameter. We formulate an optimization problem, called the k-shrink problem, that seeks to find k leaves that could be removed to maximally reduce the tree diameter. We present an algorithm to find the exact solution for this problem in polynomial time. We then use several statistical tests to find outlier species that have an unexpectedly high impact on the tree diameter. These tests can use a single tree or a set of related gene trees and can also adjust to species-specific patterns of branch length. The resulting method is called TreeShrink. We test our method on six phylogenomic biological datasets and an HIV dataset and show that the method successfully detects and removes long branches. TreeShrink removes sequences more conservatively than rogue taxon removal and often reduces gene tree discordance more than rogue taxon removal once the amount of filtering is controlled.

CONCLUSIONS

TreeShrink is an effective method for detecting sequences that lead to unrealistically long branch lengths in phylogenetic trees. The tool is publicly available at https://github.com/uym2/TreeShrink .