RPNCH: A method for constructing rooted phylogenetic networks from rooted triplets based on height function

Mohammad Hossein Reyhani, Hadi Poormohammadi

Abstract


419

     Phylogenetic networks are a generalization of phylogenetic trees which permit the representation the non-tree-like events. It is NP-hard to construct an optimal rooted phylogenetic network from a given set of rooted triplets. This paper presents a novel algorithm called RPNCH. For a given set of rooted triplets, RPNCH tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes that contains all the given rooted triplets. The performance of RPNCH algorithm on simulated data is reported here.


Keywords


Rooted phylogenetic network; Rooted Triplet; Density; Height function; Reticulation node

Full Text:

PDF

164

References


Huson D.H‎, ‎Rupp R, ‎Scornavacca C. Phylogenetic‎ ‎Networks Concepts‎, ‎Algorithms and Applications‎, ‎Cambridge‎ ‎University Press‎. 2010.

‎Aho‎ A.V, ‎‎Sagiv Y, ‎Szymanski ‎T.G, ‎Ullman J.D. ‎Inferring a‎‎tree from lowest common ancestors with an application to the‎ ‎optimization of relational expressions. ‎SIAM J‎. ‎Comp. 1981; ‎10:‎405-421‎.

‎Jansson‎ J, ‎Nguyen ‎N.B, ‎Sung W.K‎. ‎Algorithms for combining‎ ‎rooted triplets into a galled phylogenetic network. ‎SIAM Journal on Computing‎. 2006; ‎35:‎1098-1121‎.

‎Jansson J, ‎Sung W.K‎. ‎Inferring a Level-1 Phylogenetic‎ ‎Network from a Dense Set of Rooted Triplets. ‎Theoretical Computer‎ ‎Science‎. 2006; ‎363:‎60-68‎‎.

‎Huber K, Iersel ‎L‎.‎van, ‎Kelk S, ‎Suchecki R. ‎A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks. ‎IEEE/ACM Transactions on Computational Biology and Bioinformatics‎‎. 2010.

‎‎ Iersel L‎.‎van, ‎Kelk S. ‎Constructing the Simplest Possible‎ ‎Phylogenetic Network from Triplets,‎" ‎Algorithmica‎, 2009; DOI 10.1007/s00453-009-9333-0‎.

Poormohammadi H, ‎Eslahchi‎, Ch, ‎Tusserkani R. TripNet‎: ‎A method for Constructing Rooted Phylogenetic Networks from Rooted Triplets. PLoS ONE. 2014; 9(9): e106531. doi:10.1371/journal.pone.0106531.

Karp R. Reducibility among combinatorial problems. Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y. 1972; 85-103.

Eades P, Lin X, Smyth, W.F. A fast and effective heuristic for the feedback arc set problem. Information Processing Letters. 1993; 47:319-323.




DOI: https://doi.org/10.22037/jps.v8i4.16707

Refbacks

  • There are currently no refbacks.


"Journal of Paramdedical Sciences", is a publication of "School of Paramedical Sciences, Shahid Beheshti University of Medical Sciences" and "Iranian Society of Medical Proteomics".

"Journal of Paramdedical Sciences" is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

 

EISSN: 2008-4978

PISSN: 2008-496X