Phylogenetic Networks: Properties and Relationship to Trees and Clusters

  • Luay Nakhleh
  • Li-San Wang
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3680)


Phylogenetic networks model evolutionary histories in the presence of non-treelike events such as hybrid speciation and horizontal gene transfer. In spite of their widely acknowledged importance, very little is known about phylogenetic networks, which have so far been studied mostly for specific datasets.

Even when the evolutionary history of a set of species is non-treelike, individual genes in these species usually evolve in a treelike fashion. An important question, then, is whether a gene tree is “contained” inside a species network. This information is used to detect the presence of events such as horizontal gene transfer and hybrid speciation. Another question of interest for biologists is whether a group of taxa forms a clade based on a given phylogeny. This can be efficiently answered when the phylogeny is a tree simply by inspecting the edges of the tree, whereas no efficient solution currently exists for the problem when the phylogeny is a network. In this paper, we give polynomial-time algorithms for answering the above two questions.


Network Node Dependency Graph Lateral Gene Transfer Tree Node Phylogenetic Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bryant, D., Moulton, V.: NeighborNet: An agglomerative method for the construction of planar phylogenetic networks. In: Guigó, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol. 2452, pp. 375–391. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  2. 2.
    Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland (2003)Google Scholar
  3. 3.
    Huson, D.H.: SplitsTree: A program for analyzing and visualizing evolutionary data. Bioinformatics 14(1), 68–73 (1998)CrossRefGoogle Scholar
  4. 4.
    Maddison, W.P.: Gene trees in species trees. Systematic Biology 46(3), 523–536 (1997)CrossRefGoogle Scholar
  5. 5.
    Moret, B.M.E., Nakhleh, L., Warnow, T., Linder, C.R., Tholse, A., Padolina, A., Sun, J., Timme, R.: Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE/ACM Transactions on Computational Biology and Bioinformatics 1(1), 13–23 (2004)CrossRefGoogle Scholar
  6. 6.
    Nakhleh, L., Warnow, T., Linder, C.R.: Reconstructing reticulate evolution in species – theory and practice. In: Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2004), pp. 337–346 (2004)Google Scholar
  7. 7.
    Swofford, D.L., Olsen, G.J., Waddell, P.J., Hillis, D.M.: Phylogenetic inference. In: Hillis, D.M., Mable, B.K., Moritz, C. (eds.) Molecular Systematics, pp. 407–514. Sinauer Assoc., Sunderland (1996)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Luay Nakhleh
    • 1
  • Li-San Wang
    • 2
  1. 1.Department of Computer ScienceRice UniversityHoustonUSA
  2. 2.Department of BiologyUniversity of PennsylvaniaPhiladelphiaUSA

Personalised recommendations