GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

Combinatorial chromophore assembly inside a DNA four-way junction

In 1964 first proposed by Robin Holliday as a mechanistic model to solve the mystery of how genetic information is exchanged in yeast, the DNA four-way junction or Holliday junction (HJ) was proofed to be the key in- termediate in homologous recombination and became an important tool in the field of DNA origami, computation and nanomachines. Herein we use the assembly of four modified nucleic acid strands into the planar square conformation of this higher order DNA structure to demonstrate in a proof of principle manner the cumulative effect of pyrene moieties interacting inside the junction.[1][2]

An application of combinatorial optimization in the printing industry

Offset printing is a common method to produce large amounts of printed matter. We consider a real-world offset printing process that is used to imprint customer-specific designs on napkin pouches. The print- ing technology used yields a number of specific constraints. The planning problem consists of allocating designs to printing-plate slots such that the given customer demand for each design is fulfilled, all technologi- cal and organizational constraints are met and the total overproduction and setup costs are minimized. We formulate this planning problem as a mixed-binary linear program, and we develop a multi-pass matching-based savings heuristic. We report computational results for a set of problem instances devised from real-world data.

Conformational diversity versus nucleic acid triplex stability, a combinatorial study

The stability of a triple helix formed between a DNA duplex and an incoming oligonucleotide strand strongly depends on the solvent conditions and on intrinsic chemical and conformational factors. Attempts to increase triple helix stability in the past included chemical modification of the backbone, sugar ring, and bases in the third strand. However, the predictive power of such modifications is still rather poor. We therefore developed a method that allows for rapid screening of conformationally diverse third strand oligonucleotides for triplex stability in the parallel pairing motif to a given DNA double helix sequence. Combinatorial libraries of oligonucleotides of the requisite (fixed) base composition and length that vary in their sugar unit (ribose or deoxyribose) at each position were generated. After affinity chromatography against their corresponding immobilized DNA target duplex, utilizing a temperature gradient as the selection criterion, the oligonucleotides forming the most stable triple helices were selected and characterized by physicochemical methods. Thus, a series of oligonucleotides were identified that allowed us to define basic rules for triple helix stability in this conformationally diverse system. It was found that ribocytidines in the third strand increase triplex stability relative to deoxyribocytidines independently of the neighboring bases and position along the strand. However, remarkable sequence-dependent differences in stability were found for (deoxy)thymidines and uridines

Combinatorial interaction between AtbZIP44 and other bZIP transcription factors in the regulation of Arabidopsis thaliana seed maturation and germination

El gen AtbZIP44 se expresa en el endospermo micropilar y en la radícula de semillas en germinación. El mRNA del gen AtbZIP9 se localiza también en la radícula. Se realizan experimentos de interacción proteína-proteína entre los correspondientes factores transcripcionales.

Recognition principle of the TAP transporter disclosed by combinatorial peptide libraries

Transport of peptides across the membrane of the endoplasmic reticulum for assembly with MHC class I molecules is an essential step in antigen presentation to cytotoxic T cells. This task is performed by the major histocompatibility complex-encoded transporter associated with antigen processing (TAP). Using a combinatorial approach we have analyzed the substrate specificity of human TAP at high resolution and in the absence of any given sequence context, revealing the contribution of each peptide residue in stabilizing binding to TAP. Human TAP was found to be highly selective with peptide affinities covering at least three orders of magnitude. Interestingly, the selectivity is not equally distributed over the substrate. Only the N-terminal three positions and the C-terminal residue are critical, whereas effects from other peptide positions are negligible. A major influence from the peptide backbone was uncovered by peptide scans and libraries containing d amino acids. Again, independent of peptide length, critical positions were clustered near the peptide termini. These approaches demonstrate that human TAP is selective, with residues determining the affinity located in distinct regions, and point to the role of the peptide backbone in binding to TAP. This binding mode of TAP has implications in an optimized repertoire selection and in a coevolution with the major histocompatibility complex/T cell receptor complex.

An artificial cell-cycle inhibitor isolated from a combinatorial library

