Fast and accurate branch lengths estimation for phylogenomic trees

Accurate Recapitulation of Chikungunya Virus Complete Coding Sequence Phylogeny Using Variable Genome Regions for Genomic Surveillance

Chikungunya virus (CHIKV) is transmitted by mosquito bites and causes chikungunya fever (CHIKF). CHIKV has a single-stranded RNA genome and belongs to a single serotype with three genotypes. The Asian lineage has recently emerged in the Western Hemisphere, likely due to travel-associated introduction. Genetic variation accumulates in the CHIKV genome as the virus replicates, creating new lineages. Whole genome sequencing is ideal for studying virus evolution and spread but is expensive and complex. This study investigated whether specific, highly variable regions of the CHIKV genome could recapitulate the phylogeny obtained with a complete coding sequence (CDS). Our results revealed that concatenated highly variable regions accurately reconstructed CHIKV phylogeny, exhibiting statistically indistinguishable branch lengths and tree confidence compared to CDS. In addition, these regions adequately inferred the evolutionary relationships among CHIKV isolates from the American outbreak with similar results to the CDS. This finding suggests that highly variable regions can effectively capture the evolutionary relationships among CHIKV isolates, offering a simpler approach for future studies. This approach could be particularly valuable for large-scale surveillance efforts.

Branch Length Transforms using Optimal Tree Metric Matching

The abundant discordance between evolutionary relationships across the genome has rekindled interest in ways of comparing and averaging trees on a shared leaf set. However, most attempts at reconciling trees have focused on tree topology, producing metrics for comparing topologies and methods for computing median tree topologies. Using branch lengths, however, has been more elusive, due to several challenges. Species tree branch lengths can be measured in many units, often different from gene trees. Moreover, rates of evolution change across the genome, the species tree, and specific branches of gene trees. These factors compound the stochasticity of coalescence times. Thus, branch lengths are highly heterogeneous across both the genome and the tree. For many downstream applications in phylogenomic analyses, branch lengths are as important as the topology, and yet, existing tools to compare and combine weighted trees are limited. In this paper, we make progress on the question of mapping one tree to another, incorporating both topology and branch length. We define a series of computational problems to formalize finding the best transformation of one tree to another while maintaining its topology and other constraints. We show that all these problems can be solved in quadratic time and memory using a linear algebraic formulation coupled with dynamic programming preprocessing. Our formulations lead to convex optimization problems, with efficient and theoretically optimal solutions. While many applications can be imagined for this framework, we apply it to measure species tree branch lengths in the unit of the expected number of substitutions per site while allowing divergence from ultrametricity across the tree. In these applications, our method matches or surpasses other methods designed directly for solving those problems. Thus, our approach provides a versatile toolkit that finds applications in similar evolutionary questions.

Code availability

The software is available at https://github.com/shayesteh99/TCMM.git .

Data availability

Data are available on Github https://github.com/shayesteh99/TCMM-Data.git .

Antivirals for Broader Coverage against Human Coronaviruses

Coronaviruses (CoVs) are enveloped positive-sense single-stranded RNA viruses with a genome that is 27-31 kbases in length. Critical genes include the spike (S), envelope (E), membrane (M), nucleocapsid (N) and nine accessory open reading frames encoding for non-structural proteins (NSPs) that have multiple roles in the replication cycle and immune evasion (1). There are seven known human CoVs that most likely appeared after zoonotic transfer, the most recent being SARS-CoV-2, responsible for the COVID-19 pandemic. Antivirals that have been approved by the FDA for use against COVID-19 such as Paxlovid can target and successfully inhibit the main protease (MPro) activity of multiple human CoVs; however, alternative proteomes encoded by CoV genomes have a closer genetic similarity to each other, suggesting that antivirals could be developed now that target future CoVs. New zoonotic introductions of CoVs to humans are inevitable and unpredictable. Therefore, new antivirals are required to control not only the next human CoV outbreak but also the four common human CoVs (229E, OC43, NL63, HKU1) that circulate frequently and to contain sporadic outbreaks of the severe human CoVs (SARS-CoV, MERS and SARS-CoV-2). The current study found that emerging antiviral drugs, such as Paxlovid, could target other CoVs, but only SARS-CoV-2 is known to be targeted in vivo. Other drugs which have the potential to target other human CoVs are still within clinical trials and are not yet available for public use. Monoclonal antibody (mAb) treatment and vaccines for SARS-CoV-2 can reduce mortality and hospitalisation rates; however, they target the Spike protein whose sequence mutates frequently and drifts. Spike is also not applicable for targeting other HCoVs as these are not well-conserved sequences among human CoVs. Thus, there is a need for readily available treatments globally that target all seven human CoVs and improve the preparedness for inevitable future outbreaks. Here, we discuss antiviral research, contributing to the control of common and severe CoV replication and transmission, including the current SARS-CoV-2 outbreak. The aim was to identify common features of CoVs for antivirals, biologics and vaccines that could reduce the scientific, political, economic and public health strain caused by CoV outbreaks now and in the future.

