A clustering approach for vehicle routing problems with hard time windows

Dissertação para obtenção do Grau de Mestre em Logica Computicional

Constraint reasoning with local search for continuous optimization

Optimization is a very important field for getting the best possible value for the optimization function. Continuous optimization is optimization over real intervals. There are many global and local search techniques. Global search techniques try to get the global optima of the optimization problem. However, local search techniques are used more since they try to find a local minimal solution within an area of the search space. In Continuous Constraint Satisfaction Problems (CCSP)s, constraints are viewed as relations between variables, and the computations are supported by interval analysis. The continuous constraint programming framework provides branch-and-prune algorithms for covering sets of solutions for the constraints with sets of interval boxes which are the Cartesian product of intervals. These algorithms begin with an initial crude cover of the feasible space (the Cartesian product of the initial variable domains) which is recursively refined by interleaving pruning and branching steps until a stopping criterion is satisfied. In this work, we try to find a convenient way to use the advantages in CCSP branchand- prune with local search of global optimization applied locally over each pruned branch of the CCSP. We apply local search techniques of continuous optimization over the pruned boxes outputted by the CCSP techniques. We mainly use steepest descent technique with different characteristics such as penalty calculation and step length. We implement two main different local search algorithms. We use “Procure”, which is a constraint reasoning and global optimization framework, to implement our techniques, then we produce and introduce our results over a set of benchmarks.

Planning and verification of multipath routing protocols

Conventionally the problem of the best path in a network refers to the shortest path problem. However, for the vast majority of networks present nowadays this solution has some limitations which directly affect their proper functioning, as well as an inefficient use of their potentialities. Problems at the level of large networks where graphs of high complexity are commonly present as well as the appearing of new services and their respective requirements, are intrinsically related to the inability of this solution. In order to overcome the needs present in these networks, a new approach to the problem of the best path must be explored. One solution that has aroused more interest in the scientific community considers the use of multiple paths between two network nodes, where they can all now be considered as the best path between those nodes. Therefore, the routing will be discontinued only by minimizing one metric, where only one path between nodes is chosen, and shall be made by the selection of one of many paths, thereby allowing the use of a greater diversity of the present paths (obviously, if the network consents). The establishment of multi-path routing in a given network has several advantages for its operation. Its use may well improve the distribution of network traffic, improve recovery time to failure, or it can still offer a greater control of the network by its administrator. These factors still have greater relevance when networks have large dimensions, as well as when their constitution is of high complexity, such as the Internet, where multiple networks managed by different entities are interconnected. A large part of the growing need to use multipath protocols is associated to the routing made based on policies. Therefore, paths with different characteristics can be considered with equal level of preference, and thus be part of the solution for the best way problem. To perform multi-path routing using protocols based only on the destination address has some limitations but it is possible. Concepts of graph theory of algebraic structures can be used to describe how the routes are calculated and classified, enabling to model the routing problem. This thesis studies and analyzes multi-path routing protocols from the known literature and derives a new algebraic condition which allows the correct operation of these protocols without any network restriction. It also develops a range of software tools that allows the planning and the respective verification/validation of new protocols models according to the study made.

Development of principle culture medium formulations for Saccharomyces cerevisiae

Saccharomyces cerevisiae as well as other microorganisms are frequently used in industry with the purpose of obtain different kind of products that can be applied in several areas (research investigation, pharmaceutical compounds, etc.). In order to obtain high yields for the desired product, it is necessary to make an adequate medium supplementation during the growth of the microorganisms. The higher yields are typically reached by using complex media, however the exact formulation of these media is not known. Moreover, it is difficult to control the exact composition of complex media, leading to batch-to-batch variations. So, to overcome this problem, some industries choose to use defined media, with a defined and known chemical composition. However these kind of media, many times, do not reach the same high yields that are obtained by using complex media. In order to obtain similar yield with defined media the addition of many different compounds has to be tested experimentally. Therefore, the industries use a set of empirical methods with which it is tried to formulate defined media that can reach the same high yields as complex media. In this thesis, a defined medium for Saccharomyces cerevisiae was developed using a rational design approach. In this approach a given metabolic network of Saccharomyces cerevisiae is divided into a several unique and not further decomposable sub networks of metabolic reactions that work coherently in steady state, so called elementary flux modes. The EFMtool algorithm was used in order to calculate the EFM’s for two Saccharomyces cerevisiae metabolic networks (amino acids supplemented metabolic network; amino acids non-supplemented metabolic network). For the supplemented metabolic network 1352172 EFM’s were calculated and then divided into: 1306854 EFM’s producing biomass, and 18582 EFM’s exclusively producing CO2 (cellular respiration). For the non-supplemented network 635 EFM’s were calculated and then divided into: 215 EFM’s producing biomass; 420 EFM’s producing exclusively CO2. The EFM’s of each group were normalized by the respective glucose consumption value. After that, the EFMs’ of the supplemented network were grouped again into: 30 clusters for the 1306854 EFMs producing biomass and, 20 clusters for the 18582 EFM’s producing CO2. For the non-supplemented metabolic network the respective EFM’s of each metabolic function were grouped into 10 clusters. After the clustering step, the concentrations of the other medium compounds were calculated by considering a reasonable glucose amount and by accounting for the proportionality between the compounds concentrations and the glucose ratios. The approach adopted/developed in this thesis may allow a faster and more economical way for media development.

