Beware greedy algorithms.
Ontology highlight
ABSTRACT:
SUBMITTER: Simmons BI
PROVIDER: S-EPMC6850377 | biostudies-literature | 2019 May
REPOSITORIES: biostudies-literature
Publications
Beware greedy algorithms.
Simmons Benno I BI Hoeppke Christoph C Sutherland William J WJ
The Journal of animal ecology 20190315 5
To fairly compare the nestedness of ecological networks, a network's observed nestedness can be divided by its maximum nestedness. The authors show that a greedy algorithm does not find networks' maximum nestedness values. Simulated annealing achieved much better results, laying the foundation for future development of even more sophisticated algorithms. ...[more]
Similar Datasets
Project description:This work proposes a family of greedy algorithms to jointly reconstruct a set of vectors that are (i) nonnegative and (ii) simultaneously sparse with a shared support set. The proposed algorithms generalize previous approaches that were designed to impose these constraints individually. Similar to previous greedy algorithms for sparse recovery, the proposed algorithms iteratively identify promising support indices. In contrast to previous approaches, the support index selection procedure has been adapted to prioritize indices that are consistent with both the nonnegativity and shared support constraints. Empirical results demonstrate for the first time that the combined use of simultaneous sparsity and nonnegativity constraints can substantially improve recovery performance relative to existing greedy algorithms that impose less signal structure.
| S-EPMC4784713 | biostudies-literature
Project description:BACKGROUND:Position-specific priors (PSP) have been used with success to boost EM and Gibbs sampler-based motif discovery algorithms. PSP information has been computed from different sources, including orthologous conservation, DNA duplex stability, and nucleosome positioning. The use of prior information has not yet been used in the context of combinatorial algorithms. Moreover, priors have been used only independently, and the gain of combining priors from different sources has not yet been studied. RESULTS:We extend RISOTTO, a combinatorial algorithm for motif discovery, by post-processing its output with a greedy procedure that uses prior information. PSP's from different sources are combined into a scoring criterion that guides the greedy search procedure. The resulting method, called GRISOTTO, was evaluated over 156 yeast TF ChIP-chip sequence-sets commonly used to benchmark prior-based motif discovery algorithms. Results show that GRISOTTO is at least as accurate as other twelve state-of-the-art approaches for the same task, even without combining priors. Furthermore, by considering combined priors, GRISOTTO is considerably more accurate than the state-of-the-art approaches for the same task. We also show that PSP's improve GRISOTTO ability to retrieve motifs from mouse ChiP-seq data, indicating that the proposed algorithm can be applied to data from a different technology and for a higher eukaryote. CONCLUSIONS:The conclusions of this work are twofold. First, post-processing the output of combinatorial algorithms by incorporating prior information leads to a very efficient and effective motif discovery method. Second, combining priors from different sources is even more beneficial than considering them separately.
| S-EPMC3112114 | biostudies-literature
Project description:BACKGROUND:With modern methods in biotechnology, the search for biomarkers has advanced to a challenging statistical task exploring high dimensional data sets. Feature selection is a widely researched preprocessing step to handle huge numbers of biomarker candidates and has special importance for the analysis of biomedical data. Such data sets often include many input features not related to the diagnostic or therapeutic target variable. A less researched, but also relevant aspect for medical applications are costs of different biomarker candidates. These costs are often financial costs, but can also refer to other aspects, for example the decision between a painful biopsy marker and a simple urine test. In this paper, we propose extensions to two feature selection methods to control the total amount of such costs: greedy forward selection and genetic algorithms. In comprehensive simulation studies of binary classification tasks, we compare the predictive performance, the run-time and the detection rate of relevant features for the new proposed methods and five baseline alternatives to handle budget constraints. RESULTS:In simulations with a predefined budget constraint, our proposed methods outperform the baseline alternatives, with just minor differences between them. Only in the scenario without an actual budget constraint, our adapted greedy forward selection approach showed a clear drop in performance compared to the other methods. However, introducing a hyperparameter to adapt the benefit-cost trade-off in this method could overcome this weakness. CONCLUSIONS:In feature cost scenarios, where a total budget has to be met, common feature selection algorithms are often not suitable to identify well performing subsets for a modelling task. Adaptations of these algorithms such as the ones proposed in this paper can help to tackle this problem.
| S-EPMC6986087 | biostudies-literature
Project description: Not available
| S-EPMC8302881 | biostudies-literature
Project description: Not available
| S-EPMC8117966 | biostudies-literature
Project description:BackgroundFusobacterium nucleatum (F. n) is an important opportunistic pathogen causing oral and gastrointestinal disease. Faecalibacterium prausnitzii (F. p) is a next-generation probiotic and could serve as a biomarker of gut eubiosis/dysbiosis to some extent. Alterations in the human oral and gut microbiomes are associated with viral respiratory infection. The aim of this study was to characterise the oral and fecal bacterial biomarker (i.e., F. n and F. p) in COVID-19 patients by qPCR and investigate the pharyngeal microbiome of COVID-19 patients through metagenomic next-generation sequencing (mNGS).ResultsPharyngeal F. n was significantly increased in COVID-19 patients, and it was higher in male than female patients. Increased abundance of pharyngeal F. n was associated with a higher risk of a positive SARS-CoV-2 test (adjusted OR = 1.32, 95% CI = 1.06 ~ 1.65, P < 0.05). A classifier to distinguish COVID-19 patients from the healthy controls based on the pharyngeal F. n was constructed and achieved an area under the curve (AUC) of 0.843 (95% CI = 0.688 ~ 0.940, P < 0.001). However, the level of fecal F. n and fecal F. p remained unaltered between groups. Besides, mNGS showed that the pharyngeal swabs of COVID-19 patients were dominated by opportunistic pathogens.ConclusionsPharyngeal but not fecal F. n was significantly increased in COVID-19 patients, clinicians should pay careful attention to potential coinfection. Pharyngeal F. n may serve as a promising candidate indicator for COVID-19.
| S-EPMC8504566 | biostudies-literature
Project description:Supertree methods combine a set of phylogenetic trees into a single supertree. Similar to supermatrix methods, these methods provide a way to reconstruct larger parts of the Tree of Life, potentially evading the computational complexity of phylogenetic inference methods such as maximum likelihood. The supertree problem can be formalized in different ways, to cope with contradictory information in the input. Many supertree methods have been developed. Some of them solve NP-hard optimization problems like the well-known Matrix Representation with Parsimony, while others have polynomial worst-case running time but work in a greedy fashion (FlipCut). Both can profit from a set of clades that are already known to be part of the supertree. The Superfine approach shows how the Greedy Strict Consensus Merger (GSCM) can be used as preprocessing to find these clades. We introduce different scoring functions for the GSCM, a randomization, as well as a combination thereof to improve the GSCM to find more clades. This helps, in turn, to improve the resolution of the GSCM supertree. We find this modifications to increase the number of true positive clades by 18% compared to the currently used Overlap scoring.
| S-EPMC4928488 | biostudies-literature
Project description:OBJECTIVE:Because it is impossible to know which statistical learning algorithm performs best on a prediction task, it is common to use stacking methods to ensemble individual learners into a more powerful single learner. Stacking algorithms are usually based on linear models, which may run into problems, especially when predictions are highly correlated. In this study, we develop a greedy algorithm for model stacking that overcomes this issue while still being very fast and easy to interpret. We evaluate our greedy algorithm on 7 different data sets from various biomedical disciplines and compare it to linear stacking, genetic algorithm stacking and a brute force approach in different prediction settings. We further apply this algorithm on a task to optimize the weighting of the single domains (e.g., income, education) that build the German Index of Multiple Deprivation (GIMD) to be highly correlated with mortality. RESULTS:The greedy stacking algorithm provides good ensemble weights and outperforms the linear stacker in many tasks. Still, the brute force approach is slightly superior, but is computationally expensive. The greedy weighting algorithm has a variety of possible applications and is fast and efficient. A python implementation is provided.
| S-EPMC7017540 | biostudies-literature
Project description:We propose a subgroup identification approach for inferring optimal and interpretable personalized treatment rules with high-dimensional covariates. Our approach is based on a two-step greedy tree algorithm to pursue signals in a high-dimensional space. In the first step, we transform the treatment selection problem into a weighted classification problem that can utilize tree-based methods. In the second step, we adopt a newly proposed tree-based method, known as reinforcement learning trees, to detect features involved in the optimal treatment rules and to construct binary splitting rules. The method is further extended to right censored survival data by using the accelerated failure time model and introducing double weighting to the classification trees. The performance of the proposed method is demonstrated via simulation studies, as well as analyses of the Cancer Cell Line Encyclopedia (CCLE) data and the Tamoxifen breast cancer data.
| S-EPMC5378692 | biostudies-literature
Project description:A genome sequence assembly represents a model of a genome. This article explores some tools and methods for assessing the quality of an assembly, using publicly available data for Streptomyces species as the example. There is great variability in quality of assemblies deposited in GenBank. Only in a small minority of these assemblies are the raw data available, enabling full appraisal of the assembly quality.
| S-EPMC4720414 | biostudies-literature