DIVERGE: phylogeny-based analysis for functional-structural divergence of a protein family

SUMMARY: DetectIng Variability in Evolutionary Rates among GEnes (DIVERGE) is a software system to study functional divergence of a protein family by detecting site-specific change in evolutionary rate using a multiple alignment of amino acid sequences for a given phylogenetic tree. The program first conducts a statistical test for site-specific rate shifts along the tree, and predicting candidate amino acid residues responsible for functional divergence based on posterior analysis. These results can then be mapped on the 3D protein structure if available. AVAILABILITY: DIVERGE is available free of charge from http://xgu1.zool.iastate.edu/. Distribution packages for both Linux and Microsoft Windows operating systems are available, including manual and example files.     

Effect of co-evolving amino acid residues on topology of phylogenetic trees

The presence in proteins of amino acid residues that change in concert during evolution is associated with keeping constant the protein spatial structure and functions. As in the case with morphological features, correlated substitutions may become the cause of homoplasies--the independent evolution of identical non-homological adaptations. Our data obtained on model phylogenetic trees and corresponding sets of sequences have shown that the presence of correlated substitutions distorts the results of phylogenetic reconstructions. A method for accounting for co-evolving amino acid residues in phylogenetic analysis is proposed. According to this method, only a single site from the group of correlated amino acid positions should remain, whereas other positions should not be used in further phylogenetic analysis. Simulations performed have shown that replacement on the average of 8% of variable positions in a pair of model sequences by coordinately evolving amino acid residues is able to change the tree topology. The removal of such amino acid residues from sequences before phylogenetic analysis restores the correct topology.     

DPRml: distributed phylogeny reconstruction by maximum likelihood

MOTIVATION: In recent years there has been increased interest in producing large and accurate phylogenetic trees using statistical approaches. However for a large number of taxa, it is not feasible to construct large and accurate trees using only a single processor. A number of specialized parallel programs have been produced in an attempt to address the huge computational requirements of maximum likelihood. We express a number of concerns about the current set of parallel phylogenetic programs which are currently severely limiting the widespread availability and use of parallel computing in maximum likelihood-based phylogenetic analysis. RESULTS: We have identified the suitability of phylogenetic analysis to large-scale heterogeneous distributed computing. We have completed a distributed and fully cross-platform phylogenetic tree building program called distributed phylogeny reconstruction by maximum likelihood. It uses an already proven maximum likelihood-based tree building algorithm and a popular phylogenetic analysis library for all its likelihood calculations. It offers one of the most extensive sets of DNA substitution models currently available. We are the first, to our knowledge, to report the completion of a distributed phylogenetic tree building program that can achieve near-linear speedup while only using the idle clock cycles of machines. For those in an academic or corporate environment with hundreds of idle desktop machines, we have shown how distributed computing can deliver a 'free' ML supercomputer.     

Dendroscope: An interactive viewer for large phylogenetic trees

Background  

Research in evolution requires software for visualizing and editing phylogenetic trees, for increasingly very large datasets, such as arise in expression analysis or metagenomics, for example. It would be desirable to have a program that provides these services in an effcient and user-friendly way, and that can be easily installed and run on all major operating systems. Although a large number of tree visualization tools are freely available, some as a part of more comprehensive analysis packages, all have drawbacks in one or more domains. They either lack some of the standard tree visualization techniques or basic graphics and editing features, or they are restricted to small trees containing only tens of thousands of taxa. Moreover, many programs are diffcult to install or are not available for all common operating systems.     

Untangling the contribution of characters to evolutionary relationships: a case study using fossils,morphology, and Genes

Given the importance of phylogenetic trees to understanding common ancestry and evolution, they are a necessary part of the undergraduate biology curriculum. However, a number of common misconceptions, such as reading across branch tips and understanding homoplasy, can pose difficulties in student understanding. Students also may take phylogenetic trees to be fact, instead of hypotheses. Below we outline a case study that we have used in upper-level undergraduate evolution and ichthyology courses that utilizes shark teeth (representing fossils), body characters, and mitochondrial genes. Students construct their own trees using freely available software, and are prompted to compare their trees with a series of questions. Finally, students explore homoplasy, polytomies, and trees as hypotheses during a class discussion period. This case study gives students practice with tree-thinking, as well as demonstrating that tree topology is reliant on which characters and tree-building algorithms are used.     

