Counting Phylogenetic Networks

详细信息    查看全文

• 作者：Colin McDiarmid (1)
  Charles Semple (2)
  Dominic Welsh (3)
  
  1. Department of Statistics ; University of Oxford ; Oxford ; OX1 3TG ; UK
  2. School of Mathematics and Statistics ; University of Canterbury ; Private Bag 4800 ; Christchurch ; New Zealand
  3. Mathematical Institute ; University of Oxford ; Andrew Wiles Building ; Radcliffe Observatory Quarter ; Woodstock Road ; Oxford ; OX2 6GG ; UK
  
• 关键词：05C30 ; 92D15 ; 05C80 ; phylogenetic networks ; tree ; child networks ; normal networks
• 刊名：Annals of Combinatorics
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：19
• 期：1
• 页码：205-224
• 全文大小：368 KB
• 参考文献：1. Bickner, D.R.: On normal networks. PhD thesis. Iowa State University, Ames, Iowa (2012)
  2. Bollob谩s, B.: Random Graphs. Second edition. Cambridge University Press, Cambridge (2001)
  3. B贸na,M., Flajolet, P.: Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46(4), 1005鈥?019 (2009)
  4. Cardona, G., Rossello, F., Valiente, G. (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6: pp. 552-569 CrossRef
  5. Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. J. Comput. System Sci. 25(2), 171鈥?13 (1982)
  6. Gill, J.: The / k-assignment polytope, phylogenetic trees, and permutation patterns. PhD thesis. Link枚ping University, Sweden (2013)
  7. Janson, S., \({{\L}}\) uczak, T., Ruci艅ski, A.: Random Graphs. Wiley Interscience, New York (2000)
  8. McKay, B.: The shape of a random acyclic digraph. Math. Proc. Cambridge Philos. Soc. 106(3), 459鈥?65 (1989)
  9. Robinson, R.W., Wormald, N.C.: Existence of long cycles in random cubic graphs. In: Jackson, D.M., Vanstone, S.A. (Eds.) Enumeration and Design, pp. 251鈥?70. Academic Press, Toronto (1984)
  10. Robinson, R.W.,Wormald, N.C.: Almost all cubic graphs are Hamiltonian. Random Structures Algorithms 3(2), 117鈥?25 (1992)
  11. Schr枚der, E.: Vier combinatorische probleme. Z. Math. Phys. 15, 361鈥?76 (1870)
  12. Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)
  13. Vitter, J.S., Flajolet, P.: Average-case analysis of algorithms and data structures. In: van Leeuwen, J. (Ed.) Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity, pp. 431鈥?24. Elsevier, Amsterdam (1990)
  14. Willson, S.J.: Unique determination of some homoplasies at hybridization events. Bull. Math. Biol. 69(5), 1709鈥?725 (2007)
  15. Willson, S.J.: Properties of normal phylogenetic networks. Bull. Math. Biol. 72, 340鈥?58 (2010)
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  
• 出版者：Birkh盲user Basel
• ISSN：0219-3094

文摘

We give approximate counting formulae for the numbers of labelled general, treechild, and normal (binary) phylogenetic networks on n vertices. These formulae are of the form \({2^{\gamma n {\rm log}n+O(n)}}\) , where the constant \({\gamma}\) is \({\frac{3}{2}}\) for general networks, and \({\frac{5}{4}}\) for tree-child and normal networks. We also show that the number of leaf-labelled tree-child and normal networks with \({\ell}\) leaves are both \({{2}^{2 \ell {\rm log} \ell +O( \ell )}}\) . Further we determine the typical numbers of leaves, tree vertices, and reticulation vertices for each of these classes of networks.