Related Experiment Video
Updated: Jun 30, 2025
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
35.3K
Enumeration of Rooted Binary Unlabeled Galled Trees.
Lily Agranat-Tamir1, Shaili Mathur2, Noah A Rosenberg2
1Department of Biology, Stanford University, Stanford, CA, 94305, USA. lilyat@stanford.edu.
Bulletin of Mathematical Biology
|March 23, 2024
Summary
Rooted binary galled trees, which allow cycles called galls, are enumerated. Their numbers grow faster than standard binary trees, with single-gall trees showing similar exponential growth.
Area of Science:
- Combinatorics
- Graph Theory
- Mathematical Phylogenetics
Background:
- Rooted binary trees are fundamental in combinatorics.
- Wedderburn-Etherington enumeration provides a basis for tree counting.
- Galls introduce cycles into tree structures, generalizing standard trees.
Purpose of the Study:
- To enumerate rooted binary unlabeled galled trees with n leaves.
- To determine the growth rate of galled trees compared to non-galled trees.
- To explore the impact of gall number on tree enumeration.
Main Methods:
- Building upon Wedderburn-Etherington enumeration techniques.
- Utilizing recursive decomposition considering subtrees attached to galls.
- Deriving an implicit expression for the generating function.
Main Results:
- The number of rooted binary galled trees grows faster than non-galled trees.
- Galled trees with a single gall share the same exponential growth order as non-galled trees.
- The optimal number of galls for maximum tree count is intermediate.
Conclusions:
- Rooted binary galled trees offer a richer combinatorial structure than standard binary trees.
- The presence and number of galls significantly influence tree enumeration and growth rates.
- Findings have potential implications for modeling in mathematical phylogenetics.
Related Concept Videos
03:21Phylogenetic Trees
45.3K
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.
45.3K
01:19Survival Tree
84
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...
Building a Survival Tree
Constructing a...
84
02:27Basic Plant Anatomy: Roots, Stems, and Leaves
59.0K
The primary organs of vascular plants are roots, stems, and leaves, but these structures can be highly variable, adapted for the specific needs and environment of different plant species.
59.0K
01:23Phylogeny
44.0K
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.
44.0K
03:40Introduction to Seed Plants
62.0K
Most plants are seed plants—characterized by seeds, pollen, and reduced gametophytes. Seed plants include gymnosperms and angiosperms.
62.0K
02:54Evolutionary Relationships through Genome Comparisons
5.7K
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...
5.7K