Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster.

Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo (DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado. Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros tratamos una nueva variante del problema DCMST, que consiste en encontrar el árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que, en general, construiremos bosques de DRCMSTs. El modelado en los problemas de dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y determinar el rol de los nodos en la red. Proponemos una nueva representación basada en permutaciones para codificar los bosques de DRCMSTs. En esta nueva representación, una permutación codifica simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos de computación evolutiva diferentes que codifican los individuos de la población utilizando la representación propuesta. Los algoritmos que utilizamos son: algoritmo de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo genético de estado estacionario (ssGA), estrategia evolutiva basada en la matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista (ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode the forest of DRCMSTs. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight diferent evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm (EDA), generational genetic algorithm (gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES), non-elitist evolution strategy (NonElististES) and particle swarm optimization (PSO). The best results are for the estimation of distribution algorithm and both types of genetic algorithms, although the genetic algorithms are significantly faster. iv

Mode matches and their locations in the hydrophobic free energy sequences of peptide ligands and their receptor eigenfunctions

Patterns in sequences of amino acid hydrophobic free energies predict secondary structures in proteins. In protein folding, matches in hydrophobic free energy statistical wavelengths appear to contribute to selective aggregation of secondary structures in “hydrophobic zippers.” In a similar setting, the use of Fourier analysis to characterize the dominant statistical wavelengths of peptide ligands’ and receptor proteins’ hydrophobic modes to predict such matches has been limited by the aliasing and end effects of short peptide lengths, as well as the broad-band, mode multiplicity of many of their frequency (power) spectra. In addition, the sequence locations of the matching modes are lost in this transformation. We make new use of three techniques to address these difficulties: (i) eigenfunction construction from the linear decomposition of the lagged covariance matrices of the ligands and receptors as hydrophobic free energy sequences; (ii) maximum entropy, complex poles power spectra, which select the dominant modes of the hydrophobic free energy sequences or their eigenfunctions; and (iii) discrete, best bases, trigonometric wavelet transformations, which confirm the dominant spectral frequencies of the eigenfunctions and locate them as (absolute valued) moduli in the peptide or receptor sequence. The leading eigenfunction of the covariance matrix of a transmembrane receptor sequence locates the same transmembrane segments seen in n-block-averaged hydropathy plots while leaving the remaining hydrophobic modes unsmoothed and available for further analyses as secondary eigenfunctions. In these receptor eigenfunctions, we find a set of statistical wavelength matches between peptide ligands and their G-protein and tyrosine kinase coupled receptors, ranging across examples from 13.10 amino acids in acid fibroblast growth factor to 2.18 residues in corticotropin releasing factor. We find that the wavelet-located receptor modes in the extracellular loops are compatible with studies of receptor chimeric exchanges and point mutations. A nonbinding corticotropin-releasing factor receptor mutant is shown to have lost the signatory mode common to the normal receptor and its ligand. Hydrophobic free energy eigenfunctions and their transformations offer new quantitative physical homologies in database searches for peptide-receptor matches.

A general additive distance with time-reversibility and rate variation among nucleotide sites.

As additivity is a very useful property for a distance measure, a general additive distance is proposed under the stationary time-reversible (SR) model of nucleotide substitution or, more generally, under the stationary, time-reversible, and rate variable (SRV) model, which allows rate variation among nucleotide sites. A method for estimating the mean distance and the sampling variance is developed. In addition, a method is developed for estimating the variance-covariance matrix of distances, which is useful for the statistical test of phylogenies and molecular clocks. Computer simulation shows (i) if the sequences are longer than, say, 1000 bp, the SR method is preferable to simpler methods; (ii) the SR method is robust against deviations from time-reversibility; (iii) when the rate varies among sites, the SRV method is much better than the SR method because the distance is seriously underestimated by the SR method; and (iv) our method for estimating the sampling variance is accurate for sequences longer than 500 bp. Finally, a test is constructed for testing whether DNA evolution follows a general Markovian model.

DEVCON: Stata module to apply the deviation contrast transform to estimation results

devcon transforms the coefficients of 0/1 dummy variables so that they reflect deviations from the "grand mean" rather than deviations from the reference category (the transformed coefficients are equivalent to those obtained by the so called "effects coding") and adds the coefficient for the reference category. The variance-covariance matrix of the estimates is transformed accordingly. The transformed estimated can be used with post estimation procedures. In particular, devcon can be used to solve the identification problem for dummy variable effects in the so-called Blinder-Oaxaca decomposition (see the oaxaca package).

Divergent environments and population bottlenecks fail to generate premating isolation in Drosophila pseudoobscura

While the feasibility of bottleneck-induced speciation is in doubt, population bottlenecks may still affect the speciation process by interacting with divergent selection. To explore this possibility, I conducted a laboratory speciation experiment using Drosophila pseudoobscura involving 78 replicate populations assigned in a two-way factorial design to both bottleneck (present vs. absent) and environment (ancestral vs. novel) treatments. Populations independently evolved under these treatments and were then tested for assortative mating and male mating success against their common ancestor. Bottlenecks alone did not generate any premating isolation, despite an experimental design that was conducive to bottleneck-induced speciation. Premating isolation also did not evolve in the novel environment treatment, neither in the presence nor absence of bottlenecks. However, male mating success was significantly reduced in the novel environment treatment, both as a plastic response to this environment and as a result of environment-dependent inbreeding effects in the bottlenecked populations. Reduced mating success of derived males will hamper speciation by enhancing the mating success of immigrant, ancestral males. Novel environments are generally thought to promote ecological speciation by generating divergent natural selection. In the current experiment, however, the novel environment did not cause the evolution of any premating isolation and it reduced the likelihood of speciation through its effects on male mating success.

Multivariate quantitative genetics and the Lek Paradox: Genetic variance in male sexually selected traits of Drosophila serrata under field control

Single male sexually selected traits have been found to exhibit substantial genetic variance, even though natural and sexual selection are predicted to deplete genetic variance in these traits. We tested whether genetic variance in multiple male display traits of Drosophila serrata was maintained under field conditions. A breeding design involving 300 field-reared males and their laboratory-reared offspring allowed the estimation of the genetic variance-covariance matrix for six male cuticular hydrocarbons (CHCs) under field conditions. Despite individual CHCs displaying substantial genetic variance under field conditions, the vast majority of genetic variance in CHCs was not closely associated with the direction of sexual selection measured on field phenotypes. Relative concentrations of three CHCs correlated positively with body size in the field, but not under laboratory conditions, suggesting condition-dependent expression of CHCs under field conditions. Therefore condition dependence may not maintain genetic variance in preferred combinations of male CHCs under field conditions, suggesting that the large mutational target supplied by the evolution of condition dependence may not provide a solution to the lek paradox in this species. Sustained sexual selection may be adequate to deplete genetic variance in the direction of selection, perhaps as a consequence of the low rate of favorable mutations expected in multiple trait systems.

Phenotypic divergence along lines of genetic variance

Natural populations inhabiting the same environment often independently evolve the same phenotype. Is this replicated evolution a result of genetic constraints imposed by patterns of genetic covariation? We looked for associations between directions of morphological divergence and the orientation of the genetic variance-covariance matrix (G) by using an experimental system of morphological evolution in two allopatric nonsister species of rainbow fish. Replicate populations of both Melanotaenia eachamensis and Melanotaenia duboulayi have independently adapted to lake versus stream hydrodynamic environments. The major axis of divergence (z) among all eight study populations was closely associated with the direction of greatest genetic variance (g(max)), suggesting directional genetic constraint on evolution. However, the direction of hydrodynamic adaptation was strongly associated with vectors of G describing relatively small proportions of the total genetic variance, and was only weakly associated with g(max). In contrast, divergence between replicate populations within each habitat was approximately proportional to the level of genetic variance, a result consistent with theoretical predictions for neutral phenotypic divergence. Divergence between the two species was also primarily along major eigenvectors of G. Our results therefore suggest that hydrodynamic adaptation in rainbow fish was not directionally constrained by the dominant eigenvector of G. Without partitioning divergence as a consequence of the adaptation of interest (here, hydrodynamic adaptation) from divergence due to other processes, empirical studies are likely to overestimate the potential for the major eigenvectors of G to directionally constrain adaptive evolution.

Modeling the relationships between adult attachment patterns and borderline personality disorder: The role of impulsivity and aggressiveness

To obtain a better understanding of the associations among Borderline Personality Disorder (BPD), adult attachment patterns, impulsivity, and aggressiveness, we tested four competing models of these relationships: a) BPD is associated with the personality traits of impulsivity and aggressiveness, but adult attachment patterns predict neither BPD nor impulsive/aggressive features; b) adult attachment patterns are significant predictors of BPD but not of impulsive/aggressive traits, although these traits correlate with BPD; c) adult attachment patterns are significant predictors of impulsive and aggressive traits, which in turn predict BPD; and d) adult attachment patterns significantly predict both BPD and impulsive/aggressive traits. We assessed 466 consecutively admitted outpatients using the Structured Clinical Interview for DSM-IV Axis II Personality Disorders (V. 2.0), the Attachment Style Questionnaire, the Barratt Impulsiveness Scale-11, and the Aggression Questionnaire. Maximum likelihood structural equation modeling of the covariance matrix showed that model (c) was the best fitting model (chi(2) (21) = 31.67, p >.05, RMSEA = .023, test of close fit p >.85). This result indicates that adult attachment patterns act indirectly as risk factors for BPD because of their relationships with aggressive/impulsive personality traits.

