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

Phylogenetic Trees03:21

Phylogenetic Trees

Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.The length of the branches can depict time or the relative amount of change among organisms. For instance, the branch length might indicate the number of amino acid changes in the sequence that underlies the...
Phylogenetic Trees03:21

Phylogenetic Trees

Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.The length of the branches can depict time or the relative amount of change among organisms. For instance, the branch length might indicate the number of amino acid changes in the sequence that underlies the...
Survival Tree01:19

Survival 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...
Evolutionary Relationships through Genome Comparisons02:54

Evolutionary Relationships through Genome Comparisons

Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
Distance Problem01:29

Distance 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...
Short-distance Transport of Resources02:12

Short-distance Transport of Resources

Short-distance transport refers to transport that occurs over a distance of just 2-3 cells, crossing the plasma membrane in the process. Small uncharged molecules, such as oxygen, carbon dioxide, and water, can diffuse across the plasma membrane on their own. In contrast, ions and larger molecules require the assistance of transport proteins due to their charge or size. Transport across membranes also occurs within individual cells, playing a variety of essential roles for the plant as a whole.

You might also read

Related Articles

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

Sort by
Same author

The Vertebrate Genomes Project Phase I: A global reference genome resource.

bioRxiv : the preprint server for biology·2026
Same author

The complete genome of the KOLF2.1J reference iPSC line.

bioRxiv : the preprint server for biology·2026
Same author

Complete genomes of a multi-generational pedigree to expand studies of genetic and epigenetic inheritance.

bioRxiv : the preprint server for biology·2025
Same author

Rare Structural Variants Uncovered by Optical Genome Mapping in Multisystem Inflammatory Syndrome in Children (MIS-C).

Advanced genetics (Hoboken, N.J.)·2025
Same author

Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe.

Research square·2025
Same author

Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe.

bioRxiv : the preprint server for biology·2025

Related Experiment Video

Updated: Jun 25, 2026

A Simple Protocol for Mapping the Plant Root System Architecture Traits
11:09

A Simple Protocol for Mapping the Plant Root System Architecture Traits

Published on: February 10, 2023

SPR distance computation for unrooted trees.

Glenn Hickey1, Frank Dehne, Andrew Rau-Chaplin

  • 1School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6. ghickey@scs.carleton.ca

Evolutionary Bioinformatics Online
|February 11, 2009
PubMed
Summary

Calculating subtree prune and regraft (SPR) distance for unrooted phylogenetic trees is NP-Hard. This study introduces an efficient heuristic algorithm that quickly computes exact unrooted SPR distances, aiding lateral gene transfer studies.

Keywords:
SPR distancelateral gene transferphylogenetic tree metricsunrooted trees

More Related Videos

Extracting Metrics for Three-dimensional Root Systems: Volume and Surface Analysis from In-soil X-ray Computed Tomography Data
09:37

Extracting Metrics for Three-dimensional Root Systems: Volume and Surface Analysis from In-soil X-ray Computed Tomography Data

Published on: April 26, 2016

Dendritic Spine Quantification Using an Automatic Three-Dimensional Neuron Reconstruction Software
07:45

Dendritic Spine Quantification Using an Automatic Three-Dimensional Neuron Reconstruction Software

Published on: September 27, 2024

Related Experiment Videos

Last Updated: Jun 25, 2026

A Simple Protocol for Mapping the Plant Root System Architecture Traits
11:09

A Simple Protocol for Mapping the Plant Root System Architecture Traits

Published on: February 10, 2023

Extracting Metrics for Three-dimensional Root Systems: Volume and Surface Analysis from In-soil X-ray Computed Tomography Data
09:37

Extracting Metrics for Three-dimensional Root Systems: Volume and Surface Analysis from In-soil X-ray Computed Tomography Data

Published on: April 26, 2016

Dendritic Spine Quantification Using an Automatic Three-Dimensional Neuron Reconstruction Software
07:45

Dendritic Spine Quantification Using an Automatic Three-Dimensional Neuron Reconstruction Software

Published on: September 27, 2024

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Bioinformatics

Background:

  • Subtree prune and regraft (SPR) distance is crucial for comparing phylogenetic tree topologies and measuring lateral gene transfer (LGT).
  • While rooted SPR distances are well-studied, unrooted SPR distances, common in unresolved phylogenies, remain less understood.
  • Unrooted SPR distance computation is known to be NP-Hard, posing significant computational challenges.

Purpose of the Study:

  • To investigate the computational complexity of unrooted subtree prune and regraft (SPR) distance.
  • To develop an efficient heuristic algorithm for computing unrooted SPR distances.
  • To evaluate the algorithm's performance on synthetic and real-world datasets, particularly for lateral gene transfer (LGT) analysis.

Main Methods:

  • Demonstrated the NP-Hard nature of unrooted SPR distance computation.
  • Adapted and evaluated existing techniques for rooted trees in the context of unrooted trees.
  • Developed and implemented a heuristic algorithm based on a fixed-parameter tractability (FPT) approach.

Main Results:

  • Confirmed that unrooted SPR distance computation is NP-Hard.
  • The proposed heuristic algorithm efficiently computes exact unrooted SPR distances, with running times comparable to FPT algorithms.
  • Successfully applied the algorithm to analyze lateral gene transfer (LGT) in a large dataset of prokaryotic genomes.

Conclusions:

  • The developed heuristic algorithm provides an efficient solution for computing unrooted SPR distances.
  • This method significantly aids in the analysis of phylogenetic relationships and lateral gene transfer (LGT).
  • The algorithm's performance analysis offers insights applicable to related phylogenetic distance measures.