A polynomial algorithm for best-subset selection problem.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhu J
PROVIDER: S-EPMC7777147 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:The last decade of phylogenetics has seen the development of many methods that leverage constraints plus dynamic programming. The goal of this algorithmic technique is to produce a phylogeny that is optimal with respect to some objective function and that lies within a constrained version of tree space. The popular species tree estimation method ASTRAL, for example, returns a tree that (1) maximizes the quartet score computed with respect to the input gene trees and that (2) draws its branches (bipartitions) from the input constraint set. This technique has yet to be used for parsimony problems where the input are binary characters, sometimes with missing values. Here, we introduce the clade-constrained character parsimony problem and present an algorithm that solves this problem for the Dollo criterion score in [Formula: see text] time, where n is the number of leaves, k is the number of characters, and [Formula: see text] is the set of clades used as constraints. Dollo parsimony, which requires traits/mutations to be gained at most once but allows them to be lost any number of times, is widely used for tumor phylogenetics as well as species phylogenetics, for example analyses of low-homoplasy retroelement insertions across the vertebrate tree of life. This motivated us to implement our algorithm in a software package, called Dollo-CDP, and evaluate its utility for analyzing retroelement insertion presence / absence patterns for bats, birds, toothed whales as well as simulated data. Our results show that Dollo-CDP can improve upon heuristic search from a single starting tree, often recovering a better scoring tree. Moreover, Dollo-CDP scales to data sets with much larger numbers of taxa than branch-and-bound while still having an optimality guarantee, albeit a more restricted one. Lastly, we show that our algorithm for Dollo parsimony can easily be adapted to Camin-Sokal parsimony but not Fitch parsimony.
| S-EPMC10775561 | biostudies-literature
Project description:MotivationIdentifying orthologous genes in multiple genomes is a fundamental task in comparative genomics. Construction of intergenomic symmetrical best matches (SymBets) and joining them into clusters is a popular method of ortholog definition, embodied in several software programs. Despite their wide use, the computational complexity of these programs has not been thoroughly examined.ResultsIn this work, we show that in the standard approach of iteration through all triangles of SymBets, the memory scales with at least the number of these triangles, O(g(3)) (where g = number of genomes), and construction time scales with the iteration through each pair, i.e. O(g(6)). We propose the EdgeSearch algorithm that iterates over edges in the SymBet graph rather than triangles of SymBets, and as a result has a worst-case complexity of only O(g(3)log g). Several optimizations reduce the run-time even further in realistically sparse graphs. In two real-world datasets of genomes from bacteriophages (POGs) and Mollicutes (MOGs), an implementation of the EdgeSearch algorithm runs about an order of magnitude faster than the original algorithm and scales much better with increasing number of genomes, with only minor differences in the final results, and up to 60 times faster than the popular OrthoMCL program with a 90% overlap between the identified groups of orthologs.Availability and implementationC++ source code freely available for download at ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/.Supplementary informationSupplementary materials are available at Bioinformatics online.
| S-EPMC2881409 | biostudies-literature
Project description:Genetic pleiotropy refers to the simultaneous association of a gene with multiple phenotypes. It is widely distributed in the whole genome and can help to understand the common genetic mechanism of diseases or traits. In this study, a multivariate response best-subset selection (MRBSS) model based pleiotropic association analysis method is proposed. Different from the traditional genetic association model, the high-dimensional genotypic data are viewed as response variables while the multiple phenotypic data as predictor variables. Moreover, the response best-subset selection procedure is converted into an 0-1 integer optimization problem by introducing a separation parameter and a tuning parameter. Furthermore, the model parameters are estimated by using the curve search under the modified Bayesian information criterion. Simulation experiments show that the proposed method MRBSS remarkably reduces the computational time, obtains higher statistical power under most of the considered scenarios, and controls the type I error rate at a low level. The application studies in the datasets of maize yield traits and pig lipid traits further verifies the effectiveness.
| S-EPMC10712198 | biostudies-literature
Project description:The Annual Crop Planning (ACP) problem was a recently introduced problem in the literature. This study further expounds on this problem by presenting a new mathematical formulation, which is based on market economic factors. To determine solutions, a new local search metaheuristic algorithm is investigated which is called the enhanced Best Performance Algorithm (eBPA). eBPA's results are compared against two well-known local search metaheuristic algorithms; these include Tabu Search and Simulated Annealing. The results show the potential of the eBPA for continuous optimization problems.
| S-EPMC5549700 | biostudies-other
Project description:Selecting core subsets from plant genotype datasets is important for enhancing cost-effectiveness and to shorten the time required for analyses of genome-wide association studies (GWAS), and genomics-assisted breeding of crop species, etc. Recently, a large number of genetic markers (>100,000 single nucleotide polymorphisms) have been identified from high-density single nucleotide polymorphism (SNP) arrays and next-generation sequencing (NGS) data. However, there is no software available for picking out the efficient and consistent core subset from such a huge dataset. It is necessary to develop software that can extract genetically important samples in a population with coherence. We here present a new program, GenoCore, which can find quickly and efficiently the core subset representing the entire population. We introduce simple measures of coverage and diversity scores, which reflect genotype errors and genetic variations, and can help to select a sample rapidly and accurately for crop genotype dataset. Comparison of our method to other core collection software using example datasets are performed to validate the performance according to genetic distance, diversity, coverage, required system resources, and the number of selected samples. GenoCore selects the smallest, most consistent, and most representative core collection from all samples, using less memory with more efficient scores, and shows greater genetic coverage compared to the other software tested. GenoCore was written in R language, and can be accessed online with an example dataset and test results at https://github.com/lovemun/Genocore.
| S-EPMC5519076 | biostudies-literature
Project description:The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can be applied only to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and interelectronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wave function is propagated on a grid with appropriately short time steps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with 100 qubits.
| S-EPMC2596249 | biostudies-literature
Project description:Since the COVID-19 outbreak has led to drastic changes in the business environment, researchers attempt to introduce new approaches to improve the capability and flexibility of the industries. In this regard, recently, the concept of the viable supply chain, which tried to incorporate the leagile, resiliency, sustainability, and digitalization aspects into the post-pandemic supply chain, has been introduced by researchers. However, the literature shows that there is lack of study that investigated the viable supplier selection problem, as one of the crucial branches of viable supply chain management. Therefore, to cover this gap, the current work aims to develop a decision-making framework to investigated the viable supplier selection problem. In this regard, owing to the crucial role of the oxygen concentrator device during the COVID-19 outbreak, this research selects the mentioned product as a case study. After determining the indicators and alternatives of the research problem, a novel method named goal programming-based fuzzy best–worst method (GP-FBWM) is proposed to compute the indicators’ weights. Then, the potential alternatives are prioritized employing the Fuzzy Vlse Kriterijumsk Optimizacija Kompromisno Resenje method. In general, the main contributions and novelties of the present research are to incorporate the elements of the viability concepts in the supplier selection problem for the medical devices industry and to develop an efficient method GP-FBWM to measure the importance of the criteria. Then, the developed method is implemented and the obtained results are analyzed. Finally, managerial and theoretical implications are provided. Supplementary Information The online version contains supplementary material available at 10.1007/s00500-022-07572-0.
| S-EPMC9638384 | biostudies-literature
Project description:Under the influence of additive white Gaussian noise, sparse representation cannot effectively remove noise associated with the polynomial phase signal (PPS) via most dictionary learning algorithms whose training data come from the noisy signal, such as K-SVD and RLS-DLA. In this paper, we present a novel dictionary learning algorithm based on secondary exponentially weighted moving average (SEWMA) to denoise PPS. In the proposed algorithm, we first estimate the signal-to-noise (SNR) of the PPS to set the optimal rate of a weighted decline using covariance matrix model. Second we use RLS-DLA to train the dictionary. Thirdly, SEWMA is used to refine atoms in the learned dictionary. In this way, the SNR of the reconstructed signal obtained using the proposed algorithm is clearly higher than that of other algorithms, whereas the mean squared error is lower than that of other algorithms. To obtain the optimal denoising performance, the optimal rate of a weighted decline is set based on the estimated SNR. Simulation results show that the proposed method outperforms the K-SVD, RLS-DLA in mean square error and the SNR.
| S-EPMC9392793 | biostudies-literature
Project description:With evidence-based measures, COVID-19 can be effectively controlled by advanced data analysis and prediction. However, while valuable insights are available, there is a shortage of robust and rigorous research on what factors shape COVID-19 transmissions at the city cluster level. Therefore, to bridge the research gap, we adopted a data-driven hierarchical modeling approach to identify the most influential factors in shaping COVID-19 transmissions across different Chinese cities and clusters. The data used in this study are from Chinese officials, and hierarchical modeling conclusions drawn from the analysis are systematic, multifaceted, and comprehensive. To further improve research rigor, the study utilizes SPSS, Python and RStudio to conduct multiple linear regression and polynomial best subset regression (PBSR) analysis for the hierarchical modeling. The regression model utilizes the magnitude of various relative factors in nine Chinese city clusters, including 45 cities at a different level of clusters, to examine these aspects from the city cluster scale, exploring the correlation between various factors of the cities. These initial 12 factors are comprised of 'Urban population ratio', 'Retail sales of consumer goods', 'Number of tourists', 'Tourism Income', 'Ratio of the elderly population (> 60 year old) in this city', 'population density', 'Mobility scale (move in/inbound) during the spring festival', 'Ratio of Population and Health facilities', 'Jobless rate (%)', 'The straight-line distance from original epicenter Wuhan to this city', 'urban per capita GDP', and 'the prevalence of the COVID-19'. The study's results provide rigorously-tested and evidence-based insights on most instrumental factors that shape COVID-19 transmissions across cities and regions in China. Overall, the study findings found that per capita GDP and population mobility rates were the most affected factors in the prevalence of COVID-19 in a city, which could inform health experts and government officials to design and develop evidence-based and effective public health policies that could curb the spread of the COVID-19 pandemic.
| S-EPMC8817036 | biostudies-literature
Project description:The subset sum problem (SSP) is a typical nondeterministic-polynomial-time (NP)-complete problem that is hard to solve efficiently in time with conventional computers. Photons have the unique features of high propagation speed, strong robustness, and low detectable energy level and therefore can be promising candidates to meet the challenge. Here, we present a scalable chip built-in photonic computer to efficiently solve the SSP. We map the problem into a three-dimensional waveguide network through a femtosecond laser direct writing technique. We show that the photons sufficiently dissipate into the networks and search for solutions in parallel. In the case of successive primes, our approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize computations intractable for conventional computers, and suggest the SSP as a good benchmarking platform for the race between photonic and conventional computers on the way toward "photonic supremacy."
| S-EPMC6994215 | biostudies-literature