Maximum likelihood Jukes-Cantor triplets: analytic solutions

Maximum likelihood (ML) is a popular method for inferring a phylogenetic tree of the evolutionary relationship of a set of taxa, from observed homologous aligned genetic sequences of the taxa. Generally, the computation of the ML tree is based on numerical methods, which in a few cases, are known to converge to a local maximum on a tree, which is suboptimal. The extent of this problem is unknown, one approach is to attempt to derive algebraic equations for the likelihood equation and find the maximum points analytically. This approach has so far only been successful in the very simplest cases, of three or four taxa under the Neyman model of evolution of two-state characters. In this paper we extend this approach, for the first time, to four-state characters, the Jukes-Cantor model under a molecular clock, on a tree T on three taxa, a rooted triple. We employ spectral methods (Hadamard conjugation) to express the likelihood function parameterized by the path-length spectrum. Taking partial derivatives, we derive a set of polynomial equations whose simultaneous solution contains all critical points of the likelihood function. Using tools of algebraic geometry (the resultant of two polynomials) in the computer algebra packages (Maple), we are able to find all turning points analytically. We then employ this method on real sequence data and obtain realistic results on the primate-rodents divergence time.     

Quartets MaxCut: a divide and conquer quartets algorithm

Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of taxa. Supertree methods construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Hence, in order to construct the tree of life over a million and a half different species, the use of a supertree method over the product of accurate methods, is inevitable. Perhaps the simplest version of this task that is still widely applicable, yet quite challenging, is quartet-based reconstruction. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, dealing with false, conflicting quartet trees remains problematic. In this paper, we describe an algorithm for constructing a tree from a set of input quartet trees even with a significant fraction of errors. We show empirically that conflicts in the inputs are handled satisfactorily and that it significantly outperforms and outraces the Matrix Representation with Parsimony (MRP) methods that have previously been most successful in dealing with supertrees. Our algorithm is based on a divide and conquer algorithm where our divide step uses a semidefinite programming (SDP) formulation of MaxCut. We remark that this builds on previous work of ours for piecing together trees from rooted triplet trees. The recursion for unrooted quartets, however, is more complicated in that even with completely consistent set of quartet trees the problem is NP-hard, as opposed to the problem for triples where there is a linear time algorithm. This complexity leads to several issues and some solutions of possible independent interest.     

Assessment of the ultrastructural and proliferative properties of human embryonic stem cell-derived cardiomyocytes

Assessment of early ultrastructural development and cell-cycle regulation in human cardiac tissue is significantly hampered by the lack of a suitable in vitro model. Here we describe the possible utilization of human embryonic stem cell (ES) lines for investigation of these processes. With the use of the embryoid body (EB) differentiation system, human ES cell-derived cardiomyocytes at different developmental stages were isolated and their histomorphometric, ultrastructural, and proliferative properties were characterized. Histomorphometric analysis revealed an increase in cell length, area, and length-to-width ratio in late-stage EBs (>35 days) compared with early (10-21 days) and intermediate (21-35 days) stages. This was coupled with a progressive ultrastructural development from an irregular myofibrillar distribution to an organized sarcomeric pattern. Cardiomyocyte proliferation, assessed by double labeling with cardiac-specific antibodies and either [3H]thymidine incorporation or Ki-67 immunolabeling, demonstrated a gradual withdrawal from cell cycle. Hence, the percentage of positively stained nuclei in early-stage cardiomyocytes ([3H]thymidine: 60 +/- 10%, Ki-67: 54 +/- 23%) decreased to 36 +/- 7% and 9 +/- 16% in intermediate-stage EBs and to <1% in late-stage cardiomyocytes. In conclusion, a reproducible temporal pattern of early cardiomyocyte proliferation, cell-cycle withdrawal, and ultrastructural maturation was noted in this model. Establishment of this unique in vitro surrogate system may allow to examine the molecular mechanisms underlying these processes and to assess interventions aiming to modify these properties. Moreover, the detailed characterization of the ES cell-derived cardiomyocyte may be crucial for the development of future cell replacement strategies aiming to regenerate functional myocardium.     

The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection

Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa.     

Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles

One of the criteria for inferring a species tree from a collection of gene trees, when gene tree incongruence is assumed to be due to incomplete lineage sorting (ILS), is Minimize Deep Coalescence (MDC). Exact algorithms for inferring the species tree from rooted, binary trees under MDC were recently introduced. Nevertheless, in phylogenetic analyses of biological data sets, estimated gene trees may differ from true gene trees, be incompletely resolved, and not necessarily rooted. In this article, we propose new MDC formulations for the cases where the gene trees are unrooted/binary, rooted/non-binary, and unrooted/non-binary. Further, we prove structural theorems that allow us to extend the algorithms for the rooted/binary gene tree case to these cases in a straightforward manner. In addition, we devise MDC-based algorithms for cases when multiple alleles per species may be sampled. We study the performance of these methods in coalescent-based computer simulations.     

Hypothesis generation in signaling networks.

