RPNCH: A method for constructing rooted phylogenetic networks from rooted triplets based on height function
Archives of Advances in Biosciences,
Vol. 8 No. 4 (2017),
26 Mehr 2017
,
Page 14-20
https://doi.org/10.22037/jps.v8i4.16707
Abstract
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.
- Rooted phylogenetic network
- Rooted Triplet
- Density
- Height function
- Reticulation node
How to Cite
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 atree 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.
- Abstract Viewed: 662 times
- PDF Downloaded: 298 times