OrthoMaM v12: a database of curated single-copy ortholog alignments and trees to study mammalian evolutionary genomics

To date, the databases built to gather information on gene orthology do not provide end-users with descriptors of the molecular evolution information and phylogenetic pattern of these orthologues. In this context, we developed OrthoMaM, a database of ORTHOlogous MAmmalian Markers describing the evolutionary dynamics of coding sequences in mammalian genomes. OrthoMaM version 12 includes 15,868 alignments of orthologous coding sequences (CDS) from the 190 complete mammalian genomes currently available. All annotations and 1-to-1 orthology assignments are based on NCBI. Orthologous CDS can be mined for potential informative markers at the different taxonomic levels of the mammalian tree. To this end, several evolutionary descriptors of DNA sequences are provided for querying purposes (e.g. base composition and relative substitution rate). The graphical web interface allows the user to easily browse and sort the results of combined queries. The corresponding multiple sequence alignments and ML trees, inferred using state-of-the art approaches, are available for download both at the nucleotide and amino acid levels. OrthoMaM v12 can be used by researchers interested either in reconstructing the phylogenetic relationships of mammalian taxa or in understanding the evolutionary dynamics of coding sequences in their genomes. OrthoMaM is available for browsing, querying and complete or filtered download at https://orthomam.mbb.cnrs.fr/.

A Guide to Phylogenomic Inference

Phylogenomics aims at reconstructing the evolutionary histories of organisms taking into account whole genomes or large fractions of genomes. Phylogenomics has significant applications in fields such as evolutionary biology, systematics, comparative genomics, and conservation genetics, providing valuable insights into the origins and relationships of species and contributing to our understanding of biological diversity and evolution. This chapter surveys phylogenetic concepts and methods aimed at both gene tree and species tree reconstruction while also addressing common pitfalls, providing references to relevant computer programs. A practical phylogenomic analysis example including bacterial genomes is presented at the end of the chapter.

Distributed genotyping and clustering of Neisseria strains reveal continual emergence of epidemic meningococcus over a century

Core genome multilocus sequence typing (cgMLST) is commonly used to classify bacterial strains into different types, for taxonomical and epidemiological applications. However, cgMLST schemes require central databases for the nomenclature of new alleles and sequence types, which must be synchronized worldwide and involve increasingly intensive calculation and storage demands. Here, we describe a distributed cgMLST (dcgMLST) scheme that does not require a central database of allelic sequences and apply it to study evolutionary patterns of epidemic and endemic strains of the genus Neisseria. We classify 69,994 worldwide Neisseria strains into multi-level clusters that assign species, lineages, and local disease outbreaks. We divide Neisseria meningitidis into 168 endemic lineages and three epidemic lineages responsible for at least 9 epidemics in the past century. According to our analyses, the epidemic and endemic lineages experienced very different population dynamics in the past 100 years. Epidemic lineages repetitively emerged from endemic lineages, disseminated worldwide, and apparently disappeared rapidly afterward. We propose a stepwise model for the evolutionary trajectory of epidemic lineages in Neisseria, and expect that the development of similar dcgMLST schemes will facilitate epidemiological studies of other bacterial pathogens.

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.

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.

Rhodopsin-bestrophin fusion proteins from unicellular algae form gigantic pentameric ion channels

Many organisms sense light using rhodopsins, photoreceptive proteins containing a retinal chromophore. Here we report the discovery, structure and biophysical characterization of bestrhodopsins, a microbial rhodopsin subfamily from marine unicellular algae, in which one rhodopsin domain of eight transmembrane helices or, more often, two such domains in tandem, are C-terminally fused to a bestrophin channel. Cryo-EM analysis of a rhodopsin-rhodopsin-bestrophin fusion revealed that it forms a pentameric megacomplex (~700 kDa) with five rhodopsin pseudodimers surrounding the channel in the center. Bestrhodopsins are metastable and undergo photoconversion between red- and green-absorbing or green- and UVA-absorbing forms in the different variants. The retinal chromophore, in a unique binding pocket, photoisomerizes from all-trans to 11-cis form. Heterologously expressed bestrhodopsin behaves as a light-modulated anion channel.

