Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Interpreting Judgements using Knowledge Representation Methods and Computational Models of Argument

The goal of the present research is to define a Semantic Web framework for precedent modelling, by using knowledge extracted from text, metadata, and rules, while maintaining a strong text-to-knowledge morphism between legal text and legal concepts, in order to fill the gap between legal document and its semantics. The framework is composed of four different models that make use of standard languages from the Semantic Web stack of technologies: a document metadata structure, modelling the main parts of a judgement, and creating a bridge between a text and its semantic annotations of legal concepts; a legal core ontology, modelling abstract legal concepts and institutions contained in a rule of law; a legal domain ontology, modelling the main legal concepts in a specific domain concerned by case-law; an argumentation system, modelling the structure of argumentation. The input to the framework includes metadata associated with judicial concepts, and an ontology library representing the structure of case-law. The research relies on the previous efforts of the community in the field of legal knowledge representation and rule interchange for applications in the legal domain, in order to apply the theory to a set of real legal documents, stressing the OWL axioms definitions as much as possible in order to enable them to provide a semantically powerful representation of the legal document and a solid ground for an argumentation system using a defeasible subset of predicate logics. It appears that some new features of OWL2 unlock useful reasoning features for legal knowledge, especially if combined with defeasible rules and argumentation schemes. The main task is thus to formalize legal concepts and argumentation patterns contained in a judgement, with the following requirement: to check, validate and reuse the discourse of a judge - and the argumentation he produces - as expressed by the judicial text.

Specific enzymatic cleavage and payload release from peptide-based hybrid nanocapsules

Within this thesis, new approaches for the concepts of peptide-polymer conjugates and peptide-based hybrid nanomaterials are investigated. In the first part, the synthesis of a triblock polymer-peptide-polymer is carried out following a typical peptide coupling reaction, both in solution and on solid-phase. The peptide sequence is chosen, so that it is cleaved by an enzyme preparation of trypsin. End-functionalized polystyrene is used as a model hydrophobic polymer and coupled to the peptide sequence. The results show successful coupling reactions in both methods, while the solid phase method produced a more defined product. Suspensions, consisting of peptide-polymer conjugates particles, are prepared in water by ultrasonication. In contact with the enzyme, the peptide constituting the conjugated particles is cleaved. This demonstrates the enzymatic cleavage in heterophase of enzymatic sequence bond to hydrophobic polymers, and is of great interest for the encapsulation and delivery of hydrophobic molecules.rnA second approach is the preparation of peptide-based hybrid nanocapsules. This is achieved by interfacial polyaddition in inverse miniemulsion with the peptide sequence functionalized with additional amino acids. A method suitable to the use of a peptide sequence for interfacial polyaddition was developed. It is shown that, the polarity of the dispersed phase influences the structures prepared, from particle-like to polymeric shell with a liquid core.rnThe peptide sequence is equipped with a FRET pair (more exactly, an internally-quenched fluorescent system) which allows the real-time monitoring of the enzymatic cleavage of the recognition site. This system shows the successful cleavage of the peptide-based nanocapsules when trypsin preparation is added to the suspensions. A water-soluble fluorescent polymer is efficiently entrapped and its possible use as marker for the capsules is highlighted. Furthermore, a small water-soluble fluorescent dye (SR-101) is successfully encapsulated and the encapsulation efficiency as a function of the functionality of the peptide and the amount of comonomer equivalent (toluene diisocyanate) is studied. The dye is encapsulated at such a high concentration, that self-quenching occurs. Thus, the release of the encapsulated dye triggered by the enzymatic cleavage of the peptide results in a fluorescence recovery of the dye. The fluorescence recovery of the FRET pair in the peptide and of the encapsulated dye correlate well.rnFinally, nanocapsules based on a hepsin-cleavable peptide sequence are prepared. Hepsin is an enzyme, which is highly upregulated in prostate cancer cells. The cleavage of the nanocapsules is investigated with healthy and “cancerous” (hepsin-expressing) cell cultures. The degradation, followed via fluorescence recovery of the FRET system, is faster for the suspensions introduced in the hepsin expressing cell cultures.rnIn summary, this work tackles the domain of responsive nanomaterials for drug delivery from a new perspective. It presents the adaptation of the miniemulsion process for hybrid peptide-based materials, and their successful use in preparing specific enzyme-responsive nanoparticles, with hydrophilic payload release properties.rn