Biological signaling networks comprise the chemical processes by which cells detect and respond to changes in their environment. Such networks have been implicated in the regulation of important cellular activities, including cellular reproduction, mobility, and death. Though technological and scientific advances have facilitated the rapid accumulation of information about signaling networks, utilizing these massive information resources has become infeasible except through computational methods and computer-based tools. To date, visualization and simulation tools have received significant emphasis. In this paper, we present a graph-theoretic formalization of biological signaling network models that are in wide but informal use, and formulate two problems on the graph: the Constrained Downstream and Minimum Knockout Problems. Solutions to these problems yield qualitative tools for generating hypotheses about the networks, which can then be experimentally tested in a laboratory setting. Using established graph algorithms, we provide a solution to the Constrained Downstream Problem. We also show that the Minimum Knockout Problem is NP-Hard, propose a heuristic, and assess its performance. In tests on the Epidermal Growth Factor Receptor (EGFR) network, we find that our heuristic reports the correct solution to the problem in seconds. Source code for the implementations of both solutions is available from the authors upon request.     

Irrational exuberance for resolved species trees

Phylogenomics has largely succeeded in its aim of accurately inferring species trees, even when there are high levels of discordance among individual gene trees. These resolved species trees can be used to ask many questions about trait evolution, including the direction of change and number of times traits have evolved. However, the mapping of traits onto trees generally uses only a single representation of the species tree, ignoring variation in the gene trees used to construct it. Recognizing that genes underlie traits, these results imply that many traits follow topologies that are discordant with the species topology. As a consequence, standard methods for character mapping will incorrectly infer the number of times a trait has evolved. This phenomenon, dubbed “hemiplasy,” poses many problems in analyses of character evolution. Here we outline these problems, explaining where and when they are likely to occur. We offer several ways in which the possible presence of hemiplasy can be diagnosed, and discuss multiple approaches to dealing with the problems presented by underlying gene tree discordance when carrying out character mapping. Finally, we discuss the implications of hemiplasy for general phylogenetic inference, including the possible drawbacks of the widespread push for “resolved” species trees.     

Immunization of Chickens with Newcastle Disease Virus Expressing H5 Hemagglutinin Protects against Highly Pathogenic H5N1 Avian Influenza Viruses

Background

Highly-pathogenic avian influenza virus (HPAIV) and Newcastle disease virus (NDV) are the two most important poultry viruses in the world. Natural low-virulence NDV strains have been used as vaccines over the past 70 years with proven track records. We have previously developed a reverse genetics system to produce low-virulent NDV vaccine strain LaSota from cloned cDNA. This system allows us to use NDV as a vaccine vector for other avian pathogens.

Methodology/Principal Finding

Here, we constructed two recombinant NDVs (rNDVs) each of which expresses the hemagglutinin (HA) gene of HPAIV H5N1strain A/Vietnam/1203/2004 from an added gene. In one, rNDV (rNDV-HA), the open reading frame (ORF) of HA gene was expressed without modification. In the second, rNDV (rNDV-HAF), the ORF was modified so that the transmembrane and cytoplasmic domains of the encoded HA gene were replaced with those of the NDV F protein. The insertion of either version of the HA ORF did not increase the virulence of the rNDV vector. The HA protein was found to be incorporated into the envelopes of both rNDV-HA and rNDV-HAF. However, there was an enhanced incorporation of the HA protein in rNDV-HAF. Chickens immunized with a single dose of either rNDV-HA or rNDV-HAF induced a high titer of HPAIV H5-specific antibodies and were completely protected against challenge with NDV as well as lethal challenges of both homologous and heterologous HPAIV H5N1.

Conclusion and Significance

Our results suggest that these chimeric viruses have potential as safe and effective bivalent vaccines against NDV and. HPAIV. These vaccines will be convenient and affordable, which will be highly beneficial to the poultry industry. Furthermore, immunization with these vaccines will permit serological differentiation of vaccinated and avian influenza field virus infected animals.     

Stranger in a strange land: the experiences of immigrant researchers

Continuing with our Q&A series discussing issues of diversity in STEM fields, Genome Biology spoke with three researchers on their experiences as immigrants.     

Phylo SI: a new genome-wide approach for prokaryotic phylogeny

The evolutionary history of all life forms is usually represented as a vertical tree-like process. In prokaryotes, however, the vertical signal is partly obscured by the massive influence of horizontal gene transfer (HGT). The HGT creates widespread discordance between evolutionary histories of different genes as genomes become mosaics of gene histories. Thus, the Tree of Life (TOL) has been questioned as an appropriate representation of the evolution of prokaryotes. Nevertheless a common hypothesis is that prokaryotic evolution is primarily tree-like, and a routine effort is made to place new isolates in their appropriate location in the TOL. Moreover, it appears desirable to exploit non–tree-like evolutionary processes for the task of microbial classification. In this work, we present a novel technique that builds on the straightforward observation that gene order conservation (‘synteny’) decreases in time as a result of gene mobility. This is particularly true in prokaryotes, mainly due to HGT. Using a ‘synteny index’ (SI) that measures the average synteny between a pair of genomes, we developed the phylogenetic reconstruction tool ‘Phylo SI’. Phylo SI offers several attractive properties such as easy bootstrapping, high sensitivity in cases where phylogenetic signal is weak and computational efficiency. Phylo SI was tested both on simulated data and on two bacterial data sets and compared with two well-established phylogenetic methods. Phylo SI is particularly efficient on short evolutionary distances where synteny footprints remain detectable, whereas the nucleotide substitution signal is too weak for reliable sequence-based phylogenetic reconstruction. The method is publicly available at http://research.haifa.ac.il/ssagi/software/PhyloSI.zip.