Browse
Submit Data
Databases
API
Help

Dataset Information

10 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

On the approximability of the fixed-tree balanced minimum evolution problem.

ABSTRACT: The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret's proof of the NP -hardness of the BMEP suffice to prove the general NP -hardness of the FT-BMEP as well as its strong inapproximability.

SUBMITTER: Frohn M

PROVIDER: S-EPMC7778423 | biostudies-literature | 2021 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

On the approximability of the fixed-tree balanced minimum evolution problem.

Frohn Martin M

Optimization letters 20210102 6

The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret's proof of the NP -hardness of the BMEP suffice to prove the g ...[more]

PMID: 33425038

Similar Datasets

Addressing the "minimum parking" problem for on-demand mobility.

Project description:Parking infrastructure is pervasive and occupies large swaths of land in cities. However, on-demand (OD) mobility has started reducing parking needs in urban areas around the world. This trend is expected to grow significantly with the advent of autonomous driving, which might render on-demand mobility predominant. Recent studies have started looking at expected parking reductions with on-demand mobility, but a systematic framework is still lacking. In this paper, we apply a data-driven methodology based on shareability networks to address what we call the "minimum parking" problem: what is the minimum parking infrastructure needed in a city for given on-demand mobility needs? While solving the problem, we also identify a critical tradeoff between two public policy goals: less parking means increased vehicle travel from deadheading between trips. By applying our methodology to the city of Singapore we discover that parking infrastructure reduction of up to 86% is possible, but at the expense of a 24% increase in traffic measured as vehicle kilometers travelled (VKT). However, a more modest 57% reduction in parking is achievable with only a 1.3% increase in VKT. We find that the tradeoff between parking and traffic obeys an inverse exponential law which is invariant with the size of the vehicle fleet. Finally, we analyze parking requirements due to passenger pick-ups and show that increasing convenience produces a substantial increase in parking for passenger pickup/dropoff. The above findings can inform policy-makers, mobility operators, and society at large on the tradeoffs required in the transition towards pervasive on-demand mobility.

| S-EPMC7544901 | biostudies-literature

Minimum spanning tree analysis of the human connectome.

Project description:One of the challenges of brain network analysis is to directly compare network organization between subjects, irrespective of the number or strength of connections. In this study, we used minimum spanning tree (MST; a unique, acyclic subnetwork with a fixed number of connections) analysis to characterize the human brain network to create an empirical reference network. Such a reference network could be used as a null model of connections that form the backbone structure of the human brain. We analyzed the MST in three diffusion-weighted imaging datasets of healthy adults. The MST of the group mean connectivity matrix was used as the empirical null-model. The MST of individual subjects matched this reference MST for a mean 58%-88% of connections, depending on the analysis pipeline. Hub nodes in the MST matched with previously reported locations of hub regions, including the so-called rich club nodes (a subset of high-degree, highly interconnected nodes). Although most brain network studies have focused primarily on cortical connections, cortical-subcortical connections were consistently present in the MST across subjects. Brain network efficiency was higher when these connections were included in the analysis, suggesting that these tracts may be utilized as the major neural communication routes. Finally, we confirmed that MST characteristics index the effects of brain aging. We conclude that the MST provides an elegant and straightforward approach to analyze structural brain networks, and to test network topological features of individual subjects in comparison to empirical null models.

| S-EPMC5969238 | biostudies-literature

Complexity of the simplest species tree problem.

Project description:The multispecies coalescent model provides a natural framework for species tree estimation accounting for gene-tree conflicts. Although a number of species tree methods under the multispecies coalescent have been suggested and evaluated using simulation, their statistical properties remain poorly understood. Here, we use mathematical analysis aided by computer simulation to examine the identifiability, consistency, and efficiency of different species tree methods in the case of three species and three sequences under the molecular clock. We consider four major species-tree methods including concatenation, two-step, independent-sites maximum likelihood, and maximum likelihood. We develop approximations that predict that the probit transform of the species tree estimation error decreases linearly with the square root of the number of loci. Even in this simplest case, major differences exist among the methods. Full-likelihood methods are considerably more efficient than summary methods such as concatenation and two-step. They also provide estimates of important parameters such as species divergence times and ancestral population sizes,whereas these parameters are not identifiable by summary methods. Our results highlight the need to improve the statistical efficiency of summary methods and the computational efficiency of full likelihood methods of species tree estimation.

| S-EPMC8382899 | biostudies-literature

An Integer Programming Formulation of the Minimum Common String Partition Problem.

Project description:We consider the problem of finding a minimum common string partition (MCSP) of two strings, which is an NP-hard problem. The MCSP problem is closely related to genome comparison and rearrangement, an important field in Computational Biology. In this paper, we map the MCSP problem into a graph applying a prior technique and using this graph, we develop an Integer Linear Programming (ILP) formulation for the problem. We implement the ILP formulation and compare the results with the state-of-the-art algorithms from the literature. The experimental results are found to be promising.

| S-EPMC4489654 | biostudies-literature

Towards a balanced view of the bacterial tree of life.

Project description:The bacterial tree of life has recently undergone significant expansion, chiefly from candidate phyla retrieved through genome-resolved metagenomics. Bypassing the need for genome availability, we present a snapshot of bacterial phylogenetic diversity based on the recovery of high-quality SSU rRNA gene sequences extracted from nearly 7000 metagenomes and all available reference genomes. We illuminate taxonomic richness within established bacterial phyla together with environmental distribution patterns, providing a revised framework for future phylogeny-driven sequencing efforts.

