Implementation of placement and routing algorithms for computer aided design of printed circuit boards

The Printed Circuit Board (PCB) layout design is one of the most important and time consuming phases during equipment design process in all electronic industries. This paper is concerned with the development and implementation of a computer aided PCB design package. A set of programs which operate on a description of the circuit supplied by the user in the form of a data file and subsequently design the layout of a double-sided PCB has been developed. The algorithms used for the design of the PCB optimise the board area and the length of copper tracks used for the interconnections. The output of the package is the layout drawing of the PCB, drawn on a CALCOMP hard copy plotter and a Tektronix 4012 storage graphics display terminal. The routing density (the board area required for one component) achieved by this package is typically 0.8 sq. inch per IC. The package is implemented on a DEC 1090 system in Pascal and FORTRAN and SIGN(1) graphics package is used for display generation.

A co-evolutionary relationship exists between Endoraecium (Pucciniales) and its Acacia hosts in Australia

Endoraecium is a genus of rust fungi that infects several species of Acacia in Australia, South-East Asia and Hawaii. This study investigated the systematics of Endoraecium from 55 specimens in Australia based on a combined morphological and molecular approach. Phylogenetic analyses were conducted on partitioned datasets of loci from ribosomal and mitochondrial DNA. The recovered molecular phylogeny supported a recently published taxonomy based on morphology and host range that divided Endoraecium digitatum into five species. Spore morphology is synapomorphic and there is evidence Endoraecium co-evolved with its Acacia hosts. The broad host ranges of E. digitatum, E. parvum, E. phyllodiorum and E. violae-faustiae are revised in light of this study, and nine new species of Endoraecium are described from Australia based on host taxonomy, morphology and phylogenetic concordance.

Estimation of Execution Times of Process Control Algorithms on Microcomputers

An important question which has to be answered in evaluting the suitability of a microcomputer for a control application is the time it would take to execute the specified control algorithm. In this paper, we present a method of obtaining closed-form formulas to estimate this time. These formulas are applicable to control algorithms in which arithmetic operations and matrix manipulations dominate. The method does not require writing detailed programs for implementing the control algorithm. Using this method, the execution times of a variety of control algorithms on a range of 16-bit mini- and recently announced microcomputers are calculated. The formulas have been verified independently by an analysis program, which computes the execution time bounds of control algorithms coded in Pascal when they are run on a specified micro- or minicomputer.

Modeling ecological and evolutionary processes in spatially structured populations

Many species inhabit fragmented landscapes, resulting either from anthropogenic or from natural processes. The ecological and evolutionary dynamics of spatially structured populations are affected by a complex interplay between endogenous and exogenous factors. The metapopulation approach, simplifying the landscape to a discrete set of patches of breeding habitat surrounded by unsuitable matrix, has become a widely applied paradigm for the study of species inhabiting highly fragmented landscapes. In this thesis, I focus on the construction of biologically realistic models and their parameterization with empirical data, with the general objective of understanding how the interactions between individuals and their spatially structured environment affect ecological and evolutionary processes in fragmented landscapes. I study two hierarchically structured model systems, which are the Glanville fritillary butterfly in the Åland Islands, and a system of two interacting aphid species in the Tvärminne archipelago, both being located in South-Western Finland. The interesting and challenging feature of both study systems is that the population dynamics occur over multiple spatial scales that are linked by various processes. My main emphasis is in the development of mathematical and statistical methodologies. For the Glanville fritillary case study, I first build a Bayesian framework for the estimation of death rates and capture probabilities from mark-recapture data, with the novelty of accounting for variation among individuals in capture probabilities and survival. I then characterize the dispersal phase of the butterflies by deriving a mathematical approximation of a diffusion-based movement model applied to a network of patches. I use the movement model as a building block to construct an individual-based evolutionary model for the Glanville fritillary butterfly metapopulation. I parameterize the evolutionary model using a pattern-oriented approach, and use it to study how the landscape structure affects the evolution of dispersal. For the aphid case study, I develop a Bayesian model of hierarchical multi-scale metapopulation dynamics, where the observed extinction and colonization rates are decomposed into intrinsic rates operating specifically at each spatial scale. In summary, I show how analytical approaches, hierarchical Bayesian methods and individual-based simulations can be used individually or in combination to tackle complex problems from many different viewpoints. In particular, hierarchical Bayesian methods provide a useful tool for decomposing ecological complexity into more tractable components.

Evolutionary Genomics of Prokaryotic Viruses

