Abstract
Phylogenetic trees correspond one-to-one to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetic algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4.
Keywords
Phylogenetic treeTree (set theory)Computer scienceSet (abstract data type)SupertreeGraphTheoretical computer scienceClosure (psychology)MathematicsPhylogenetic networkAlgorithmCombinatoricsBiology
Affiliated Institutions
Related Publications
IQPNNI: Moving Fast Through Tree Space and Stopping in Time
An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast al...
Graph rigidity and distributed formation stabilization of multi-vehicle systems
We provide a graph theoretical framework that allows us to formally define formations of multiple vehicles and the issues arising in uniqueness of graph realizations and its con...
Success of Phylogenetic Methods in the Four-Taxon Case
The success of 16 methods of phylogenetic inference was examined using consistency and simulation analysis. Success—the frequency with which a tree-making method correctly ident...
Numerical operator calculus in higher dimensions
When an algorithm in dimension one is extended to dimension d , in nearly every case its computational cost is taken to the power d . This fundamental difficulty is the single g...
Terrace Aware Data Structure for Phylogenomic Inference from Supermatrices
In phylogenomics the analysis of concatenated gene alignments, the so-called supermatrix, is commonly accompanied by the assumption of partition models. Under such models each g...
Publication Info
- Year
- 2004
- Type
- article
- Volume
- 1
- Issue
- 3
- Pages
- 109-115
- Citations
- 154
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
154
OpenAlex
Cite This
Andreas Dress,
Daniel H. Huson
(2004).
Constructing splits graphs.
IEEE/ACM Transactions on Computational Biology and Bioinformatics
, 1
(3)
, 109-115.
https://doi.org/10.1109/tcbb.2004.27
Identifiers
- DOI
- 10.1109/tcbb.2004.27