title: A program to compute the soft Robinson-Foulds distance between phylogenetic networks.
abstract: Over the past two decades, phylogenetic networks have been studied to model reticulate evolutionary events. The relationships among phylogenetic networks, phylogenetic trees and clusters serve as the basis for reconstruction and comparison of phylogenetic networks. To understand these relationships, two problems are raised: the tree containment problem, which asks whether a phylogenetic tree is displayed in a phylogenetic network, and the cluster containment problem, which asks whether a cluster is represented at a node in a phylogenetic network. Both the problems are NP-complete.
  
  
  
  A fast exponential-time algorithm for the cluster containment problem on arbitrary networks is developed and implemented in C. The resulting program is further extended into a computer program for fast computation of the Soft Robinson-Foulds distance between phylogenetic networks.
  
  
  
  Two computer programs are developed for facilitating reconstruction and validation of phylogenetic network models in evolutionary and comparative genomics. Our simulation tests indicated that they are fast enough for use in practice. Additionally, the distribution of the Soft Robinson-Foulds distance between phylogenetic networks is demonstrated to be unlikely normal by our simulation data.
authors.affiliation: Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore, 117417, Singapore.
authors.forename: Bingxin
authors.initials: B
authors.lastname: Lu
authors.affiliation: Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge, Singapore, 119076, Singapore. matzlx@nus.edu.sg.
authors.forename: Louxin
authors.initials: L
authors.lastname: Zhang
authors.affiliation: Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore, 117417, Singapore.
authors.forename: Hon Wai
authors.initials: HW
authors.lastname: Leong
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D019295:Computational Biology / Q000706:statistics & numerical data*; D009033:Culicidae / Q000145:classification / Q000235:genetics; D008957:Models, Genetic; D010802:Phylogeny; D010940:Plant Proteins / Q000235:genetics; D006109:Poaceae / Q000145:classification / Q000235:genetics; D012330:RNA, Double-Stranded / Q000235:genetics; D012331:RNA, Fungal / Q000235:genetics; D012232:Rhizoctonia / Q000145:classification / Q000235:genetics; D012984:Software
chemical_list: D010940:Plant Proteins; D012330:RNA, Double-Stranded; D012331:RNA, Fungal
keywords: (Soft) Robinson–Foulds distance; Cluster containment problem; Exponential-time algorithm; Phylogenetic network; Tree containment problem