Characterizing and Extending Answer Set Semantics using Possibility Theory

Answer Set Programming (ASP) is a popular framework for modelling combinatorial problems. However, ASP cannot be used easily for reasoning about uncertain information. Possibilistic ASP (PASP) is an extension of ASP that combines possibilistic logic and ASP. In PASP a weight is associated with each rule, whereas this weight is interpreted as the certainty with which the conclusion can be established when the body is known to hold. As such, it allows us to model and reason about uncertain information in an intuitive way. In this paper we present new semantics for PASP in which rules are interpreted as constraints on possibility distributions. Special models of these constraints are then identified as possibilistic answer sets. In addition, since ASP is a special case of PASP in which all the rules are entirely certain, we obtain a new characterization of ASP in terms of constraints on possibility distributions. This allows us to uncover a new form of disjunction, called weak disjunction, that has not been previously considered in the literature. In addition to introducing and motivating the semantics of weak disjunction, we also pinpoint its computational complexity. In particular, while the complexity of most reasoning tasks coincides with standard disjunctive ASP, we find that brave reasoning for programs with weak disjunctions is easier.

Inhibition of O-GlcNAc transferase activity reprograms prostate cancer cell metabolism

Metabolic networks are highly connected and complex, but a single enzyme, O-GlcNAc transferase (OGT) can sense the availability of metabolites and also modify target proteins. We show that inhibition of OGT activity inhibits the proliferation of prostate cancer cells, leads to sustained loss of c-MYC and suppresses the expression of CDK1, elevated expression of which predicts prostate cancer recurrence (p=0.00179). Metabolic profiling revealed decreased glucose consumption and lactate production after OGT inhibition. This decreased glycolytic activity specifically sensitized prostate cancer cells, but not cells representing normal prostate epithelium, to inhibitors of oxidative phosphorylation (rotenone and metformin). Intra-cellular alanine was depleted upon OGT inhibitor treatment. OGT inhibitor increased the expression and activity of alanine aminotransferase (GPT2), an enzyme that can be targeted with a clinically approved drug, cycloserine. Simultaneous inhibition of OGT and GPT2 inhibited cell viability and growth rate, and additionally activated a cell death response. These combinatorial effects were predominantly seen in prostate cancer cells, but not in a cell-line derived from normal prostate epithelium. Combinatorial treatments were confirmed with two inhibitors against both OGT and GPT2. Taken together, here we report the reprogramming of energy metabolism upon inhibition of OGT activity, and identify synergistically lethal combinations that are prostate cancer cell specific.

Microneedles: A New Frontier in Nanomedicine Delivery

This review aims to concisely chart the development of two individual research fields, namely nanomedicines, with specific emphasis on nanoparticles (NP) and microparticles (MP), and microneedle (MN) technologies, which have, in the recent past, been exploited in combinatorial approaches for the efficient delivery of a variety of medicinal agents across the skin. This is an emerging and exciting area of pharmaceutical sciences research within the remit of transdermal drug delivery and as such will undoubtedly continue to grow with the emergence of new formulation and fabrication methodologies for particles and MN. Firstly, the fundamental aspects of skin architecture and structure are outlined, with particular reference to their influence on NP and MP penetration. Following on from this, a variety of different particles are described, as are the diverse range of MN modalities currently under development. The review concludes by highlighting some of the novel delivery systems which have been described in the literature exploiting these two approaches and directs the reader towards emerging uses for nanomedicines in combination with MN.

Synthesis of FPGA-based accelerators implementing recursive algorithms

O desenvolvimento de sistemas computacionais é um processo complexo, com múltiplas etapas, que requer uma análise profunda do problema, levando em consideração as limitações e os requisitos aplicáveis. Tal tarefa envolve a exploração de técnicas alternativas e de algoritmos computacionais para optimizar o sistema e satisfazer os requisitos estabelecidos. Neste contexto, uma das mais importantes etapas é a análise e implementação de algoritmos computacionais. Enormes avanços tecnológicos no âmbito das FPGAs (Field-Programmable Gate Arrays) tornaram possível o desenvolvimento de sistemas de engenharia extremamente complexos. Contudo, o número de transístores disponíveis por chip está a crescer mais rapidamente do que a capacidade que temos para desenvolver sistemas que tirem proveito desse crescimento. Esta limitação já bem conhecida, antes de se revelar com FPGAs, já se verificava com ASICs (Application-Specific Integrated Circuits) e tem vindo a aumentar continuamente. O desenvolvimento de sistemas com base em FPGAs de alta capacidade envolve uma grande variedade de ferramentas, incluindo métodos para a implementação eficiente de algoritmos computacionais. Esta tese pretende proporcionar uma contribuição nesta área, tirando partido da reutilização, do aumento do nível de abstracção e de especificações algorítmicas mais automatizadas e claras. Mais especificamente, é apresentado um estudo que foi levado a cabo no sentido de obter critérios relativos à implementação em hardware de algoritmos recursivos versus iterativos. Depois de serem apresentadas algumas das estratégias para implementar recursividade em hardware mais significativas, descreve-se, em pormenor, um conjunto de algoritmos para resolver problemas de pesquisa combinatória (considerados enquanto exemplos de aplicação). Versões recursivas e iterativas destes algoritmos foram implementados e testados em FPGA. Com base nos resultados obtidos, é feita uma cuidada análise comparativa. Novas ferramentas e técnicas de investigação que foram desenvolvidas no âmbito desta tese são também discutidas e demonstradas.

Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Determination of (0,2)-regular sets in graphs and applications