Modelling heterotachy in phylogenetic inference by reversible-jump Markov chain Monte Carlo

The rate at which a given site in a gene sequence alignment evolves over time may vary. This phenomenon--known as heterotachy--can bias or distort phylogenetic trees inferred from models of sequence evolution that assume rates of evolution are constant. Here, we describe a phylogenetic mixture model designed to accommodate heterotachy. The method sums the likelihood of the data at each site over more than one set of branch lengths on the same tree topology. A branch-length set that is best for one site may differ from the branch-length set that is best for some other site, thereby allowing different sites to have different rates of change throughout the tree. Because rate variation may not be present in all branches, we use a reversible-jump Markov chain Monte Carlo algorithm to identify those branches in which reliable amounts of heterotachy occur. We implement the method in combination with our 'pattern-heterogeneity' mixture model, applying it to simulated data and five published datasets. We find that complex evolutionary signals of heterotachy are routinely present over and above variation in the rate or pattern of evolution across sites, that the reversible-jump method requires far fewer parameters than conventional mixture models to describe it, and serves to identify the regions of the tree in which heterotachy is most pronounced. The reversible-jump procedure also removes the need for a posteriori tests of 'significance' such as the Akaike or Bayesian information criterion tests, or Bayes factors. Heterotachy has important consequences for the correct reconstruction of phylogenies as well as for tests of hypotheses that rely on accurate branch-length information. These include molecular clocks, analyses of tempo and mode of evolution, comparative studies and ancestral state reconstruction. The model is available from the authors' website, and can be used for the analysis of both nucleotide and morphological data.     

Phylogenetic inference from conserved sites alignments.

Molecular sequences provide a rich source of data for inferring the phylogenetic relationships among species. However, recent work indicates that even an accurate multiple alignment of a large sequence set may yield an incorrect phylogeny and that the quality of the phylogenetic tree improves when the input consists only of the highly conserved, motif regions of the alignment. This work introduces two methods of producing multiple alignments that include only the conserved regions of the initial alignment. The first method retains conserved motifs, whereas the second retains individual conserved sites in the initial alignment. Using parsimony analysis on a mitochondrial data set containing 19 species among which the phylogenetic relationships are widely accepted, both conserved alignment methods produce better phylogenetic trees than the complete alignment. Unlike any of the 19 inference methods used before to analyze this data, both methods produce trees that are completely consistent with the known phylogeny. The motif-based method employs far fewer alignment sites for comparable error rates. For a larger data set containing mitochondrial sequences from 39 species, the site-based method produces a phylogenetic tree that is largely consistent with known phylogenetic relationships and suggests several novel placements. J. Exp. Zool. ( Mol. Dev. Evol.) 285:128-139, 1999.     

Interactive analysis of phylogeny and character evolution using the computer program MacClade

Computer programs for phylogenetic analysis have been important tools in systematics and evolutionary biology, but most have been designed primarily for the reconstruction of phylogenetic trees and not the interpretation of patterns of character evolution. Described here is the computer program MacClade, designed for interactive analysis of character evolution and phylogeny. For a given tree and a matrix of character data, MacClade displays its reconstruction of character evolution by shading the branches of the tree to indicate ancestral states. Trees can be manipulated for instance by picking up and moving branches. Assumptions underlying the reconstruction of character evolution can be varied extensively. With these manipulations and MacClade's graphical feedback, one can explore the relationships among phylogenetic trees, character data, assumptions and interpretations of character evolution. MacClade has extensive facilities for editing data, displaying various summaries of character evolution in charts and diagrams, and printing.     

Something for nothing? Reconstruction of ancestral character states in asterinid sea star development

