Who is Who in Phylogenetic Networks

Publications related to 'tree containment'   Order by:   Type | Year

Only And Or     related to:

Associated keywords

branch-length characterization cluster-containment compressed-network distinct-cluster-network dynamic-programming evaluation explicit-network exponential-algorithm FPT from-clusters from-network from-rooted-trees from-unrooted-trees FU-stable-network galled-network galled-tree genetically-stable-network level-k-phylogenetic-network nearly-stable-network nested-network normal-network NP-complete phylogenetic-network phylogeny polynomial pseudo-polynomial quasi-reticulation-visible-network reconstruction regular-network reticulation-visible-network software spread survey time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network unicyclic-network unrooted-tree-based-network

Article (Journal)

1 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In TCS, Vol. 401:153-164, 2008. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf.         2 Leo van Iersel, Charles Semple and Mike Steel. Locating a tree in a phylogenetic network. In IPL, Vol. 110(23), 2010. Keywords: cluster containment, explicit network, from network, level k phylogenetic network, normal network, NP complete, phylogenetic network, polynomial, regular network, time consistent network, tree containment, tree sibling network, tree-child network. Note: http://arxiv.org/abs/1006.3122.         Toggle abstract "Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete. © 2010 Elsevier B.V. All rights reserved." 3 Katharina Huber, Vincent Moulton, Mike Steel and Taoyang Wu. Folding and unfolding phylogenetic trees and networks. In JOMB, Vol. 73(6):1761-1780, 2016. Keywords: compressed network, explicit network, FU-stable network, NP complete, phylogenetic network, phylogeny, tree containment, tree sibling network. Note: http://arxiv.org/abs/1506.04438.         4 Magnus Bordewich and Charles Semple. Reticulation-visible networks. In Advances in Applied Mathematics, Vol. 78:114-141, 2016. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS16.pdf.         5 Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi and Celine Scornavacca. Do branch lengths help to locate a tree in a phylogenetic network? In BMB, Vol. 78(9):1773-1795, 2016. Keywords: branch length, explicit network, FPT, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, pseudo-polynomial, time consistent network, tree containment, tree sibling network. Note: http://arxiv.org/abs/1607.06285.         6 Leo van Iersel, Steven Kelk, Giorgios Stamoulis, Leen Stougie and Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. In ALG, Vol. 80(11):2993-3022, 2018. Keywords: explicit network, FPT, from network, from unrooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, tree containment. Note: https://hal.inria.fr/hal-01599716.         7 Andreas Gunawan, Bhaskar DasGupta and Louxin Zhang. A decomposition theorem and two algorithms for reticulation-visible networks. In Information and Computation, Vol. 252:161-175, 2017. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: https://www.cs.uic.edu/~dasgupta/resume/publ/papers/Infor_Comput_IC4848_final.pdf.         8 Andrew R. Francis, Katharina Huber and Vincent Moulton. Tree-based unrooted phylogenetic networks. In BMB, Vol. 80(2):404-416, 2018. Keywords: characterization, explicit network, NP complete, phylogenetic network, phylogeny, tree containment, tree-based network, unrooted tree-based network. Note: https://arxiv.org/abs/1704.02062.         9 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Solving the Tree Containment Problem in Linear Time for Nearly Stable Phylogenetic Networks. In DAM, Vol. 246:62-79, 2018. Keywords: explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01575001/en/.         10 Andreas Gunawan, Hongwei Yan and Louxin Zhang. Compression of Phylogenetic Networks and Algorithm for the Tree Containment Problem. In JCB, Vol. 25(3), 2019. Keywords: explicit network, phylogenetic network, phylogeny, polynomial, quasi-reticulation-visible network, reticulation-visible network, tree containment, tree-child network. Note: https://arxiv.org/abs/1806.07625.

InProceedings

11 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In Proceedings of the Tenth Italian Conference on Theoretical Computer Science (ICTCS'07), 2007. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/ictcs07.pdf.         12 Luay Nakhleh and Li-San Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919-926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.         13 Luay Nakhleh and Li-San Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:82-99 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.         14 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Locating a Tree in A Phylogenetic Network in Quadratic Time. In RECOMB15, Vol. 9029:96-107 of LNCS, Springer, 2015. Keywords: evaluation, explicit network, from network, from rooted trees, genetically stable network, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal.archives-ouvertes.fr/hal-01116231/en.         15 Jittat Fakcharoenphol, Tanee Kumpijit and Attakorn Putwattana. A Faster Algorithm for the Tree Containment Problem for Binary Nearly Stable Phylogenetic Networks. In Proceedings of the The 12th International Joint Conference on Computer Science and Software Engineering (JCSSE'15), Pages 337-342, IEEE, 2015. Keywords: dynamic programming, explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment.         16 Andreas Gunawan, Bhaskar DasGupta and Louxin Zhang. Locating a Tree in a Reticulation-Visible Network in Cubic Time. In RECOMB16, Vol. 9649:266 of LNBI, Springer, 2016. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: http://arxiv.org/abs/1507.02119.         17 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. In IWOCA15, Vol. 9538:197-208 of LNCS, springer, 2016. Keywords: explicit network, from network, from rooted trees, genetically stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01226035 .         18 Andreas Gunawan, Bingxin Lu and Louxin Zhang. A program for verification of phylogenetic network models. In ECCB16, Vol. 32(17):i503-i510 of BIO, 2016. Keywords: exponential algorithm, from network, from rooted trees, phylogenetic network, phylogeny, software, tree containment. Note: http://dx.doi.org/10.1093/bioinformatics/btw467.         19 Mathias Weller. Linear-Time Tree Containment in Phylogenetic Networks. In RECOMB-CG18, Vol. 11183:309-323 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, reconstruction, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.06364.         20 Andreas Gunawan. Solving the Tree Containment Problem for Reticulation-visible Networks in Linear Time. In AlCoB18, Vol. 10849:24-36 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.04088.         21 Louxin Zhang. Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks. In WALCOM20, Vol. 12049:22-27 of LNCS, Springer, 2020. Keywords: cluster containment, galled network, galled tree, nearly-stable network, phylogenetic network, phylogeny, polynomial, reticulation-visible network, survey, time consistent network, tree containment, tree-based network, tree-child network.

InBook

22 Louxin Zhang. Clusters, Trees, and Phylogenetic Network Classes. In Tandy Warnow editor, Bioinformatics and Phylogenetics. Seminal Contributions of Bernard Moret, Vol. 29:277-315 of Computational Biology, Springer, 2019. Keywords: cluster containment, explicit network, phylogenetic network, phylogeny, polynomial, tree containment.

MastersThesis

23 Maxime Morgado. Propriétés structurelles et relations des classes de réseaux phylogénétiques. Master's thesis, ENS Cachan, 2015. Keywords: compressed network, distinct-cluster network, explicit network, galled network, galled tree, level k phylogenetic network, nested network, normal network, phylogenetic network, phylogeny, regular network, spread, tree containment, tree sibling network, tree-based network, tree-child network, unicyclic network.

PhdThesis

24 Andreas Gunawan. On the tree and cluster containment problems for phylogenetic networks. PhD thesis, National University of Singapore, 2018. Keywords: cluster containment, explicit network, galled network, genetically stable network, nearly-stable network, phylogenetic network, phylogeny, reticulation-visible network, tree containment. Note: https://scholarbank.nus.edu.sg/handle/10635/144270.