Related Experiment Video
Updated: Jul 9, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
A decomposition theory for phylogenetic networks and incompatible characters
Dan Gusfield1, Vikas Bansal, Vineet Bafna
1Department of Computer Science, University of California, Davis, CA 95616, USA. gusfield@cs.ucdavis.edu
Summary
Phylogenetic networks model evolution beyond trees, incorporating events like recombination. This study disproves a conjecture about minimizing recombination nodes in phylogenetic networks, showing counterexamples exist but are rare in simulated data.
Area of Science:
- Computational Biology
- Evolutionary Biology
- Graph Theory
Background:
- Phylogenetic networks model evolutionary history, including non-tree-like events like recombination and reticulation.
- Algorithmic challenges involve reconstructing evolutionary histories and minimizing reticulation events from sequence data.
- Conflict graphs and incompatibility graphs are used to analyze these evolutionary models.
Purpose of the Study:
- To further develop the structural importance of non-trivial connected components in incompatibility and conflict graphs for phylogenetic networks.
- To prove a general decomposition theorem for phylogenetic networks based on sequence incompatibilities.
- To investigate and resolve the open question regarding the existence of a fully decomposed phylogenetic network that minimizes recombination nodes.
Main Methods:
- Proving a general decomposition theorem for phylogenetic networks using incompatibility data.
- Developing a polynomial-time algorithm to identify the maximal embedded tree structure within a network.
- Analyzing the conjecture on minimizing recombination nodes through theoretical investigation and simulation.
Main Results:
- A general decomposition theorem for phylogenetic networks is proven, applicable to various reticulation events.
- A maximal embedded tree structure is identified within networks when perfect phylogeny is not possible.
- The conjecture that a fully decomposed network always minimizes recombination nodes is disproved for both single and multiple crossover recombination.
Conclusions:
- The study advances the theory of phylogenetic networks by providing a decomposition theorem and identifying maximal embedded tree structures.
- While the conjecture on minimizing recombination nodes is generally false, it holds true in specific cases.
- Counterexamples to the conjecture are shown to be rare in simulated data, particularly for single-crossover recombination.
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,...
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...
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...
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...