| S-EPMC5644168 | biostudies-literature

Dynamic minimum set problem for reserve design: Heuristic solutions for large problems.

Project description:Conversion of wild habitats to human dominated landscape is a major cause of biodiversity loss. An approach to mitigate the impact of habitat loss consists of designating reserves where habitat is preserved and managed. Determining the most valuable areas to preserve in a landscape is called the reserve design problem. There exists several possible formulations of the reserve design problem, depending on the objectives and the constraints. In this article, we considered the dynamic problem of designing a reserve that contains a desired area of several key habitats. The dynamic case implies that the reserve cannot be designed in one time step, due to budget constraints, and that habitats can be lost before they are reserved, due for example to climate change or human development. We proposed two heuristics strategies that can be used to select sites to reserve each year for large reserve design problem. The first heuristic is a combination of the Marxan and site-ordering algorithms and the second heuristic is an augmented version of the common naive myopic heuristic. We evaluated the strategies on several simulated examples and showed that the augmented greedy heuristic is particularly interesting when some of the habitats to protect are particularly threatened and/or the compactness of the network is accounted for.

| S-EPMC5854297 | biostudies-literature

A Strategy for Problem Solving of Filling Imbalance in Geometrically Balanced Injection Molds.

Project description:Simulation and experimental studies were performed on filling imbalance in geometrically balanced injection molds. An original strategy for problem solving was developed to optimize the imbalance phenomenon. The phenomenon was studied both by simulation and experimentation using several different runner systems at various thermo-rheological material parameters and process operating conditions. Three optimization procedures were applied, Response Surface Methodology (RSM), Taguchi method, and Artificial Neural Networks (ANN). Operating process parameters: the injection rate, melt temperature, and mold temperature, as well as the geometry of the runner system were optimized. The imbalance of mold filling as well as the process parameters: the injection pressure, injection time, and molding temperature were optimization criteria. It was concluded that all the optimization procedures improved filling imbalance. However, the Artificial Neural Networks approach seems to be the most efficient optimization procedure, and the Brain Construction Algorithm (BSM) is proposed for problem solving of the imbalance phenomenon.

| S-EPMC7240486 | biostudies-literature

Phase unwrapping with a rapid opensource minimum spanning tree algorithm (ROMEO).

Project description:PurposeTo develop a rapid and accurate MRI phase-unwrapping technique for challenging phase topographies encountered at high magnetic fields, around metal implants, or postoperative cavities, which is sufficiently fast to be applied to large-group studies including Quantitative Susceptibility Mapping and functional MRI (with phase-based distortion correction).MethodsThe proposed path-following phase-unwrapping algorithm, ROMEO, estimates the coherence of the signal both in space-using MRI magnitude and phase information-and over time, assuming approximately linear temporal phase evolution. This information is combined to form a quality map that guides the unwrapping along a 3D path through the object using a computationally efficient minimum spanning tree algorithm. ROMEO was tested against the two most commonly used exact phase-unwrapping methods, PRELUDE and BEST PATH, in simulated topographies and at several field strengths: in 3T and 7T in vivo human head images and 9.4T ex vivo rat head images.ResultsROMEO was more reliable than PRELUDE and BEST PATH, yielding unwrapping results with excellent temporal stability for multi-echo or multi-time-point data. It does not require image masking and delivers results within seconds, even in large, highly wrapped multi-echo data sets (eg, 9 seconds for a 7T head data set with 31 echoes and a 208 × 208 × 96 matrix size).ConclusionOverall, ROMEO was both faster and more accurate than PRELUDE and BEST PATH, delivering exact results within seconds, which is well below typical image acquisition times, enabling potential on-console application.

| S-EPMC7821134 | biostudies-literature

Minimum distance quantile regression for spatial autoregressive panel data models with fixed effects.

Project description:This paper considers the quantile regression model with individual fixed effects for spatial panel data. Efficient minimum distance quantile regression estimators based on instrumental variable (IV) method are proposed for parameter estimation. The proposed estimator is computational fast compared with the IV-FEQR estimator proposed by Dai et al. (2020). Asymptotic properties of the proposed estimators are also established. Simulations are conducted to study the performance of the proposed method. Finally, we illustrate our methodologies using a cigarettes demand data set.

| S-EPMC8670681 | biostudies-literature

Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction.

Project description:Phylogenetic trees inferred using commonly-used models of sequence evolution are unrooted, but the root position matters both for interpretation and downstream applications. This issue has been long recognized; however, whether the potential for discordance between the species tree and gene trees impacts methods of rooting a phylogenetic tree has not been extensively studied. In this paper, we introduce a new method of rooting a tree based on its branch length distribution; our method, which minimizes the variance of root to tip distances, is inspired by the traditional midpoint rerooting and is justified when deviations from the strict molecular clock are random. Like midpoint rerooting, the method can be implemented in a linear time algorithm. In extensive simulations that consider discordance between gene trees and the species tree, we show that the new method is more accurate than midpoint rerooting, but its relative accuracy compared to using outgroups to root gene trees depends on the size of the dataset and levels of deviations from the strict clock. We show high levels of error for all methods of rooting estimated gene trees due to factors that include effects of gene tree discordance, deviations from the clock, and gene tree estimation error. Our simulations, however, did not reveal significant differences between two equivalent methods for species tree estimation that use rooted and unrooted input, namely, STAR and NJst. Nevertheless, our results point to limitations of existing scalable rooting methods.

| S-EPMC5553649 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data