Understanding the genetic networks that operate inside cells will require the dissection of interactions among network members. Here we describe a peptide aptamer isolated from a combinatorial library that distinguishes among such interactions. This aptamer binds to cyclin-dependent kinase 2 (Cdk2) and inhibits its kinase activity. In contrast to naturally occurring inhibitors, such as p21Cip1, which inhibit the activity of Cdk2 on all its substrates, inhibition by pep8 has distinct substrate specificity. We show that the aptamer binds to Cdk2 at or near its active site and that its mode of inhibition is competitive. Expression of pep8 in human cells retards their progression through the G1 phase of the cell cycle. Our results suggest that the aptamer inhibits cell-cycle progression by blocking the activity of Cdk2 on substrates needed for the G1-to-S transition. This work demonstrates the feasibility of selection of artificial proteins to perform functions not developed during evolution. The ability to select proteins that block interactions between a gene product and some partners but not others should make sophisticated genetic manipulations possible in human cells and other currently intractable systems.

Allosteric inhibitors of inducible nitric oxide synthase dimerization discovered via combinatorial chemistry

Potent and selective inhibitors of inducible nitric oxide synthase (iNOS) (EC 1.14.13.39) were identified in an encoded combinatorial chemical library that blocked human iNOS dimerization, and thereby NO production. In a cell-based iNOS assay (A-172 astrocytoma cells) the inhibitors had low-nanomolar IC50 values and thus were >1,000-fold more potent than the substrate-based direct iNOS inhibitors 1400W and N-methyl-l-arginine. Biochemical studies confirmed that inhibitors caused accumulation of iNOS monomers in mouse macrophage RAW 264.7 cells. High affinity (Kd ≈ 3 nM) of inhibitors for isolated iNOS monomers was confirmed by using a radioligand binding assay. Inhibitors were >1,000-fold selective for iNOS versus endothelial NOS dimerization in a cell-based assay. The crystal structure of inhibitor bound to the monomeric iNOS oxygenase domain revealed inhibitor–heme coordination and substantial perturbation of the substrate binding site and the dimerization interface, indicating that this small molecule acts by allosterically disrupting protein–protein interactions at the dimer interface. These results provide a mechanism-based approach to highly selective iNOS inhibition. Inhibitors were active in vivo, with ED50 values of <2 mg/kg in a rat model of endotoxin-induced systemic iNOS induction. Thus, this class of dimerization inhibitors has broad therapeutic potential in iNOS-mediated pathologies.

Making artificial antibodies: A format for phage display of combinatorial heterodimeric arrays

The gene VII protein (pVII) and gene IX protein (pIX) are associated closely on the surface of filamentous bacteriophage that is opposite of the end harboring the widely exploited pIII protein. We developed a phagemid format wherein antibody heavy- and light-chain variable regions were fused to the amino termini of pVII and pIX, respectively. Significantly, the fusion proteins interacted to form a functional Fv-binding domain on the phage surface. Our approach will be applicable to the display of generic peptide and protein libraries that can form combinatorial heterodimeric arrays. Consequently, it represents a first step toward artificial antibodies and the selection of novel biological activities.

Combinatorial roles for pRB, p107, and p130 in E2F-mediated cell cycle control

Numerous studies have implicated the pRB family of nuclear proteins in the control of cell cycle progression. Although over-expression experiments have revealed that each of these proteins, pRB, p107, and p130, can induce a G1 cell cycle arrest, mouse knockouts demonstrated distinct developmental requirements for these proteins, as well as partial functional redundancy between family members. To study the mechanism by which the closely related pRB family proteins contribute to cell cycle progression, we generated 3T3 fibroblasts derived from embryos that lack one or more of these proteins (pRB−/−, p107−/−, p130−/−, pRB−/−/p107−/−, pRB−/−/p130−/−, and p107−/−/p130−/−). By comparing the growth and cell cycle characteristics of these cells, we have observed clear differences in the manner in which they transit through the G1 and S phases as well as exit from the cell cycle. Deletion of Rb, or more than one of the family members, results in a shortening of G1 and a lengthening of S phase, as well as a reduction in growth factor requirements. In addition, the individual cell lines showed differential regulation of a subset of E2F-dependent gene promoters, as well as differences in cell cycle-dependent kinase activity. Taken together, these observations suggest that the closely related pRB family proteins affect cell cycle progression through distinct biochemical mechanisms and that their coordinated action may contribute to their diverse functions in various physiological settings.