Analysis of population pharmacokinetic data using NONMEM and WinBUGS

The aim of this report is to describe the use of WinBUGS for two datasets that arise from typical population pharmacokinetic studies. The first dataset relates to gentamicin concentration-time data that arose as part of routine clinical care of 55 neonates. The second dataset incorporated data from 96 patients receiving enoxaparin. Both datasets were originally analyzed by using NONMEM. In the first instance, although NONMEM provided reasonable estimates of the fixed effects parameters it was unable to provide satisfactory estimates of the between-subject variance. In the second instance, the use of NONMEM resulted in the development of a successful model, albeit with limited available information on the between-subject variability of the pharmacokinetic parameters. WinBUGS was used to develop a model for both of these datasets. Model comparison for the enoxaparin dataset was performed by using the posterior distribution of the log-likelihood and a posterior predictive check. The use of WinBUGS supported the same structural models tried in NONMEM. For the gentamicin dataset a one-compartment model with intravenous infusion was developed, and the population parameters including the full between-subject variance-covariance matrix were available. Analysis of the enoxaparin dataset supported a two compartment model as superior to the one-compartment model, based on the posterior predictive check. Again, the full between-subject variance-covariance matrix parameters were available. Fully Bayesian approaches using MCMC methods, via WinBUGS, can offer added value for analysis of population pharmacokinetic data.

