Instance generators and test suites for the multiobjective quadratic assignment problem

We describe, and make publicly available, two problem instance generators for a multiobjective version of the well-known quadratic assignment problem (QAP). The generators allow a number of instance parameters to be set, including those controlling epistasis and inter-objective correlations. Based on these generators, several initial test suites are provided and described. For each test instance we measure some global properties and, for the smallest ones, make some initial observations of the Pareto optimal sets/fronts. Our purpose in providing these tools is to facilitate the ongoing study of problem structure in multiobjective (combinatorial) optimization, and its effects on search landscape and algorithm performance.

All-or-none (or something in between) transition of DNA

DNA compaction can be caused by multivalent ions as condensing agents. Both discontinuous (all-or-none) and continuous (pearl-necklace structure) transitions have been observed in experiments as the concentration of the condensing agent was increased. We have investigated the DNA transition by analytical calculations in the infinite-chain limit. A mechanism for pearl-necklace structures could be a combinatorial entropy term, which favours a mixture of globules and coils in a single chain. However, when a surface term is taken into account, it gives rise to a discontinuous transition. We also consider the role of surface charges on the globule.

On the radius of centrality in evolving communication networks

In this article, we investigate how the choice of the attenuation factor in an extended version of Katz centrality influences the centrality of the nodes in evolving communication networks. For given snapshots of a network, observed over a period of time, recently developed communicability indices aim to identify the best broadcasters and listeners (receivers) in the network. Here we explore the attenuation factor constraint, in relation to the spectral radius (the largest eigenvalue) of the network at any point in time and its computation in the case of large networks. We compare three different communicability measures: standard, exponential, and relaxed (where the spectral radius bound on the attenuation factor is relaxed and the adjacency matrix is normalised, in order to maintain the convergence of the measure). Furthermore, using a vitality-based measure of both standard and relaxed communicability indices, we look at the ways of establishing the most important individuals for broadcasting and receiving of messages related to community bridging roles. We compare those measures with the scores produced by an iterative version of the PageRank algorithm and illustrate our findings with two examples of real-life evolving networks: the MIT reality mining data set, consisting of daily communications between 106 individuals over the period of one year, a UK Twitter mentions network, constructed from the direct \emph{tweets} between 12.4k individuals during one week, and a subset the Enron email data set.

A bifurcated pathway to thiazoles and imidazoles using a modular flow microreactor

A scalable method for the preparation of 4,5-disubstituted thiazoles and imidazoles as distinct regioisomeric products using a modular flow microreactor has been devised. The process makes use of microfluidic reaction chips and packed immobilized-reagent columns to effect bifurcation of the reaction pathway.

Regulation of actin assembly by SCAR/WAVE proteins.

Actin reorganization is a tightly regulated process that co-ordinates complex cellular events, such as cell migration, chemotaxis, phagocytosis and adhesion, but the molecular mechanisms that underlie these processes are not well understood. SCAR (suppressor of cAMP receptor)/WAVE [WASP (Wiskott-Aldrich syndrome protein)-family verprolin homology protein] proteins are members of the conserved WASP family of cytoskeletal regulators, which play a critical role in actin dynamics by triggering Arp2/3 (actin-related protein 2/3)-dependent actin nucleation. SCAR/WAVEs are thought to be regulated by a pentameric complex which also contains Abi (Abl-interactor), Nap (Nck-associated protein), PIR121 (p53-inducible mRNA 121) and HSPC300 (haematopoietic stem progenitor cell 300), but the structural organization of the complex and the contribution of its individual components to the regulation of SCAR/WAVE function remain unclear. Additional features of SCAR/WAVE regulation are highlighted by the discovery of other interactors and distinct complexes. It is likely that the combinatorial assembly of different components of SCAR/WAVE complexes will prove to be vital for their roles at the centre of dynamic actin reorganization.

Dynamical properties of S-gap shifts and other shift spaces

