Pool Evolution: A Parallel Pattern for Evolutionary and Symbolic Computing

We introduce a new parallel pattern derived from a specific application domain and show how it turns out to have application beyond its domain of origin. The pool evolution pattern models the parallel evolution of a population subject to mutations and evolving in such a way that a given fitness function is optimized. The pattern has been demonstrated to be suitable for capturing and modeling the parallel patterns underpinning various evolutionary algorithms, as well as other parallel patterns typical of symbolic computation. In this paper we introduce the pattern, we discuss its implementation on modern multi/many core architectures and finally present experimental results obtained with FastFlow and Erlang implementations to assess its feasibility and scalability.

On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω(m) messages, where m is the number of edges in the network, and Ω(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms. 

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

The signature of fine scale local adaptation in Atlantic salmon revealed from common garden experiments in nature

Understanding the extent, scale and genetic basis of local adaptation is important for conservation and management. Its relevance in salmonids at microgeographic scales, where dispersal (and hence potential gene flow) can be substantial, has however been questioned. Here we compare the fitness of communally-reared offspring of local and foreign Atlantic salmon Salmo salar from adjacent Irish rivers and reciprocal F1 hybrid crosses between them, in the wild ‘home’ environment of the local population. Experimental groups did not differ in wild smolt output but a catastrophic flood event may have limited our ability to detect freshwater performance differences, which were evident in a previous study. Foreign parr exhibited higher, and hybrids intermediate, emigration rates from the natal stream relative to local parr, consistent with genetically-based behavioural differences. Adult return rates were lower for the foreign compared to the local group. Overall lifetime success of foreigners and hybrids relative to locals was estimated at 31% and 40% (mean of both hybrid groups), respectively. The results imply a genetic basis to fitness differences among populations separated by only 50km, driven largely by variation in smolt to adult return rates. Hence even if supplementary stocking programs obtain broodstock from neighbouring rivers, the risk of extrinsic outbreeding depression may be high.

Convergent genetic and expression data implicate immunity in Alzheimer's disease

Background: Late-onset Alzheimer's disease (AD) is heritable with 20 genes showing genome-wide association in the International Genomics of Alzheimer's Project (IGAP). To identify the biology underlying the disease, we extended these genetic data in a pathway analysis.

Methods: The ALIGATOR and GSEA algorithms were used in the IGAP data to identify associated functional pathways and correlated gene expression networks in human brain.

Results: ALIGATOR identified an excess of curated biological pathways showing enrichment of association. Enriched areas of biology included the immune response (P = 3.27 X 10(-12) after multiple testing correction for pathways), regulation of endocytosis (P = 1.31 X 10(-11)), cholesterol transport (P = 2.96 X 10(-9)), and proteasome-ubiquitin activity (P = 1.34 X 10(-6)). Correlated gene expression analysis identified four significant network modules, all related to the immune response (corrected P = .002-.05).

Conclusions: The immime response, regulation of endocytosis, cholesterol transport, and protein ubiquitination represent prime targets for AD therapeutics. (C) 2015 Published by Elsevier Inc. on behalf of The Alzheimer's Association.

A Fast Algorithm for Sparse Support Vector Machines for Mobile Computing Applications

This research presents a fast algorithm for projected support vector machines (PSVM) by selecting a basis vector set (BVS) for the kernel-induced feature space, the training points are projected onto the subspace spanned by the selected BVS. A standard linear support vector machine (SVM) is then produced in the subspace with the projected training points. As the dimension of the subspace is determined by the size of the selected basis vector set, the size of the produced SVM expansion can be specified. A two-stage algorithm is derived which selects and refines the basis vector set achieving a locally optimal model. The model expansion coefficients and bias are updated recursively for increase and decrease in the basis set and support vector set. The condition for a point to be classed as outside the current basis vector and selected as a new basis vector is derived and embedded in the recursive procedure. This guarantees the linear independence of the produced basis set. The proposed algorithm is tested and compared with an existing sparse primal SVM (SpSVM) and a standard SVM (LibSVM) on seven public benchmark classification problems. Our new algorithm is designed for use in the application area of human activity recognition using smart devices and embedded sensors where their sometimes limited memory and processing resources must be exploited to the full and the more robust and accurate the classification the more satisfied the user. Experimental results demonstrate the effectiveness and efficiency of the proposed algorithm. This work builds upon a previously published algorithm specifically created for activity recognition within mobile applications for the EU Haptimap project [1]. The algorithms detailed in this paper are more memory and resource efficient making them suitable for use with bigger data sets and more easily trained SVMs.

Partially Ordered Preferences in Decision Trees: Computing Strategies with Imprecision in Probabilities

Partially ordered preferences generally lead to choices that do not abide by standard expected utility guidelines; often such preferences are revealed by imprecision in probability values. We investigate five criteria for strategy selection in decision trees with imprecision in probabilities: “extensive” Γ-maximin and Γ-maximax, interval dominance, maximality and E-admissibility. We present algorithms that generate strategies for all these criteria; our main contribution is an algorithm for Eadmissibility that runs over admissible strategies rather than over sets of probability distributions.

Adaptation of Cladocerans in metal-polluted heterogeneous environments

No presente trabalho o cladócero Daphnia longispina foi utilizado como organismo modelo para a avaliação dos efeitos ecológicos da adaptação a ambientes contaminados por metais. Foram amostradas populações naturais de D. longispina num local sujeito à contaminação por metais e num local próximo, de referência, ambos localizados no sistema aquático na área envolvente à mina abandonada de São Domingos. Várias linhagens clonais de ambas as populações foram mantidas em laboratório, sob condições controladas, para a execução dos testes. Um dos testes realizados permitiu estudar e quantificar as diferenças na tolerância letal entre as linhagens clonadas de ambas as populações e também avaliar os custos associados. Utilizando vinte linhagens clonais de D. longispina das duas populações verificou-se que apenas clones sensíveis ao cobre estavam presentes na população de referência e clones resistentes ao cobre estavam presentes na população do local contaminado. Os custos associados à tolerância foram ilustrados pela determinação de taxas alimentares mais baixas para a população tolerante quando comparadas com as da população de referência. Outro dos testes realizados permitiu comparar as respostas de clones de populações de ambos os locais – contaminado e referência – à exposição a concentrações sub-letais do metal cobre. A tolerância evidenciada anteriormente ao nível letal foi confirmada ao nível sub-letal, com o clone proveniente da população do local contaminado evidenciando uma maior tolerância ao cobre quando comparado com os restantes clones, para todos os parâmetros analisados (taxas alimentares, consumo de oxigénio, crescimento e reprodução). Os efeitos da aclimatação ao cobre ao longo de várias gerações foram também avaliados num clone de D. longispina. Os resultados evidenciaram a existência de uma adaptação fisiológica ao cobre ao longo das várias gerações que, no entanto, apenas aumentou marginalmente a tolerância a níveis de cobre letais. Para além disso, observou-se também uma grande variação nas respostas do clone de D. longispina estudado, não só entre concentrações de cobre mas também entre gerações. Os resultados obtidos nos vários estudos realizados com linhagens clonais de ambas as populações de D. longispina reforçam a importância de integrar a temática do desenvolvimento de tolerância à poluição aquando da avaliação dos riscos ambientais e ecológicos de compostos químicos, como os metais, no meio ambiente.

Genetic and bacterial programming for B-Spline neural networks design

The design phase of B-spline neural networks is a highly computationally complex task. Existent heuristics have been found to be highly dependent on the initial conditions employed. Increasing interest in biologically inspired learning algorithms for control techniques such as Artificial Neural Networks and Fuzzy Systems is in progress. In this paper, the Bacterial Programming approach is presented, which is based on the replication of the microbial evolution phenomenon. This technique produces an efficient topology search, obtaining additionally more consistent solutions.

The effect of redundancy and neutrality in genetic search

An experimental study aimed at assessing the influence of redundancy and neutrality on the performance of an (1+1)-ES evolution strategy modeled using Markov chains and applied to NK fitness landscapes is presented. For the study, two families of redundant binary representations, one non-neutral family which is based on linear transformations and that allows the phenotypic neighborhoods to be designed in a simple and effective way, and the neutral family based on the mathematical formulation of error control codes are used. The results indicate whether redundancy or neutrality affects more strongly the behavior of the algorithm used.

Training neuro-fuzzy models using evolution based algorithms

The normal design process for neural networks or fuzzy systems involve two different phases: the determination of the best topology, which can be seen as a system identification problem, and the determination of its parameters, which can be envisaged as a parameter estimation problem. This latter issue, the determination of the model parameters (linear weights and interior knots) is the simplest task and is usually solved using gradient or hybrid schemes. The former issue, the topology determination, is an extremely complex task, especially if dealing with real-world problems.

Ecological genetics in the North Atlantic: environmental gradients and adaptation at specific loci

The North Atlantic intertidal community provides a rich set of organismal and environmental material for the study of ecological genetics. Clearly defined environmental gradients exist at multiple spatial scales: there are broad latitudinal trends in temperature, meso-scale changes in salinity along estuaries, and smaller scale gradients in desiccation and temperature spanning the intertidal range. The geology and geography of the American and European coasts provide natural replication of these gradients, allowing for population genetic analyses of parallel adaptation to environmental stress and heterogeneity. Statistical methods have been developed that provide genomic neutrality tests of population differentiation and aid in the process of candidate gene identification. In this paper, we review studies of marine organisms that illustrate associations between an environmental gradient and specific genetic markers. Such highly differentiated markers become candidate genes for adaptation to the environmental factors in question, but the functional significance of genetic variants must be comprehensively evaluated. We present a set of predictions about locus-specific selection across latitudinal, estuarine, and intertidal gradients that are likely to exist in the North Atlantic. We further present new data and analyses that support and contradict these simple selection models. Some taxa show pronounced clinal variation at certain loci against a background of mild clinal variation at many loci. These cases illustrate the procedures necessary for distinguishing selection driven by internal genomic vs. external environmental factors. We suggest that the North Atlantic intertidal community provides a model system for identifying genes that matter in ecology due to the clarity of the environmental stresses and an extensive experimental literature on ecological function. While these organisms are typically poor genetic and genomic models, advances in comparative genomics have provided access to molecular tools that can now be applied to taxa with well-defined ecologies. As many of the organisms we discuss have tight physiological limits driven by climatic factors, this synthesis of molecular population genetics with marine ecology could provide a sensitive means of assessing evolutionary responses to climate change.

Genetic structure at range edge: Low diversity and high inbreeding in Southeast Asian mangrove (Avicennia marina) populations

Understanding the genetic composition and mating systems of edge populations provides important insights into the environmental and demographic factors shaping species’ distribution ranges. We analysed samples of the mangrove Avicennia marina from Vietnam, northern Philippines and Australia, with microsatellite markers. We compared genetic diversity and structure in edge (Southeast Asia, and Southern Australia) and core (North and Eastern Australia) populations, and also compared our results with previously published data from core and southern edge populations. Comparisons highlighted significantly reduced gene diversity and higher genetic structure in both margins compared to core populations, which can be attributed to very low effective population size, pollinator scarcity and high environmental pressure at distribution margins. The estimated level of inbreeding was significantly higher in northeastern populations compared to core and southern populations. This suggests that despite the high genetic load usually associated with inbreeding, inbreeding or even selfing may be advantageous in margin habitats due to the possible advantages of reproductive assurance, or local adaptation. The very high level of genetic structure and inbreeding show that populations of A. marina are functioning as independent evolutionary units more than as components of a metapopulation system connected by gene flow. The combinations of those characteristics make these peripheral populations likely to develop local adaptations and therefore to be of particular interest for conservation strategies as well as for adaptation to possible future environmental changes.

Design of neuro-fuzzy models by evolutionary and gradient-based algorithms

All systems found in nature exhibit, with different degrees, a nonlinear behavior. To emulate this behavior, classical systems identification techniques use, typically, linear models, for mathematical simplicity. Models inspired by biological principles (artificial neural networks) and linguistically motivated (fuzzy systems), due to their universal approximation property, are becoming alternatives to classical mathematical models. In systems identification, the design of this type of models is an iterative process, requiring, among other steps, the need to identify the model structure, as well as the estimation of the model parameters. This thesis addresses the applicability of gradient-basis algorithms for the parameter estimation phase, and the use of evolutionary algorithms for model structure selection, for the design of neuro-fuzzy systems, i.e., models that offer the transparency property found in fuzzy systems, but use, for their design, algorithms introduced in the context of neural networks. A new methodology, based on the minimization of the integral of the error, and exploiting the parameter separability property typically found in neuro-fuzzy systems, is proposed for parameter estimation. A recent evolutionary technique (bacterial algorithms), based on the natural phenomenon of microbial evolution, is combined with genetic programming, and the resulting algorithm, bacterial programming, advocated for structure determination. Different versions of this evolutionary technique are combined with gradient-based algorithms, solving problems found in fuzzy and neuro-fuzzy design, namely incorporation of a-priori knowledge, gradient algorithms initialization and model complexity reduction.

The activity of mouse Cerberus like 2 during cardiogenesis - genetic and morphogenetic studies

Cardiogenesis is a delicate and complex process that requires the coordination of an intricate network of pathways and the different cell types. Therefore, understanding heart development at the morphogenetic level is an essential requirement to uncover the causes of congenital heart disease and to provide insight for disease therapies. Mouse Cerberus like 2 (Cerl2) has been defined as a Nodal antagonist in the node with an important role in the Left-Right (L/R) axis establishment, at the early embryonic development. As expected, Cerl2 knockout mice (Cerl2-/-) showed multiple laterality defects with associated cardiac failure. In order to identify the endogenous role of Cerl2 during heart formation independent of its described functions in the node, we accurately analyzed animals where laterality defects were not present. We thereby unravel the consequences of Cerl2 lossof- function in the heart, namely increased left ventricular thickness due to hyperplasia of cardiomyocytes and de-regulated expression of cardiac genes. Furthermore, the Cerl2 mutant neonates present impaired cardiac function. Once that the cardiac expression of Cerl2 is mostly observed in the left ventricle until around midgestration, this result suggest a specific regulatory role of Cerl2 during the formation of the left ventricular myoarchitecture. Here, we present two possible molecular mechanisms underlying the cardiac Cerl2 function, the regulation of Cerl2 antagonist in activation of the TGFßs/Nodal/Activin/Smad2 signaling identified by increased Smad2 phosphorilation in Cerl2-/- hearts and the negative feedback between Cerl2 and Wnt/ß-catenin signaling in heart formation. In this work and since embryonic stem cells derived from 129 mice strain is extensively used to produce targeted mutants, we also present echocardiographic reference values to progressive use of juveniles and young adult 129/Sv strain in cardiac studies. In addition, we investigate the cardiac physiology of the surviving Cerl2 mutants in 129/Sv background over time through a follow-up study using echocardiographic analysis. Our results revealed that Cerl2-/- mice are able to improve and maintain the diastolic and most of systolic cardiac physiologic parameters as analyzed until young adult age. Since Cerl2 is no longer expressed in the postnatal heart, we suggest that an intrinsic and compensatory mechanism of adaptation may be active for recovering the decreased cardiac function found in Cerl2 mutant neonates. Altogether, these data highlight the role of Cerl2 during embryonic heart development in mice. Furthermore, we also suggest that Cerl2-/- may be an interesting model to uncover the molecular, cellular and physiological mechanisms behind the improvement of the cardiac function, contributing to the development of therapeutic approaches to treat heart failures.