Transforming phylogenetic networks: Moving beyond tree space

Article, Preprint English OPEN
Huber, Katharina T. ; Moulton, Vincent ; Wu, Taoyang (2016)
  • Related identifiers: doi: 10.1016/j.jtbi.2016.05.030
  • Subject: Mathematics - Combinatorics | Quantitative Biology - Populations and Evolution
    arxiv: Quantitative Biology::Genomics | Quantitative Biology::Quantitative Methods | Quantitative Biology::Populations and Evolution
    acm: ComputingMethodologies_PATTERNRECOGNITION | MathematicsofComputing_DISCRETEMATHEMATICS

Phylogenetic networks are a generalization of phylogenetic trees that are used to represent reticulate evolution. Unrooted phylogenetic networks form a special class of such networks, which naturally generalize unrooted phylogenetic trees. In this paper we define two operations on unrooted phylogenetic networks, one of which is a generalization of the well-known nearest-neighbor interchange (NNI) operation on phylogenetic trees. We show that any unrooted phylogenetic network can be transformed into any other such network using only these operations. This generalizes the well-known fact that any phylogenetic tree can be transformed into any other such tree using only NNI operations. It also allows us to define a generalization of tree space and to define some new metrics on unrooted phylogenetic networks. To prove our main results, we employ some fascinating new connections between phylogenetic networks and cubic graphs that we have recently discovered. Our results should be useful in developing new strategies to search for optimal phylogenetic networks, a topic that has recently generated some interest in the literature, as well as for providing new ways to compare networks.
  • References (32)
    32 references, page 1 of 4

    Allen, B. and M. Steel. 2001. Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics 5:1{15.

    Allman, E. S. and J. A. Rhodes. 2003. Phylogenetic invariants for the general markov model of sequence mutation. Mathematical Biosciences 186:113{144.

    Bandelt, H.-J., P. Forster, B. C. Sykes, and M. B. Richards. 1995. Mitochondrial portraits of human populations using median networks. Genetics 141:743{753.

    Bapteste, E., L. van Iersel, A. Janke, S. Kelchner, S. Kelk, J. McInerney, D. Morrison, L. Nakhleh, M. Steel, L. Stougie, and J. Whit eld. 2013. Networks: expanding evolutionary thinking. Trends in Genetics 29(8):439{441.

    Batagelj, V. 1981. Inductive classes of cubic graphs. Pages 89{101 in Colloquia Mathematics Societatis Janos Bolyai, 37. Finite and In nite Sets, Eger (Hungary). Elsevier Science.

    Billera, L. J., S. P. Holmes, and K. Vogtmann. 2001. Geometry of the space of phylogenetic trees. Advances in Applied Mathematics 27:733{767.

    Brinkmann, G., J. Goedgebeur, and B. D. McKay. 2011. Generation of cubic graphs. Discrete Mathematics and Theoretical Computer Science 13:69{79.

    Brinkmann, G., N. Van Cleemput, and T. Pisanski. 2013. Generation of various classes of trivalent graphs. Theoretical Computer Science 502:16{29.

    Bryant, D. and V. Moulton. 2004. Neighbor-net: an agglomerative method for the construction of phylogenetic networks. Molecular Biology and Evolution 21:255{265.

    Cardona, G., M. Llabres, F. Rossello, and G. Valiente. 2009. Metrics for phylogenetic networks ii: Nodal and triplets metrics. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 6:454{469.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    University of East Anglia digital repository - IRUS-UK 0 6
Share - Bookmark