




Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. The comparison of treesibling time consistent phylogenetic networks is graphisomorphism complete. In The Scientific World Journal, Vol. 2014(254279):16, 2014. Keywords: abstract network, distance between networks, from network, isomorphism, phylogenetic network, tree sibling network. Note: http://arxiv.org/abs/0902.4640.
Toggle abstract
"Several polynomial time computable metrics on the class of semibinary treesibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic treesibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all treesibling time consistent phylogenetic networks that can be computed in polynomial time. © 2014 Gabriel Cardona et al."






Tetsuo Asano,
Jesper Jansson,
Kunihiko Sadakane,
Ryuhei Uehara and
Gabriel Valiente. Faster computation of the Robinson–Foulds distance between phylogenetic networks. In Information Sciences, Vol. 197:7790, 2012. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread.
Toggle abstract
"The RobinsonFoulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N 1, N 2 with n leaf labels and at most m nodes and e edges each, the RobinsonFoulds distance measures the number of clusters of descendant leaves not shared by N 1 and N 2. The fastest known algorithm for computing the RobinsonFoulds distance between N 1 and N 2 runs in O(me) time. In this paper, we improve the time complexity to O(ne/log n) for general phylogenetic networks and O(nm/log n) for general phylogenetic networks with bounded degree (assuming the word RAM model with a word length of ⌈logn⌉ bits), and to optimal O(m) time for leafouterplanar networks as well as optimal O(n) time for level1 phylogenetic networks (that is, galledtrees). We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a levelk network is at most k + 1, which implies that for one level1 and one levelk phylogenetic network, our algorithm runs in O((k + 1)e) time. © 2012 Elsevier Inc. All rights reserved."






Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Comparison of Galled Trees. In TCBB, Vol. 8(2):410427, 2011. Note: http://arxiv.org/abs/0906.1166.
Toggle abstract
"Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomialtime algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods. © 2011 IEEE."






Tetsuo Asano,
Jesper Jansson,
Kunihiko Sadakane,
Ryuhei Uehara and
Gabriel Valiente. Faster Computation of the RobinsonFoulds Distance between Phylogenetic Networks. In CPM10, Vol. 6129:190201 of LNCS, springer, 2010. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread. Note: http://hdl.handle.net/10119/9859, slides available at http://cs.nyu.edu/parida/CPM2010/MainPage_files/18.pdf.
Toggle abstract
"The RobinsonFoulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2 with n leaves, m nodes, and e edges, the RobinsonFoulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the RobinsonFoulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a levelk phylogenetic network is at most k + 1, which implies that for two levelk phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time. © SpringerVerlag Berlin Heidelberg 2010."



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."






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 Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Metrics for phylogenetic networks II: Nodal and triplets metrics. In TCBB, Vol. 6(3):454469, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1109/TCBB.2008.127.
Toggle abstract
"The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second 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 generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of treechild time consistent phylogenetic networks by induction, but also to generate all treechild time consistent phylogenetic networks with a given number of leaves. © 2009 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. On Nakhleh's metric for reduced phylogenetic networks. In TCBB, Vol. 6(4):629638, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: Preliminary versions: http://arxiv.org/abs/0809.0110 and http://arxiv.org/abs/0801.2354v1.
Toggle abstract
"We prove that Nakhleh's metric for reduced phylogenetic networks is also a metric on the classes of treechild phylogenetic networks, semibinary treesibling time consistent phylogenetic networks, and multilabeled phylogenetic trees. We also prove that it separates distinguishable phylogenetic networks. In this way, it becomes the strongest dissimilarity measure for phylogenetic networks available so far. Furthermore, we propose a generalization of that metric that separates arbitrary phylogenetic networks. © 2009 IEEE."



Francesc Rosselló and
Gabriel Valiente. All that Glisters is not Galled. In MBIO, Vol. 221(1):5459, 2009. Keywords: galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/0904.2448.
Toggle abstract
"Galled trees, evolutionary networks with isolated reticulation cycles, have appeared under several slightly different definitions in the literature. In this paper, we establish the actual relationships between the main four such alternative definitions: namely, the original galled trees, level1 networks, nested networks with nesting depth 1, and evolutionary networks with arcdisjoint reticulation cycles. © 2009 Elsevier Inc. All rights reserved."



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. A Distance Metric for a Class of TreeSibling Phylogenetic Networks. In BIO, Vol. 24(13):14811488, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network. Note: http://dx.doi.org/10.1093/bioinformatics/btn231.
Toggle abstract
"Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a nonextant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this articlea distance measure on the class of semibinary treesibling time consistent phylogenetic networks, which generalize treechild time consistent phylogenetic networks, and thus also galledtrees. The practical interest of this distance measure is 2fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomialtime algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)."



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."



Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. Extended Newick: It is Time for a Standard Representation. In BMCB, Vol. 9:532, 2008. Keywords: evaluation, explicit network, phylogenetic network, Program Bio PhyloNetwork, Program Dendroscope, Program NetGen, Program PhyloNet, Program SplitsTree, Program TCS, visualization. Note: http://bioinfo.uib.es/media/uploaded/bmc2008enewicksub.pdf.





