Who is Who in Phylogenetic Networks

Publication no #575   Type :   Html | Bib | Both

Created: 2007-11-22 18:40:55     Modified: 2010-09-17 18:39:29

575 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved." @Article{BrandesCornelsen2009,       AUTHOR = {Brandes, Ulrik and Cornelsen, Sabine},       TITLE = {Phylogenetic Graph Models Beyond Trees},       YEAR = {2009},       JOURNAL = {DAM},       VOLUME = {157},       NUMBER = {10},       PAGES = {2361-2369},       URL = {http://dx.doi.org/10.1016/j.dam.2008.06.031},       NOTE = {http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf},       KEYWORDS = {abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction} }