Title :
Constructing splits graphs
Author :
Dress, Andreas W M ; Huson, Daniel H.
Author_Institution :
Max-Planck-lnstitutc for Mathematics in the Sci., Leipzig, Germany
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 :
biology computing; evolution (biological); genetics; trees (mathematics); Neighbor-Net; SplitsTree4; Z-closure method; consensus networks; phylogenetic trees; split decomposition; splits graphs; tree reconstruction; Computer networks; Concrete; Data visualization; Phylogeny; Reconstruction algorithms; Runtime; Software algorithms; Tree graphs; Index Terms- Phylogenetic networks; graph drawing.; splits graphs; Algorithms; Computational Biology; Evolution, Molecular; Models, Genetic; Phylogeny; Software;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2004.27