Related Experiment Videos
Reconstructing gene trees from Fitch's xenology relation.
Manuela Geiß1,2, John Anders1,2, Peter F Stadler1,2,3,4,5,6,7,8
1Bioinformatics Group, Department of Computer Science, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany.
Journal of Mathematical Biology
|June 29, 2018
Summary
Xenology, defined by horizontal gene transfer, is a non-symmetric gene relationship. This study identifies forbidden subgraphs characterizing xenology and provides a linear-time algorithm for phylogenetic tree construction.
Area of Science:
- Genomics
- Bioinformatics
- Evolutionary Biology
Background:
- Horizontal gene transfer (HGT) complicates evolutionary relationships between genes.
- Xenology, as defined by Fitch, specifically addresses genes separated by HGT events.
- The asymmetric nature of HGT necessitates a non-symmetric definition of xenology.
Purpose of the Study:
- To formally characterize xenology relations using graph theory.
- To develop an efficient algorithm for identifying xenology and reconstructing phylogenetic trees.
- To explore the implications of xenology being a heritable graph property.
Main Methods:
- Graph theory, specifically identifying forbidden induced subgraphs.
- Developing a linear-time algorithm for xenology recognition.
- Constructing least-resolved edge-labeled phylogenetic trees.
Main Results:
- Xenology relations are precisely characterized by a small set of forbidden induced subgraphs.
- Each xenology relation corresponds to a unique least-resolved edge-labeled phylogenetic tree.
- A linear-time algorithm for xenology recognition and tree construction is presented.
Conclusions:
- The characterization of xenology via forbidden subgraphs provides a robust framework.
- The developed algorithm offers efficient computational tools for evolutionary analysis.
- The heritable nature of xenology has significant implications for approximation algorithms in phylogenetics.