Related Experiment Video
Updated: Jun 20, 2026
10:23
A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
Published on: July 11, 2025
Species tree inference by minimizing deep coalescences.
1Department of Computer Science, Rice University, Houston, Texas, United States of America.
Plos Computational Biology
|September 15, 2009
Summary
We present two exact methods, integer linear programming and dynamic programming, to accurately infer species trees by minimizing deep coalescences (MDC). These novel solutions are faster and more reliable than previous heuristics for phylogenetic analysis.
Area of Science:
- Phylogenetics and evolutionary biology
- Computational biology and bioinformatics
Background:
- The minimizing deep coalescences (MDC) criterion, proposed by Maddison, optimizes species tree inference from incongruent gene trees due to lineage sorting.
- Existing heuristic search methods for MDC are not guaranteed to find optimal solutions and can be slow.
Purpose of the Study:
- To develop and implement exact solutions for inferring species trees under the MDC criterion.
- To provide guaranteed optimal solutions that minimize deep coalescences.
Main Methods:
- Developed a novel integer linear programming (ILP) formulation for MDC optimization.
- Developed a simple dynamic programming (DP) approach for MDC optimization.
- Applied and tested solutions on yeast, Apicomplexan, and simulated datasets.
Main Results:
- Both ILP and DP solutions guarantee finding the species tree that minimizes deep coalescences.
- The exact solutions are computationally efficient, enabling accurate analysis of genome-scale data.
- MDC criterion provides accurate species tree topology estimates.
- Solutions can identify potential horizontal gene transfer events.
Conclusions:
- The developed exact solutions significantly improve species tree inference accuracy and speed.
- The DP approach offers a tool independent of proprietary software, facilitating broader integration.
- The findings support the utility of MDC for accurate phylogenetic reconstruction and evolutionary event detection.
Related Concept Videos
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.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...
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.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...
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...
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...
01:23Phylogeny
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...
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,...