38 research outputs found
Enclosing a set of objects by two minimum area rectangles
No full textIn this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose an O(n alpha(n)log n) worst-case time algorithm, where alpha() is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons defined by n vertices, a pair of axis-parallel rectangles (s,t) such that s boolean OR t encloses all objects in M and area(s) + area(t) is minimum. The algorithm works in O(n alpha (n) log log n) worst-case space. Moreover, we prove an Omega(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case time O(n log n), using worst-case space O(n log log n). (C) 1996 Academic Press, Inc
ENCLOSING MANY BOXES BY AN OPTIMAL PAIR OF BOXES
No full textWe look at the problem: Given a set M of n d-dimensional intervals, find two d-dimensional intervals S, T, such that all intervals in M are enclosed by S or by T, the distribution is balanced and the intervals S and T fulfill a geometric criterion, e.g. like minimum area sum. Up to now no polynomial time algorithm was known for that problem. We present an O(dn log n + d2n2d-1) algorithm for finding an optimal solution
AI Model for Predicting Anti-PD1 Response in Melanoma Using Multi-Omics Biomarkers
No full textBackground: Immune checkpoint inhibitors (ICIs) have demonstrated significantly improved clinical efficacy in a minority of patients with advanced melanoma, whereas non-responders potentially suffer from severe side effects and delays in other treatment options. Predicting the response to anti-PD1 treatment in melanoma remains a challenge because the current FDA-approved gold standard, the nonsynonymous tumor mutation burden (nsTMB), offers limited accuracy. Methods: In this study, we developed a multi-omics-based machine learning model that integrates genomic and transcriptomic biomarkers to predict the response to anti-PD1 treatment in patients with advanced melanoma. We employed least absolute shrinkage and selection operator (LASSO) regression with 49 biomarkers extracted from tumor–normal whole-exome and RNA sequencing as input features. The performance of the multi-omics AI model was thoroughly compared to that of nsTMB alone and to models that use only genomic or transcriptomic biomarkers. Results: We used publicly available DNA and RNA-seq datasets of melanoma patients for the training and validation of our model, forming a meta-cohort of 449 patients for which the outcome was recorded as a RECIST score. The model substantially improved the prediction of anti-PD1 outcomes compared to nsTMB alone, with an ROC AUC of 0.7 in the training set and an ROC AUC of 0.64 in the test set. Using SHAP values, we demonstrated the explainability of the model’s predictions on a per-sample basis. Conclusions: We demonstrated that models using only RNA-seq or multi-omics biomarkers outperformed nsTMB in predicting the response of melanoma patients to ICI. Furthermore, our machine learning approach improves clinical usability by providing explanations of its predictions on a per-patient basis. Our findings underscore the utility of multi-omics data for selecting patients for treatment with anti-PD1 drugs. However, to train clinical-grade AI models for routine applications, prospective studies collecting larger melanoma cohorts with consistent application of exome and RNA sequencing are required
Manufacturing capacity planning and the value of multi-stage stochastic programming under Markovian demand
No full textManufacturing capacity planning and the value of multi-stage stochastic programming under Markovian demand
No full textAccelerated photochemical reactions at oil-water interface exploiting melting point depression
No full textWater can accelerate a variety of organic reactions far beyond the rates observed in classical organic solvents. However, using pure water as a solvent introduces solubility constraints that have limited the applicability of efficient photochemistry in particular. We report here the formation of aggregates between pairs of arenes, heteroarenes, enamines, or esters with different electron affinities in an aqueous medium, leading to an oil-water phase boundary through substrate melting point depression. The active hydrogen atoms in the reactants engage in hydrogen bonds with water, thereby accelerating photochemical reactions. This methodology realizes appealingly simple conditions for aqueous coupling reactions of complex solid molecules, including complex drug molecules that are poorly soluble in water
An asymptotically optimal multiversion B-tree
No full textIn a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) Btree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others
Biallelic MAD2L1BP (p31comet) mutation is associated with mosaic aneuploidy and juvenile granulosa cell tumors
No full textCharacterization for high dynamic range imaging
No full textIn this paper we present a new practical camera characterization technique to improve color accuracy in high dynamic range (HDR) imaging. Camera characterization refers to the process of mapping device-dependent signals, such as digital camera RAW images, into a well-defined color space. This is a well-understood process for low dynamic range (LDR) imaging and is part of most digital cameras — usually mapping from the raw camera signal to the sRGB or Adobe RGB color space. This paper presents an efficient and accurate characterization method for high dynamic range imaging that extends previous methods originally designed for LDR imaging. We demonstrate that our characterization method is very accurate even in unknown illumination conditions, effectively turning a digital camera into a measurement device that measures physically accurate radiance values — both in terms of luminance and color — rivaling more expensive measurement instruments
