Related Experiment Video
Updated: Feb 25, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
36.2K
The combinatorics of discrete time-trees: theory and open problems
Alex Gavryushkin1, Chris Whidden2, Frederick A Matsen2
1Department of Biosystems Science and Engineering, ETH Zürich, 4058, Basel, Switzerland. alex@gavruskin.com.
Journal of Mathematical Biology
|July 31, 2017
Summary
This study introduces a new hierarchy of discrete approximations for time-trees, which are rooted phylogenetic trees with divergence and sampling dates. The research explores graph-theoretic properties, enabling efficient exploration and construction of these complex evolutionary models.
Area of Science:
- Computational Biology
- Phylogenetics
- Graph Theory
Background:
- Time-trees, rooted phylogenetic trees with divergence and sampling dates, are crucial in phylogenetics.
- The parameter space of time-trees remains largely unexplored, hindering computational analysis.
- Existing phylogenetic graph models offer limited resolution for temporal evolutionary data.
Purpose of the Study:
- To introduce and analyze a hierarchy of discrete approximations for the space of time-trees.
- To investigate graph-theoretic properties of these time-tree approximations, including neighborhood sizes and diameters.
- To develop efficient algorithmic methods for exploring and constructing time-tree graphs.
Main Methods:
- Development of a hierarchy of discrete time-tree approximations.
- Application of graph-theoretic concepts, including graph grammars, to analyze these approximations.
- Computation of neighborhood sizes, diameter bounds, and shortest path algorithms.
Main Results:
- Demonstrated that 1-neighborhood sizes remain linear, facilitating efficient local exploration and construction.
- Established upper bounds for r-neighborhood sizes, improving upon previous results for specific graph types.
- Extended graph grammar concepts to analyze the structure and properties of time-tree graphs.
Conclusions:
- The proposed hierarchy provides a tractable framework for studying the graph-theoretic and algorithmic properties of time-trees.
- Efficient algorithms for time-tree graph exploration and construction are now possible.
- Future research directions include exploring the applicability of the split theorem to shortest paths in time-tree graphs.
Related Concept Videos
01:19Survival Tree
449
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...
449
01:24BIBO stability of continuous and discrete -time systems
967
System stability is a fundamental concept in signal processing, often assessed using convolution. For a system to be considered bounded-input bounded-output (BIBO) stable, any bounded input signal must produce a bounded output signal. A bounded input signal is one where the modulus does not exceed a certain constant at any point in time.
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
967
01:12Theorems of Pappus and Guldinus: Problem Solving
1.1K
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
1.1K
01:15Thevinin's Theorem
1.6K
Thévenin's theorem plays a pivotal role in electrical circuit analysis, offering a solution to the challenges posed by variable loads within a circuit. In practical applications, it is common to encounter circuits where certain elements remain fixed while others fluctuate, often referred to as the "load." A typical household electrical outlet serves as a prime example of a variable load, as it can be connected to a variety of appliances, each with its own unique electrical characteristics.
1.6K
01:16Basic Discrete Time Signals
768
The unit step sequence is defined as 1 for zero and positive values of the integer n. This sequence can be graphically displayed using a set of eight sample points, showing a step function starting from n=0 and remaining constant thereafter.
The unit impulse or sample sequence is mathematically expressed as zero for all n values except at n=0, where it is one. The unit impulse sequence, denoted by δ(n), is the first difference of the unit step sequence, while the unit step sequence u(n) is the...
The unit impulse or sample sequence is mathematically expressed as zero for all n values except at n=0, where it is one. The unit impulse sequence, denoted by δ(n), is the first difference of the unit step sequence, while the unit step sequence u(n) is the...
768
01:14Castigliano's Theorem: Problem Solving
1.3K
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam is...
1.3K