




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



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, tree child network.






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






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, tree child 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."










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, tree child 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."






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, tree child network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_611.pdf.