Evolutionary history of biological entities is recorded within their nucleic acid sequences and can (sometimes) be deciphered by thorough genomic analysis. In this study we sought to gain insights into the diversity and evolution of bacterial and archaeal viruses. Our primary interest was pointed towards those virus groups/families for which comprehensive genomic analysis was not previously possible due to the lack of sufficient amount of genomic data. During the course of this work twenty-five putative proviruses integrated into various prokaryotic genomes were identified, enabling us to undertake a comparative genomics approach. This analysis allowed us to test the previously formulated evolutionary hypotheses and also provided valuable information on the molecular mechanisms behind the genome evolution of the studied virus groups.

Effects of environmental variation on ecological and evolutionary dynamics

Environmental variation is a fact of life for all the species on earth: for any population of any particular species, the local environmental conditions are liable to vary in both time and space. In today's world, anthropogenic activity is causing habitat loss and fragmentation for many species, which may profoundly alter the characteristics of environmental variation in remaining habitat. Previous research indicates that, as habitat is lost, the spatial configuration of remaining habitat will increasingly affect the dynamics by which populations are governed. Through the use of mathematical models, this thesis asks how environmental variation interacts with species properties to influence population dynamics, local adaptation, and dispersal evolution. More specifically, we couple continuous-time continuous-space stochastic population dynamic models to landscape models. We manipulate environmental variation via parameters such as mean patch size, patch density, and patch longevity. Among other findings, we show that a mixture of high and low quality habitat is commonly better for a population than uniformly mediocre habitat. This conclusion is justified by purely ecological arguments, yet the positive effects of landscape heterogeneity may be enhanced further by local adaptation, and by the evolution of short-ranged dispersal. The predicted evolutionary responses to environmental variation are complex, however, since they involve numerous conflicting factors. We discuss why the species that have high levels of local adaptation within their ranges may not be the same species that benefit from local adaptation during range expansion. We show how habitat loss can lead to either increased or decreased selection for dispersal depending on the type of habitat and the manner in which it is lost. To study the models, we develop a recent analytical method, Perturbation expansion, to enable the incorporation of environmental variation. Within this context, we use two methods to address evolutionary dynamics: Adaptive dynamics, which assumes mutations occur infrequently so that the ecological and evolutionary timescales can be separated, and via Genotype distributions, which assume mutations are more frequent. The two approaches generally lead to similar predictions yet, exceptionally, we show how the evolutionary response of dispersal behaviour to habitat turnover may qualitatively depend on the mutation rate.

The role of productivity in the ecological and evolutionary dynamics of predator-prey interaction

Productivity is predicted to drive the ecological and evolutionary dynamics of predator-prey interaction through changes in resource allocation between different traits. However, resources are seldom constantly available and thus temporal variation in productivity could have considerable effect on the species' potential to evolve. To study this, three long-term microbial laboratory experiments were established where Serratia marcescens prey bacteria was exposed to predation of protist Tetrahymena thermophila in different prey resource environments. The consequences of prey resource availability for the ecological properties of the predator-prey system, such as trophic dynamics, stability, and virulence, were determined. The evolutionary changes in species traits and prey genetic diversity were measured. The prey defence evolved stronger in high productivity environment. Increased allocation to defence incurred cost in terms of reduced prey resource use ability, which probably constrained prey evolution by increasing the effect of resource competition. However, the magnitude of this trade-off diminished when measured in high resource concentrations. Predation selected for white, non-pigmented, highly defensive prey clones that produced predation resistant biofilm. The biofilm defence was also potentially accompanied with cytotoxicity for predators and could have been traded off with high motility. Evidence for the evolution of predators was also found in one experiment suggesting that co-evolutionary dynamics could affect the evolution and ecology of predator-prey interaction. Temporal variation in resource availability increased variation in predator densities leading to temporally fluctuating selection for prey defences and resource use ability. Temporal variation in resource availability was also able to constrain prey evolution when the allocation to defence incurred high cost. However, when the magnitude of prey trade-off was small and the resource turnover was periodically high, temporal variation facilitated the formation of predator resistant biofilm. The evolution of prey defence constrained the transfer of energy from basal to higher trophic levels, decreasing the strength of top-down regulation on prey community. Predation and temporal variation in productivity decreased the stability of populations and prey traits in general. However, predation-induced destabilization was less pronounced in the high productivity environment where the evolution of prey defence was stronger. In addition, evolution of prey defence weakened the environmental variation induced destabilization of predator population dynamics. Moreover, protozoan predation decreased the S. marcescens virulence in the insect host moth (Parasemia plantaginis) suggesting that species interactions outside the context of host-pathogen relationship could be important indirect drivers for the evolution of pathogenesis. This thesis demonstrates that rapid evolution can affect various ecological properties of predator-prey interaction. The effect of evolution on the ecological dynamics depended on the productivity of the environment, being most evident in the constant environments with high productivity.