Natural compounds Camptothecin and Triptolide: highly specific enzyme inhibitors and tools to dissect transcriptional functions

With this work I elucidated new and unexpected mechanisms of two strong and highly specific transcription inhibitors: Triptolide and Campthotecin. Triptolide (TPL) is a diterpene epoxide derived from the Chinese plant Trypterigium Wilfoordii Hook F. TPL inhibits the ATPase activity of XPB, a subunit of the general transcription factor TFIIH. In this thesis I found that degradation of Rbp1 (the largest subunit of RNA Polymerase II) caused by TPL treatments, is preceded by an hyperphosphorylation event at serine 5 of the carboxy-terminal domain (CTD) of Rbp1. This event is concomitant with a block of RNA Polymerase II at promoters of active genes. The enzyme responsible for Ser5 hyperphosphorylation event is CDK7. Notably, CDK7 downregulation rescued both Ser5 hyperphosphorylation and Rbp1 degradation triggered by TPL. Camptothecin (CPT), derived from the plant Camptotheca acuminata, specifically inhibits topoisomerase 1 (Top1). We first found that CPT induced antisense transcription at divergent CpG islands promoter. Interestingly, by immunofluorescence experiments, CPT was found to induce a burst of R loop structures (DNA/RNA hybrids) at nucleoli and mitochondria. We then decided to investigate the role of Top1 in R loop homeostasis through a short interfering RNA approach (RNAi). Using DNA/RNA immunoprecipitation techniques coupled to NGS I found that Top1 depletion induces an increase of R loops at a genome-wide level. We found that such increase occurs on the entire gene body. At a subset of loci R loops resulted particularly stressed after Top1 depletion: some of these genes showed the formation of new R loops structures, whereas other loci showed a reduction of R loops. Interestingly we found that new peaks usually appear at tandem or divergent genes in the entire gene body, while losses of R loop peaks seems to be a feature specific of 3’ end regions of convergent genes.

Learning Methods and Algorithms for Semantic Text Classification across Multiple Domains

Information is nowadays a key resource: machine learning and data mining techniques have been developed to extract high-level information from great amounts of data. As most data comes in form of unstructured text in natural languages, research on text mining is currently very active and dealing with practical problems. Among these, text categorization deals with the automatic organization of large quantities of documents in priorly defined taxonomies of topic categories, possibly arranged in large hierarchies. In commonly proposed machine learning approaches, classifiers are automatically trained from pre-labeled documents: they can perform very accurate classification, but often require a consistent training set and notable computational effort. Methods for cross-domain text categorization have been proposed, allowing to leverage a set of labeled documents of one domain to classify those of another one. Most methods use advanced statistical techniques, usually involving tuning of parameters. A first contribution presented here is a method based on nearest centroid classification, where profiles of categories are generated from the known domain and then iteratively adapted to the unknown one. Despite being conceptually simple and having easily tuned parameters, this method achieves state-of-the-art accuracy in most benchmark datasets with fast running times. A second, deeper contribution involves the design of a domain-independent model to distinguish the degree and type of relatedness between arbitrary documents and topics, inferred from the different types of semantic relationships between respective representative words, identified by specific search algorithms. The application of this model is tested on both flat and hierarchical text categorization, where it potentially allows the efficient addition of new categories during classification. Results show that classification accuracy still requires improvements, but models generated from one domain are shown to be effectively able to be reused in a different one.

Multicentre study for a robust protocol in single-voxel spectroscopy: quantification of MRS signals by time-domain fitting algorithms

