作者：
Benati, SUniv Trent
Dipartimento Informat Studi Aziendali I-38100 Trent Italy
Recent advances in risk theory identify risk as a measure related to the tail of a probability distribution function, since it represents the "worst" outcomes of the random variable. Measures like value-at-r...
详细信息
Recent advances in risk theory identify risk as a measure related to the tail of a probability distribution function, since it represents the "worst" outcomes of the random variable. Measures like value-at-risk (VaR), conditional VaR, expected shortfall and so on have become familiar operational tools for many financial applications. In this paper, one of these measures, the worst conditional expectation with threshold alpha of a discrete random variable Z, shortly WCEalpha(Z), is considered. It has been found that its computation can be formulated as a fractional integer programming problem with a single linear constraint, but its complexity is NP-hard, therefore it must be solved by implicit enumeration. Due to its similarity with the knapsack problem, it has been found that a good upper bound and a sharp data structure allow the implementation of a branch&bound that is able to solve realistic size problems in less than one hundredth of a second. (C) 2003 Elsevier B.V. All rights reserved.
We present an equivalent value function reformulation for a class of single-ratio fractionalinteger Programs (FIPs) with stochastic right-hand sides and propose a two-phase solution approach. The first phase construc...
详细信息
We present an equivalent value function reformulation for a class of single-ratio fractionalinteger Programs (FIPs) with stochastic right-hand sides and propose a two-phase solution approach. The first phase constructs the value functions of FIPs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of the value functions of FIPs and utilize them in our algorithms. We show that in certain cases our approach can solve instanceswhose extensive forms have the same order ofmagnitude as the largest stochastic quadratic integer programs solved in the literature.
Background With a growing amount of (multi-)omics data being available, the extraction of knowledge from these datasets is still a difficult problem. Classical enrichment-style analyses require predefined pathways or ...
详细信息
Background With a growing amount of (multi-)omics data being available, the extraction of knowledge from these datasets is still a difficult problem. Classical enrichment-style analyses require predefined pathways or gene sets that are tested for significant deregulation to assess whether the pathway is functionally involved in the biological process under study. De novo identification of these pathways can reduce the bias inherent in predefined pathways or gene sets. At the same time, the definition and efficient identification of these pathways de novo from large biological networks is a challenging problem. Results We present a novel algorithm, DeRegNet, for the identification of maximally deregulated subnetworks on directed graphs based on deregulation scores derived from (multi-)omics data. DeRegNet can be interpreted as maximum likelihood estimation given a certain probabilistic model for de-novo subgraph identification. We use fractional integer programming to solve the resulting combinatorial optimization problem. We can show that the approach outperforms related algorithms on simulated data with known ground truths. On a publicly available liver cancer dataset we can show that DeRegNet can identify biologically meaningful subgraphs suitable for patient stratification. DeRegNet can also be used to find explicitly multi-omics subgraphs which we demonstrate by presenting subgraphs with consistent methylation-transcription patterns. DeRegNet is freely available as open-source software. Conclusion The proposed algorithmic framework and its available implementation can serve as a valuable heuristic hypothesis generation tool contextualizing omics data within biomolecular networks.
暂无评论