Analysis, testing and development of safe cleaning methods of rusted stone material

Three different treatments were applied on several specimens of dolomitic and calcitic marble, properly stained with rust to mimic real situations (the stone specimens were exposed to the natural environment for about six months in contact with rusted iron). Thirty six marble specimens, eighteen calcitic and eighteen dolomitic, were characterized before and after treatment and monitored throughout the cleaning tests. The specimens were characterized by SEM-EDS (Scanning Electron Microscopy coupled with Energy Dispersion System), XRD (XRay Diffraction), XRF (X-Ray Fluorescence), FTIR (Fourier Transform Infrared Spectroscopy) and color measurements. It was also made a microscopic and macroscopic analysis of the stone surface along with the tests of short and long term capillary absorption. A series of test trials were conducted in order to understand which concentrations and contact times best suits to this purpose, to confirm what had been written to date in the literature. We sought to develop new methods of treatment application, skipping the usual methods of applying chemical treatments on stone substrates, with the use of cellulose poultice, resorting to the agar, a gel already used in many other areas, being something new in this area, which possesses great applicability in the field of conservation of stone materials. After the application of the best methodology for cleaning, specimens were characterized again in order to understand which treatment was more effective and less harmful, both for the operator and the stone material. Very briefly conclusions were that for a very intense and deep penetration into the stone, a solution of 3.5% of SDT buffered with ammonium carbonate to pH around 7 applied with agar support would be indicated. For rust stains in its initial state, the use of Ammonium citrate at a concentration of 5% buffered with ammonium to pH 7 could be applied more than once until satisfactory results appear.

Analysis and treatment of a nineteenth century oil painting

This thesis focused on the study and treatment of a 19th century female portrait in oil from ECOMUSEU Municipal do Seixal, Portugal. The portrait, which depicts Isabel Maria Lourenço Affonso was in poor condition and a large strip of paint and canvas was missing (approximately 9cm by 66cm, almost 11% of the total surface area). The portrait is a companion piece to a male portrait (the relationship was established as part of this study), therefore a technical study of both paintings was considered essential to support the choices made during the treatment. The project involved three main areas: - The study of the history, condition, materials and techniques of both paintings. This allowed their comparison and understanding of their relationship; - The treatment of Isabel Maria Lourenço Affonso. The choices made and problems encountered are described. - The production of a replacement for the missing strip of paint and canvas. The practical solution developed to overcome such an unusual challenge is described along with the creative and flexible thinking required. Because not all traditional infill materials cope well on a mechanical level with thin layers over a very large surface (many are too brittle), strict criteria had to be employed to choose the appropriate material. The primary goal was to find a fill which would remain flexible and be capable of accepting surface texture, such that there would be a good visual match with the painting. Analysis and testing was carried out to evaluate the physical properties of the fill material chosen, BEVA® Gesso-P. The successful creation of the replacement strip has resulted in two publications and one presentation: Publication pending in The Picture Restorer, Leslie Carlyle, Raquel Marques, Isabel Pombo Cardoso and Sara Babo, “Creating a Textured Replacement Strip for the Missing Lower Portion of an Oil Portrait: Problem Solving and Practical Solutions”. Abstract accepted for presentation and publication, International Meeting on Retouching of Cultural Heritage (2RECH), Raquel Marques, Leslie Carlyle and Isabel Pombo Cardoso, “Textured Replacement Strip for a Missing Portion of a Portrait: Problem Solving and Practical Solutions”.

Gas tungsten arc welding of NiTi shape memory alloy

Shape memory alloys are characterized by the ability of recovering their initial shape after being deformed and by superelasticity. Since the discovery of these alloys, a new field of interest emerged not only for the scientific community but also to many industries. However, these alloys present poor machinability which constitute a constrain in the design of complex components for new applications. Thus, the demand for joining techniques able to join these alloys without compromising their properties became of great importance to enlarge the complexity of existing applications. Literature shows that these alloys are joined mainly using laser welding. In the present study, similar NiTi butt joints, were produced using TIG welding. The welds were performed in 1.5 mm thick plates across the rolling direction. A special fixture and gas assist device was designed and manufactured. Also a robot arm was adapted to accommodate the welding torch to assure the repeatability of the welding parameters. Welds were successfully achieved without macroscopic defects, such as pores and distortions. Very superficial oxidation was seen on the top surface due to insufficient shielding gas flow on the weld face. The welded joints were mechanically tested and structurally characterized. Testing methods were used to evaluate macro and microstructure, as well as the phase transformation temperatures, the mechanical single and cyclic behaviour and the shape recovery ability. Differential Scanning Calorimetry (DSC), Scanning Electron Microscopy (SEM), Energy Dispersive Spectroscopy (EDS), microhardness measurements were techniques also used to evaluate the welded joints. A depletion in Ni in the fusion zone was seen, as well as a shift in Ms temperature. For strain values of 4% the accumulated irrecoverable strain was of about 30% and increased with the strain imposed during cycling. Nevertheless, a complete recovery of initial shape was observed when testing the shape memory effect on a dedicated device that introduces a deformation of 6.7%. That is, the welding procedure does not remove the ability of the specimens to recover their initial shape.

