Related Experiment Video
Updated: Mar 20, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
36.3K
On the fixed parameter tractability of agreement-based phylogenetic distances
Magnus Bordewich1, Celine Scornavacca2, Nihan Tokac1
1School of Engineering and Computing Sciences, Durham University, Durham, DH1 3LE, UK.
Journal of Mathematical Biology
|May 26, 2016
Summary
This study introduces a "cluster reduction" rule to efficiently compute phylogenetic tree dissimilarity measures. This new method improves computational time for hybridization number, rooted subtree prune and regraft (rSPR) distance, and tree bisection and reconnection (TBR) distance calculations.
Area of Science:
- Computational Biology
- Phylogenetics
- Algorithm Analysis
Background:
- Phylogenetic trees are crucial for understanding evolutionary relationships.
- Measuring dissimilarity between trees is vital but computationally challenging.
- Existing methods like hybridization number, rSPR, and TBR distances are NP-hard.
Purpose of the Study:
- To develop a more efficient method for computing phylogenetic tree dissimilarity.
- To introduce and analyze the "cluster reduction" rule for TBR distance.
- To improve the fixed-parameter tractability of phylogenetic tree comparison algorithms.
Main Methods:
- Analysis of the "cluster reduction" rule for hybridization number and rSPR distance.
- Introduction and application of the "cluster reduction" rule to TBR distance.
- Transformation of existing algorithms using the cluster reduction rule to improve time complexity.
Main Results:
- The "cluster reduction" rule enhances computational efficiency for phylogenetic tree dissimilarity measures.
- Algorithms utilizing this rule can achieve improved time complexity.
- The new approach offers a more tractable solution for comparing large phylogenetic trees.
Conclusions:
- The "cluster reduction" rule is a valuable tool for accelerating computations in phylogenetics.
- This method significantly improves the efficiency of calculating key phylogenetic tree dissimilarity metrics.
- The findings contribute to more scalable and efficient phylogenetic network analysis.
Related Concept Videos
01:28Microbial Phylogeny
9
Understanding the evolutionary relationships among microorganisms is fundamental to microbial ecology and taxonomy. Phylogenetic trees are essential tools for inferring these relationships, relying primarily on comparative analyses of molecular sequences such as DNA, RNA, or proteins. In microbial studies, these trees typically depict the evolutionary paths of diverse bacterial and archaeal species by mapping genetic differences accumulated over time.Phylogenetic trees are composed of tips,...
9
02:54Evolutionary Relationships through Genome Comparisons
7.2K
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...
7.2K
03:21Phylogenetic Trees
51.6K
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.
51.6K
02:05Gene Evolution - Fast or Slow?
8.3K
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...
In contrast, regions which code...
8.3K
01:23Phylogeny
64.4K
Phylogeny is concerned with the evolutionary diversification of organisms or groups of organisms. A group of organisms with a name is called a taxon (singular). Taxa (plural) can span different levels of the evolutionary hierarchy. For instance, the group containing all birds is a taxon (comprising the class Aves), and the group of all species of daisies (the genus Bellis) is a taxon. Phylogenies can likewise include just one genus (i.e., depict species relationships) or span an entire kingdom.
64.4K
01:22Phylogenetic Species Concept in Microbiology
2
The phylogenetic species concept (PSC) is a framework used to delineate species based on evolutionary relationships, emphasizing shared ancestry and diagnosable genetic traits. Unlike morphological or biological species concepts, the PSC is particularly advantageous for microbial taxonomy, where traditional reproductive or phenotypic criteria often fall short due to the prevalence of asexual reproduction, minimal morphological differentiation, and widespread horizontal gene transfer among...
2