











Louxin Zhang. Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks. In WALCOM20, Vol. 12049:2227 of LNCS, Springer, 2020. Keywords: cluster containment, galled network, galled tree, nearlystable network, phylogenetic network, phylogeny, polynomial, reticulationvisible network, survey, time consistent network, tree containment, treebased network, treechild network.



Remie Janssen,
Mark Jones and
Yukihiro Murakami. Combining Networks Using Cherry Picking Sequences. In AlCoB20, Vol. 12099:7792 of LNCS, Springer, 2020. Keywords: cherrypicking, explicit network, FPT, from network, hybridization, orchard network, phylogenetic network, phylogeny, treechild network.



Remie Janssen and
Yukihiro Murakami. Linear Time Algorithm for TreeChild Network Containment. In AlCoB20, Vol. 12099:93107 of LNCS, Springer, 2020. Keywords: explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, reconstruction, treechild network, treechild sequence. Note: https://doi.org/10.1007/9783030422660_8.








Janosch Döcker,
Leo van Iersel,
Steven Kelk and
Simone Linz. Deciding the existence of a cherrypicking sequence is hard on two trees. In DAM, Vol. 260:131143, 2019. Keywords: cherrypicking, explicit network, hybridization, minimum number, NP complete, phylogenetic network, phylogeny, reconstruction, temporalhybridization number, time consistent network, treechild network. Note: https://arxiv.org/abs/1712.02965.





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, quasireticulationvisible network, reticulationvisible network, tree containment, treechild network. Note: https://arxiv.org/abs/1806.07625.



Yukihiro Murakami,
Leo van Iersel,
Remie Janssen,
Mark Jones and
Vincent Moulton. Reconstructing TreeChild Networks from ReticulateEdgeDeleted Subnetworks. In BMB, Vol. 81:38233863, 2019. Keywords: from subnetworks, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction, treechild network, uniqueness. Note: https://doi.org/10.1007/s1153801900641w.



Juan Wang and
Maozu Guo. A review of metrics measuring dissimilarity for rooted phylogenetic networks. In Briefings in Bioinformatics, Vol. 20(6):19721980, 2019. Keywords: distance between networks, explicit network, from network, mu distance, phylogenetic network, phylogeny, survey, tree sibling network, treechild network.








Magnus Bordewich,
Charles Semple and
Nihan Tokac. Constructing treechild networks from distance matrices. In Algorithmica, Vol. 80(8):22402259, 2018. Keywords: compressed network, explicit network, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, treechild network, uniqueness. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSN17.pdf.





Janosch Döcker and
Simone Linz. On the existence of a cherrypicking sequence. In TCS, Vol. 714:3650, 2018. Keywords: cherrypicking, explicit network, from rooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, temporalhybridization number, time consistent network, treechild network. Note: https://arxiv.org/abs/1712.04127.








Magnus Bordewich,
Simone Linz and
Charles Semple. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. In JTB, Vol. 423:112, 2017. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, reticulationvisible network, SPR distance, treebased network, treechild network. Note: https://simonelinz.files.wordpress.com/2017/04/bls171.pdf.










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, distinctcluster 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, treebased network, treechild network, unicyclic network.






Paul Cordue,
Simone Linz and
Charles Semple. Phylogenetic Networks that Display a Tree Twice. In BMB, Vol. 76(10):26642679, 2014. Keywords: from rooted trees, normal network, phylogenetic network, phylogeny, reconstruction, treechild network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/CLS14.pdf.
Toggle abstract
"In the last decade, the use of phylogenetic networks to analyze the evolution of species whose past is likely to include reticulation events, such as horizontal gene transfer or hybridization, has gained popularity among evolutionary biologists. Nevertheless, the evolution of a particular gene can generally be described without reticulation events and therefore be represented by a phylogenetic tree. While this is not in contrast to each other, it places emphasis on the necessity of algorithms that analyze and summarize the treelike information that is contained in a phylogenetic network. We contribute to the toolbox of such algorithms by investigating the question of whether or not a phylogenetic network embeds a tree twice and give a quadratictime algorithm to solve this problem for a class of networks that is more general than treechild networks. © 2014, Society for Mathematical Biology."



Adrià Alcalà Mena,
Mercè Llabrés,
Francesc Rosselló and
Pau Rullan. TreeChild Cluster Networks. In Fundamenta Informaticae, Vol. 134(12):115, 2014. Keywords: explicit network, from clusters, phylogenetic network, phylogeny, Program PhyloNetwork, reconstruction, treechild network.