Magnetic Resonance Spectroscopy (MRS) is an advanced clinical and research application which guarantees a specific biochemical and metabolic characterization of tissues by the detection and quantification of key metabolites for diagnosis and disease staging. The "Associazione Italiana di Fisica Medica (AIFM)" has promoted the activity of the "Interconfronto di spettroscopia in RM" working group. The purpose of the study is to compare and analyze results obtained by perfoming MRS on scanners of different manufacturing in order to compile a robust protocol for spectroscopic examinations in clinical routines. This thesis takes part into this project by using the GE Signa HDxt 1.5 T at the Pavillion no. 11 of the S.Orsola-Malpighi hospital in Bologna. The spectral analyses have been performed with the jMRUI package, which includes a wide range of preprocessing and quantification algorithms for signal analysis in the time domain. After the quality assurance on the scanner with standard and innovative methods, both spectra with and without suppression of the water peak have been acquired on the GE test phantom. The comparison of the ratios of the metabolite amplitudes over Creatine computed by the workstation software, which works on the frequencies, and jMRUI shows good agreement, suggesting that quantifications in both domains may lead to consistent results. The characterization of an in-house phantom provided by the working group has achieved its goal of assessing the solution content and the metabolite concentrations with good accuracy. The goodness of the experimental procedure and data analysis has been demonstrated by the correct estimation of the T2 of water, the observed biexponential relaxation curve of Creatine and the correct TE value at which the modulation by J coupling causes the Lactate doublet to be inverted in the spectrum. The work of this thesis has demonstrated that it is possible to perform measurements and establish protocols for data analysis, based on the physical principles of NMR, which are able to provide robust values for the spectral parameters of clinical use.

Functional characterization of the placenta specific protein PLAC1 and its use for cancer immunotherapy

Summary Antibody-based cancer therapies have been successfully introduced into the clinic and have emerged as the most promising therapeutics in oncology. The limiting factor regarding the development of therapeutical antibody vaccines is the identification of tumor-associated antigens. PLAC1, the placenta-specific protein 1, was categorized for the first time by the group of Prof. Sahin as such a tumor-specific antigen. Within this work PLAC1 was characterized using a variety of biochemical methods. The protein expression profile, the cellular localization, the conformational state and especially the interacting partners of PLAC1 and its functionality in cancer were analyzed. Analysis of the protein expression profile of PLAC1 in normal human tissue confirms the published RT-PCR data. Except for placenta no PLAC1 expression was detectable in any other normal human tissue. Beyond, an increased PLAC1 expression was detected in several cancer cell lines derived of trophoblastic, breast and pancreatic lineage emphasizing its properties as tumor-specific antigen. rnThe cellular localization of PLAC1 revealed that PLAC1 contains a functional signal peptide which conducts the propeptide to the endoplasmic reticulum (ER) and results in the secretion of PLAC1 by the secretory pathway. Although PLAC1 did not exhibit a distinct transmembrane domain, no unbound protein was detectable in the cell culture supernatant of overexpressing cells. But by selective isolation of different cellular compartments PLAC1 was clearly enriched within the membrane fraction. Using size exclusion chromatography PLAC1 was characterized as a highly aggregating protein that forms a network of high molecular multimers, consisting of a mixture of non-covalent as well as covalent interactions. Those interactions were formed by PLAC1 with itself and probably other cellular components and proteins. Consequently, PLAC1 localize outside the cell, where it is associated to the membrane forming a stable extracellular coat-like structure.rnThe first mechanistic hint how PLAC1 promote cancer cell proliferation was achieved identifying the fibroblast growth factor FGF7 as a specific interacting partner of PLAC1. Moreover, it was clearly shown that PLAC1 as well as FGF7 bind to heparin, a glycosaminoglycan of the ECM that is also involved in FGF-signaling. The participation of PLAC1 within this pathway was approved after co-localizing PLAC1, FGF7 and the FGF7 specific receptor (FGFR2IIIb) and identifying the formation of a trimeric complex (PLAC1, FGF7 and the specific receptor FGFR2IIIb). Especially this trimeric complex revealed the role of PLAC1. Binding of PLAC1 together with FGF7 leads to the activation of the intracellular tyrosine kinase of the FGFR2IIIb-receptor and mediate the direct phosphorylation of the AKT-kinase. In the absence of PLAC1, no FGF7 mediated phosphorylation of AKT was observed. Consequently the function of PLAC1 was clarified: PLAC1 acts as a co-factor by stimulating proliferation by of the FGF7-FGFR2 signaling pathway.rnAll together, these novel biochemical findings underline that the placenta specific protein PLAC1 could be a new target for cancer immunotherapy, especially considering its potential applicability for antibody therapy in tumor patients.

La comunicazione aziendale tra redazione e traduzione: Il caso di ipack srl.

