Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Survival Tree01:19

Survival Tree

245
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
 Building a Survival Tree
Constructing a...
245
Optimal Foraging00:48

Optimal Foraging

12.9K
How animals obtain and eat their food is called foraging behavior. Foraging can include searching for plants and hunting for prey and depends on the species and environment.
12.9K
Gene Evolution - Fast or Slow?02:05

Gene Evolution - Fast or Slow?

7.7K
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
7.7K
Gene Evolution - Fast or Slow?02:05

Gene Evolution - Fast or Slow?

3.2K
3.2K
Woodward–Hoffmann Selection Rules and Microscopic Reversibility01:34

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

3.5K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.5K
Stability of Equilibrium Configuration: Problem Solving01:13

Stability of Equilibrium Configuration: Problem Solving

797
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
797

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

Newton-type algorithms for inverse optimization: weighted bottleneck Hamming distance and <math><msub><mi>ℓ</mi> <mi>∞</mi></msub></math> -norm objectives.

Optimization letters·2025
Same journal

A necessary condition for the guarantee of the superiorization method.

Optimization letters·2025
Same journal

Strategy investments in zero-sum games.

Optimization letters·2024
Same journal

A unified analysis of convex and non‑convex <math></math>‑ball projection problems.

Optimization letters·2024
Same journal

Multi-objective home health care routing: a variable neighborhood search method.

Optimization letters·2023
Same journal

A link between the steepest descent method and fixed-point iterations.

Optimization letters·2023
See all related articles

Related Experiment Video

Updated: Nov 22, 2025

Daily Transfers, Archiving Populations, and Measuring Fitness in the Long-Term Evolution Experiment with Escherichia coli
15:00

Daily Transfers, Archiving Populations, and Measuring Fitness in the Long-Term Evolution Experiment with Escherichia coli

Published on: August 18, 2023

4.0K

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

Martin Frohn1

  • 1CORE, Université Catholique de Louvain, Voie du Roman Pays 34, 1348 Louvain-la-Neuve, Belgium.

Optimization Letters
|January 11, 2021
PubMed
Summary
This summary is machine-generated.

The Fixed-Tree BMEP (FT-BMEP) problem, concerning taxon assignment to minimize evolutionary distance, is proven to be NP-hard. This resolves a decade-old question and establishes its strong inapproximability.

Keywords:
Computational complexityFixed-tree balanced minimum evolution problemPhylogenetics

More Related Videos

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach
04:35

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach

Published on: July 3, 2020

3.6K
Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.4K

Related Experiment Videos

Last Updated: Nov 22, 2025

Daily Transfers, Archiving Populations, and Measuring Fitness in the Long-Term Evolution Experiment with Escherichia coli
15:00

Daily Transfers, Archiving Populations, and Measuring Fitness in the Long-Term Evolution Experiment with Escherichia coli

Published on: August 18, 2023

4.0K
Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach
04:35

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach

Published on: July 3, 2020

3.6K
Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.4K

Area of Science:

  • Computational Biology
  • Algorithm Analysis
  • Phylogenetics

Background:

  • The Balanced Minimum Evolution Problem (BMEP) is a key challenge in phylogenetics.
  • The Fixed-Tree BMEP (FT-BMEP) is a specific variant of BMEP.
  • The computational complexity of FT-BMEP has remained an open problem for nearly ten years.

Purpose of the Study:

  • To determine the computational complexity of the Fixed-Tree BMEP (FT-BMEP).
  • To establish the hardness and inapproximability of the FT-BMEP.

Main Methods:

  • Adaptation of Fiorini and Joret's proof for BMEP's NP-hardness.
  • Application of modified proof techniques to the FT-BMEP.

Main Results:

  • The Fixed-Tree BMEP (FT-BMEP) is proven to be NP-hard.
  • The FT-BMEP is shown to be strongly inapproximable.
  • This resolves a long-standing open problem in computational phylogenetics.

Conclusions:

  • The computational complexity of FT-BMEP is definitively established.
  • The findings have significant implications for the efficiency of phylogenetic tree reconstruction algorithms.
  • Future research may focus on developing approximation algorithms for FT-BMEP.