In this paper, relevant results about the determination of (k,t)-regular sets, using the main eigenvalues of a graph, are reviewed and some results about the determination of (0,2)-regular sets are introduced. An algorithm for that purpose is also described. As an illustration, this algorithm is applied to the determination of maximum matchings in arbitrary graphs.

Optimised search heuristics: combining metaheuristics and exact methods to solve scheduling problems

Tese dout., Matemática, Investigação Operacional, Universidade do Algarve, 2009

Development of new approaches for the synthesis and decoding of one-bead one-compound cyclic peptide libraries

La plupart des processus cellulaires et biologiques reposent, à un certain niveau, sur des interactions protéine-protéine (IPP). Leur manipulation avec des composés chimiques démontre un grand potentiel pour la découverte de nouveaux médicaments. Malgré la demande toujours croissante en molécules capables d’interrompre sélectivement des IPP, le développement d’inhibiteurs d’IPP est fortement limité par la grande taille de la surface d’interaction. En considérant la nature de cette surface, la capacité à mimer des structures secondaires de protéines est très importante pour lier une protéine et inhiber une IPP. Avec leurs grandes capacités peptidomimétiques et leurs propriétés pharmacologiques intéressan-tes, les peptides cycliques sont des prototypes moléculaires de choix pour découvrir des ligands de protéines et développer de nouveaux inhibiteurs d’IPP. Afin d’exploiter pleinement la grande diversité accessible avec les peptides cycliques, l’approche combinatoire «one-bead-one-compound» (OBOC) est l’approche la plus accessible et puissante. Cependant, l’utilisation des peptides cycliques dans les chimiothèques OBOC est limitée par les difficultés à séquencer les composés actifs après le criblage. Sans amine libre en N-terminal, la dégradation d’Edman et la spectrométrie de masse en tandem (MS/MS) ne peuvent pas être utilisées. À cet égard, nous avons développé de nouvelles approches par ouverture de cycle pour préparer et décoder des chimiothèques OBOC de peptides cycliques. Notre stratégie était d’introduire un résidu sensible dans le macrocycle et comme ancrage pour permettre la linéarisation des peptides et leur largage des billes pour le séquençage par MS/MS. Tout d’abord, des résidus sensibles aux nucléophiles, aux ultraviolets ou au bromure de cyanogène ont été introduits dans un peptide cyclique et leurs rendements de clivage évalués. Ensuite, les résidus les plus prometteurs ont été utilisés dans la conception et le développement d’approches en tandem ouverture de cycle / clivage pour le décodage de chimiothèques OBOC de peptides cycliques. Dans la première approche, une méthionine a été introduite dans le macrocycle comme ancrage pour simultanément permettre l’ouverture du cycle et le clivage des billes par traitement au bromure de cyanogène. Dans la seconde approche, un résidu photosensible a été utilisé dans le macrocycle comme ancrage pour permettre l’ouverture du cycle et le clivage suite à une irradiation aux ultraviolets. Le peptide linéaire généré par ces approches peut alors être efficacement séquencé par MS/MS. Enfin, une chimiothèque OBOC a été préparée et criblée la protéine HIV-1 Nef pour identifier des ligands sélectifs. Le développement de ces méthodologies permttra l’utilisation de composés macrocycliques dans les chimiothèques OBOC et constitue une contribution importante en chimie médicinale pour la découverte de ligands de protéines et le développement d’inhibiteurs d’IPP.

Desenvolvimento de ferramentas de apoio multicritério à decisão em problemas de localização

Tese de doutoramento, Estatística e Investigação Operacional (Análise de Sistemas), Universidade de Lisboa, Faculdade de Ciências, 2014

Developing Low Fouling Peptides and Zwitterionic Materials for Biomedical Applications

Thesis (Ph.D.)--University of Washington, 2015

Simulated annealing metaheuristic to solve the optimal power flow

The optimal power flow problem has been widely studied in order to improve power systems operation and planning. For real power systems, the problem is formulated as a non-linear and as a large combinatorial problem. The first approaches used to solve this problem were based on mathematical methods which required huge computational efforts. Lately, artificial intelligence techniques, such as metaheuristics based on biological processes, were adopted. Metaheuristics require lower computational resources, which is a clear advantage for addressing the problem in large power systems. This paper proposes a methodology to solve optimal power flow on economic dispatch context using a Simulated Annealing algorithm inspired on the cooling temperature process seen in metallurgy. The main contribution of the proposed method is the specific neighborhood generation according to the optimal power flow problem characteristics. The proposed methodology has been tested with IEEE 6 bus and 30 bus networks. The obtained results are compared with other wellknown methodologies presented in the literature, showing the effectiveness of the proposed method.

Ant colony search algorithm for the optimal power flow problem

To maintain a power system within operation limits, a level ahead planning it is necessary to apply competitive techniques to solve the optimal power flow (OPF). OPF is a non-linear and a large combinatorial problem. The Ant Colony Search (ACS) optimization algorithm is inspired by the organized natural movement of real ants and has been successfully applied to different large combinatorial optimization problems. This paper presents an implementation of Ant Colony optimization to solve the OPF in an economic dispatch context. The proposed methodology has been developed to be used for maintenance and repairing planning with 48 to 24 hours antecipation. The main advantage of this method is its low execution time that allows the use of OPF when a large set of scenarios has to be analyzed. The paper includes a case study using the IEEE 30 bus network. The results are compared with other well-known methodologies presented in the literature.