This dissertation is the result of my participation in the Language Toolkit project, a recent collaboration between the Chamber of Commerce of Forlì and the School of Foreign Languages and Literatures, Interpreting and Translation at the University of Bologna, which aims to make students meet with the companies of our territory, in this case Ipack, based in Mercato Saraceno (FC). My dissertation is a specialized translation work from Italian into English of two documents that were entrusted to me: the declaration of compliance of Ipack’s products and a summary of the quality manual. They are two high technical texts and, therefore, the translation task required a preliminary phase of research on the topics and on the terminology of this specific domain. The dissertation consists of five chapters. The first chapter briefly introduces the company with which I collaborated for my dissertation project and provides an overview of business communication and a brief classification of Ipack’s communication tools. The second chapter covers the background topics, namely food packaging and quality management systems within companies. The third chapter concerns the analysis of the two texts, describing the intra-textual and extra-textual aspects, as well as the morphosyntaxical and lexical features. The fourth chapter is dedicated to the revision work on one of the two texts, the one about quality procedures. In the commentary following my review, I explain the methodology and the strategies that I used and I also provide some extended examples of the main changes applied to the original text, with respect to both content and linguistic features. Finally, the fifth chapter focuses on the translation of the texts followed by a commentary that explains the work methodology, resources and my translation choices, accompanied by practical examples.

Specific processing of tenascin-C by the metalloprotease meprinbeta neutralizes its inhibition of cell spreading

The metalloprotease meprin has been implicated in tissue remodelling due to its capability to degrade extracellular matrix components. Here, we investigated the susceptibility of tenascin-C to cleavage by meprinbeta and the functional properties of its proteolytic fragments. A set of monoclonal antibodies against chicken and human tenascin-C allowed the mapping of proteolytic fragments generated by meprinbeta. In chicken tenascin-C, meprinbeta processed all three major splicing variants by removal of 10kDa N-terminal and 38kDa C-terminal peptides, leaving a large central part of subunits intact. A similar cleavage pattern was found for large human tenascin-C variant where two N-terminal peptides (10 or 15kDa) and two C-terminal fragments (40 and 55kDa) were removed from the intact subunit. N-terminal sequencing revealed the exact amino acid positions of cleavage sites. In both chicken and human tenascin-C N-terminal cleavages occurred just before and/or after the heptad repeats involved in subunit oligomerization. In the human protein, an additional cleavage site was identified in the alternative fibronectin type III repeat D. Whereas all these sites are known to be attacked by several other proteases, a unique cleavage by meprinbeta was located to the 7th constant fibronectin type III repeat in both chicken and human tenascin-C, thereby removing the C-terminal domain involved in its anti-adhesive activity. In cell adhesion assays meprinbeta-digested human tenascin-C was not able to interfere with fibronectin-mediated cell spreading, confirming cleavage in the anti-adhesive domain. Whereas the expression of meprinbeta and tenascin-C does not overlap in normal colon tissue, inflamed lesions of the mucosa from patients with Crohn's disease exhibited many meprinbeta-positive leukocytes in regions where tenascin-C was strongly induced. Our data indicate that, at least under pathological conditions, meprinbeta might attack specific functional sites in tenascin-C that are important for its oligomerization and anti-adhesive activity.

The lectin-like domain of tumor necrosis factor improves lung function after rat lung transplantation--potential role for a reduction in reactive oxygen species generation

To test the hypothesis that the lectin-like domain of tumor necrosis factor, mimicked by the TIP peptide, can improve lung function after unilateral orthotopic lung isotransplantation. Because of a lack of a specific treatment for ischemia reperfusion-mediated lung injury, accompanied by a disrupted barrier integrity and a dysfunctional alveolar liquid clearance, alternative therapies restoring these parameters after lung transplantation are required.

Knowing the future: partial foreknowledge effects on the programming of prosaccades and antisaccades

Foreknowledge about the demands of an upcoming trial may be exploited to optimize behavioural responses. In the current study we systematically investigated the benefits of partial foreknowledge--that is, when some but not all aspects of a future trial are known in advance. For this we used an ocular motor paradigm with horizontal prosaccades and antisaccades. Predictable sequences were used to create three partial foreknowledge conditions: one with foreknowledge about the stimulus location only, one with foreknowledge about the task set only, and one with foreknowledge about the direction of the required response only. These were contrasted with a condition of no-foreknowledge and a condition of complete foreknowledge about all three parameters. The results showed that the three types of foreknowledge affected saccadic efficiency differently. While foreknowledge about stimulus-location had no effect on efficiency, task foreknowledge had some effect and response-foreknowledge was as effective as complete foreknowledge. Foreknowledge effects on switch costs followed a similar pattern in general, but were not specific for switching of the trial attribute for which foreknowledge was available. We conclude that partial foreknowledge has a differential effect on efficiency, most consistent with preparatory activation of a motor schema in advance of the stimulus, with consequent benefits for both switched and repeated trials.