Efficient paraconsistent reasoning with rules and ontologies for the semantic web

Ontologies formalized by means of Description Logics (DLs) and rules in the form of Logic Programs (LPs) are two prominent formalisms in the field of Knowledge Representation and Reasoning. While DLs adhere to the OpenWorld Assumption and are suited for taxonomic reasoning, LPs implement reasoning under the Closed World Assumption, so that default knowledge can be expressed. However, for many applications it is useful to have a means that allows reasoning over an open domain and expressing rules with exceptions at the same time. Hybrid MKNF knowledge bases make such a means available by formalizing DLs and LPs in a common logic, the Logic of Minimal Knowledge and Negation as Failure (MKNF). Since rules and ontologies are used in open environments such as the Semantic Web, inconsistencies cannot always be avoided. This poses a problem due to the Principle of Explosion, which holds in classical logics. Paraconsistent Logics offer a solution to this issue by assigning meaningful models even to contradictory sets of formulas. Consequently, paraconsistent semantics for DLs and LPs have been investigated intensively. Our goal is to apply the paraconsistent approach to the combination of DLs and LPs in hybrid MKNF knowledge bases. In this thesis, a new six-valued semantics for hybrid MKNF knowledge bases is introduced, extending the three-valued approach by Knorr et al., which is based on the wellfounded semantics for logic programs. Additionally, a procedural way of computing paraconsistent well-founded models for hybrid MKNF knowledge bases by means of an alternating fixpoint construction is presented and it is proven that the algorithm is sound and complete w.r.t. the model-theoretic characterization of the semantics. Moreover, it is shown that the new semantics is faithful w.r.t. well-studied paraconsistent semantics for DLs and LPs, respectively, and maintains the efficiency of the approach it extends.

The use of analytical hierarchy process in spatial decision support system for land use management

Geographic information systems give us the possibility to analyze, produce, and edit geographic information. Furthermore, these systems fall short on the analysis and support of complex spatial problems. Therefore, when a spatial problem, like land use management, requires a multi-criteria perspective, multi-criteria decision analysis is placed into spatial decision support systems. The analytic hierarchy process is one of many multi-criteria decision analysis methods that can be used to support these complex problems. Using its capabilities we try to develop a spatial decision support system, to help land use management. Land use management can undertake a broad spectrum of spatial decision problems. The developed decision support system had to accept as input, various formats and types of data, raster or vector format, and the vector could be polygon line or point type. The support system was designed to perform its analysis for the Zambezi river Valley in Mozambique, the study area. The possible solutions for the emerging problems had to cover the entire region. This required the system to process large sets of data, and constantly adjust to new problems’ needs. The developed decision support system, is able to process thousands of alternatives using the analytical hierarchy process, and produce an output suitability map for the problems faced.

Adesão à terapêutica medicamentosa em doentes com Diabetes Mellitus Tipo 2 : um estudo no ACES Almada e Seixal

RESUMO - A (não) adesão à terapêutica é um problema mundial que, para além de afetar diretamente a saúde dos indivíduos, afeta também os recursos económicos e sociais. Apesar da importância em aderir à terapêutica, largamente fundamentada na evidência científica, facto é que, em muitos casos, os doentes não o fazem. Assim, estudar as questões relacionadas com a adesão tem vindo a ganhar cada vez mais relevância e atualmente constitui um desafio para os sistemas de saúde, pois os mecanismos envolvidos no comportamento de adesão dos indivíduos são complexos. Deste modo, com este estudo pretendeu-se caracterizar uma amostra de indivíduos com diabetes mellitus tipo 2 e relacionar o seu nível de adesão à terapêutica medicamentosa com os fatores de não adesão. Este estudo foi desenvolvido no Agrupamento de Centros de Saúde (ACES) Almada e Seixal e nele participaram 151 diabéticos tipo 2. Para a recolha de dados utilizou-se o Questionário de Identificação de Fatores de Não Adesão adaptado de Cabral e Silva (2010) e a Medida de Adesão aos Tratamentos de Delgado e Lima (2001). Os resultados mostraram um perfil de participantes maioritariamente idosos, reformados, do género feminino, casados, com o ensino primário completo, rendimento mensal entre 301-1000 euros e tendencialmente aderentes à terapêutica medicamentosa. O (i) esquecimento, o (ii) preço da medicação, o (iii) número elevado de medicamentos para tomar de uma vez só, não perceber bem o que deve tomar e como e (v) adormecer antes da toma foram os fatores de não adesão relatados com mais frequência. Foram encontradas relações significativas entre o nível de adesão e o esquecimento, o preço da medicação o número elevado de medicamentos para tomar de uma vez só e adormecer antes da toma. Não encontrámos relações significativas entre o nível de adesão e os dados sociodemográficos, os fatores terapêuticos e o fator de não adesão “não perceber bem o que deve tomar e como”. No presente estudo são discutidos os resultados obtidos, consideradas algumas limitações e efetuadas propostas de investigações futuras.