Dissecting the complex genetic basis of mate choice

The genetic analysis of mate choice is fraught with difficulties. Males produce complex signals and displays that can consist of a combination of acoustic, visual, chemical and behavioural phenotypes. Furthermore, female preferences for these male traits are notoriously difficult to quantify. During mate choice, genes not only affect the phenotypes of the individual they are in, but can influence the expression of traits in other individuals. How can genetic analyses be conducted to encompass this complexity? Tighter integration of classical quantitative genetic approaches with modern genomic technologies promises to advance our understanding of the complex genetic basis of mate choice.

The cost of uniqueness in groundwater model calibration

Calibration of a groundwater model requires that hydraulic properties be estimated throughout a model domain. This generally constitutes an underdetermined inverse problem, for which a Solution can only be found when some kind of regularization device is included in the inversion process. Inclusion of regularization in the calibration process can be implicit, for example through the use of zones of constant parameter value, or explicit, for example through solution of a constrained minimization problem in which parameters are made to respect preferred values, or preferred relationships, to the degree necessary for a unique solution to be obtained. The cost of uniqueness is this: no matter which regularization methodology is employed, the inevitable consequence of its use is a loss of detail in the calibrated field. This, ill turn, can lead to erroneous predictions made by a model that is ostensibly well calibrated. Information made available as a by-product of the regularized inversion process allows the reasons for this loss of detail to be better understood. In particular, it is easily demonstrated that the estimated value for an hydraulic property at any point within a model domain is, in fact, a weighted average of the true hydraulic property over a much larger area. This averaging process causes loss of resolution in the estimated field. Where hydraulic conductivity is the hydraulic property being estimated, high averaging weights exist in areas that are strategically disposed with respect to measurement wells, while other areas may contribute very little to the estimated hydraulic conductivity at any point within the model domain, this possibly making the detection of hydraulic conductivity anomalies in these latter areas almost impossible. A study of the post-calibration parameter field covariance matrix allows further insights into the loss of system detail incurred through the calibration process to be gained. A comparison of pre- and post-calibration parameter covariance matrices shows that the latter often possess a much smaller spectral bandwidth than the former. It is also demonstrated that, as all inevitable consequence of the fact that a calibrated model cannot replicate every detail of the true system, model-to-measurement residuals can show a high degree of spatial correlation, a fact which must be taken into account when assessing these residuals either qualitatively, or quantitatively in the exploration of model predictive uncertainty. These principles are demonstrated using a synthetic case in which spatial parameter definition is based oil pilot points, and calibration is Implemented using both zones of piecewise constancy and constrained minimization regularization. (C) 2005 Elsevier Ltd. All rights reserved.