Stephen J. Willson. Treeaverage distances on certain phylogenetic networks have their weights uniquely determined. In ALMOB, Vol. 7(13), 2012. Keywords: from distances, from network, normal network, phylogenetic network, phylogeny, reconstruction, treechild network. Note: hhttp://www.public.iastate.edu/~swillson/TreeAverageDis10All.pdf.
Toggle abstract
"A phylogenetic network N has vertices corresponding to species and arcs corresponding to direct genetic inheritance from the species at the tail to the species at the head. Measurements of DNA are often made on species in the leaf set, and one seeks to infer properties of the network, possibly including the graph itself. In the case of phylogenetic trees, distances between extant species are frequently used to infer the phylogenetic trees by methods such as neighborjoining.This paper proposes a treeaverage distance for networks more general than trees. The notion requires a weight on each arc measuring the genetic change along the arc. For each displayed tree the distance between two leaves is the sum of the weights along the path joining them. At a hybrid vertex, each character is inherited from one of its parents. We will assume that for each hybrid there is a probability that the inheritance of a character is from a specified parent. Assume that the inheritance events at different hybrids are independent. Then for each displayed tree there will be a probability that the inheritance of a given character follows the tree; this probability may be interpreted as the probability of the tree. The treeaverage distance between the leaves is defined to be the expected value of their distance in the displayed trees.For a class of rooted networks that includes rooted trees, it is shown that the weights and the probabilities at each hybrid vertex can be calculated given the network and the treeaverage distances between the leaves. Hence these weights and probabilities are uniquely determined. The hypotheses on the networks include that hybrid vertices have indegree exactly 2 and that vertices that are not leaves have a treechild. © 2012 Willson; licensee BioMed Central Ltd."






Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Path lengths in treechild time consistent hybridization networks. In Information Sciences, Vol. 180(3):366383, 2010. Keywords: distance between networks, phylogenetic network, phylogeny, time consistent network, treechild network. Note: http://arxiv.org/abs/0807.0087?context=cs.CE.
Toggle abstract
"Hybridization networks are representations of evolutionary histories that allow for the inclusion of reticulate events like recombinations, hybridizations, or lateral gene transfers. The recent growth in the number of hybridization network reconstruction algorithms has led to an increasing interest in the definition of metrics for their comparison that can be used to assess the accuracy or robustness of these methods. In this paper we establish some basic results that make it possible the generalization to treechild time consistent (TCTC) hybridization networks of some of the oldest known metrics for phylogenetic trees: those based on the comparison of the vectors of path lengths between leaves. More specifically, we associate to each hybridization network a suitably defined vector of 'splitted' path lengths between its leaves, and we prove that if two TCTC hybridization networks have the same such vectors, then they must be isomorphic. Thus, comparing these vectors by means of a metric for realvalued vectors defines a metric for TCTC hybridization networks. We also consider the case of fully resolved hybridization networks, where we prove that simpler, 'nonsplitted' vectors can be used. © 2009 Elsevier Inc. All rights reserved."



Miguel Arenas,
Mateus Patricio,
David Posada and
Gabriel Valiente. Characterization of Phylogenetic Networks with NetTest. In BMCB, Vol. 11:268, 2010. Keywords: explicit network, galled tree, phylogenetic network, Program NetTest, software, time consistent network, tree sibling network, treechild network, visualization. Note: http://dx.doi.org/10.1186/1471210511268, software available at http://darwin.uvigo.es/software/nettest/.
Toggle abstract
"Background: Typical evolutionary events like recombination, hybridization or gene transfer make necessary the use of phylogenetic networks to properly depict the evolution of DNA and protein sequences. Although several theoretical classes have been proposed to characterize these networks, they make stringent assumptions that will likely not be met by the evolutionary process. We have recently shown that the complexity of simulated networks is a function of the population recombination rate, and that at moderate and large recombination rates the resulting networks cannot be categorized. However, we do not know whether these results extend to networks estimated from real data.Results: We introduce a web server for the categorization of explicit phylogenetic networks, including the most relevant theoretical classes developed so far. Using this tool, we analyzed statistical parsimony phylogenetic networks estimated from ~5,000 DNA alignments, obtained from the NCBI PopSet and Polymorphix databases. The level of characterization was correlated to nucleotide diversity, and a high proportion of the networks derived from these data sets could be formally characterized.Conclusions: We have developed a public web server, NetTest (freely available from the software section at http://darwin.uvigo.es), to formally characterize the complexity of phylogenetic networks. Using NetTest we found that most statistical parsimony networks estimated with the program TCS could be assigned to a known network class. The level of network characterization was correlated to nucleotide diversity and dependent upon the intra/interspecific levels, although no significant differences were detected among genes. More research on the properties of phylogenetic networks is clearly needed. © 2010 Arenas et al; licensee BioMed Central Ltd."



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, treechild network. Note: http://arxiv.org/abs/1006.3122.
Toggle abstract
"Phylogenetic trees and networks are leaflabelled 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 NPcomplete in general. In this article, we consider the restriction of these problems to several wellstudied classes of phylogenetic networks. We show that Tree Containment is polynomialtime solvable for normal networks, for binary treechild networks, and for levelk networks. On the other hand, we show that, even for treesibling, timeconsistent, regular networks, both Tree Containment and Cluster Containment remain NPcomplete. © 2010 Elsevier B.V. All rights reserved."






Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. Comparison of treechild phylogenetic networks. In TCBB, Vol. 6(4):552569, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Bio PhyloNetwork, Program PhyloNetwork, tree sibling network, treechild network. Note: http://arxiv.org/abs/0708.3499.
Toggle abstract
"Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a wellfounded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called treechild phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the wellknown RobinsonFoulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a treechild phylogenetic network from its path multiplicity vectors, for computing the distance between two treechild phylogenetic networks and for aligning a pair of treechild phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/ phylonetworks/mudistance/. © 2009 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Metrics for phylogenetic networks I: Generalizations of the RobinsonFoulds metric. In TCBB, Vol. 6(1):4661, 2009. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, time consistent network, treechild network, tripartition distance. Note: http://dx.doi.org/10.1109/TCBB.2008.70.
Toggle abstract
"The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the first in a series of papers devoted to the analysis and comparison of metrics for treechild time consistent phylogenetic networks on the same set of taxa. In this paper, we study three metrics that have already been introduced in the literature: the RobinsonFoulds distance, the tripartitions distance and the $mu$distance. They generalize to networks the classical RobinsonFoulds or partition distance for phylogenetic trees. We analyze the behavior of these metrics by studying their least and largest values and when they achieve them. As a byproduct of this study, we obtain tight bounds on the size of a treechild time consistent phylogenetic network. © 2006 IEEE."