Reactive electron scattering from biomolecules and technologically relevant molecules

The role of a set of gases relevant within the context of biomolecules and technologically relevant molecules under the interaction of low-energy electrons was studied in an effort to contribute to the understanding of the underlying processes yielding negative ion formation. The results are relevant within the context of damage to living material exposed to energetic radiation, to the role of dopants in the ion-molecule chemistry processes, to Electron Beam Induced Deposition (EBID) and Ion Beam Induced Deposition (IBID) techniques. The research described in this thesis addresses dissociative electron attachment (DEA) and electron transfer studies involving experimental setups from the University of Innsbruck, Austria and Universidade Nova de Lisboa, Portugal, respectively. This thesis presents DEA studies, obtained by a double focusing mass spectrometer, of dimethyl disulphide (C2H6S2), two isomers, enflurane and isoflurane (C3F5Cl5) and two chlorinated ethanes, pentachloroethane (C2HCl5) and hexachloroethane (C2Cl6), along with quantum chemical calculations providing information on the molecular orbitals as well as thermochemical thresholds of anion formation for enflurane, isoflurane, pentachloroethane and hexachloroethane. The experiments represent the most accurate DEA studies to these molecules, with significant differences from previous work reported in the literature. As far as electron transfer studies are concerned, negative ion formation in collisions of neutral potassium atoms with N1 and N3 methylated pyrimidine molecules were obtained by time-of-flight mass spectrometry (TOF). The results obtained allowed to propose concerted mechanisms for site and bond selective excision of bonds.

Electron driven reactions in sulphur containing biological prototypes

The interaction of ionising radiation with living tissues may direct or indirectly generate several secondary species with relevant genotoxic potential. Due to recent findings that electrons with energies below the ionisation threshold can effectively damage DNA, radiation-induced damage to biological systems has increasingly come under scrutiny. The exact physico-chemical processes that occur in the first stages of electron induced damage remain to be explained. However, it is also known that free electrons have a short lifetime in the physiological medium. Hence, electron transfer processes studies represent an alternative approach through which the role of "bound" electrons as a source of damage to biological tissues can be further explored. The thesis work consists of studying dissociative electron attachment (DEA) and electron transfer to taurine and thiaproline. DEA measurements were executed in Siedlce University with Prof. Janina Kopyra under COST action MP1002 (Nanoscale insights in ion beam cancer therapy). The electron transfer experiments were conducted in a crossed atom(potassium)-molecule beam arrangement. In these studies the anionic fragmentation patterns were obtained. The results of both mechanisms are shown to be significantly different, unveiling that the damaging potential of secondary electrons can be underestimated. In addition, sulphur atoms appear to strongly influence the dissociation process, demonstrating that certain reactions can be controlled by substitution of sulphur at specific molecular sites.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Elucidating the role of glycans in leucocyte function

