Analysis of DNA sequence transformations on grids

Study of the evolution of species or organisms is essential for various biological applications. Evolution is typically studied at the molecular level by analyzing the mutations of DNA sequences of organisms. Techniques have been developed for building phylogenetic or evolutionary trees for a set of sequences. Though phylogenetic trees capture the overall evolutionary relationships among the sequences, they do not reveal fine-level details of the evolution. In this work, we attempt to resolve various fine-level sequence transformation details associated with a phylogenetic tree using cellular automata. In particular, our work tries to determine the cellular automata rules for neighbor-dependent mutations of segments of DNA sequences. We also determine the number of time steps needed for evolution of a progeny from an ancestor and the unknown segments of the intermediate sequences in the phylogenetic tree. Due to the existence of vast number of cellular automata rules, we have developed a grid system that performs parallel guided explorations of the rules on grid resources. We demonstrate our techniques by conducting experiments on a grid comprising machines in three countries and obtaining potentially useful statistics regarding evolutions in three HIV sequences. In particular, our work is able to verify the phenomenon of neighbor-dependent mutations and find that certain combinations of neighbor-dependent mutations, defined by a cellular automata rule, occur with greater than 90% probability. We also find the average number of time steps for mutations for some branches of phylogenetic tree over a large number of possible transformations with standard deviations less than 2.

The origins of the evolutionary signal used to predict protein-protein interactions

Background: The correlation of genetic distances between pairs of protein sequence alignments has been used to infer protein-protein interactions. It has been suggested that these correlations are based on the signal of co-evolution between interacting proteins. However, although mutations in different proteins associated with maintaining an interaction clearly occur (particularly in binding interfaces and neighbourhoods), many other factors contribute to correlated rates of sequence evolution. Proteins in the same genome are usually linked by shared evolutionary history and so it would be expected that there would be topological similarities in their phylogenetic trees, whether they are interacting or not. For this reason the underlying species tree is often corrected for. Moreover processes such as expression level, are known to effect evolutionary rates. However, it has been argued that the correlated rates of evolution used to predict protein interaction explicitly includes shared evolutionary history; here we test this hypothesis. Results: In order to identify the evolutionary mechanisms giving rise to the correlations between interaction proteins, we use phylogenetic methods to distinguish similarities in tree topologies from similarities in genetic distances. We use a range of datasets of interacting and non-interacting proteins from Saccharomyces cerevisiae. We find that the signal of correlated evolution between interacting proteins is predominantly a result of shared evolutionary rates, rather than similarities in tree topology, independent of evolutionary divergence. Conclusions: Since interacting proteins do not have tree topologies that are more similar than the control group of non-interacting proteins, it is likely that coevolution does not contribute much to, if any, of the observed correlations.

Evolutionary games with two timescales

We consider a two timescale model of learning by economic agents wherein active or 'ontogenetic' learning by individuals takes place on a fast scale and passive or 'phylogenetic' learning by society as a whole on a slow scale, each affecting the evolution of the other. The former is modelled by the Monte Carlo dynamics of physics, while the latter is modelled by the replicator dynamics of evolutionary biology. Various qualitative aspects of the dynamics are studied in some simple cases, both analytically and numerically, and its role as a useful modelling device is emphasized.

Species-area and species-individual relationships for tropical trees: A comparison of three 50-ha plots