Novel variants in growth differentiation factor 9 in mothers of dizygotic twins

Context: Genes from the ovarian bone morphogenetic signaling pathway (GDF9 and BMP15) are critical for normal human fertility. We previously identified a deletion mutation in GDF9 in sisters with spontaneous dizygotic (DZ) twins, but the prevalence of rare GDF9 variants in twinning families is unknown. Objective: The objective was to evaluate the frequency of rare variants in GDF9 in families with a history of DZ twinning. Design and Subjects: We recruited 3450 individuals from 915 DZ twinning families (1693 mothers of twins) and 1512 controls of Caucasian origin. One mother of DZ twins was selected from 279 of the 915 families, and a DNA sample was screened for rare variants in GDF9 using denaturant HPLC. Variants were confirmed by DNA sequencing and genotyped in the entire sample by matrix-assisted laser desorption ionization time of flight (MALDI-TOF) mass spectrometry. Results: We found two novel insertion/deletions (c.392-393insT, c.1268-1269delAA) and four missense alterations in the GDF9 sequence in mothers of twins. Two of the missense variants (c.307C > T, p.Pro103Ser and c.362C > T, p.Thr121Leu) were located in the proregion of GDF9 and two (c.1121C > T, p.Pro374Leu and c.1360C > T, p.Arg454Cys) in the mature protein region. For each variant, the frequencies were higher in cases compared with controls. The proportion of mothers of DZ twins carrying any variant (4.12%) was significantly higher (P < 0.0001) than the proportion of carriers in controls (2.29%). Conclusion: We describe new variants in the GDF9 gene that are significantly more common in mothers of DZ twins than controls, suggesting that rare GDF9 variants contribute to the likelihood of DZ twinning.

Investigations into an optimal transmission scheme for a MIMO system operating in a ricain fading environment

This paper describes investigations into an optimal transmission scheme for a multiple input multiple output (MIMO) system operating in a Rician fading environment. The considerations are reduced to determining a covariance matrix of transmitted signals which maximizes the MIMO capacity under the condition that the receiver has perfect knowledge of the channel while the transmitter has the information about selected statistical quantities which are measured at the receiver. An optimal covariance matrix, which requires information of the Rice factor and the signal to noise ratio, is determined. The transmission scheme relying on the choice of the proposed covariance matrix outperforms the other transmission schemes which were reported earlier in the literature. The proposed scheme realizes an upper bound limit for the MIMO capacity under arbitrary Rician fading conditions. ©2005 IEEE

Non-rigid object tracking in complex scenes

A recently proposed colour based tracking algorithm has been established to track objects in real circumstances [Zivkovic, Z., Krose, B. 2004. An EM-like algorithm for color-histogram-based object tracking. In: Proc, IEEE Conf. on Computer Vision and Pattern Recognition, pp. 798-803]. To improve the performance of this technique in complex scenes, in this paper we propose a new algorithm for optimally adapting the ellipse outlining the objects of interest. This paper presents a Lagrangian based method to integrate a regularising component into the covariance matrix to be computed. Technically, we intend to reduce the residuals between the estimated probability distribution and the expected one. We argue that, by doing this, the shape of the ellipse can be properly adapted in the tracking stage. Experimental results show that the proposed method has favourable performance in shape adaption and object localisation.