Evolving graphs: dynamical models, inverse problems and propagation

Applications such as neuroscience, telecommunication, online social networking, transport and retail trading give rise to connectivity patterns that change over time. In this work, we address the resulting need for network models and computational algorithms that deal with dynamic links. We introduce a new class of evolving range-dependent random graphs that gives a tractable framework for modelling and simulation. We develop a spectral algorithm for calibrating a set of edge ranges from a sequence of network snapshots and give a proof of principle illustration on some neuroscience data. We also show how the model can be used computationally and analytically to investigate the scenario where an evolutionary process, such as an epidemic, takes place on an evolving network. This allows us to study the cumulative effect of two distinct types of dynamics.

Generic systolic array for genetic algorithms

The authors present a systolic design for a simple GA mechanism which provides high throughput and unidirectional pipelining by exploiting the inherent parallelism in the genetic operators. The design computes in O(N+G) time steps using O(N2) cells where N is the population size and G is the chromosome length. The area of the device is independent of the chromosome length and so can be easily scaled by replicating the arrays or by employing fine-grain migration. The array is generic in the sense that it does not rely on the fitness function and can be used as an accelerator for any GA application using uniform crossover between pairs of chromosomes. The design can also be used in hybrid systems as an add-on to complement existing designs and methods for fitness function acceleration and island-style population management

Soft topographic map for clustering and classification of bacteria

In this work a new method for clustering and building a topographic representation of a bacteria taxonomy is presented. The method is based on the analysis of stable parts of the genome, the so-called “housekeeping genes”. The proposed method generates topographic maps of the bacteria taxonomy, where relations among different type strains can be visually inspected and verified. Two well known DNA alignement algorithms are applied to the genomic sequences. Topographic maps are optimized to represent the similarity among the sequences according to their evolutionary distances. The experimental analysis is carried out on 147 type strains of the Gammaprotebacteria class by means of the 16S rRNA housekeeping gene. Complete sequences of the gene have been retrieved from the NCBI public database. In the experimental tests the maps show clusters of homologous type strains and present some singular cases potentially due to incorrect classification or erroneous annotations in the database.

Parallel genetic algorithms for the tuning of a fuzzy AQM controller

This paper presents the results of the application of a parallel Genetic Algorithm (GA) in order to design a Fuzzy Proportional Integral (FPI) controller for active queue management on Internet routers. The Active Queue Management (AQM) policies are those policies of router queue management that allow the detection of network congestion, the notification of such occurrences to the hosts on the network borders, and the adoption of a suitable control policy. Two different parallel implementations of the genetic algorithm are adopted to determine an optimal configuration of the FPI controller parameters. Finally, the results of several experiments carried out on a forty nodes cluster of workstations are presented.

Implementing a generic systolic array for genetic algorithms

We have designed a highly parallel design for a simple genetic algorithm using a pipeline of systolic arrays. The systolic design provides high throughput and unidirectional pipelining by exploiting the implicit parallelism in the genetic operators. The design is significant because, unlike other hardware genetic algorithms, it is independent of both the fitness function and the particular chromosome length used in a problem. We have designed and simulated a version of the mutation array using Xilinix FPGA tools to investigate the feasibility of hardware implementation. A simple 5-chromosome mutation array occupies 195 CLBs and is capable of performing more than one million mutations per second. I. Introduction Genetic algorithms (GAs) are established search and optimization techniques which have been applied to a range of engineering and applied problems with considerable success [1]. They operate by maintaining a population of trial solutions encoded, using a suitable encoding scheme.

Evolutionary bi-stability in pathogen transmission mode

Many pathogens transmit to new hosts by both infection (horizontal transmission) and transfer to the infected host's offspring (vertical transmission). These two transmission modes require speci®c adap- tations of the pathogen that can be mutually exclusive, resulting in a trade-off between horizontal and vertical transmission. We show that in mathematical models such trade-offs can lead to the simultaneous existence of two evolutionary stable states (evolutionary bi-stability) of allocation of resources to the two modes of transmission. We also show that jumping between evolutionary stable states can be induced by gradual environmental changes. Using quantitative PCR-based estimates of abundance in seed and vege- tative parts, we show that the pathogen of wheat, Phaeosphaeria nodorum, has jumped between two distinct states of transmission mode twice in the past 160 years, which, based on published evidence, we interpret as adaptation to environmental change. The ®nding of evolutionary bi-stability has impli- cations for human, animal and other plant diseases. An ill-judged change in a disease control programme could cause the pathogen to evolve a new, and possibly more damaging, combination of transmission modes. Similarly, environmental changes can shift the balance between transmission modes, with adverse effects on human, animal and plant health.

