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:BackgroundPosition-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.ResultsWe 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.ConclusionsThe 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:Hyperspectral images include information from a wide range of spectral bands deemed valuable for computer vision applications in various domains such as agriculture, surveillance, and reconnaissance. Anomaly detection in hyperspectral images has proven to be a crucial component of change and abnormality identification, enabling improved decision-making across various applications. These abnormalities/anomalies can be detected using background estimation techniques that do not require the prior knowledge of outliers. However, each hyperspectral anomaly detection (HS-AD) algorithm models the background differently. These different assumptions may fail to consider all the background constraints in various scenarios. We have developed a new approach called Greedy Ensemble Anomaly Detection (GE-AD) to address this shortcoming. It includes a greedy search algorithm to systematically determine the suitable base models from HS-AD algorithms and hyperspectral unmixing for the first stage of a stacking ensemble and employs a supervised classifier in the second stage of a stacking ensemble. It helps researchers with limited knowledge of the suitability of the HS-AD algorithms for the application scenarios to select the best methods automatically. Our evaluation shows that the proposed method achieves a higher average F1-macro score with statistical significance compared to the other individual methods used in the ensemble. This is validated on multiple datasets, including the Airport-Beach-Urban (ABU) dataset, the San Diego dataset, the Salinas dataset, the Hydice Urban dataset, and the Arizona dataset. The evaluation using the airport scenes from the ABU dataset shows that GE-AD achieves a 14.97% higher average F1-macro score than our previous method (HUE-AD), at least 17.19% higher than the individual methods used in the ensemble, and at least 28.53% higher than the other state-of-the-art ensemble anomaly detection algorithms. As using the combination of greedy algorithm and stacking ensemble to automatically select suitable base models and associated weights have not been widely explored in hyperspectral anomaly detection, we believe that our work will expand the knowledge in this research area and contribute to the wider application of this approach.
| S-EPMC11204925 | biostudies-literature
Project description: Not available
| S-EPMC4256650 | biostudies-literature
Project description:Finding the optimal embedding of networks into low-dimensional hyperbolic spaces is a challenge that received considerable interest in recent years, with several different approaches proposed in the literature. In general, these methods take advantage of the exponentially growing volume of the hyperbolic space as a function of the radius from the origin, allowing a (roughly) uniform spatial distribution of the nodes even for scale-free small-world networks, where the connection probability between pairs decays with hyperbolic distance. One of the motivations behind hyperbolic embedding is that optimal placement of the nodes in a hyperbolic space is widely thought to enable efficient navigation on top of the network. According to that, one of the measures that can be used to quantify the quality of different embeddings is given by the fraction of successful greedy paths following a simple navigation protocol based on the hyperbolic coordinates. In the present work, we develop an optimisation scheme for this score in the native disk representation of the hyperbolic space. This optimisation algorithm can be either used as an embedding method alone, or it can be applied to improve this score for embeddings obtained from other methods. According to our tests on synthetic and real networks, the proposed optimisation can considerably enhance the success rate of greedy paths in several cases, improving the given embedding from the point of view of navigability.
| S-EPMC10754836 | biostudies-literature
Project description: Not available
| S-EPMC8302881 | biostudies-literature
Project description: Not available
| S-EPMC8117966 | biostudies-literature
Project description: Not available
| S-EPMC6544187 | 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