Iron metabolic pathways in the processes of sponge plasticity

The ability to regulate oxygen consumption evolved in ancestral animals and is intrinsically linked to iron metabolism. The iron pathways have been intensively studied in mammals, whereas data on distant invertebrates are limited. Sea sponges represent the oldest animal phylum and have unique structural plasticity and capacity to reaggregate after complete dissociation. We studied iron metabolic factors and their expression during reaggregation in the White Sea cold-water sponges Halichondria panicea and Halisarca dujardini. De novo transcriptomes were assembled using RNA-Seq data, and evolutionary trends were analyzed with bioinformatic tools. Differential expression during reaggregation was studied for H. dujardini. Enzymes of the heme biosynthesis pathway and transport globins, neuroglobin (NGB) and androglobin (ADGB), were identified in sponges. The globins mutate at higher evolutionary rates than the heme synthesis enzymes. Highly conserved iron-regulatory protein 1 (IRP1) presumably interacts with the iron-responsive elements (IREs) found in mRNAs of ferritin (FTH1) and a putative transferrin receptor NAALAD2. The reaggregation process is accompanied by increased expression of IRP1, the antiapoptotic factor BCL2, the inflammation factor NFκB (p65), FTH1 and NGB, as well as by an increase in mitochondrial density. Our data indicate a complex mechanism of iron regulation in sponge structural plasticity and help to better understand general mechanisms of morphogenetic processes in multicellular species.

Characterization of the 20S proteasome of the lepidopteran, Spodoptera frugiperda

Multiple complexes of 20S proteasomes with accessory factors play an essential role in proteolysis in eukaryotic cells. In this report, several forms of 20S proteasomes from extracts of Spodoptera frugiperda (Sf9) cells were separated using electrophoresis in a native polyacrylamide gel and examined for proteolytic activity in the gel and by Western blotting. Distinct proteasome bands isolated from the gel were subjected to liquid chromatography-tandem mass spectrometry and identified as free core particles (CP) and complexes of CP with one or two dimers of assembly chaperones PAC1-PAC2 and activators PA28γ or PA200. In contrast to the activators PA28γ and PA200 that regulate the access of protein substrates to the internal proteolytic chamber of CP in an ATP-independent manner, the 19S regulatory particle (RP) in 26S proteasomes performs stepwise substrate unfolding and opens the chamber gate in an ATP-dependent manner. Electron microscopic analysis suggested that spontaneous dissociation of RP in isolated 26S proteasomes leaves CPs with different gate sizes related presumably to different stages in the gate opening. The primary structure of 20S proteasome subunits in Sf9 cells was determined by a search of databases and by sequencing. The protein sequences were confirmed by mass spectrometry and verified by 2D gel electrophoresis. The relative rates of sequence divergence in the evolution of 20S proteasome subunits, the assembly chaperones and activators were determined by using bioinformatics. The data confirmed the conservation of regular CP subunits and PA28γ, a more accelerated evolution of PAC2 and PA200, and especially high divergence rates of PAC1.

SWPhylo - A Novel Tool for Phylogenomic Inferences by Comparison of Oligonucleotide Patterns and Integration of Genome-Based and Gene-Based Phylogenetic Trees

Modern phylogenetic studies may benefit from the analysis of complete genome sequences of various microorganisms. Evolutionary inferences based on genome-scale analysis are believed to be more accurate than the gene-based alternative. However, the computational complexity of current phylogenomic procedures, inappropriateness of standard phylogenetic tools to process genome-wide data, and lack of reliable substitution models which correlates with alignment-free phylogenomic approaches deter microbiologists from using these opportunities. For example, the super-matrix and super-tree approaches of phylogenomics use multiple integrated genomic loci or individual gene-based trees to infer an overall consensus tree. However, these approaches potentially multiply errors of gene annotation and sequence alignment not mentioning the computational complexity and laboriousness of the methods. In this article, we demonstrate that the annotation- and alignment-free comparison of genome-wide tetranucleotide frequencies, termed oligonucleotide usage patterns (OUPs), allowed a fast and reliable inference of phylogenetic trees. These were congruent to the corresponding whole genome super-matrix trees in terms of tree topology when compared with other known approaches including 16S ribosomal RNA and GyrA protein sequence comparison, complete genome-based MAUVE, and CVTree methods. A Web-based program to perform the alignment-free OUP-based phylogenomic inferences was implemented at http://swphylo.bi.up.ac.za/. Applicability of the tool was tested on different taxa from subspecies to intergeneric levels. Distinguishing between closely related taxonomic units may be enforced by providing the program with alignments of marker protein sequences, eg, GyrA.