Mapping and controlling molecular processes: The application of control theory and system identification algorithms to ASOPS and other fast pulse spectroscopies

Asynchronous Optical Sampling (ASOPS) [1,2] and frequency comb spectrometry [3] based on dual Ti:saphire resonators operated in a master/slave mode have the potential to improve signal to noise ratio in THz transient and IR sperctrometry. The multimode Brownian oscillator time-domain response function described by state-space models is a mathematically robust framework that can be used to describe the dispersive phenomena governed by Lorentzian, Debye and Drude responses. In addition, the optical properties of an arbitrary medium can be expressed as a linear combination of simple multimode Brownian oscillator functions. The suitability of a range of signal processing schemes adopted from the Systems Identification and Control Theory community for further processing the recorded THz transients in the time or frequency domain will be outlined [4,5]. Since a femtosecond duration pulse is capable of persistent excitation of the medium within which it propagates, such approach is perfectly justifiable. Several de-noising routines based on system identification will be shown. Furthermore, specifically developed apodization structures will be discussed. These are necessary because due to dispersion issues, the time-domain background and sample interferograms are non-symmetrical [6-8]. These procedures can lead to a more precise estimation of the complex insertion loss function. The algorithms are applicable to femtosecond spectroscopies across the EM spectrum. Finally, a methodology for femtosecond pulse shaping using genetic algorithms aiming to map and control molecular relaxation processes will be mentioned.

Managing threatened species – the ecological toolbox, evolutionary theory and the declining-population paradigm

1. The management of threatened species is an important practical way in which conservationists can intervene in the extinction process and reduce the loss of biodiversity. Understanding the causes of population declines (past, present and future) is pivotal to designing effective practical management. This is the declining-population paradigm identified by Caughley. 2. There are three broad classes of ecological tool used by conservationists to guide management decisions for threatened species: statistical models of habitat use, demographic models and behaviour-based models. Each of these is described here, illustrated with a case study and evaluated critically in terms of its practical application. 3. These tools are fundamentally different. Statistical models of habitat use and demographic models both use descriptions of patterns in abundance and demography, in relation to a range of factors, to inform management decisions. In contrast, behaviourbased models describe the evolutionary processes underlying these patterns, and derive such patterns from the strategies employed by individuals when competing for resources under a specific set of environmental conditions. 4. Statistical models of habitat use and demographic models have been used successfully to make management recommendations for declining populations. To do this, assumptions are made about population growth or vital rates that will apply when environmental conditions are restored, based on either past data collected under favourable environmental conditions or estimates of these parameters when the agent of decline is removed. As a result, they can only be used to make reliable quantitative predictions about future environments when a comparable environment has been experienced by the population of interest in the past. 5. Many future changes in the environment driven by management will not have been experienced by a population in the past. Under these circumstances, vital rates and their relationship with population density will change in the future in a way that is not predictable from past patterns. Reliable quantitative predictions about population-level responses then need to be based on an explicit consideration of the evolutionary processes operating at the individual level. 6. Synthesis and applications. It is argued that evolutionary theory underpins Caughley’s declining-population paradigm, and that it needs to become much more widely used within mainstream conservation biology. This will help conservationists examine critically the reliability of the tools they have traditionally used to aid management decision-making. It will also give them access to alternative tools, particularly when predictions are required for changes in the environment that have not been experienced by a population in the past.

Evolutionary relationships of "candidatus riesia spp.," endosymbiotic enterobacteriaceae living within hematophagous primate lice