The beta-isoform of neuronal nitric oxide synthase (nNOS) lacking the PDZ domain is localized at the sarcolemma

In skeletal muscles, the expression of neuronal NO synthase (nNOS) isoforms is uncharacterized at the protein level. We therefore conducted epitope mapping with anti-peptide-antibodies. Antibodies specific for the nNOS N-terminus recognized the 160-kDa alpha-isoform. In contrast, antibodies against the middle portion or the C-terminus of nNOS bound additionally to the truncated 140-kDa beta-isoform which lacks the PDZ-domain present in the alpha-isoform. All nNOS immunohistochemical reactivity was confined to the sarcolemma. Consistently, immunoblotting disclosed both nNOS-isoforms to be co-enriched in the membrane-associated fractions. The beta-isoform was co-immunoprecipitated with alpha-isoform antibodies in muscle extracts indicating an association of both nNOS-isoforms to direct the beta-variant to the sarcolemma.

Patient with syncope and LQTS carrying a mutation in the PAS domain of the hERG1 channel

We report the case of a woman with syncope and persistently prolonged QTc interval. Screening of congenital long QT syndrome (LQTS) genes revealed that she was a heterozygous carrier of a novel KCNH2 mutation, c.G238C. Electrophysiological and biochemical characterizations unveiled the pathogenicity of this new mutation, displaying a 2-fold reduction in protein expression and current density due to a maturation/trafficking-deficient mechanism. The patient's phenotype can be fully explained by this observation. This study illustrates the importance of performing genetic analyses and mutation characterization when there is a suspicion of congenital LQTS. Identifying mutations in the PAS domain or other domains of the hERG1 channel and understanding their effect may provide more focused and mutation-specific risk assessment in this population.

Alba-domain proteins of Trypanosoma brucei are cytoplasmic RNA-binding proteins that interact with the translation machinery

Trypanosoma brucei and related pathogens transcribe most genes as polycistronic arrays that are subsequently processed into monocistronic mRNAs. Expression is frequently regulated post-transcriptionally by cis-acting elements in the untranslated regions (UTRs). GPEET and EP procyclins are the major surface proteins of procyclic (insect midgut) forms of T. brucei. Three regulatory elements common to the 3' UTRs of both mRNAs regulate mRNA turnover and translation. The glycerol-responsive element (GRE) is unique to the GPEET 3' UTR and regulates its expression independently from EP. A synthetic RNA encompassing the GRE showed robust sequence-specific interactions with cytoplasmic proteins in electromobility shift assays. This, combined with column chromatography, led to the identification of 3 Alba-domain proteins. RNAi against Alba3 caused a growth phenotype and reduced the levels of Alba1 and Alba2 proteins, indicative of interactions between family members. Tandem-affinity purification and co-immunoprecipitation verified these interactions and also identified Alba4 in sub-stoichiometric amounts. Alba proteins are cytoplasmic and are recruited to starvation granules together with poly(A) RNA. Concomitant depletion of all four Alba proteins by RNAi specifically reduced translation of a reporter transcript flanked by the GPEET 3' UTR. Pulldown of tagged Alba proteins confirmed interactions with poly(A) binding proteins, ribosomal protein P0 and, in the case of Alba3, the cap-binding protein eIF4E4. In addition, Alba2 and Alba3 partially cosediment with polyribosomes in sucrose gradients. Alba-domain proteins seem to have exhibited great functional plasticity in the course of evolution. First identified as DNA-binding proteins in Archaea, then in association with nuclear RNase MRP/P in yeast and mammalian cells, they were recently described as components of a translationally silent complex containing stage-regulated mRNAs in Plasmodium. Our results are also consistent with stage-specific regulation of translation in trypanosomes, but most likely in the context of initiation.