Evolutionary Genetics in the WIld : from Populations to Individuals

Predicting evolutionary outcomes and reconstructing past evolutionary transitions are among the main goals of evolutionary biology. Ultimately, understanding the mechanisms of evolutionary change will also provide answers to the timely question of whether and how organisms will adapt to changing environmental conditions. In this thesis, I have investigated the relative roles of natural selection, random genetic drift and genetic correlations in the evolution of complex traits at different levels of organisation from populations to individuals. I have shown that natural selection has been the driving force behind body shape divergence of marine and freshwater threespine stickleback (Gasterosteus aculeatus) populations, while genetic drift may have played a significant role in the more fine scale divergence among isolated freshwater populations. These results are concurrent with the patterns that have emerged in the published studies comparing the relative importance of natural selection and genetic drift as explanations for population divergence in different traits and taxa. I have also shown that body shape and armour divergence among threespine stickleback populations is likely to be biased by the patterns of genetic variation and covariation. Body shape and armour variation along the most likely direction of evolution the direction of maximum genetic variance reflects the general patterns of variation observed wild populations across the distribution range of the threespine stickleback. Conversely, it appears that genetic correlations between the sexes have not imposed significant constraints on the evolution of sexual dimorphism in threespine stickleback body shape and armour. I have demonstrated that the patterns of evolution seen in the wild can be experimentally recreated to tease out the effects of different selection agents in detail. In addition, I have shown how important it is to take into account the correlative nature of traits, when making interpretations about the effects of natural selection on individual traits. Overall, this thesis provides a demonstration of how considering the relative roles of different mechanism of evolutionary change at different levels of organisation can aid in an emergence of a comprehensive picture of how adaptive divergence in wild populations occurs.

A Proof of Convergence of the B-RED and P-RED Algorithms for Random Early Detection

In [8], we recently presented two computationally efficient algorithms named B-RED and P-RED for random early detection. In this letter, we present the mathematical proof of convergence of these algorithms under general conditions to local minima.

Applications of gene sequence polymorphisms in evolutionary genetic studies of Atlantic salmon (Salmo salar) and other teleost fish species

Evolutionary genetics incorporates traditional population genetics and studies of the origins of genetic variation by mutation and recombination, and the molecular evolution of genomes. Among the primary forces that have potential to affect the genetic variation within and among populations, including those that may lead to adaptation and speciation, are genetic drift, gene flow, mutations and natural selection. The main challenges in knowing the genetic basis of evolutionary changes is to distinguish the adaptive selection forces that cause existent DNA sequence variants and also to identify the nucleotide differences responsible for the observed phenotypic variation. To understand the effects of various forces, interpretation of gene sequence variation has been the principal basis of many evolutionary genetic studies. The main aim of this thesis was to assess different forms of teleost gene sequence polymorphisms in evolutionary genetic studies of Atlantic salmon (Salmo salar) and other species. Firstly, the level of Darwinian adaptive evolution affected coding regions of the growth hormone (GH) gene during the teleost evolution was investigated based on the sequence data existing in public databases. Secondly, a target gene approach was used to identify within population variation in the growth hormone 1 (GH1) gene in salmon. Then, a new strategy for single nucleotide polymorphisms (SNPs) discovery in salmonid fishes was introduced, and, finally, the usefulness of a limited number of SNP markers as molecular tools in several applications of population genetics in Atlantic salmon was assessed. This thesis showed that the gene sequences in databases can be utilized to perform comparative studies of molecular evolution, and some putative evidence of the existence of Darwinian selection during the teleost GH evolution was presented. In addition, existent sequence data was exploited to investigate GH1 gene variation within Atlantic salmon populations throughout its range. Purifying selection is suggested to be the predominant evolutionary force controlling the genetic variation of this gene in salmon, and some support for gene flow between continents was also observed. The novel approach to SNP discovery in species with duplicated genome fragments introduced here proved to be an effective method, and this may have several applications in evolutionary genetics with different species - e.g. when developing gene-targeted markers to investigate quantitative genetic variation. The thesis also demonstrated that only a few SNPs performed highly similar signals in some of the population genetic analyses when compared with the microsatellite markers. This may have useful applications when estimating genetic diversity in genes having a potential role in ecological and conservation issues, or when using hard biological samples in genetic studies as SNPs can be applied with relatively highly degraded DNA.

Natural actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic, natural-gradient and functi approximation ideas,and we provide their convergence proofs. Actor-critic reinforcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their compatibility with function-approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of special interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further reduce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal difference learning in the actor and by incorporating natural gradients. Our results extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.