Development of GEBRET: a web-based analysis tool for retroelements in primate genomes

Retroelements play important roles in primate evolution. Specifically, human endogenous retroviruses (HERVs) and Alu elements are primate-specific retroelements. In addition, SVA elements belong to the youngest family of hominid non-long terminal repeat (LTR) retrotransposons. Retroelements can affect adjacent gene expression, supplying cis-regulatory elements, splice sites, and poly-A signals. We developed a database, GEnome-wide Browser for RETroelement (GEBRET, http://neobio.cs.pusan.ac.kr/~gebre/), for comparing the distribution of primate-specific retroelements and adjacent genes. GEBRET database components include 47,381 HERVs, 53,924 Alus and 4639 SVAs in five primate genomes of human, chimpanzee, orangutan, rhesus macaque, and marmoset. Host genes located upstream of a retroelement were also visualized and classified as five categories (0.0, 0.5, 1.0, 2.0, and 3.0Kb). Our results suggest that retroelements preferentially integrate into the distal promoter region relative to the core promoter region. GEBRET database is designed to investigate the distribution of retroelements (HERVs, Alus and SVAs) in the primate genomes that have been sequenced. Our software will be useful in the field to study the impact of retroelements on primate genome evolution.     

ArrayCyGHt: a web application for analysis and visualization of array-CGH data

ArrayCyGHt is a web-based application tool for analysis and visualization of microarray-comparative genomic hybridization (array-CGH) data. Full process of array-CGH data analysis, from normalization of raw data to the final visualization of copy number gain or loss, can be straightforwardly achieved on this arrayCyGHt system without the use of any further software. ArrayCyGHt, therefore, provides an easy and fast tool for the analysis of copy number aberrations in any kinds of data format. AVAILABILITY: ArrayCyGHt can be accessed at http://genomics.catholic.ac.kr/arrayCGH/     

Drawing phylogenetic trees in LATEX and Microsoft Word

SUMMARY: newicktree is a PSTricks-based LATEX package which enables phylogenetic trees described in the Newick format to be drawn directly into LATEX documents. mswordtree is a macro for producing phylogenetic trees using the drawing elements available in Microsoft Word. AVAILABILITY: Both programs are available free from the John Innes Centre's Bioinformatics Research Group website at http://jic-bioinfo.bbsrc.ac.uk/bioinformatics-research/software/index.html. SUPPLEMENTARY INFORMATION: A full user-guide for newicktree and installation and usage instructions for mswordtree and available at http://jic-bioinfo.bbsrc.ac.uk/bioinformatics-research/software/index.html     

Multiple sequence alignment with the Clustal series of programs

The Clustal series of programs are widely used in molecular biology for the multiple alignment of both nucleic acid and protein sequences and for preparing phylogenetic trees. The popularity of the programs depends on a number of factors, including not only the accuracy of the results, but also the robustness, portability and user-friendliness of the programs. New features include NEXUS and FASTA format output, printing range numbers and faster tree calculation. Although, Clustal was originally developed to run on a local computer, numerous Web servers have been set up, notably at the EBI (European Bioinformatics Institute) (http://www.ebi.ac.uk/clustalw/).     

NanoStriDE: normalization and differential expression analysis of NanoString nCounter data

Background

Relationships between species, genes and genomes have been printed as trees for over a century. Whilst this may have been the best format for exchanging and sharing phylogenetic hypotheses during the 20^th century, the worldwide web now provides faster and automated ways of transferring and sharing phylogenetic knowledge. However, novel software is needed to defrost these published phylogenies for the 21^st century.

Results

TreeRipper is a simple website for the fully-automated recognition of multifurcating phylogenetic trees (http://linnaeus.zoology.gla.ac.uk/~jhughes/treeripper/). The program accepts a range of input image formats (PNG, JPG/JPEG or GIF). The underlying command line c++ program follows a number of cleaning steps to detect lines, remove node labels, patch-up broken lines and corners and detect line edges. The edge contour is then determined to detect the branch length, tip label positions and the topology of the tree. Optical Character Recognition (OCR) is used to convert the tip labels into text with the freely available tesseract-ocr software. 32% of images meeting the prerequisites for TreeRipper were successfully recognised, the largest tree had 115 leaves.

Conclusions

Despite the diversity of ways phylogenies have been illustrated making the design of a fully automated tree recognition software difficult, TreeRipper is a step towards automating the digitization of past phylogenies. We also provide a dataset of 100 tree images and associated tree files for training and/or benchmarking future software. TreeRipper is an open source project licensed under the GNU General Public Licence v3.     

DupTree: a program for large-scale phylogenetic analyses using gene tree parsimony

DupTree is a new software program for inferring rooted species trees from collections of gene trees using the gene tree parsimony approach. The program implements a novel algorithm that significantly improves upon the run time of standard search heuristics for gene tree parsimony, and enables the first truly genome-scale phylogenetic analyses. In addition, DupTree allows users to examine alternate rootings and to weight the reconciliation costs for gene trees. DupTree is an open source project written in C++. Availability: DupTree for Mac OS X, Windows, and Linux along with a sample dataset and an on-line manual are available at http://genome.cs.iastate.edu/CBL/DupTree     

Characters Are Key: The Effect of Synapomorphies on Cladogram Comprehension

Cladograms, phylogenetic trees that depict evolutionary relationships among a set of taxa, are one of the most powerful predictive tools in modern biology. They are usually depicted in one of two formats—tree or ladder. Previous research (Novick and Catley 2007) has found that college students have much greater difficulty understanding a cladogram’s hierarchical structure when it is depicted in the ladder format. Such understanding would seem to be a prerequisite for successful tree thinking. The present research examined the effect of a theoretically guided manipulation—adding a synapomorphy on each branch that supports two or more taxa—on students’ understanding of the hierarchical structure of ladder cladograms. Synapomorphies are characters shared by a group of taxa due to inheritance from a common ancestor. Thus, their depiction on a cladogram may facilitate the understanding of evolutionary relationships. Students’ comprehension was assessed in terms of success at translating relationships depicted in the ladder format to the tree format. The results indicated that adding synapomorphies provided powerful conceptual scaffolding that improved comprehension for students with both weaker and stronger backgrounds in biology. For stronger background students, the benefit of adding synapomorphies to the ladders was comparable to that of approximately two hours of instruction in phylogenetics that emphasized the ladder format.     

The Role of Functional Analysis in Phylogenetic Inference: Examples from the History of the Xiphosura

SYNOPSIS. Conventional cladistic analyses of phylogeny can beinterpreted as operating at the level of phylogenetic trees.They assume that all "evolutionary steps" (transitions fromone character state to the next, along a morphocline) are independentand equal, and, on that basis, select the cladogram which isconsistent with the most parsimonious trees. Evaluation of theassumptions of independence and equality requires considerationof hypotheses at the levelof scenarios. In some cases, argumentsbased on functional analysis can suggest revised interpretationsof either homology or polarity. If properly formulated, thesearguments can alter the evaluation of parsimony for trees tothe extent that even the choice of cladogram is affected. Thestructure of scenario level arguments is identical to that ofarguments operating at tree level. Examples of phylogeneticinference in the context of xiphosurans (horseshoe crabs), usingboth comparative morphological and functional analysis, illustratethis approach. In different cases, orthodox interpretationsof relationship are either challenged or corroborated. Althoughthe introduction of functional analysis into the process ofphylogenetic inference may appear to compromise the usefulnessof the reconstructed phylogeny for testing hypotheses concerningthe role of natural selection in evolution, it actually increasesthe strength of such tests.     

EVOLUTIONARY CHARACTER ANALYSIS: TRACING CHARACTER CHANGE ON A CLADOGRAM

Abstract— There has been little formal discussion concerning character analysis in cladistics, even though characters and their character state trees are central to phylogenetic analyses. We refer to this field as Evolutionary Character Analysis. This paper defines the components of evolutionary character analysis: character state trees, transmodal characters, cladogram characters, attribute and character phylogenies; and the use of these components in phylogenetic inference and evolutionary studies. Character state trees and their effect on cladogram construction are discussed. A new method for numerically coding complex character state trees is described that further reduces the number of variables required to describe them. This method, ordinal coding, reduces the size of data matrices, and facilitates retrieval of state codes. This paper advocates the use of both biological evidence and evidence internal to the cladogram itself to construct character state trees (CSTs). We discuss general models of character evolution (morphocline analysis, Fitch minimum mutation model, etc.) and their role in forming CSTs. Character state trees formed with theories of character evolution are referred to as transmodal characters. These transmodal characters are contrasted with cladogram characters (Mickevich, 1982), and the place of each in a phylogenetic analysis is discussed. The method for determining cladogram characters is detailed with more complicated examples than found in previous publications. We advocate testing transmodal characters by comparing them with the resultant cladogram characters. This comparison involves transformation series analysis (TSA; Mickevich, 1982) which is viewed as an extension of reciprocal illumination. The TSA procedure and its place in hypothesis testing are reviewed. Tracing the evolution of characters interests both systematists and non-systematists alike. When character state trees (transmodal characters) are optimized on pre-existing phylogenies, character phylogenies and attribute phylogenies result. Attributes are defined as a feature that may or may not be homologous (i.e., ecological categories, plant hosts, etc.). We provide two illustrations of this approach, one involving the evolution of the anuran ear and another involving the coevolution of the butterfly Heliconius and its hostplants. Finally, the components of phylogenetic character analysis can be used to test more general evolutionary theories such as the biogenetic law and vicariance biogeography.     

RAxML-III: a fast program for maximum likelihood-based inference of large phylogenetic trees

MOTIVATION: The computation of large phylogenetic trees with statistical models such as maximum likelihood or bayesian inference is computationally extremely intensive. It has repeatedly been demonstrated that these models are able to recover the true tree or a tree which is topologically closer to the true tree more frequently than less elaborate methods such as parsimony or neighbor joining. Due to the combinatorial and computational complexity the size of trees which can be computed on a Biologist's PC workstation within reasonable time is limited to trees containing approximately 100 taxa. RESULTS: In this paper we present the latest release of our program RAxML-III for rapid maximum likelihood-based inference of large evolutionary trees which allows for computation of 1.000-taxon trees in less than 24 hours on a single PC processor. We compare RAxML-III to the currently fastest implementations for maximum likelihood and bayesian inference: PHYML and MrBayes. Whereas RAxML-III performs worse than PHYML and MrBayes on synthetic data it clearly outperforms both programs on all real data alignments used in terms of speed and final likelihood values. Availability SUPPLEMENTARY INFORMATION: RAxML-III including all alignments and final trees mentioned in this paper is freely available as open source code at http://wwwbode.cs.tum/~stamatak CONTACT: stamatak@cs.tum.edu.     

Fels-Rand: an Xlisp-Stat program for the comparative analysis of data under phylogenetic uncertainty

MOTIVATION: Currently available programs for the comparative analysis of phylogenetic data do not perform optimally when the phylogeny is not completely specified (i.e. the phylogeny contains polytomies). Recent literature suggests that a better way to analyse the data would be to create random trees from the known phylogeny that are fully-resolved but consistent with the known tree. A computer program is presented, Fels-Rand, that performs such analyses. A randomisation procedure is used to generate trees that are fully resolved but whose structure is consistent with the original tree. Statistics are then calculated on a large number of these randomly-generated trees. Fels-Rand uses the object-oriented features of Xlisp-Stat to manipulate internal tree representations. Xlisp-Stat's dynamic graphing features are used to provide heuristic tools to aid in analysis, particularly outlier analysis. The usefulness of Xlisp-Stat as a system for phylogenetic computation is discussed. AVAILABILITY: Available from the author or at http://www.uq.edu.au/~ansblomb/Fels-Rand.sit.hqx. Xlisp-Stat is available from http://stat.umn.edu/~luke/xls/xlsinfo/xlsinfo.html. CONTACT: s.blomberg@abdn.ac.uk     

Phylogenetic reconstruction from non-genomic data

MOTIVATION: Recent results related to horizontal gene transfer suggest that phylogenetic reconstruction cannot be determined conclusively from sequence data, resulting in a shift from approaches based on polymorphism information in DNA or protein sequence to studies aimed at understanding the evolution of complete biological processes. The increasing amount of available information on metabolic pathways for several species makes it of greater relevance to understand the similarities and differences among such pathways. These similarities can then be used to infer phylogenetic trees not based exclusively in sequence data, therefore avoiding the previously mentioned problems. RESULTS: In this article, we present a method to assess the structural similarity of metabolic pathways for several organisms. Our algorithms work by using one of the three possible enzyme similarity measures (hierarchical, information content, gene ontology), and one of the two clustering methods (neighbor-joining, unweighted pair group method with arithmetic mean), to produce a phylogenetic tree both in Newick and graphic format. The web server implementing our algorithms is optimized to answer queries in linear time. AVAILABILITY: The software is available for free public use on a web server, at the address http://www.jaist.ac.jp/~clemente/cgi-bin/phylo.pl. It is available on demand in source code form for research use to educational institutions, non-profit research institutes, government research laboratories and individuals, for non-exclusive use, without the right of the licensee to further redistribute the source code.     

GenNon-h: Generating multiple sequence alignments on nonhomogeneous phylogenetic trees

ABSTRACT: BACKGROUND: A number of software packages are available to generate DNA multiple sequence alignments (MSAs) evolved under continuous-time Markov processes on phylogenetic trees. On the other hand, methods of simulating the DNA MSA directly from the transition matrices do not exist. Moreover, existing software restricts to the time-reversible models and it is not optimized to generate nonhomogeneous data (i.e. placing distinct substitution rates at different lineages). RESULTS: We present the first package designed to generate MSAs evolving under discrete-time Markov processes on phylogenetic trees, directly from probability substitution matrices. Based on the input model and a phylogenetic tree in the Newick format (with branch lengths measured as the expected number of substitutions per site), the algorithm produces DNA alignments of desired length. GenNon-h is publicly available for download. CONCLUSION: The software presented here is an efficient tool to generate DNA MSAs on a given phylogenetic tree. GenNon-h provides the user with the nonstationary or nonhomogeneous phylogenetic data that is well suited for testing complex biological hypotheses, exploring the limits of the reconstruction algorithms and their robustness to such models.     

On the biochemical systematics of selected mammalian taxa: empirical comparison of qualitative and quantitative approaches in the evaluation of protein electrophoretic data

Empirical data sets of Artiodactyla (Antilocapridae, Bovidae, Cervidae, Suidae), Carnivora (Mustelidae) and Rodentia (Sciuridae, Cricetidae, Arvicolidae, Muridae), obtained by horizontal starch el electrophoresis of 15–34 isoenzyme sstems, were used to calculate genetic distances and to construct phylogenetic trees by the following methods: Nei's D (corrected for small sample sizes) - UPGMA, FITCH, KITSCH (out of Felsenstein's PHYLIP-package); Rogers -distance - distance-Wanger tree; maximum likelihood approach (cavalli -Sforza -Edwards ); maximum parsimony method (wagner ); Hennigian cladogram. The results were re-examined using the statisticar methods of jackknife and bootstrap. The following problems became apparent and were studied in more detail: inconstancy of molecular evolutionary rate among taxa, non-uniformity of evolutionary rate among isoenzymes, possible convergence of alloenzymes, different evolutionary histories of taxa (radiations/bottlenecks), methodological influences sample sizes / rare alleles, comparability of data sets). The results show, that many branches of the various phylogenetic trees are fairly constant. The ambiguous position of the remaining OTU's is due to insufficient evidence in the primary data rather than to theroperties of cluster algorithms. However, since these problematic cases are also uncertain in phylogenies based on morphological characters and palaeontological results, even an increased data set may not lead to a cyear decision unless additional taxa of crucial importance are examined. Molecular evolutionary rate among taxa seems to be accelerated in some cases, possibly due to random fixation of different alleles during bottlenecks, when a highly polymorpic ancestral form underwent a series of adaptive radiations. Isoenzymes can be divided into groups with different evolutionary rates. Thus, data sets are only comparable with respect to genetic variability and differentiation, when they contain a similar amount of representatives of each of these categories.     

HICLAS: a taxonomic database system for displaying and comparing biological classification and phylogenetic trees

MOTIVATION: Numerous database management systems have been developed for processing various taxonomic data bases on biological classification or phylogenetic information. In this paper, we present an integrated system to deal with interacting classifications and phylogenies concerning particular taxonomic groups. RESULTS: An information-theoretic view (taxon view) has been applied to capture taxonomic concepts as taxonomic data entities. A data model which is suitable for supporting semantically interacting dynamic views of hierarchic classifications and a query method for interacting classifications have been developed. The concept of taxonomic view and the data model can also be expanded to carry phylogenetic information in phylogenetic trees. We have designed a prototype taxonomic database system called HICLAS (HIerarchical CLAssification System) based on the concept of taxon view, and the data models and query methods have been designed and implemented. This system can be effectively used in the taxonomic revisionary process, especially when databases are being constructed by specialists in particular groups, and the system can be used to compare classifications and phylogenetic trees. AVAILABILITY: Freely available at the WWW URL: http://aims.cps.msu.edu/hiclas/ CONTACT: pramanik@cps.msu.edu; lotus@wipm.whcnc.ac.cn     

真正柑桔果树群植物的分支学研究

本文用相容性分析方法(Compatability snalysis)分析了真正柑桔果树群(芸香科Rutaceae-柑桔亚科Aurantioideae-柑桔族(Citreae)-柑桔亚族(Citrinae)植物内各属间的分支学关系。给出了建立在7个相容性性状组成的最大族所决定的分支图。性状极性的确定使用了外群法。结果表明,柑桔属(Citrus L.)和多蕊桔属(Clymenia Swing)构成一个单系类群,他们的姐妹群是金柑属(Fortunella Swing.)。被认为起源于中国的3个属,柑桔属(Citrus)、金柑属(Fortunella)和积属(Poncirus Raf.)并未构成一个单系类群。本文还利用分支关系分析和讨论了真正柑桔果树群的种系发生关系。     

A phylogenetic analysis of Coelopidae (Diptera) based on morphological and DNA sequence data

The phylogenetic relationships of 22 species of Coelopidae are reconstructed based on a data matrix consisting of morphological and DNA sequence characters (16S rDNA, EF-1alpha). Optimal gap and transversion costs are determined via a sensitivity analysis and both equal weighting and a transversion cost of 2 are found to perform best based on taxonomic congruence, character incongruence, and tree support. The preferred phylogenetic hypothesis is fully resolved and well-supported by jackknife, bootstrap, and Bremer support values, but it is in conflict with the cladogram based on morphological characters alone. Most notably, the Coelopidae and the genus Coelopa are not monophyletic. However, partitioned Bremer Support and an analysis of node stability under different gap and transversion costs reveal that the critical clades rendering these taxa non-monophyletic are poorly supported. Furthermore, the monophyly of Coelopidae and Coelopa is not rejected in analyses using 16S rDNA that was manually aligned. The resolution of the tree based on this reduced data sets is, however, lower than for the tree based on the full data sets. Partitioned Bremer support values reveal that 16S rDNA characters provide the largest amount of tree support, but the support values are heavily dependent on analysis conditions. Problems with direct comparison of branch support values for trees derived using fixed alignments with those obtained under optimization alignment are discussed. Biogeographic history and available behavioral and genetic data are also discussed in light of this first cladogram for Coelopidae based on a quantitative phylogenetic analysis.     

IQPNNI: moving fast through tree space and stopping in time

An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast algorithms to generate a list of potential candidate trees. The key ingredient is the definition of so-called important quartets (IQs), which allow the computation of an intermediate tree in O(n(2)) time for n sequences. The resulting tree is then further optimized by applying the nearest neighbor interchange (NNI) operation. Subsequently a random fraction of the sequences is deleted from the best tree found so far. The deleted sequences are then re-inserted in the smaller tree using the important quartet puzzling (IQP) algorithm. These steps are repeated several times and the best tree, with respect to the likelihood criterion, is considered as the inferred phylogenetic tree. Moreover, we suggest a rule which indicates when to stop the search. Simulations show that IQPNNI gives a slightly better accuracy than other programs tested. Moreover, we applied the approach to 218 small subunit rRNA sequences and 500 rbcL sequences. We found trees with higher likelihood compared to the results by others. A program to reconstruct DNA or amino acid based phylogenetic trees is available online (http://www.bi.uni-duesseldorf.de/software/iqpnni).     

构建微生物分子分类系统进化树的快速运算法与数据结构

本文介绍了构建系统进化树的NJ方法（NeighborJoiningMethod）所涉及的算法与数据结构。文中给出了基于数据复用性的算法改进,获得了快速算法──FNJ算法,从而将算法的时间复杂度由（N⁵）降低为（N³）;并给出了自动绘制进化分枝图的算法。