检索结果-内蒙古大学图书馆

PEMT: a patent enrichment tool for drug discovery (vol 39, btac716, 2023)

学校读者我要写书评

暂无评论

BIOINFORMATICS 2023年第12期39卷 btac716-btac716页

作者： Gadiya, Yojana Zaliani, Andrea Gribbon, Philip Hofmann-Apitius, Martin Fraunhofer Institute for Translational Medicine and Pharmacology (ITMP) Hamburg 22525 Germany Fraunhofer Cluster of Excellence for Immune-Mediated Diseases (CIMD) Frankfurt 60590 Germany Department of Bioinformatics Fraunhofer Institute for Algorithms and Scientific Computing (SCAI) Sankt Augustin 53754 Germany Bonn-Aachen International Center for Information Technology (B-IT) University of Bonn Bonn 53113 Germany

Motivation Drug discovery practitioners in industry and academia use semantic tools to extract information from online scientific literature to generate new insights into targets, therapeutics and diseases. However, due to complexities in access and analysis, patent-based literature is often overlooked as a source of information. As drug discovery is a highly competitive field, naturally, tools that tap into patent literature can provide any actor in the field an advantage in terms of better informed decision-making. Hence, we aim to facilitate access to patent literature through the creation of an automatic tool for extracting information from patents described in existing public *** Here, we present PEMT, a novel patent enrichment tool, that takes advantage of public databases like ChEMBL and SureChEMBL to extract relevant patent information linked to chemical structures and/or gene names described through FAIR principles and metadata annotations. PEMT aims at supporting drug discovery and research by establishing a patent landscape around genes of interest. The pharmaceutical focus of the tool is mainly due to the subselection of International Patent Classification codes, but in principle, it can be used for other patent fields, provided that a link between a concept and chemical structure is investigated. Finally, we demonstrate a use-case in rare diseases by generating a gene-patent list based on the epidemiological prevalence of these diseases and exploring their underlying patent *** and implementation PEMT is an open-source Python tool and its source code and PyPi package are available at https://***/Fraunhofer-ITMP/PEMT and https://***/project/PEMT/, *** information Supplementary data are available at Bioinformatics online.

关键词：

Parameterized study of STEINER TREE on unit disk graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Kolay, Sudeshna Algorithms and Complexity Group Tu Wien Vienna Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur

We study the STEINER TREE problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R. The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the STEINER TREE problem on unit disk graphs can be solved in nO(√t+k)time. We also show that the STEINER TREE problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for STEINER TREE on disk graphs with bounded aspect ratio. Finally, we prove that STEINER TREE on disk graphs parameterized by k is W[1]-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Hardness

Approximation algorithms for coupled task scheduling minimizing the sum of completion times

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fischer, David Györgyi, Péter Institute of Algorithms and Complexity Hamburg University of Technology Blohmstraße 15 Hamburg21079 Germany Institute for Computer Science and Control Eötvös Loránd Research Network Kende Str. 13-17. Budapest1111 Hungary

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task *** Codes 90B35 © 2022, CC BY.

关键词： Approximation algorithms

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bergougnoux, Benjamin Chekan, Vera Ganian, Robert Kanté, Mamadou Moustapha Mnich, Matthias Oum, Sang-Il Pilipczuk, Michal van Leeuwen, Erik Jan Institute of Informatics University of Warsaw Poland Humboldt-Universität zu Berlin Germany Algorithms and Complexity Group TU Wien Vienna Austria Université Clermont Auvergne Clermont Auvergne INP LIMOS CNRS Clermont-Ferrand France Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Daejeon Korea Republic of Department of Mathematical Sciences KAIST Daejeon Korea Republic of Dept. Information and Computing Sciences Utrecht University Netherlands

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, Independent Set can be solved in time 2O(dk) · nO(1) using O(dk2 log n) space;Max Cut can be solved in time nO(dk) using O(dk log n) space;and Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial. Copyright © 2023, The Authors. All rights reserved.

关键词： Dynamic programming

Resource and service discovery for large-scale robot networks in disaster scenarios

学校读者我要写书评

暂无评论

Resource and service discovery for large-scale robot network...

IEEE International Workshop on Safety, Security, and Rescue Robotics (SSRR)

作者： Jia Lei Du S. Ruhrup U. Witkowski U. Ruckert System and Circuit Technology Research Group Heinz Nixdorf Institute University of Paderborn Paderborn Germany Algorithms and Complexity Research Group Heinz Nixdorf Institute University of Paderborn Paderborn Germany

If robots are deployed in large numbers in disaster scenarios, the ability to discover and exchange resources and services with other robots in an open, heterogeneous, large-scale network would be essential for a successful operation. In this paper we present a discovery protocol that enables robots to efficiently locate resources and services available in large-scale networks. It is specifically designed for robot networks which are characterized by potentially highly dynamic network topologies and high service announcement-to-lookup ratios. The protocol exploits the position data of the robots to increase scalability and efficiency. A cell-based overlay structure is created, with master nodes in each cell. Through proactive intra-cell communication and reactive inter-cell communication, scalability is ensured and the effects of node movements on the overall network are minimized.

关键词： Large-scale systems Intelligent networks Robot sensing systems Mobile communication Mobile robots Scalability Robotics and automation Protocols Humans Robot vision systems

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time 40

学校读者我要写书评

暂无评论

Fully Dynamic Maximum Independent Sets of Disks in Polylogar...

40th International Symposium on Computational Geometry, SoCG 2024

作者： Bhore, Sujoy Nöllenburg, Martin Tóth, Csaba D. Wulms, Jules Department of Computer Science and Engineering Indian Institute of Technology Bombay Mumbai India Institute of Logic and Computation Algorithms and Complexity Group TU Wien Austria Department of Mathematics California State University Northridge Los AngelesCA United States Department of Computer Science Tufts University MedfordMA United States Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959773164

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1 + Ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another;hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted. © Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.

关键词： Data structures

Gerrymandering on graphs: Computational complexity and parameterized algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket Institute of Mathematical Science HBNI India Indian Institute of Technology Jodhpur India Indian Institute of Technology Hyderabad India Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Science HBNI India University of Bergen Norway

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerrymandering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm wit

关键词： Graph theory

学校读者我要写书评

暂无评论

Minimum Link Fencing

arXiv 2022年

作者： Bhore, Sujoy Klute, Fabian Löffler, Maarten Nöllenburg, Martin Terziadis, Soeren Villedieu, Anaïs Department of Computer Science & Engineering Indian Institute of Technology Bombay India Department of Information and Computing Sciences Utrecht University Netherlands Algorithms and Complexity Group TU Wien Austria

We study a variant of the geometric multicut problem, where we are given a set P of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where P contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of P \ {Q} does not intersect Q. © 2022, CC BY.

关键词： Computational geometry

Envy-free dynamic pricing schemes

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bérczi, Kristóf Codazzi, Laura Golak, Julian Grigoriev, Alexander MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Institute of Algorithms and Complexity Hamburg University of Technology Hamburg Germany Department of Data Analytics and Digitalisation Maastricht University Maastricht Netherlands

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive. © 2023, CC BY.

关键词： Polynomial approximation