Related Experiment Video
Updated: Jun 5, 2026
08:16
Collecting and Processing Drone-based Remotely Sensed Data for Use in Forest Recovery Monitoring
Published on: October 24, 2025
A polynomial-time algorithm computing lower and upper bounds of the rooted subtree prune and regraft distance
Lavanya Kannan1, Hua Li, Arcady Mushegian
1Bioinformatics Center, Stowers Institute for Medical Research, Kansas City, Missouri, USA. lkannan@amnh.org
Summary
We introduce D-Clust, an O(n⁴) algorithm for computing tree distances using rooted subtree prune and regraft (rSPR) operations. It provides near-precise distance measures for phylogenetic analysis and horizontal gene transfer detection.
Area of Science:
- Computational Biology
- Phylogenetics
- Bioinformatics
Background:
- Rooted, leaf-labeled trees model hierarchical biological relationships, crucial for evolutionary history.
- Rooted Subtree Prune and Regraft (rSPR) operations transform trees, with the minimum number indicating tree dissimilarity.
- Computing exact rSPR distance is NP-hard, necessitating heuristic approaches for phylogenetic analysis and horizontal gene transfer detection.
Purpose of the Study:
- To develop an efficient algorithm for calculating tree distances based on rSPR operations.
- To provide both lower and upper bound heuristics for the d(rSPR) distance.
- To generate a sequence of rSPR operations transforming one tree into another.
Main Methods:
- Developed a novel O(n⁴) recursive algorithm named D-Clust.
- The algorithm computes lower and upper bound heuristics for the distance between trees with n shared leaves.
- The algorithm also outputs the sequence of rSPR operations for tree transformation.
Main Results:
- Experiments on simulated trees (up to 100 leaves) show D-Clust's bounds are nearly equal for small distances, approximating the precise value.
- The upper bound provided by D-Clust is comparable to existing heuristic methods across all tested tree pairs.
- The algorithm effectively provides a sequence of rSPR operations for tree interconversion.
Conclusions:
- D-Clust offers an efficient and accurate method for estimating tree dissimilarity using rSPR operations.
- The algorithm aids in phylogenetic analysis and the detection of horizontal gene transfer events.
- D-Clust provides a valuable tool for comparing evolutionary histories represented by tree structures.
Related Concept Videos
01:19Survival Tree
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 survival tree begins...
Building a Survival Tree
Constructing a survival tree begins...
01:30Fundamental Theorem of Algebra
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the Complete Factorization...
01:15Construction of Root Locus
The construction of a root locus involves several key steps to analyze and visualize the behavior of a system's poles with varying gain. The number of branches in the root locus equals the number of closed-loop poles and is symmetrical about the real axis.
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain increases.
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain increases.
01:29Distance Problem
When an object's velocity changes over time, the total distance traveled can be determined by summing small displacement intervals over short increments. This approach approximates the true distance through numerical summation and the use of integral calculus. An estimate of the total displacement can be obtained by measuring velocity at regular intervals and multiplying each value by the corresponding time step.If a runner accelerates over the first three seconds of a race, speed measurements...
01:27Real Zeros of Polynomials
Polynomials are algebraic expressions of terms with variables raised to non-negative integer powers. A central aspect of analyzing polynomial functions is determining their real zeros—values of the variable for which the polynomial evaluates to zero. These values represent the x-intercepts of the polynomial’s graph.The Rational Zeros Theorem lists possible rational solutions for a polynomial equation with integer coefficients. If f(x)=anxn+....+a0, then every rational zero is of the form p/q,...
01:26Long Division of Polynomials
Polynomial division is an essential algebraic process to simplify expressions and solve equations. Just as numerical division separates a number into quotient and remainder, polynomial long division partitions a polynomial into simpler components; in this context, the dividend is the polynomial being divided, the divisor is the expression dividing it, and the result is expressed in terms of a quotient and a remainder.The division begins by arranging the dividend and divisor in standard...