SUMMARY Traits from early development mapped onto phylogenetic trees can potentially offer insight into the evolutionary history of development by inferring the states of those characters among ancestors at nodes in the phylogeny. A key and often-overlooked aspect of such mapping is the underlying model of character evolution. Without a well-supported and realistic model ("nothing"), character mapping of ancestral traits onto phylogenetic trees might often return results ("something") that lack a sound basis. Here we reconsider a challenging case study in this area of evolutionary developmental biology: the inference of ancestral states for ecological and morphological characters in the reproduction and larval development of asterinid sea stars. We apply improved analytical methods to an expanded set of asterinid phylogenetic data and developmental character states. This analysis shows that the new methods might generally offer some independent insight into choice of a model of character evolution, but that in the specific case of asterinid sea stars the quantitative features of the model (especially the relative probabilities of different directions of change) have an important effect on the results. We suggest caution in applying ancestral state reconstructions in the absence of an independently corroborated model of character evolution, and highlight the need for such modeling in evolutionary developmental biology.     

Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases

MOTIVATION: Comparative sequence analysis is widely used to study genome function and evolution. This approach first requires the identification of homologous genes and then the interpretation of their homology relationships (orthology or paralogy). To provide help in this complex task, we developed three databases of homologous genes containing sequences, multiple alignments and phylogenetic trees: HOBACGEN, HOVERGEN and HOGENOM. In this paper, we present two new tools for automating the search for orthologs or paralogs in these databases. RESULTS: First, we have developed and implemented an algorithm to infer speciation and duplication events by comparison of gene and species trees (tree reconciliation). Second, we have developed a general method to search in our databases the gene families for which the tree topology matches a peculiar tree pattern. This algorithm of unordered tree pattern matching has been implemented in the FamFetch graphical interface. With the help of a graphical editor, the user can specify the topology of the tree pattern, and set constraints on its nodes and leaves. Then, this pattern is compared with all the phylogenetic trees of the database, to retrieve the families in which one or several occurrences of this pattern are found. By specifying ad hoc patterns, it is therefore possible to identify orthologs in our databases.     

Phylogeny, host-parasite relationship and zoogeography

Phylogeny is the evolutionary history of a group or the lineage of organisms and is reconstructed based on morphological, molecular and other characteristics. The genealogical relationship of a group of taxa is often expressed as a phylogenetic tree. The difficulty in categorizing the phylogeny is mainly due to the existence of frequent homoplasies that deceive observers. At the present time, cladistic analysis is believed to be one of the most effective methods of reconstructing a phylogenetic tree. Excellent computer program software for phylogenetic analysis is available. As an example, cladistic analysis was applied for nematode genera of the family Acuariidae, and the phylogenetic tree formed was compared with the system used currently. Nematodes in the genera Nippostrongylus and Heligmonoides were also analyzed, and the validity of the reconstructed phylogenetic trees was observed from a zoogeographical point of view. Some of the theories of parasite evolution were briefly reviewed as well. Coevolution of parasites and humans was discussed with special reference to the evolutionary relationship between Enterobius and primates.     

Unicyclic networks: compatibility and enumeration

Graphs obtained from a binary leaf labeled ("phylogenetic") tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call "unicyclic networks") also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem and a simple, fast algorithm to determine 1-cycle compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multicyclic networks.     

Topology improves phylogenetic motif functional site predictions

Prediction of protein functional sites from sequence-derived data remains an open bioinformatics problem. We have developed a phylogenetic motif (PM) functional site prediction approach that identifies functional sites from alignment fragments that parallel the evolutionary patterns of the family. In our approach, PMs are identified by comparing tree topologies of each alignment fragment to that of the complete phylogeny. Herein, we bypass the phylogenetic reconstruction step and identify PMs directly from distance matrix comparisons. In order to optimize the new algorithm, we consider three different distance matrices and 13 different matrix similarity scores. We assess the performance of the various approaches on a structurally nonredundant data set that includes three types of functional site definitions. Without exception, the predictive power of the original approach outperforms the distance matrix variants. While the distance matrix methods fail to improve upon the original approach, our results are important because they clearly demonstrate that the improved predictive power is based on the topological comparisons. Meaning that phylogenetic trees are a straightforward, yet powerful way to improve functional site prediction accuracy. While complementary studies have shown that topology improves predictions of protein-protein interactions, this report represents the first demonstration that trees improve functional site predictions as well.     

