Unicyclic Networks: Compatibility and Enumeration

ABSTRACT

Graphs obtained from a binary leaf labeled ("phylogenetic”) tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call "unicyclic networks”) also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem and a simple, fast algorithm to determine 1{\hbox{-}}{\rm cycle} compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multicyclic networks.

REFERENCES

• 1: [1] M.C. Baroni, "Hybrid Phylogenies: A Graph-Based Approach to Represent Reticulate Evolution," PhD thesis, Univ. of Canterbury, New Zealand, 2004.
• 2: [2] M.C. Baroni, C. Semple, and M. Steel, "A Framework for Representing Reticulate Evolution," Annals of Combinatorics, vol. 8, pp. 391-408, 2004.
• 3: M. Carter , M. Hendy , D. Penny , L. A. Székely , N. C. Wormald, On the distribution of lengths of evolutionary trees, SIAM Journal on Discrete Mathematics, v.3 n.1, p.38-47, Feb. 1990 [doi>10.1137/0403005]
• 4: [4] J. Felsenstein, Inferring Phylogenies. Sinauer Press, 2004.
• 5: Ian P. Goulden , David M. Jackson, Combinatorial Enumeration, Dover Publications, Incorporated, 2004
• 6: [6] D. Gusfield, S. Eddhu, C. Langley, "Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination," J. Bioinformatics and Computational Biology, vol. 2, pp. 173-213, 2004.
• 7: [7] B. Holland, K. Huber, V. Moulton, and P.J. Lockhart, "Using Consensus Networks to Visualize Contradictory Evidence for Species Phylogeny," Soc. Molecular Biology and Evolution, vol. 21, pp. 1459-1461, 2004.
• 8: Daniel H. Huson , Tobias Dezulian , Tobias Klopper , Mike A. Steel, Phylogenetic Super-Networks from Partial Trees, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.4, p.151-158, October 2004 [doi>10.1109/TCBB.2004.44]
• 9: [9] D.H. Huson, T. Kloepper, P.J. Lockhart, and M.A. Steel, "Reconstruction of Reticulate Networks from Gene Trees," Proc. Int'l Conf. Research in Computational Molecular Biology (RECOMB), pp. 233-249, 2005.
• 10: [10] T.N.D. Huydn, J. Jansson, N.B. Nguyen, and W.-K. Sung, "Constructing a Smallest Refinining Galled Phylogenetic Network," Proc. Int'l Conf. Research in Computational Molecular Biology (RECOMB), pp. 265-280, 2005.
• 11: [11] J. Jansson and W.-K. Sung, "The Maximum Agreement of Two Nested Phylogenetic Networks," Proc. Int'l Symp. Algorithms and Computation (ISAAC), pp. 581-593, 2004.
• 12: [12] P. Legendre, "Biological Applications of Reticulate Analysis," J. Classification, vol. 17, pp. 191-195, 2000.
• 13: [13] J.O. McInerney and M. Wilkinson, "New Methods Ring Changes for the Tree of Life," Trends in Ecology and Evolution, vol. 20, pp. 105-107, 2005.
• 14: [14] J. Mallet, "Hybridization as an Invasion of the Genome," Trends in Ecology and Evolution, vol. 20, pp. 229-237, 2005.
• 15: Bernard M. E. Moret , Luay Nakhleh , Tandy Warnow , C. Randal Linder , Anna Tholse , Anneke Padolina , Jerry Sun , Ruth Timme, Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.13-23, January 2004 [doi>10.1109/TCBB.2004.10]
• 16: Luay Nakhleh , Tandy Warnow , C. Randal Linder, Reconstructing reticulate evolution in species: theory and practice, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.337-346, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974659]
• 17: [17] M.C. Rivera and J.C. Lake, "The Ring of Life Provides Evidence for a Genome Fusion Origin of Eukaryotes," Nature, vol. 431, pp. 152-155, 2004.
• 18: [18] F.J. Rohlf, "Phylogenetic Models and Reticulations," J. Classification , vol. 17, pp. 185-189, 2000.
• 19: [19] E. Schröder, "Vier Combinatorische Probleme," Zeitschrift für Mathematik und Physik, vol. 15, pp. 361-376, 1870.
• 20: [20] C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
• 21: [21] C. Semple and M. Steel, "Cyclic Permutations and Evolutionary Trees," Advances in Applied Math., vol. 32, pp. 669-680, 2004.
• 22: [22] Y. Song and J. Hein, "On the Minimum Number of Recombination Events in the Evolutionary History of DNA Sequences," J. Math. Biology, vol. 48, pp. 160-186, 2003.
• 23: [23] L. Wang, K. Zhang, and L. Zhang, "Perfect Phylogenetic Networks with Recombination," J. Computational Biology, vol. 8, pp. 69-78, 2001.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions
      G.2.2 Graph Theory

General Terms:
Algorithms, Design

Keywords:
Phylogenetic tree, compatibility, circular orderings, generating function, galled-trees.