RESUMO: O processo de glicosilação é a modificação pós-traducional de proteínas mais comum e está envolvido em vários processos fisiológicos e patológicos. Especificamente, certos perfis glicosídeos estão correlacionados a estados específicos de diferenciação celular, e podem modular vários eventos celulares, como sinalização celular, migração celular e interações hospedeiro-patogénio. Assim sendo, a glicosilação desempenha um papel crucial na modulação de vários processos imunológicos. No entanto, permanece por esclarecer como as estruturas glicosídicas influenciam a imunidade. Especificamente, algumas estruturas glicosídicas terminais que estão modificadas pela ligação de ácido siálico desempenham um papel importante em várias funções do sistema imune, nomeadamente migração leucocitária em contexto de inflamação e ativação de células imunes. Como tal, este trabalho teve como objectivo investigar como a expressão de certos glicanos influencia componentes importantes da resposta imune inata e adaptativa. Este trabalho está dividido em três componentes principais: 1) A imunidade está amplamente dependente da habilidade das células circulantes migrarem para os tecidos inflamados, sendo que a ligação de leucócitos à Eselectina endotelial é o primeiro passo. Assim, nós analisámos a estrutura e função dos ligandos de E-selectina que são expressos pelas células humanas mononucleares de sangue periférico (PBMCs), fornecendo novos conhecimentos para a compreensão dos intervenientes moleculares que mediam a ligação dos monócitos, células CD4+ e CD8+T e células B ao endotélio vascular. Surpreendentemente, os monócitos apresentaram maior capacidade de ligação à E-selectina comparativamente aos linfócitos. Esta observação pode ser explicada pelo facto de os monócitos humanos expressarem, uniformemente, um vasto reportório de glicoproteínas que exibem afinidade de ligação à E-selectina, nomeadamente: as glicoformas do CD43 (CD43E) e do CD44 (HCELL), em adição à já previamente reportada glicoforma da PSGL-1 (CLA). Consistentemente, a diferente capacidade que as diversas populações linfocitárias apresentam de se ligar à E-selectina, está integralmente relacionada com a sua expressão de glicoproteínas com afinidade de ligação à E-selectina. Enquanto que as células CD4+T apresentam uma elevada reatividade à E-selectina, as células CD8+T e B demonstram pouca ou nenhuma capacidade de ligação à E-selectina. Esta atividade de ligação à E-selectina das células CD4+T é conferida pela expressão de HCELL, em adição às já previamente reportadas CLA e CD43E. As células CD8+ T não expressam HCELL e apenas expressam pequenas quantidades de CLA e CD43E, enquanto que as células B não expressam ligandos de Eselectina. Mais, a exofucosilação da superfície destas células, levou ao dramático aumento da expressão dos ligandos de E-selectina em todos as populações leucocitárias, verificando-se que a criação de certos ligandos de E-selectina está dependente do tipo de célula, após fucosilação. Colectivamente, estes resultados redefinem o nosso conhecimento acerca dos mecanismos moleculares que governam o tráfico das células mononucleares de sangue periférico em contexto de inflamação. 2) A habilidade das células dendríticas (DCs) para extravasarem em locais de inflamação é crucial para o sucesso da terapia com DCs. Assim, analisámos a estrutura e função das moléculas de adesão que mediam a migração transendotelial (TEM) das DCs. Para isso, foram usadas DCs geradas a partir da diferenciação de monócitos (mo-DCS), obtidos quer pelo métodos de separação imuno-magnética de células CD14+ (CD14-S) ou por isolamento por aderência ao plástico (PA-S). Os resultados obtidos indicam que as glicoformas de ligação à Eselectina de PSGL-1, CD43 e CD44 são expressas pelas CD14-S mo-DCs, enquanto que as PA-S mo-DCs expressam apenas CLA. É importante notar que a ligação do CD44 nas mo-DCs, mas não nas PA-S mo-DCs, desencadeia a ativação e consequente adesão da VLA-4 ao endotélio na ausência de um gradiente de quimiocinas. Procedeu-se também à análise dos ligandos E-selectina expressos em mo-DCs geradas a partir de monócitos do sangue do cordão umbilical (UCB) e, inesperadamente, as UCB mo-DCs não expressam qualquer glicoproteína com reatividade à E-selectina. Além disso, a exofucosilação das mo- DCs humanas utilizando uma α(1,3)-fucosiltransferase aumenta significativamente a expressão de HCELL e, portanto, estas células apresentam uma capacidade aumentada para se ligarem à E-selectina em condições de fluxo hemodinâmico. Estes resultados destacam o papel do HCELL no desencadeamento do TEM das CD14-S mo-DCs e sugerem que estratégias para potenciar a expressão de HCELL poderão impulsionar o recrutamento de mo-DCs para locais de inflamação. 3) Outro obstáculo para alcançar o sucesso promissor de vacinas baseadas em DCs é o estabelecimento de abordagens eficientes que poderão melhorar o estado de maturação e apresentação antigénica das DCs. Por conseguinte, foram investigadas abordagens alternativas que podem superar este obstáculo. Através da remoção de ácido siálico de superfície celular das DCs, conseguiu-se induzir a maturação de DC humanas e de ratinhos. Notavelmente, tanto as DCs humanas como as de ratinho, ao serem desialiladas mostraram uma capacidade aumentada para induzir a proliferação de células T, para secretar citocinas Th1 e para induzir a morte específica de células tumorais. Em adição, as DCs desialiladas apresentam uma maior capacidade de apresentação cruzada de antigénios tumorais às células T citotóxicas. Colectivamente, o presente estudo oferece uma visão chave para optimizar a capacidade das DCs em induzir respostas imunitárias anti-tumorais, e indica que o tratamento com sialidase é uma nova tecnologia para melhorar a eficácia e aplicabilidade das vacinas baseadas em DCs. Coletivamente, os nossos resultados demostram como a glicosilação e a sua manipulação podem modular a imunidade. Concretamente, através de uma reação de exofucosilação conseguimos aumentar fortemente a capacidade de os leucócitos extravasarem para os tecidos afectados, enquanto que a remoção dos níveis de ácido siálico da superfície celular das DCs, induz potentes respostas anti-tumorais mediadas por células T citotóxicas. ------------------------------------ ABSTRACT: Glycosylation is the most widely form of protein post-translational modification and is involved in many physiological and pathological processes. Specifically, certain patterns of glycosylation are associated with determined stages of cell differentiation and can modulate processes like cell-signaling and migration and host-pathogen interactions. As such, glycosylation plays a crucial role in the modulation of several immune events. However, how glycans execute this immune-modulation and, therefore, influence immunity is still poorly unknown. Specifically, some terminal sialic acid-modified determinants are known to be involved in several physiological immune processes, including leukocyte trafficking into sites of inflammation and cell immune activation. Therefore, in this work, we sought to investigate more deeply how the expression of these glycosidic structures affects events form both innate and adaptive immune responses. To this end, we divided our work into three main parts: 1) Immunity critically depends on the ability of sentinel circulating cells to infiltrate injured sites, of which leukocyte binding to endothelial E-selectin is the critical first step. Thus, we first analyzed the structure and function of the E-selectin ligands expressed on native human peripheral blood mononuclear cells (PBMCs), providing novel insights into the molecular effectors governing adhesion of circulating monocytes, and of circulating CD4+T, CD8+T and B cells, to vascular endothelium under hemodynamic shear conditions. Strikingly, monocytes show a higher ability to tether and roll on endothelial cells than lymphocyte subsets. This is due to the fact that human circulating monocytes uniformly display a wide repertoire of E-selectin binding glycoproteins, namely the E-selectin-binding glycoforms of CD43 (CD43E) and CD44 (HCELL), in addition to the previously described E-selectin-binding glycoform of PSGL-1 (CLA). In addition, we also observed a differential ability of the different lymphocyte subsets to bind to Eselectin under hemodynamic shear stress conditions, and these differences were highly correlated with their individual expression of E-selectin binding glycoproteins. While CD4+T cells show a robust E-selectin binding ability, CD8+T and B cells show little to no E-selectin reactivity. CD4+T cell potent Eselectin rolling activity is conferred by HCELL expression, in addition to the previously reported E-selectin-binding glycoproteins CD43E and CLA. CD8+T cells display no HCELL and low amounts of CLA and CD43E, whereas B cells lack E-selectin ligand expression. Moreover, enforced exofucosylation of cell surface of these cells noticeably increases expression of functional E-selectin ligands among all leukocytes subsets, with cell type-dependent specificity in the protein scaffolds that are modified. Taken together, these findings redefine our understanding of the molecular mechanisms governing the trafficking patterns of PBMCs that are relevant in the context of acute or chronic inflammatory conditions. 2) The ability of circulating dendritic cells (DCs) to extravasate at inflammatory sites is critical to the success of DC-based therapies. Therefore, we assessed the structure and function of adhesion molecules mediating the transendothelial migration (TEM) of human monocyte derived-DCs (mo-DCs), obtained either by CD14 positive immune-magnetic selection (CD14-S) or by plastic adherence of blood monocytes (PA-S). We report for the first time that the E-selectin binding glycoforms of PSGL-1, CD43 and CD44 are all expressed on CD14-S mo-DCs, in contrast to PA-S mo-DCs that express only CLA. Importantly, CD44 engagement on CD14-S mo-DCs, but not on PA-S mo-DCs, triggers VLA-4-dependent adhesiveness and programs TEM in absence of chemokine gradient. We also analyzed the E-selectin ligands expressed on mo-DCs generated from umbilical cord blood (UCB) monocytes, and unexpectedly, UCB mo-DCs do not express any glycoprotein with E-selectin reactivity. Furthermore, exoglycosylation of human mo-DCs using an α(1,3)-fucosyltransferase significantly increases expression of HCELL, and therefore exofucosylated mo-DCs exhibit an augmented ability to bind to E-selectin under hemodynamic shear stress conditions. These findings highlight a role for HCELL engagement in priming TEM of CD14-S mo-DCs, and suggest that strategies to enforce HCELL expression could boost mo-DC recruitment to inflammatory sites. 3) Another obstacle to achieve the promising success of DC-based vaccines is the establishment of efficient approaches that could successfully enhance maturation and cross-presentation ability of DCs. Therefore, we investigated an alternative approach that can overcome this problem. Through removal of sialic acid content from DC cell surface we are able to elicit maturation of both human and mouse DCs. Notably, desialylated human and murine DCs showed enhanced ability to induce autologous T cell to proliferate, to secrete Th1 cytokines and to kill tumor cells. Moreover, desialylated DCs display enhanced cross-presentation of tumor antigens to cytotoxic CD8+ T cells. Collectively, this study offers key insight to optimize the ability of DCs to boost anti-tumor immune responses, and indicates that the treatment with an exogenous sialidase is a powerful new technology to improve the efficacy and applicability of DC-based vaccines. Overall, our findings show how glycosylation and its manipulation can modulate immunity. Concretely, through an exofucosylation reaction we are able to greatly augment the ability of leukocytes to extravasate into injured tissues, while removal of sialic acid moieties from cell surface of DCs, significantly potentiate their ability to induce anti-tumor cytotoxic T cell-mediate responses.