The primary endosymbiotic bacteria from three species of parasitic primate lice were characterized molecularly. We have confirmed the characterization of the primary endosymbiont (P-endosymbiont) of the human head/body louse Pediculus humanus and provide new characterizations of the P-endosymbionts from Pediculus schaeffi from chimpanzees and Pthirus pubis, the pubic louse of humans. The endosymbionts show an average percent sequence divergence of 11 to 15% from the most closely related known bacterium "Candidatus Arsenophonus insecticola." We propose that two additional species be added to the genus "Candidatus Riesia." The new species proposed within "Candidatus Riesia" have sequence divergences of 3.4% and 10 to 12% based on uncorrected pairwise differences. Our Bayesian analysis shows that the branching pattern for the primary endosymbionts was the same as that for their louse hosts, suggesting a long coevolutionary history between primate lice and their primary endosymbionts. We used a calibration of 5.6 million years to date the divergence between endosymbionts from human and chimpanzee lice and estimated an evolutionary rate of nucleotide substitution of 0.67% per million years, which is 15 to 30 times faster than previous estimates calculated for Buchnera, the primary endosymbiont in aphids. Given the evidence for cospeciation with primate lice and the evidence for fast evolutionary rates, this lineage of endosymbiotic bacteria can be evaluated as a fast-evolving marker of both louse and primate evolutionary histories.

The genome strikes back: The evolutionary importance of defence against mobile elements

Increasingly, we regard the genome as a site and source of genetic conflict. This fascinating 'bottom-up' view brings up appealing connections between genome biology and whole-organism ecology, in which populations of elements compete with one another in their genomic habitat. Unlike other habitats, though, a host genome has its own evolutionary interests and is often able to defend itself against molecular parasites. Most well-studied organisms employ strategies to protect their genomes against the harmful effects of genomic parasites, including methylation, various pathways of RNA interference, and more unusual tricks such as repeat induced point-mutation (RIP). These genome defence systems are not obscure biological curiosities, but fundamentally important to the integrity and cohesion of the genome, and exert a powerful influence on genome evolution.

Evolutionary history of vegetative reproduction in Porpidia s. l. (lichen-forming ascomycota)

The evolutionary history of gains and losses of vegetative reproductive propagules (soredia) in Porpidia s.l., a group of lichen-forming ascomycetes, was clarified using Bayesian Markov chain Monte Carlo (MCMC) approaches to monophyly tests and a combined MCMC and maximum likelihood approach to ancestral character state reconstructions. The MCMC framework provided confidence estimates for the reconstructions of relationships and ancestral character states, which formed the basis for tests of evolutionary hypotheses. Monophyly tests rejected all hypotheses that predicted any clustering of reproductive modes in extant taxa. In addition, a nearest-neighbor statistic could not reject the hypothesis that the vegetative reproductive mode is randomly distributed throughout the group. These results show that transitions between presence and absence of the vegetative reproductive mode within Porpidia s.l. occurred several times and independently of each other. Likelihood reconstructions of ancestral character states at selected nodes suggest that - contrary to previous thought - the ancestor to Porpidia s.l. already possessed the vegetative reproductive mode. Furthermore, transition rates are reconstructed asymmetrically with the vegetative reproductive mode being gained at a much lower rate than it is lost. A cautious note has to be added, because a simulation study showed that the ancestral character state reconstructions were highly dependent on taxon sampling. However, our central conclusions, particularly the higher rate of change from vegetative reproductive mode present to absent than vice versa within Porpidia s.l., were found to be broadly independent of taxon sampling. [Ancestral character state reconstructions; Ascomycota, Bayesian inference; hypothesis testing; likelihood; MCMC; Porpidia; reproductive systems]

Large punctuational contribution of speciation to evolutionary divergence at the molecular level

A long-standing debate in evolutionary biology concerns whether species diverge gradually through time or by punctuational episodes at the time of speciation. We found that approximately 22% of substitutional changes at the DNA level can be attributed to punctuational evolution, and the remainder accumulates from background gradual divergence. Punctuational effects occur at more than twice the rate in plants and fungi than in animals, but the proportion of total divergence attributable to punctuational change does not vary among these groups. Punctuational changes cause departures from a clock-like tempo of evolution, suggesting that they should be accounted for in deriving dates from phylogenies. Punctuational episodes of evolution may play a larger role in promoting evolutionary divergence than has previously been appreciated.