1 Species-accumulation curves for woody plants were calculated in three tropical forests, based on fully mapped 50-ha plots in wet, old-growth forest in Peninsular Malaysia, in moist, old-growth forest in central Panama, and in dry, previously logged forest in southern India. A total of 610 000 stems were identified to species and mapped to < Im accuracy. Mean species number and stem number were calculated in quadrats as small as 5 m x 5 m to as large as 1000 m x 500 m, for a variety of stem sizes above 10 mm in diameter. Species-area curves were generated by plotting species number as a function of quadrat size; species-individual curves were generated from the same data, but using stem number as the independent variable rather than area. 2 Species-area curves had different forms for stems of different diameters, but species-individual curves were nearly independent of diameter class. With < 10(4) stems, species-individual curves were concave downward on log-log plots, with curves from different forests diverging, but beyond about 104 stems, the log-log curves became nearly linear, with all three sites having a similar slope. This indicates an asymptotic difference in richness between forests: the Malaysian site had 2.7 times as many species as Panama, which in turn was 3.3 times as rich as India. 3 Other details of the species-accumulation relationship were remarkably similar between the three sites. Rectangular quadrats had 5-27% more species than square quadrats of the same area, with longer and narrower quadrats increasingly diverse. Random samples of stems drawn from the entire 50 ha had 10-30% more species than square quadrats with the same number of stems. At both Pasoh and BCI, but not Mudumalai. species richness was slightly higher among intermediate-sized stems (50-100mm in diameter) than in either smaller or larger sizes, These patterns reflect aggregated distributions of individual species, plus weak density-dependent forces that tend to smooth the species abundance distribution and 'loosen' aggregations as stems grow. 4 The results provide support for the view that within each tree community, many species have their abundance and distribution guided more by random drift than deterministic interactions. The drift model predicts that the species-accumulation curve will have a declining slope on a log-log plot, reaching a slope of O.1 in about 50 ha. No other model of community structure can make such a precise prediction. 5 The results demonstrate that diversity studies based on different stem diameters can be compared by sampling identical numbers of stems. Moreover, they indicate that stem counts < 1000 in tropical forests will underestimate the percentage difference in species richness between two diverse sites. Fortunately, standard diversity indices (Fisher's sc, Shannon-Wiener) captured diversity differences in small stem samples more effectively than raw species richness, but both were sample size dependent. Two nonparametric richness estimators (Chao. jackknife) performed poorly, greatly underestimating true species richness.

Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

A fuzzy multistage evolutionary (FUME) clustering technique

n this paper, a multistage evolutionary scheme is proposed for clustering in a large data base, like speech data. This is achieved by clustering a small subset of the entire sample set in each stage and treating the cluster centroids so obtained as samples, together with another subset of samples not considered previously, as input data to the next stage. This is continued till the whole sample set is exhausted. The clustering is accomplished by constructing a fuzzy similarity matrix and using the fuzzy techniques proposed here. The technique is illustrated by an efficient scheme for voiced-unvoiced-silence classification of speech.

Tissue culture of forest trees: Clonal multiplication of Eucalyptus grandis L

Axillary shoot proliferation was obtained using explants of Eucalyptus grandis L. juvenile and mature stages on a defined medium. Murashige and Skoog medium (MS) supplemented with benzyladenine (BA), naphthalene acetic acid (NAA) and additional thiamine. Excised shoots were induced to root on a sequence of three media: (1) White's medium containing indoleacetic acid (IAA), NAA and indole butyric acid; (IBA), (2) half-strength MS medium with charcoal and (3) half-strength MS liquid medium. The two types of explants differed in rooting response, with juvenile-derived shoots giving 60% rooting and adult-derived ones only 35%. Thus, the factors limiting cloning of selected trees in vitro are determined to be those controlling rooting of shoots in E. grandis.

On the Structure of Contractible Edges in k-connected Partial k-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k - 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.

Mapping of fuelwood trees using geoinformatics

Rural population of India constitutes about 70% of the total population and traditional fuels account for 75% of the rural energy needs. Depletion of woodlands coupled with the persistent dependency on fuel wood has posed a serious problem for household energy provision in many parts. This study highlights that the traditional fuels still meet 85-95% of fuel needs in rural areas of Kolar district: people prefer fuel wood for cooking and agriculture residues for water heating and other purposes. However, rapid changes in land cover and land use in recent times have affected these traditional fuels availability necessitating inventorying, mapping and monitoring of bioresources for sustainable management of bioresources. Remote sensing data (Multispectal and Panchromatic), Geographic Information System (GIS), field surveys and non-destructive sampling were used to assess spatially the availability and demand of energy. Field surveys indicate that rural household depends on species such as Prosopis juliflora, Acacia nilotica, Acacia auriculiformis to meet fuel wood requirement for domestic activities. Hence, to take stock of fuel wood availability, mapping was done at species level (with 88% accuracy) considering villages as sampling units using fused multispectral and panchromatic data. (C) 2009 Elsevier Ltd. All rights reserved.

Evolutionary Significance of Self-acylation Property in Acyl Carrier Proteins

Acyl carrier protein is an integral component of many cellular metabolic processes. A number of studies have reported self-acylation behavior in acyl carrier proteins. Although AM exhibit high levels of similarity in their primary and tertiary structures, self-acylation behavior is restricted to only some ACPs that can be classified into two major families based on their function. The first family of ACPs is involved in polyketide biosynthesis, whereas the second family participates in fatty acid synthesis. Facilitated by the growing number of genome sequences available for analyses, large-scale phylogenetic studies were used in these studies to uncover as to how self-acylation behavior of acyl carrier proteins is linked with the evolution of metabolic pathways in organisms. These studies show that self-acylation behavior in acyl carrier proteins was lost during the course of evolution, with certain organisms and organelles viz. plastids, retaining it for specified functions. (C) 2009 IUBMB IUBMB Life, 61(8): 853-859, 2009

Branch-branch connections in trees analogous to hyphal fusions in fungal colonies

the leopard tree Caesalpinia ferrea (Leguminosae) a native of eastern Brazil-some of the leader branches connect to and fuse with neighbouring branches of the same tree. The bridge initials project out as pegs or protuberances and apparently extend in a coordinated manner, connecting branches up to 4 ft apart. The fusion of two branches of the same tree implies intra-plant communication involving signaling factor(s). The bridges resemble fusions between hyphae in a fungal colony. Whereas hyphal fusions are common and the process is apparently completed in <1 h, branch fusions in C. ferrea tree are limited and a slow process, apparently requiring several months to years to complete. Branch fusions in C. ferrea are in accord with Claus Mattheck's analysis that tree branches actually seek contact rather than avoid contacts.

Context-dependency of a complex fruit-frugivore mutualism: temporal variation in crop size and neighborhood effects

The quantity of fruit consumed by dispersers is highly variable among individuals within plant populations. The outcome Of Such selection operated by firugivores has been examined mostly with respect to changing spatial contexts. The influence of varying temporal contexts on frugivore choice, and their possible demographic and evolutionary consequences is poorly understood. We examined if temporal variation in fruit availability across a hierarchy of nested temporal levels (interannual, intraseasonal, 120 h, 24 h) altered frugivore choice for a complex seed dispersal system in dry tropical forests of southern India. The interactions between Phyllanthus emblica and its primary disperser (ruminants) was mediated by another frugivore (a primate),which made large quantities of fruit available on the ground to ruminants. The direction and strength of crop size and neighborhood effects on this interaction varied with changing temporal contexts.Fruit availability was higher in the first of the two study years, and at the start of the season in both years. Fruit persistence on trees,determined by primate foraging, was influenced by crop size andconspecific neighborhood densities only in the high fruit availability year. Fruit removal by ruminants was influenced by crop size in both years and neighborhood densities only in the high availability year. In both years, these effects were stronger at the start of the season.Intraseasonal reduction in fruit availability diminished inequalities in fruit removal by ruminants and the influence of crop size and fruiting neighborhoods. All trees were not equally attractive to frugivores in a P. emblica population at all points of time. Temporal asymmetry in frugivore-mediated selection could reduce potential for co-evolution between firugivores and plants by diluting selective pressures. Inter-dependencies; formed between disparate animal consumers can add additional levels of complexity to plant-frugivore mutualistic networks and have potential reproductive consequences for specific individuals within populations.

A Geometric Algorithm for Learning Oblique Decision Trees

In this paper we present a novel algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess goodness of hyperplanes at each node. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy, based on some recent variants of SVM, to assess the hyperplanes in such a way that the geometric structure in the data is taken into account. We show through empirical studies that our method is effective.

Analysis of the beta-glucoside utilization (bgl) genes of Shigella sonnei: evolutionary implications for their maintenance in a cryptic state

The pattern of expression of the genes involved in the utilization of aryl beta-glucosides such as arbutin and salicin is different in the genus Shigella compared to Escherichia coli. The results presented here indicate that the homologue of the cryptic bgl operon of E. coli is conserved in Shigella sonnei and is the primary system involved in beta-glucoside utilization in the organism. The organization of the bgl genes in 5. sonnei is similar to that of E. coli; however there are three major differences in terms of their pattern of expression. (i) The bglB gene, encoding phospho-beta-glucosidase B, is insertionally inactivated in 5. sonnei. As a result, mutational activation of the silent bgl promoter confers an Arbutin-positive (Arb(+)) phenotype to the cells in a single step; however, acquiring a Salicin-positive (Sal(+)) phenotype requires the reversion or suppression of the bglB mutation in addition. (ii) Unlike in E. coli, a majority of the activating mutations (conferring the Arb(+) phenotype) map within the unlinked hns locus, whereas activation of the E. coli bgl operon under the same conditions is predominantly due to insertions within the bglR locus. (iii) Although the bgl promoter is silent in the wild-type strain of 5. sonnei (as in the case of E. coli), transcriptional and functional analyses indicated a higher basal level of transcription of the downstream genes. This was correlated with a 1 bp deletion within the putative Rho-independent terminator present in the leader sequence preceding the homologue of the bglG gene. The possible evolutionary implications of these differences for the maintenance of the genes in the cryptic state are discussed.

Reducing the babel in plant volatile communication: using the forest to see the trees

While plants of a single species emit a diversity of volatile organic compounds (VOCs) to attract or repel interacting organisms, these specific messages may be lost in the midst of the hundreds of VOCs produced by sympatric plants of different species, many of which may have no signal content. Receivers must be able to reduce the babel or noise in these VOCs in order to correctly identify the message. For chemical ecologists faced with vast amounts of data on volatile signatures of plants in different ecological contexts, it is imperative to employ accurate methods of classifying messages, so that suitable bioassays may then be designed to understand message content. We demonstrate the utility of `Random Forests' (RF), a machine-learning algorithm, for the task of classifying volatile signatures and choosing the minimum set of volatiles for accurate discrimination, using datam from sympatric Ficus species as a case study. We demonstrate the advantages of RF over conventional classification methods such as principal component analysis (PCA), as well as data-mining algorithms such as support vector machines (SVM), diagonal linear discriminant analysis (DLDA) and k-nearest neighbour (KNN) analysis. We show why a tree-building method such as RF, which is increasingly being used by the bioinformatics, food technology and medical community, is particularly advantageous for the study of plant communication using volatiles, dealing, as it must, with abundant noise.