“School of Biological”

Back to Papers Home
Back to Papers of School of Biological

Paper   IPM / Biological / 16344
School of Biological Sciences
  Title:   Netcombin: An algorithm for constructing optimal phylogenetic network from rooted triplets
1.  Hadi Poormohammadi
2.  Mohsen Sardari Zarchi
  Status:   Published
  Journal: Plos One
  No.:  9
  Vol.:  15
  Year:  2020
  Pages:   https://doi.org/10.1371/journal.pone.0227842
  Supported by:  IPM
Phylogenetic networks construction is one the most important challenge in phylogenetics. These networks can present complex non-treelike events such as gene flow, horizontal gene transfers, recombination or hybridizations. Among phylogenetic networks, rooted structures are commonly used to represent the evolutionary history of a species set, explicitly. Triplets are well known input for constructing the rooted networks. Obtaining an optimal rooted network that contains all given triplets is main problem in network construction. The optimality criteria include minimizing the level or the number of reticulation nodes. The complexity of this problem is known to be NP-hard. In this research, a new algorithm called Netcombin is introduced to construct approximately an optimal network which is consistent with input triplets. The innovation of this algorithm is based on binarization and expanding processes. The binarization process innovatively uses a measure to construct a binary rooted tree T consistent with the approximately maximum number of input triplets. Then T is expanded using a heuristic function by adding minimum number of edges to obtain final network with the approximately minimum number of reticulation nodes. In order to evaluate the proposed algorithm, Netcombin is compared with four state of the art algorithms, RPNCH, NCHB, TripNet, and SIMPLISTIC. The experimental results on simulated data obtained from biologically generated sequences data indicate that by considering the trade-off between speed and precision, the Netcombin outperforms the others.

Download TeX format
back to top
scroll left or right