“School of Biological”

Back to Papers Home
Back to Papers of School of Biological

Paper   IPM / Biological / 14384
School of Biological Sciences
  Title:   TripNet: A Method for Constructing Rooted Phylogenetic Networks from Rooted Triplets
1.  Hadi Poormohammadi
2.  Changiz Eslahchi
3.  Ruzbeh Tusserkani
  Status:   Published
  Journal: Plos One
  Year:  2014
  Pages:   http://dx.doi.org/10.1371/journal.pone.0106531
  Supported by:  IPM
The problem of constructing an optimal rooted phylogenetic network from an arbitrary set of rooted triplets is an NP-hard problem. In this paper, we present a heuristic algorithm called TripNet, which tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes from an arbitrary set of rooted triplets. Despite of current methods that work for dense set of rooted triplets, a key innovation is the applicability of TripNet to non-dense set of rooted triplets. We prove some theorems to clarify the performance of the algorithm. To demonstrate the efficiency of TripNet, we compared TripNet with SIMPLISTIC. It is the only available software which has the ability to return some rooted phylogenetic network consistent with a given dense set of rooted triplets. But the results show that for complex networks with high levels, the SIMPLISTIC running time increased abruptly. However in all cases TripNet outputs an appropriate rooted phylogenetic network in an acceptable time. Also we tetsed TripNet on the Yeast data. The results show that Both TripNet and optimal networks have the same clustering and TripNet produced a level-3 network which contains only one more reticulation node than the optimal network.

Download TeX format
back to top
scroll left or right