Phylogenomics

Phylogenomics aims at reconstructing the evolutionary histories of organisms taking into account whole genomes or large fractions of genomes. The abundance of genomic data for an enormous variety of organisms has enabled phylogenomic inference of many groups, and this has motivated the development of many computer programs implementing the associated methods. This chapter surveys phylogenetic concepts and methods aimed at both gene tree and species tree reconstruction while also addressing common pitfalls, providing references to relevant computer programs. A practical phylogenomic analysis example including bacterial genomes is presented at the end of the chapter.

Comparative analysis of inverted repeats of polypod fern (Polypodiales) plastomes reveals two hypervariable regions

BACKGROUND

Ferns are large and underexplored group of vascular plants (~ 11 thousands species). The genomic data available by now include low coverage nuclear genomes sequences and partial sequences of mitochondrial genomes for six species and several plastid genomes.

RESULTS

We characterized plastid genomes of three species of Dryopteris, which is one of the largest fern genera, using sequencing of chloroplast DNA enriched samples and performed comparative analysis with available plastomes of Polypodiales, the most species-rich group of ferns. We also sequenced the plastome of Adianthum hispidulum (Pteridaceae). Unexpectedly, we found high variability in the IR region, including duplication of rrn16 in D. blanfordii, complete loss of trnI-GAU in D. filix-mas, its pseudogenization due to the loss of an exon in D. blanfordii. Analysis of previously reported plastomes of Polypodiales demonstrated that Woodwardia unigemmata and Lepisorus clathratus have unusual insertions in the IR region. The sequence of these inserted regions has high similarity to several LSC fragments of ferns outside of Polypodiales and to spacer between tRNA-CGA and tRNA-TTT genes of mitochondrial genome of Asplenium nidus. We suggest that this reflects the ancient DNA transfer from mitochondrial to plastid genome occurred in a common ancestor of ferns. We determined the marked conservation of gene content and relative evolution rate of genes and intergenic spacers in the IRs of Polypodiales. Faster evolution of the four intergenic regions had been demonstrated (trnA- orf42, rrn16-rps12, rps7-psbA and ycf2-trnN).

CONCLUSIONS

IRs of Polypodiales plastomes are dynamic, driven by such events as gene loss, duplication and putative lateral transfer from mitochondria.

Bad Clade Deletion Supertrees: A Fast and Accurate Supertree Algorithm

Supertree methods merge a set of overlapping phylogenetic trees into a supertree containing all taxa of the input trees. The challenge in supertree reconstruction is the way of dealing with conflicting information in the input trees. Many different algorithms for different objective functions have been suggested to resolve these conflicts. In particular, there exist methods based on encoding the source trees in a matrix, where the supertree is constructed applying a local search heuristic to optimize the respective objective function. We present a novel heuristic supertree algorithm called Bad Clade Deletion (BCD) supertrees. It uses minimum cuts to delete a locally minimal number of columns from such a matrix representation so that it is compatible. This is the complement problem to Matrix Representation with Compatibility (Maximum Split Fit). Our algorithm has guaranteed polynomial worst-case running time and performs swiftly in practice. Different from local search heuristics, it guarantees to return the directed perfect phylogeny for the input matrix, corresponding to the parent tree of the input trees, if one exists. Comparing supertrees to model trees for simulated data, BCD shows a better accuracy (F1 score) than the state-of-the-art algorithms SuperFine (up to 3%) and Matrix Representation with Parsimony (up to 7%); at the same time, BCD is up to 7 times faster than SuperFine, and up to 600 times faster than Matrix Representation with Parsimony. Finally, using the BCD supertree as a starting tree for a combined Maximum Likelihood analysis using RAxML, we reach significantly improved accuracy (1% higher F1 score) and running time (1.7-fold speedup).