We study the dynamical properties of certain shift spaces. To help study these properties we introduce two new classes of shifts, namely boundedly supermultiplicative (BSM) shifts and balanced shifts. It turns out that any almost specified shift is both BSM and balanced, and any balanced shift is BSM. However, as we will demonstrate, there are examples of shifts which are BSM but not balanced. We also study the measure theoretic properties of balanced shifts. We show that a shift space admits a Gibbs state if and only if it is balanced. Restricting ourselves to S-gap shifts, we relate certain dynamical properties of an S-gap shift to combinatorial properties from expansions in non-integer bases. This identification allows us to use the machinery from expansions in non-integer bases to give straightforward constructions of S -gap shifts with certain desirable properties. We show that for any q∈(0,1) there is an S-gap shift which has the specification property and entropy q . We also use this identification to address the question, for a given q∈(0,1), how many S-gap shifts exist with entropy q? For certain exceptional values of q there is a unique S-gap shift with this entropy.

Isoform specificity for oestrogen receptor and thyroid hormone receptor genes and their interactions on the NR2D gene promoter

Oestrogens are critical for the display of lordosis behaviour and, in recent years, have also been shown to be involved in synaptic plasticity. In the brain, the regulation of ionotropic glutamate receptors has consequences for excitatory neurotransmission. Oestrogen regulation of the N-methyl-d-aspartate receptor subunit 2D (NR2D) has generated considerable interest as a possible molecular mechanism by which synaptic plasticity can be modulated. Since more than one isoform of the oestrogen receptor (ER) exists in mammals, it is possible that oestrogen regulation via the ERalpha and ERbeta isoforms on the NR2D oestrogen response element (ERE) is not equivalent. In the kidney fibroblast (CV1) cell line, we show that in response to 17beta-oestradiol, only ERalpha, not ERbeta, could upregulate transcription from the ERE which is in the 3' untranslated region of the NR2D gene. When this ERE is in the 5' position, neither ERalpha nor ERbeta showed transactivation capacity. Thyroid hormone receptor (TR) modulation of ER mediated induction has been shown for other ER target genes, such as the preproenkephalin and oxytocin receptor genes. Since the various TR isoforms exhibit distinct roles, we hypothesized that TR modulation of ER induction may also be isoform specific. This is indeed the case. The TRalpha1 isoform stimulated ERalpha mediated induction from the 3'-ERE whereas the TRbeta1 isoform inhibited this induction. This study shows that isoforms of both the ER and TR have different transactivation properties. Such flexible regulation and crosstalk by nuclear receptor isoforms leads to different transcriptional outcomes and the combinatorial logic may aid neuroendocrine integration.

Characterization of proteinases from the midgut of Rhipicephalus (Boophilus) microplus involved in the generation of antimicrobial peptides

Background: Hemoglobin is a rich source of biologically active peptides, some of which are potent antimicrobials (hemocidins). A few hemocidins have been purified from the midgut contents of ticks. Nonetheless, how antimicrobials are generated in the tick midgut and their role in immunity is still poorly understood. Here we report, for the first time, the contribution of two midgut proteinases to the generation of hemocidins. Results: An aspartic proteinase, designated BmAP, was isolated from the midgut of Rhipicephalus (Boophilus) microplus using three chromatographic steps. Reverse transcription-quantitative polymerase chain reaction revealed that BmAP is restricted to the midgut. The other enzyme is a previously characterized midgut cathepsin L-like cysteine proteinase designated BmCL1. Substrate specificities of native BmAP and recombinant BmCL1 were mapped using a synthetic combinatorial peptide library and bovine hemoglobin. BmCL1 preferred substrates containing non-polar residues at P2 subsite and polar residues at P1, whereas BmAP hydrolysed substrates containing non-polar amino acids at P1 and P1`. Conclusions: BmAP and BmCL1 generate hemocidins from hemoglobin alpha and beta chains in vitro. We postulate that hemocidins may be important for the control of tick pathogens and midgut flora.

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

Density profiles in the raise and peel model with and without a wall; physics and combinatorics

We consider the raise and peel model of a one-dimensional fluctuating interface in the presence of an attractive wall. The model can also describe a pair annihilation process in disordered unquenched media with a source at one end of the system. For the stationary states, several density profiles are studied using Monte Carlo simulations. We point out a deep connection between some profiles seen in the presence of the wall and in its absence. Our results are discussed in the context of conformal invariance ( c = 0 theory). We discover some unexpected values for the critical exponents, which are obtained using combinatorial methods. We have solved known ( Pascal`s hexagon) and new (split-hexagon) bilinear recurrence relations. The solutions of these equations are interesting in their own right since they give information on certain classes of alternating sign matrices.

Fragment-Based QSAR and Molecular Modeling Studies on a Series of Discodermolide Analogs as Microtubule-Stabilizing Anticancer Agents