A phylogenetic approach to cultural evolution

There has been a rapid increase in the use of phylogenetic methods to study the evolution of languages and culture. Languages fit a tree model of evolution well, at least in their basic vocabulary, challenging the view that blending, or admixture among neighbouring groups, was predominant in cultural history. Here, we argue that we can use language trees to test hypotheses about not only cultural history and diversification, but also bio-cultural adaptation. Phylogenetic comparative methods take account of the non-independence of cultures (Galton's problem), which can cause spurious statistical associations in comparative analyses. Advances in phylogenetic methods offer new possibilities for the analysis of cultural evolution, including estimating the rate of evolution and the direction of coevolutionary change of traits on the tree. They also enable phylogenetic uncertainty to be incorporated into the analyses, so that one does not have to treat phylogenetic trees as if they were known without error.     

A phylogenomic approach to microbial evolution

To study the origin and evolution of biochemical pathways in microorganisms, we have developed methods and software for automatic, large-scale reconstructions of phylogenetic relationships. We define the complete set of phylogenetic trees derived from the proteome of an organism as the phylome and introduce the term phylogenetic connection as a concept that describes the relative relationships between taxa in a tree. A query system has been incorporated into the system so as to allow searches for defined categories of trees within the phylome. As a complement, we have developed the pyphy system for visualising the results of complex queries on phylogenetic connections, genomic locations and functional assignments in a graphical format. Our phylogenomics approach, which links phylogenetic information to the flow of biochemical pathways within and among microbial species, has been used to examine more than 8000 phylogenetic trees from seven microbial genomes. The results have revealed a rich web of phylogenetic connections. However, the separation of Bacteria and Archaea into two separate domains remains robust.     

The Use (and Misuse) of Phylogenetic Trees in Comparative Behavioral Analyses

Phylogenetic comparative methods play a critical role in our understanding of the adaptive origin of primate behaviors. To incorporate evolutionary history directly into comparative behavioral research, behavioral ecologists rely on strong, well-resolved phylogenetic trees. Phylogenies provide the framework on which behaviors can be compared and homologies can be distinguished from similarities due to convergent or parallel evolution. Phylogenetic reconstructions are also of critical importance when inferring the ancestral state of behavioral patterns and when suggesting the evolutionary changes that behavior has undergone. Improvements in genome sequencing technologies have increased the amount of data available to researchers. Recently, several primate phylogenetic studies have used multiple loci to produce robust phylogenetic trees that include hundreds of primate species. These trees are now commonly used in comparative analyses and there is a perception that we have a complete picture of the primate tree. But how confident can we be in those phylogenies? And how reliable are comparative analyses based on such trees? Herein, we argue that even recent molecular phylogenies should be treated cautiously because they rely on many assumptions and have many shortcomings. Most phylogenetic studies do not model gene tree diversity and can produce misleading results, such as strong support for an incorrect species tree, especially in the case of rapid and recent radiations. We discuss implications that incorrect phylogenies can have for reconstructing the evolution of primate behaviors and we urge primatologists to be aware of the current limitations of phylogenetic reconstructions when applying phylogenetic comparative methods.     

Phylogenetic mixture models can reduce node-density artifacts

We investigate the performance of phylogenetic mixture models in reducing a well-known and pervasive artifact of phylogenetic inference known as the node-density effect, comparing them to partitioned analyses of the same data. The node-density effect refers to the tendency for the amount of evolutionary change in longer branches of phylogenies to be underestimated compared to that in regions of the tree where there are more nodes and thus branches are typically shorter. Mixture models allow more than one model of sequence evolution to describe the sites in an alignment without prior knowledge of the evolutionary processes that characterize the data or how they correspond to different sites. If multiple evolutionary patterns are common in sequence evolution, mixture models may be capable of reducing node-density effects by characterizing the evolutionary processes more accurately. In gene-sequence alignments simulated to have heterogeneous patterns of evolution, we find that mixture models can reduce node-density effects to negligible levels or remove them altogether, performing as well as partitioned analyses based on the known simulated patterns. The mixture models achieve this without knowledge of the patterns that generated the data and even in some cases without specifying the full or true model of sequence evolution known to underlie the data. The latter result is especially important in real applications, as the true model of evolution is seldom known. We find the same patterns of results for two real data sets with evidence of complex patterns of sequence evolution: mixture models substantially reduced node-density effects and returned better likelihoods compared to partitioning models specifically fitted to these data. We suggest that the presence of more than one pattern of evolution in the data is a common source of error in phylogenetic inference and that mixture models can often detect these patterns even without prior knowledge of their presence in the data. Routine use of mixture models alongside other approaches to phylogenetic inference may often reveal hidden or unexpected patterns of sequence evolution and can improve phylogenetic inference.     

TrExML: a maximum-likelihood approach for extensive tree-space exploration

MOTIVATION: Maximum-likelihood analysis of nucleotide and amino acid sequences is a powerful approach for inferring phylogenetic relationships and for comparing evolutionary hypotheses. Because it is a computationally demanding and time-consuming process, most algorithms explore only a minute portion of tree-space, with the emphasis on finding the most likely tree while ignoring the less likely, but not significantly worse, trees. However, when such trees exist, it is equally important to identify them to give due consideration to the phylogenetic uncertainty. Consequently, it is necessary to change the focus of these algorithms such that near optimal trees are also identified. RESULTS: This paper presents the Advanced Stepwise Addition Algorithm for exploring tree-space and two algorithms for generating all binary trees on a set of sequences. The Advanced Stepwise Addition Algorithm has been implemented in TrExML, a phylogenetic program for maximum-likelihood analysis of nucleotide sequences. TrExML is shown to be more effective at finding near optimal trees than a similar program, fastDNAml, implying that TrExML offers a better approach to account for phylogenetic uncertainty than has previously been possible. A program, TreeGen, is also described; it generates binary trees on a set of sequences allowing for extensive exploration of tree-space using other programs. AVAILABILITY: TreeGen, TrExML, and the sequence data used to test the programs are available from the following two WWW sites: http://whitetail.bemidji.msus. edu/trexml/and http://jcsmr.anu.edu.au/dmm/humgen.+ ++html.     

Phylogenetic comparison of metabolic capacities of organisms at genome level

Horizontal gene transfer (HGT) has been shown to widely spread in organisms by comparative genomic studies. However, its effect on the phylogenetic relationship of organisms, especially at a system level of different cellular functions, is still not well understood. In this work, we have constructed phylogenetic trees based on the enzyme, reaction, and gene contents of metabolic networks reconstructed from annotated genome information of 82 sequenced organisms. Results from different phylogenetic distance definitions and based on three different functional subsystems (i.e., metabolism, cellular processes, information storage and processing) were compared. Results based on the three different functional subsystems give different pictures on the phylogenetic relationship of organisms, reflecting the different extents of HGT in the different functional systems. In general, horizontal transfer is prevailing in genes for metabolism, but less in genes for information processing. Nevertheless, the major results of metabolic network-based phylogenetic trees are in good agreement with the tree based on 16S rRNA and genome trees, confirming the three domain classification and the close relationship between eukaryotes and archaea at the level of metabolic networks. These results strongly support the hypothesis that although HGT is widely distributed, it is nevertheless constrained by certain pre-existing metabolic organization principle(s) during the evolution. Further research is needed to identify the organization principle and constraints of metabolic network on HGT which have large impacts on understanding the evolution of life and in purposefully manipulating cellular metabolism.     

DNA似近距离及进化时间的估算

在似近分析和Ｎｅｉ氏遗传距离的基础上,给出了ＤＮＡ似近距离计算公式,并以ＤＮＡ似近距离估算类群间的分歧时间（进化时间）,应用１０种限制内切酶对猕猴属（ｇｅｎｕｓ Ｍａｃａｃａ）内５个种ｍｔＤＮＡ的切点数据计算了这５个种的ＤＮＡ似近距离和进化时间,比较由ＤＮＡ似近距,遗传距离构建的歧化树和Ｆｏｏｄｅｎ及Ｄｅｌｓｏｎ的形态歧化树表明,除遗传距离的歧化树外,其它三种歧化树都有一个共同点,就是熊猴（Ｍ．ａ