Related Experiment Video
Updated: May 9, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Minimizing the average distance to a closest leaf in a phylogenetic tree
Frederick A Matsen1, Aaron Gallagher, Connor O McCoy
1Program in Computational Biology, Fred Hutchinson Cancer Research Center, Seattle, WA 91802, USA.
Systematic Biology
|July 12, 2013
Summary
This study introduces a new method for selecting representative molecular sequence subsets, minimizing Average Distance to the Closest Leaf (ADCL). An exact dynamic programming approach offers superior solutions compared to greedy or Partitioning Around Medoids heuristics.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Selecting representative subsets of molecular sequences is crucial for efficient analysis and comparative studies.
- Existing methods may not effectively capture diversity or accurately represent larger datasets.
Purpose of the Study:
- To formalize sequence subset selection problems using the Average Distance to the Closest Leaf (ADCL) criterion.
- To develop and evaluate algorithms for minimizing ADCL, aiming for representative sequence subsets.
Main Methods:
- Investigated greedy algorithms, finding them ineffective.
- Evaluated a Partitioning Around Medoids (PAM) heuristic, noting its tendency to get stuck in local minima.
- Developed an exact dynamic programming approach for ADCL minimization.
Main Results:
- The greedy algorithm was ineffective.
- PAM heuristic showed good performance on simulated trees but can get stuck in local minima.
- The exact dynamic programming approach provides optimal solutions and is applicable for various subset sizes.
- ADCL criterion selects fewer chimeric sequences than random subsets on real data.
Conclusions:
- An exact dynamic programming algorithm effectively minimizes Average Distance to the Closest Leaf for representative molecular sequence subset selection.
- This approach offers advantages over heuristic methods like PAM, especially in solution optimality and flexibility.
- The developed algorithms, implemented in public software, improve the selection of reference sequences for phylogenetic analysis and reduce chimeric sequence identification.
Related Concept Videos
01:28Microbial Phylogeny
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,...
03:21Phylogenetic 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.
03:21Phylogenetic 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.
02:54Evolutionary 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...
02:05Gene Evolution - Fast or Slow?
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...
02:05Gene Evolution - Fast or Slow?
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...