Related Experiment Videos
Binets: Fundamental Building Blocks for Phylogenetic Networks
Leo van Iersel1, Vincent Moulton2, Eveline de Swart3
1Delft Institute of Applied Mathematics, Delft University of Technology, Delft, The Netherlands. l.j.j.v.iersel@gmail.com.
Bulletin of Mathematical Biology
|April 8, 2017
Summary
This study explores phylogenetic networks, which model organism evolution with reticulate events. Researchers found that simple network components called binets can determine the number of reticulations in a network, aiding evolutionary studies.
Area of Science:
- Computational Biology
- Evolutionary Biology
- Graph Theory
Background:
- Phylogenetic networks generalize evolutionary trees to model reticulate evolution.
- Constructing phylogenetic networks from smaller components like binets (2-leaved networks) is an active research area.
Purpose of the Study:
- To investigate the properties of collections of binets for constructing phylogenetic networks.
- To determine if binets can uniquely identify key network parameters, such as reticulation number.
- To analyze the computational complexity of problems related to binets and phylogenetic networks.
Main Methods:
- Analysis of structural properties of phylogenetic networks, focusing on lowest stable ancestors.
- Investigating the compatibility of collections of level-1 binets with binary networks.
- Algorithmic analysis of decision and optimization problems concerning binets.
Main Results:
- A collection of level-1 binets compatible with a binary network is also compatible with a binary level-1 network.
- Binets do not determine network topology but do determine the number of reticulations.
- Deciding arbitrary binet compatibility is graph isomorphism-hard; level-1 binet compatibility is polynomial-time solvable.
- Finding a network displaying maximum binets is NP-hard, but a 1/3-approximation algorithm exists.
Conclusions:
- Properties of binets offer insights into the structure and construction of phylogenetic networks.
- Algorithmic results provide a foundation for efficient computation related to binet collections.
- This research contributes to developing new methods for inferring evolutionary histories from complex data.