Phylogenetic search through partial tree mixing.

BACKGROUND: Recent advances in sequencing technology have created large data sets upon which phylogenetic inference can be performed. Current research is limited by the prohibitive time necessary to perform tree search on a reasonable number of individuals. This research develops new phylogenetic algorithms that can operate on tens of thousands of species in a reasonable amount of time through several innovative search techniques. RESULTS: When compared to popular phylogenetic search algorithms, better trees are found much more quickly for large data sets. These algorithms are incorporated in the PSODA application available at http://dna.cs.byu.edu/psoda CONCLUSIONS: The use of Partial Tree Mixing in a partition based tree space allows the algorithm to quickly converge on near optimal tree regions. These regions can then be searched in a methodical way to determine the overall optimal phylogenetic solution.

Analysis of long branch extraction and long branch shortening.

BACKGROUND: Long branch attraction (LBA) is a problem that afflicts both the parsimony and maximum likelihood phylogenetic analysis techniques. Research has shown that parsimony is particularly vulnerable to inferring the wrong tree in Felsenstein topologies. The long branch extraction method is a procedure to detect a data set suffering from this problem so that Maximum Likelihood could be used instead of Maximum Parsimony. RESULTS: The long branch extraction method has been well cited and used by many authors in their analysis but no strong validation has been performed as to its accuracy. We performed such an analysis by an extensive search of the branch length search space under two topologies of six taxa, a Felsenstein-like topology and Farris-like topology. We also examine a long branch shortening method. CONCLUSIONS: The long branch extraction method seems to mask the majority of the search space rendering it ineffective as a detection method of LBA. A proposed alternative, the long branch shortening method, is also ineffective in predicting long branch attraction for all tree topologies.

Inferring gene regulatory networks from asynchronous microarray data with AIRnet.

BACKGROUND: Modern approaches to treating genetic disorders, cancers and even epidemics rely on a detailed understanding of the underlying gene signaling network. Previous work has used time series microarray data to infer gene signaling networks given a large number of accurate time series samples. Microarray data available for many biological experiments is limited to a small number of arrays with little or no time series guarantees. When several samples are averaged to examine differences in mean value between a diseased and normal state, information from individual samples that could indicate a gene relationship can be lost. RESULTS: Asynchronous Inference of Regulatory Networks (AIRnet) provides gene signaling network inference using more practical assumptions about the microarray data. By learning correlation patterns for the changes in microarray values from all pairs of samples, accurate network reconstructions can be performed with data that is normally available in microarray experiments. CONCLUSIONS: By focussing on the changes between microarray samples, instead of absolute values, increased information can be gleaned from expression data.

On the use of cartographic projections in visualizing phylo-genetic tree space.

Phylogenetic analysis is becoming an increasingly important tool for biological research. Applications include epidemiological studies, drug development, and evolutionary analysis. Phylogenetic search is a known NP-Hard problem. The size of the data sets which can be analyzed is limited by the exponential growth in the number of trees that must be considered as the problem size increases. A better understanding of the problem space could lead to better methods, which in turn could lead to the feasible analysis of more data sets. We present a definition of phylogenetic tree space and a visualization of this space that shows significant exploitable structure. This structure can be used to develop search methods capable of handling much larger data sets.

Acetylation and characterization of spruce (Picea abies) galactoglucomannans.

Acetylated galactoglucomannans (GGMs) are the main hemicellulose type in most softwood species and can be utilized as, for example, bioactive polymers, hydrocolloids, papermaking chemicals, or coating polymers. Acetylation of spruce GGM using acetic anhydride with pyridine as catalyst under different conditions was conducted to obtain different degrees of acetylation on a laboratory scale, whereas, as a classic method, it can be potentially transferred to the industrial scale. The effects of the amount of catalyst and acetic anhydride, reaction time, temperature and pretreatment by acetic acid were investigated. A fully acetylated product was obtained by refluxing GGM for two hours. The structures of the acetylated GGMs were determined by SEC-MALLS/RI, (1)H and (13)C NMR and FTIR spectroscopy. NMR studies also indicated migration of acetyl groups from O-2 or O-3 to O-6 after a heating treatment in a water bath. The thermal stability of the products was investigated by DSC-TGA.

An open source phylogenetic search and alignment package.

PSODA is a comprehensive phylogenetics package, including alignment, phylogenetic search under both parsimony and maximum likelihood, and visualisation and analysis tools. PSODA offers performance comparable to PAUP* in an open source package that aims to provide a foundation for researchers examining new phylogenetic algorithms. A key new feature is PsodaScript, an extension to the nearly ubiquitous NEXUS format, that includes conditional and loop constructs; thereby allowing complex meta-search techniques like the parsimony ratchet to be easily and compactly implemented. PSODA promises to be a valuable tool in the future development of novel phylogenetic techniques. This paper seeks to familiarise researchers with PSODA and its features, in particular the internal scripting language, PsodaScript. PSODA is freely available from the PSODA.

Parsimony accelerated maximum likelihood searches.

Phylogenetic search is a key tool used in a variety of biological research endeavours. However, this search problem is known to be computationally difficult, due to the astronomically large search space, making the use of heuristic methods necessary. The performance of heuristic methods for finding Maximum Likelihood (ML) trees can be improved by using parsimony as an initial estimator for ML. The time spent in performing the parsimony search to boost performance is insignificant compared to the time spent in the ML search, leading to an overall gain in search time. These parsimony boosted ML searches lead to topologies with scores statistically similar to the unboosted searches, but in less time.