Inhibition of microtubule function is an attractive rational approach to anticancer therapy. Although taxanes are the most prominent among the microtubule-stabilizers, their clinical toxicity, poor pharmacokinetic properties, and resistance have stimulated the search for new antitumor agents having the same mechanism of action. Discodermolide is an example of nontaxane natural product that has the same mechanism of action, demonstrating superior antitumor efficacy and therapeutic index. The extraordinary chemical and biological properties have qualified discodermolide as a lead structure for the design of novel anticancer agents with optimized therapeutic properties. In the present work, we have employed a specialized fragment-based method to develop robust quantitative structure - activity relationship models for a series of synthetic discodermolide analogs. The generated molecular recognition patterns were combined with three-dimensional molecular modeling studies as a fundamental step on the path to understanding the molecular basis of drug-receptor interactions within this important series of potent antitumoral agents.

Classical and hologram QSAR studies on a series of inhibitors of trypanosomatid Glyceraldehyde-3-Phosphate Dehydrogenase

Leishmaniasis and trypanosomiasis are major causes of morbidity and mortality in both tropical and subtropical regions of the world. The current available drugs are limited, ineffective, and require long treatment regimens. Due to the high dependence of trypanosomatids on glycolysis as a source of energy, some glycolytic enzymes have been identified as attractive targets for drug design. In the present work, classical Two-Dimensional Quantitative Structure -Activity Relationships (2D QSAR) and Hologram QSAR (HQSAR) studies were performed on a series of adenosine derivatives as inhibitors of Leishmania mexicana Glyceraldehyde-3-Phosphate Dehydrogenase (LmGAPDH). Significant correlation coefficients (classical QSAR, r(2)=0.83 and q(2) =0.81; HQSAR, r(2)=0.91 and q(2) =0.86) were obtained for the 56 training set compounds, indicating the potential of the models for untested compounds. The models were then externally validated using a test set of 14 structurally related compounds and the predicted values were in good agreement with the experimental results (classical QSAR, r(pred)(2) = 0.94; HQSAR, r(pred)(2) = 0.92).

A novel MAP-MRF approach for multispectral image contextual classification using combination of suboptimal iterative algorithms

In this paper we present a novel approach for multispectral image contextual classification by combining iterative combinatorial optimization algorithms. The pixel-wise decision rule is defined using a Bayesian approach to combine two MRF models: a Gaussian Markov Random Field (GMRF) for the observations (likelihood) and a Potts model for the a priori knowledge, to regularize the solution in the presence of noisy data. Hence, the classification problem is stated according to a Maximum a Posteriori (MAP) framework. In order to approximate the MAP solution we apply several combinatorial optimization methods using multiple simultaneous initializations, making the solution less sensitive to the initial conditions and reducing both computational cost and time in comparison to Simulated Annealing, often unfeasible in many real image processing applications. Markov Random Field model parameters are estimated by Maximum Pseudo-Likelihood (MPL) approach, avoiding manual adjustments in the choice of the regularization parameters. Asymptotic evaluations assess the accuracy of the proposed parameter estimation procedure. To test and evaluate the proposed classification method, we adopt metrics for quantitative performance assessment (Cohen`s Kappa coefficient), allowing a robust and accurate statistical analysis. The obtained results clearly show that combining sub-optimal contextual algorithms significantly improves the classification performance, indicating the effectiveness of the proposed methodology. (C) 2010 Elsevier B.V. All rights reserved.

Testing permutation properties through subpermutations

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well approximated based on a randomly chosen subpermutation of much smaller size. In this context, we use a theory of convergence of permutation sequences developed by the present authors [C. Hoppen, Y. Kohayakawa, C.G. Moreira, R.M. Sampaio, Limits of permutation sequences through permutation regularity, Manuscript, 2010, 34pp.] to characterize testable permutation parameters along the lines of the work of Borgs et al. [C. Borgs, J. Chayes, L Lovasz, V.T. Sos, B. Szegedy, K. Vesztergombi, Graph limits and parameter testing, in: STOC`06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 261-270.] in the case of graphs. Moreover, we obtain a permutation result in the direction of a famous result of Alon and Shapira [N. Alon, A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, SIAM J. Comput. 37 (6) (2008) 1703-1727.] stating that every hereditary graph property is testable. (C) 2011 Elsevier B.V. All rights reserved.