Elucidating the role of glycans in leucocyte function

RESUMO:O processo de glicosilação é a modificação pós-traducional de proteínas mais comum e está envolvido em vários processos fisiológicos e patológicos. Especificamente, certos perfis glicosídeos estão correlacionados a estados específicos de diferenciação celular, e podem modular vários eventos celulares, como sinalização celular, migração celular e interações hospedeiro-patogénio. Assim sendo, a glicosilação desempenha um papel crucial na modulação de vários processos imunológicos. No entanto, permanece por esclarecer como as estruturas glicosídicas influenciam a imunidade. Especificamente, algumas estruturas glicosídicas terminais que estão modificadas pela ligação de ácido siálico desempenham um papel importante em várias funções do sistema imune, nomeadamente migração leucocitária em contexto de inflamação e ativação de células imunes. Como tal, este trabalho teve como objectivo investigar como a expressão de certos glicanos influencia componentes importantes da resposta imune inata e adaptativa. Este trabalho está dividido em três componentes principais: 1) A imunidade está amplamente dependente da habilidade das células circulantes migrarem para os tecidos inflamados, sendo que a ligação de leucócitos à Eselectina endotelial é o primeiro passo. Assim, nós analisámos a estrutura e função dos ligandos de E-selectina que são expressos pelas células humanas mononucleares de sangue periférico (PBMCs), fornecendo novos conhecimentos para a compreensão dos intervenientes moleculares que mediam a ligação dos monócitos, células CD4+ e CD8+T e células B ao endotélio vascular. Surpreendentemente, os monócitos apresentaram maior capacidade de ligação à E-selectina comparativamente aos linfócitos. Esta observação pode ser explicada pelo facto de os monócitos humanos expressarem, uniformemente, um vasto reportório de glicoproteínas que exibem afinidade de ligação à E-selectina, nomeadamente: as glicoformas do CD43 (CD43E) e do CD44 (HCELL), em adição à já previamente reportada glicoforma da PSGL-1 (CLA). Consistentemente, a diferente capacidade que as diversas populações linfocitárias apresentam de se ligar à E-selectina, está integralmente relacionada com a sua expressão de glicoproteínas com afinidade de ligação à E-selectina. Enquanto que as células CD4+T apresentam uma elevada reatividade à E-selectina, as células CD8+T e B demonstram pouca ou nenhuma capacidade de ligação à E-selectina. Esta atividade de ligação à E-selectina das células CD4+T é conferida pela expressão de HCELL, em adição às já previamente reportadas CLA e CD43E. As células CD8+ T não expressam HCELL e apenas expressam pequenas quantidades de CLA e CD43E, enquanto que as células B não expressam ligandos de Eselectina. Mais, a exofucosilação da superfície destas células, levou ao dramático aumento da expressão dos ligandos de E-selectina em todos as populações leucocitárias, verificando-se que a criação de certos ligandos de E-selectina está dependente do tipo de célula, após fucosilação. Colectivamente, estes resultados redefinem o nosso conhecimento acerca dos mecanismos moleculares que governam o tráfico das células mononucleares de sangue periférico em contexto de inflamação. 2) A habilidade das células dendríticas (DCs) para extravasarem em locais de inflamação é crucial para o sucesso da terapia com DCs. Assim, analisámos a estrutura e função das moléculas de adesão que mediam a migração transendotelial (TEM) das DCs. Para isso, foram usadas DCs geradas a partir da diferenciação de monócitos (mo-DCS), obtidos quer pelo métodos de separação imuno-magnética de células CD14+ (CD14-S) ou por isolamento por aderência ao plástico (PA-S). Os resultados obtidos indicam que as glicoformas de ligação à Eselectina de PSGL-1, CD43 e CD44 são expressas pelas CD14-S mo-DCs, enquanto que as PA-S mo-DCs expressam apenas CLA. É importante notar que a ligação do CD44 nas mo-DCs, mas não nas PA-S mo-DCs, desencadeia a ativação e consequente adesão da VLA-4 ao endotélio na ausência de um gradiente de quimiocinas. Procedeu-se também à análise dos ligandos E-selectina expressos em mo-DCs geradas a partir de monócitos do sangue do cordão umbilical (UCB) e, inesperadamente, as UCB mo-DCs não expressam qualquer glicoproteína com reatividade à E-selectina. Além disso, a exofucosilação das mo- DCs humanas utilizando uma α(1,3)-fucosiltransferase aumenta significativamente a expressão de HCELL e, portanto, estas células apresentam uma capacidade aumentada para se ligarem à E-selectina em condições de fluxo hemodinâmico. Estes resultados destacam o papel do HCELL no desencadeamento do TEM das CD14-S mo-DCs e sugerem que estratégias para potenciar a expressão de HCELL poderão impulsionar o recrutamento de mo-DCs para locais de inflamação. 3) Outro obstáculo para alcançar o sucesso promissor de vacinas baseadas em DCs é o estabelecimento de abordagens eficientes que poderão melhorar o estado de maturação e apresentação antigénica das DCs. Por conseguinte, foram investigadas abordagens alternativas que podem superar este obstáculo. Através da remoção de ácido siálico de superfície celular das DCs, conseguiu-se induzir a maturação de DC humanas e de ratinhos. Notavelmente, tanto as DCs humanas como as de ratinho, ao serem desialiladas mostraram uma capacidade aumentada para induzir a proliferação de células T, para secretar citocinas Th1 e para induzir a morte específica de células tumorais. Em adição, as DCs desialiladas apresentam uma maior capacidade de apresentação cruzada de antigénios tumorais às células T citotóxicas. Colectivamente, o presente estudo oferece uma visão chave para optimizar a capacidade das DCs em induzir respostas imunitárias anti-tumorais, e indica que o tratamento com sialidase é uma nova tecnologia para melhorar a eficácia e aplicabilidade das vacinas baseadas em DCs. Coletivamente, os nossos resultados demostram como a glicosilação e a sua manipulação podem modular a imunidade. Concretamente, através de uma reação de exofucosilação conseguimos aumentar fortemente a capacidade de os leucócitos extravasarem para os tecidos afectados, enquanto que a remoção dos níveis de ácido siálico da superfície celular das DCs, induz potentes respostas anti-tumorais mediadas por células T citotóxicas. ---------------------------- ABSTRACT: Glycosylation is the most widely form of protein post-translational modification and is involved in many physiological and pathological processes. Specifically, certain patterns of glycosylation are associated with determined stages of cell differentiation and can modulate processes like cell-signaling and migration and host-pathogen interactions. As such, glycosylation plays a crucial role in the modulation of several immune events. However, how glycans execute this immune-modulation and, therefore, influence immunity is still poorly unknown. Specifically, some terminal sialic acid-modified determinants are known to be involved in several physiological immune processes, including leukocyte trafficking into sites of inflammation and cell immune activation. Therefore, in this work, we sought to investigate more deeply how the expression of these glycosidic structures affects events form both innate and adaptive immune responses. To this end, we divided our work into three main parts: 1) Immunity critically depends on the ability of sentinel circulating cells to infiltrate injured sites, of which leukocyte binding to endothelial E-selectin is the critical first step. Thus, we first analyzed the structure and function of the E-selectin ligands expressed on native human peripheral blood mononuclear cells (PBMCs), providing novel insights into the molecular effectors governing adhesion of circulating monocytes, and of circulating CD4+T, CD8+T and B cells, to vascular endothelium under hemodynamic shear conditions. Strikingly, monocytes show a higher ability to tether and roll on endothelial cells than lymphocyte subsets. This is due to the fact that human circulating monocytes uniformly display a wide repertoire of E-selectin binding glycoproteins, namely the E-selectin-binding glycoforms of CD43 (CD43E) and CD44 (HCELL), in addition to the previously described E-selectin-binding glycoform of PSGL-1 (CLA). In addition, we also observed a differential ability of the different lymphocyte subsets to bind to Eselectin under hemodynamic shear stress conditions, and these differences were highly correlated with their individual expression of E-selectin binding glycoproteins. While CD4+T cells show a robust E-selectin binding ability, CD8+T and B cells show little to no E-selectin reactivity. CD4+T cell potent Eselectin rolling activity is conferred by HCELL expression, in addition to the previously reported E-selectin-binding glycoproteins CD43E and CLA. CD8+T cells display no HCELL and low amounts of CLA and CD43E, whereas B cells lack E-selectin ligand expression. Moreover, enforced exofucosylation of cell surface of these cells noticeably increases expression of functional E-selectin ligands among all leukocytes subsets, with cell type-dependent specificity in the protein scaffolds that are modified. Taken together, these findings redefine our understanding of the molecular mechanisms governing the trafficking patterns of PBMCs that are relevant in the context of acute or chronic inflammatory conditions. 2) The ability of circulating dendritic cells (DCs) to extravasate at inflammatory sites is critical to the success of DC-based therapies. Therefore, we assessed the structure and function of adhesion molecules mediating the transendothelial migration (TEM) of human monocyte derived-DCs (mo-DCs), obtained either by CD14 positive immune-magnetic selection (CD14-S) or by plastic adherence of blood monocytes (PA-S). We report for the first time that the E-selectin binding glycoforms of PSGL-1, CD43 and CD44 are all expressed on CD14-S mo-DCs, in contrast to PA-S mo-DCs that express only CLA. Importantly, CD44 engagement on CD14-S mo-DCs, but not on PA-S mo-DCs, triggers VLA-4-dependent adhesiveness and programs TEM in absence of chemokine gradient. We also analyzed the E-selectin ligands expressed on mo-DCs generated from umbilical cord blood (UCB) monocytes, and unexpectedly, UCB mo-DCs do not express any glycoprotein with E-selectin reactivity. Furthermore, exoglycosylation of human mo-DCs using an α(1,3)-fucosyltransferase significantly increases expression of HCELL, and therefore exofucosylated mo-DCs exhibit an augmented ability to bind to E-selectin under hemodynamic shear stress conditions. These findings highlight a role for HCELL engagement in priming TEM of CD14-S mo-DCs, and suggest that strategies to enforce HCELL expression could boost mo-DC recruitment to inflammatory sites.3) Another obstacle to achieve the promising success of DC-based vaccines is the establishment of efficient approaches that could successfully enhance maturation and cross-presentation ability of DCs. Therefore, we investigated an alternative approach that can overcome this problem. Through removal of sialic acid content from DC cell surface we are able to elicit maturation of both human and mouse DCs. Notably, desialylated human and murine DCs showed enhanced ability to induce autologous T cell to proliferate, to secrete Th1 cytokines and to kill tumor cells. Moreover, desialylated DCs display enhanced cross-presentation of tumor antigens to cytotoxic CD8+ T cells. Collectively, this study offers key insight to optimize the ability of DCs to boost anti-tumor immune responses, and indicates that the treatment with an exogenous sialidase is a powerful new technology to improve the efficacy and applicability of DC-based vaccines. Overall, our findings show how glycosylation and its manipulation can modulate immunity. Concretely, through an exofucosylation reaction we are able to greatly augment the ability of leukocytes to extravasate into injured tissues, while removal of sialic acid moieties from cell surface of DCs, significantly potentiate their ability to induce anti-tumor cytotoxic T cell-mediate responses.