Gabriel Valiente. Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R. Pages 184208, Taylor & Francis/CRC Press, 2009. Keywords: counting, distance between networks, galled tree, generation, phylogenetic network, phylogeny, survey, time consistent network, tree sibling network, treechild network. Note: http://books.google.fr/books?id=F4YIIUWb7yMC.






Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. Tripartitions do not always discriminate phylogenetic networks. In MBIO, Vol. 211(2):356370, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, treechild network, tripartition distance. Note: http://arxiv.org/abs/0707.2376, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/valiente/.
Toggle abstract
"Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. In a recent series of papers devoted to the study of reconstructibility of phylogenetic networks, Moret, Nakhleh, Warnow and collaborators introduced the socalled tripartition metric for phylogenetic networks. In this paper we show that, in fact, this tripartition metric does not satisfy the separation axiom of distances (zero distance means isomorphism, or, in a more relaxed version, zero distance means indistinguishability in some specific sense) in any of the subclasses of phylogenetic networks where it is claimed to do so. We also present a subclass of phylogenetic networks whose members can be singled out by means of their sets of tripartitions (or even clusters), and hence where the latter can be used to define a meaningful metric. © 2007 Elsevier Inc. All rights reserved."



Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. A Perl Package and an Alignment Tool for Phylogenetic Networks. In BMCB, Vol. 9:175, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree sibling network, treechild network. Note: http://dx.doi.org/10.1186/147121059175.
Toggle abstract
"Background: Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of evolutionary events acting at the population level, like recombination between genes, hybridization between lineages, and lateral gene transfer. While most phylogenetics tools implement a wide range of algorithms on phylogenetic trees, there exist only a few applications to work with phylogenetic networks, none of which are opensource libraries, and they do not allow for the comparative analysis of phylogenetic networks by computing distances between them or aligning them. Results: In order to improve this situation, we have developed a Perl package that relies on the BioPerl bundle and implements many algorithms on phylogenetic networks. We have also developed a Java applet that makes use of the aforementioned Perl package and allows the user to make simple experiments with phylogenetic networks without having to develop a program or Perl script by him or herself. Conclusion: The Perl package is available as part of the BioPerl bundle, and can also be downloaded. A webbased application is also available (see availability and requirements). The Perl package includes full documentation of all its features. © 2008 Cardona et al; licensee BioMed Central Ltd."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Phylogenetic Networks: Justification, Models, Distances and Algorithms. In VI Jornadas de Matemática Discreta y Algorítmica (JMDA'08), 2008. Keywords: distance between networks, mu distance, phylogenetic network, phylogeny, polynomial, survey, time consistent network, treechild network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_611.pdf.



Miguel Arenas,
Gabriel Valiente and
David Posada. Characterization of reticulate networks based on the coalescent with recombination. In MBE, Vol. 25(12):25172520, 2008. Keywords: coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree sibling network, treechild network. Note: http://dx.doi.org/10.1093/molbev/msn219.
Toggle abstract
"Phylogenetic networks aim to represent the evolutionary history of taxa. Within these, reticulate networks are explicitly able to accommodate evolutionary events like recombination, hybridization, or lateral gene transfer. Although several metrics exist to compare phylogenetic networks, they make several assumptions regarding the nature of the networks that are not likely to be fulfilled by the evolutionary process. In order to characterize the potential disagreement between the algorithms and the biology, we have used the coalescent with recombination to build the type of networks produced by reticulate evolution and classified them as regular, tree sibling, tree child, or galled trees. We show that, as expected, the complexity of these reticulate networks is a function of the population recombination rate. At small recombination rates, most of the networks produced are already more complex than regular or tree sibling networks, whereas with moderate and large recombination rates, no network fit into any of the standard classes. We conclude that new metrics still need to be devised in order to properly compare two phylogenetic networks that have arisen from reticulating evolutionary process. © 2008 The Authors."








Luay Nakhleh and
LiSan Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, treechild network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.



Luay Nakhleh and
LiSan Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:8299 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, treechild network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.



