
Katharina Huber,
Leo van Iersel,
Vincent Moulton,
Celine Scornavacca and
Taoyang Wu. Reconstructing phylogenetic level1 networks from nondense binet and trinet sets. In ALG, Vol. 77(1):173200, 2017. Keywords: explicit network, FPT, from binets, from trinets, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1411.6804.



Leo van Iersel,
Steven Kelk,
Giorgios Stamoulis,
Leen Stougie and
Olivier Boes. On unrooted and rootuncertain variants of several wellknown phylogenetic network problems. In ALG, 2017. Keywords: explicit network, FPT, from network, from unrooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, tree containment. Note: https://hal.inria.fr/hal01599716, to appear.





Philippe Gambette,
Katharina Huber and
Guillaume Scholz. Bridging the gap between rooted and unrooted phylogenetic networks. In BMB, 2017. Keywords: circular split system, explicit network, from splits, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction, split network, uniqueness. Note: http://arxiv.org/abs/1511.08387, to appear.



Julia Matsieva,
Steven Kelk,
Celine Scornavacca,
Chris Whidden and
Dan Gusfield. A Resolution of the Static Formulation Question for the Problem of Computing the History Bound. In TCBB, Vol. 14(2):404417, 2017. Keywords: ARG, explicit network, from sequences, minimum number, phylogenetic network, phylogeny.



Misagh Kordi and
Mukul S. Bansal. On the Complexity of DuplicationTransferLoss Reconciliation with NonBinary Gene Trees. In TCBB, Vol. 14(3):587599, 2017. Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://compbio.engr.uconn.edu/papers/Kordi_DTLreconciliationPreprint2015.pdf.







Bingxin Lu,
Louxin Zhang and
Hon Wai Leong. A program to compute the soft RobinsonFoulds distance between phylogenetic networks. In APBC17, Vol. 18(Suppl. 2):111 of BMC Genomics, 2017. Keywords: cluster containment, distance between networks, explicit network, exponential algorithm, from network, phylogenetic network, phylogeny, Program iceluPhyloNetwork. Note: http://dx.doi.org/10.1186/s1286401735005.





Celine Scornavacca,
Joan Carles Pons and
Gabriel Cardona. Fast algorithm for the reconciliation of gene trees and LGT networks. In JTB, Vol. 418:129137, 2017. Keywords: duplication, explicit network, from network, from rooted trees, lateral gene transfer, LGT network, loss, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.



Leo van Iersel,
Vincent Moulton,
Eveline De Swart and
Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):11351154, 2017. Keywords: approximation, explicit network, from binets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/s1153801702754.



Leo van Iersel,
Steven Kelk,
Nela Lekic,
Chris Whidden and
Norbert Zeh. Hybridization Number on Three Rooted Binary Trees is EPT. In SIDMA, Vol. 30(3):16071631, 2016. Keywords: agreement forest, explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1402.2136.





Andreas Gunawan,
Bhaskar DasGupta and
Louxin Zhang. Locating a Tree in a ReticulationVisible Network in Cubic Time. In RECOMB2016, Vol. 9649:266 of LNBI, Springer, 2016. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulationvisible network, tree containment. Note: http://arxiv.org/abs/1507.02119.



Sajad Mirzaei and
Yufeng Wu. Fast Construction of Near Parsimonious Hybridization Networks for Multiple Phylogenetic Trees. In TCBB, Vol. 13(3):565570, 2016. Keywords: bound, explicit network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program PIRN, reconstruction, software. Note: http://www.engr.uconn.edu/~ywu/Papers/PIRNspreprint.pdf.



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:197208 of LNCS, springer, 2016. Keywords: explicit network, from network, from rooted trees, genetically stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://halupecupem.archivesouvertes.fr/hal01226035 .



Vincent Ranwez,
Celine Scornavacca,
JeanPhilippe Doyon and
Vincent Berry. Inferring gene duplications, transfers and losses can be done in a discrete framework. In JOMB, Vol. 72(7):18111844, 2016. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction.





François Chevenet,
JeanPhilippe Doyon,
Celine Scornavacca,
Edwin Jacox,
Emmanuelle Jousselin and
Vincent Berry. SylvX: a viewer for phylogenetic tree reconciliations. In BIO, Vol. 32(4):608610, 2016. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program SylvX, software, visualization. Note: https://www.researchgate.net/profile/Emmanuelle_Jousselin/publication/283446016_SylvX_a_viewer_for_phylogenetic_tree_reconciliations/links/5642146108aec448fa621efa.pdf.









Hussein A. Hejase and
Kevin J. Liu. A scalability study of phylogenetic network inference methods using empirical datasets and simulations involving a single reticulation. Vol. 17(422):112, 2016. Keywords: abstract network, evaluation, from sequences, phylogenetic network, phylogeny, Program PhyloNet, Program PhyloNetworks SNaQ, reconstruction, simulation, unicyclic network. Note: http://dx.doi.org/10.1186/s1285901612771.



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):17731795, 2016. Keywords: branch length, explicit network, FPT, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, pseudopolynomial, time consistent network, tree containment, tree sibling network. Note: http://arxiv.org/abs/1607.06285.







Maria Anaya,
Olga AnipchenkoUlaj,
Aisha Ashfaq,
Joyce Chiu,
Mahedi Kaiser,
Max Shoji Ohsawa,
Megan Owen,
Ella Pavlechko,
Katherine St. John,
Shivam Suleria,
Keith Thompson and
Corrine Yap. On Determining if Treebased Networks Contain Fixed Trees. In BMB, Vol. 78(5):961969, 2016. Keywords: explicit network, FPT, NP complete, phylogenetic network, phylogeny, treebased network. Note: http://arxiv.org/abs/1602.02739.





James Oldman,
Taoyang Wu,
Leo van Iersel and
Vincent Moulton. TriLoNet: Piecing together small networks to reconstruct reticulate evolutionary histories. In MBE, Vol. 33(8):21512162, 2016. Keywords: explicit network, from trinets, galled tree, phylogenetic network, phylogeny, Program LEV1ATHAN, Program TriLoNet, reconstruction.













Juan Wang. A Survey of Methods for Constructing Rooted Phylogenetic Networks. In PLoSONE, Vol. 11(11):e0165834, 2016. Keywords: evaluation, explicit network, from clusters, phylogenetic network, phylogeny, Program BIMLR, Program Dendroscope, Program LNetwork, reconstruction, survey. Note: http://dx.doi.org/10.1371/journal.pone.0165834.





Leo van Iersel,
Steven Kelk and
Celine Scornavacca. Kernelizations for the hybridization number problem on multiple nonbinary trees. In JCSS, Vol. 82(6):10751089, 2016. Keywords: explicit network, from rooted trees, kernelization, minimum number, phylogenetic network, phylogeny, Program Treeduce, reconstruction. Note: https://arxiv.org/abs/1311.4045v3.



Katharina Huber,
Leo van Iersel,
Vincent Moulton and
Taoyang Wu. How much information is needed to infer reticulate evolutionary histories? In Systematic Biology, Vol. 64(1):102111, 2015. Keywords: explicit network, from network, from rooted trees, from trinets, identifiability, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://dx.doi.org/10.1093/sysbio/syu076.





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:96107 of LNCS, Springer, 2015. Keywords: evaluation, explicit network, from network, from rooted trees, genetically stable network, nearlystable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal.archivesouvertes.fr/hal01116231/en.



Benjamin Albrecht. Computing all hybridization networks for multiple binary phylogenetic input trees. In BMCB, Vol. 16(236):115, 2015. Keywords: agreement forest, explicit network, exponential algorithm, FPT, from rooted trees, phylogenetic network, phylogeny, Program Hybroscale, Program PIRN, reconstruction. Note: http://dx.doi.org/10.1186/s1285901506607.





Gergely J. Szöllösi,
Adrián Arellano Davín,
Eric Tannier,
Vincent Daubin and
Bastien Boussau. Genomescale phylogenetic analysis finds extensive gene transfer among fungi. In Philosophical Transactions of the Royal Society of London B: Biological Sciences, Vol. 370(1678):111, 2015. Keywords: duplication, from sequences, lateral gene transfer, loss, phylogenetic network, phylogeny, Program ALE, reconstruction. Note: http://dx.doi.org/10.1098/rstb.2014.0335.





Marc Thuillard and
Didier FraixBurnet. Phylogenetic Trees and Networks Reduce to Phylogenies on Binary States: Does It Furnish an Explanation to the Robustness of Phylogenetic Trees against Lateral Transfers? In Evolutionary Bioinformatics, Vol. 11:213221, 2015. [Abstract] Keywords: circular split system, explicit network, from multistate characters, outerplanar, perfect, phylogenetic network, phylogeny, planar, polynomial, reconstruction, split. Note: http://dx.doi.org/10.4137%2FEBO.S28158.



Gabriel Cardona,
Joan Carles Pons and
Francesc Rosselló. A reconstruction problem for a class of phylogenetic networks with lateral gene transfers. In ALMOB, Vol. 10(28):115, 2015. Keywords: explicit network, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program LGTnetwork, reconstruction, software, treebased network. Note: http://dx.doi.org/10.1186/s130150150059z.



Leo van Iersel,
Steven Kelk,
Nela Lekic and
Leen Stougie. Approximation algorithms for nonbinary agreement forests. In SIDMA, Vol. 28(1):4966, 2014. Keywords: agreement forest, approximation, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1210.3211.
Toggle abstract
"Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomialtime 4approximation and a fixedparameter tractable (exact) algorithm that runs in O(4opoly(n)) time, where n = X and k is the number of components of the agreement forest minus one. Moreover, we show that a capproximation algorithm for nonbinary maf and a dapproximation algorithm for the classical problem Directed Feedback Vertex Set (dfvs) can be combined to yield a d(c+3)approximation for nonbinary maaf. The algorithms for maf have been implemented and made publicly available. © 2014 Society for Industrial and Applied Mathematics."



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



Steven Kelk and
Celine Scornavacca. Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable. In ALG, Vol. 68(4):886915, 2014. Keywords: explicit network, FPT, from clusters, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1108.3653.
Toggle abstract
"Here we show that, given a set of clusters C on a set of taxa X, where X=n, it is possible to determine in time f(k)×poly(n) whether there exists a level≤k network (i.e. a network where each biconnected component has reticulation number at most k) that represents all the clusters in C in the softwired sense, and if so to construct such a network. This extends a result from Kelk et al. (in IEEE/ACM Trans. Comput. Biol. Bioinform. 9:517534, 2012) which showed that the problem is polynomialtime solvable for fixed k. By defining "kreticulation generators" analogous to "levelk generators", we then extend this fixed parameter tractability result to the problem where k refers not to the level but to the reticulation number of the whole network. © 2012 Springer Science+Business Media New York."



Hadi Poormohammadi,
Changiz Eslahchi and
Ruzbeh Tusserkani. TripNet: A Method for Constructing Rooted Phylogenetic Networks from Rooted Triplets. In PLoS ONE, Vol. 9(9):e106531, 2014. Keywords: explicit network, from triplets, heuristic, level k phylogenetic network, phylogenetic network, phylogeny, Program TripNet, reconstruction, software. Note: http://arxiv.org/abs/1201.3722.
Toggle abstract
"The problem of constructing an optimal rooted phylogenetic network from an arbitrary set of rooted triplets is an NPhard problem. In this paper, we present a heuristic algorithm called TripNet, which tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes from an arbitrary set of rooted triplets. Despite of current methods that work for dense set of rooted triplets, a key innovation is the applicability of TripNet to nondense set of rooted triplets. We prove some theorems to clarify the performance of the algorithm. To demonstrate the efficiency of TripNet, we compared TripNet with SIMPLISTIC. It is the only available software which has the ability to return some rooted phylogenetic network consistent with a given dense set of rooted triplets. But the results show that for complex networks with high levels, the SIMPLISTIC running time increased abruptly. However in all cases TripNet outputs an appropriate rooted phylogenetic network in an acceptable time. Also we tetsed TripNet on the Yeast data. The results show that Both TripNet and optimal networks have the same clustering and TripNet produced a level3 network which contains only one more reticulation node than the optimal network."



Leo van Iersel and
Vincent Moulton. Trinets encode treechild and level2 phylogenetic networks. In JOMB, Vol. 68(7):17071729, 2014. Keywords: explicit network, from trinets, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1210.0362.
Toggle abstract
"Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that level1 phylogenetic networks are encoded by their trinets, and also conjectured that all "recoverable" rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level2 networks and binary treechild networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets. © 2013 SpringerVerlag Berlin Heidelberg."



Anthony Labarre and
Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. In TCBB, Vol. 11(2):389397, 2014. Keywords: abstract network, from unrooted trees, heuristic, NP complete, phylogenetic network, phylogeny, reconstruction. Note: https://halupecupem.archivesouvertes.fr/hal00855669.
Toggle abstract
"Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of t partially labelled trees. Although algorithms have been proposed for solving that problem on two graphs, the complexity of the general problem on trees remains unknown. In this paper, we show that the corresponding decision problem is NPcomplete for t=3. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the idpsystem, and assess the performance of both methods on randomly generated data. © 20042012 IEEE."





Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In Journal of Discrete Algorithms, Vol. 25:6678, 2014. Keywords: distance between networks, explicit network, from network, galled network, phylogenetic network, phylogeny, polynomial, triplet distance.
Toggle abstract
"We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a socalled galled tree with n leaves then the rooted triplet distance can be computed in o(n2.687) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance between two galled trees to that of counting monochromatic and almostmonochromatic triangles in an undirected, edgecolored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new algorithmic results that may be of independent interest: (i) the number of triangles in a connected, undirected, uncolored graph with m edges can be computed in o(m1.408) time; (ii) if G is a connected, undirected, edgecolored graph with n vertices and C is a subset of the set of edge colors then the number of monochromatic triangles of G with colors in C can be computed in o(n2.687) time; and (iii) if G is a connected, undirected, edgecolored graph with n vertices and R is a binary relation on the colors that is computable in O(1) time then the number of Rchromatic triangles in G can be computed in o(n2.687) time. © 2013 Elsevier B.V. All rights reserved."



Ward C Wheeler. Phyletic groups on networks. In Cladistics, Vol. 30(4):447451, 2014. Keywords: explicit network, from network, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1111/cla.12062.
Toggle abstract
"Three additional phyletic group types, "periphyletic," "epiphyletic", and "anaphyletic" (in addition to Hennigian mono, para, and polyphyletic) are defined in terms of trees and phylogenetic networks (trees with directed reticulate edges) via a generalization of the algorithmic definitions of Farris. These designations concern groups defined as monophyletic on trees, but with additional gains or losses of members from network edges. These distinctions should be useful in discussion of systems with nonvertical inheritance such as recombination between viruses, horizontal exchange between bacteria, hybridization in plants and animals, as well as human linguistic evolution. Examples are illustrated with IndoEuropean language groups. © The Willi Hennig Society 2013."



Sarah Bastkowski,
Andreas Spillner and
Vincent Moulton. Fishing for minimum evolution trees with NeighborNets. In IPL, Vol. 114(12):318, 2014. Keywords: circular split system, from distances, NeighborNet, phylogeny, polynomial.
Toggle abstract
"In evolutionary biology, biologists commonly use a phylogenetic tree to represent the evolutionary history of some set of species. A common approach taken to construct such a tree is to search through the space of all possible phylogenetic trees on the set so as to find one that optimizes some score function, such as the minimum evolution criterion. However, this is hampered by the fact that the space of phylogenetic trees is extremely large in general. Interestingly, an alternative approach, which has received somewhat less attention in the literature, is to instead search for trees within some set of bipartitions or splits of the set of species in question. Here we consider the problem of searching through a set of splits that is circular. Such sets can, for example, be generated by the NeighborNet algorithm for constructing phylogenetic networks. More specifically, we present an O(n4) time algorithm for finding an optimal minimum evolution tree in a circular set of splits on a set of species of size n. In addition, using simulations, we compare the performance of this algorithm when applied to NeighborNet output with that of FastME, a leading method for searching for minimum evolution trees in tree space. We find that, even though a circular set of splits represents just a tiny fraction of the total number of possible splits of a set, the trees obtained from circular sets compare quite favorably with those obtained with FastME, suggesting that the approach could warrant further investigation. © 2013 Elsevier B.V."



Lavanya Kannan and
Ward C Wheeler. Exactly Computing the Parsimony Scores on Phylogenetic Networks Using Dynamic Programming. In JCB, Vol. 21(4):303319, 2014. Keywords: explicit network, exponential algorithm, from network, from sequences, parsimony, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Scoring a given phylogenetic network is the first step that is required in searching for the best evolutionary framework for a given dataset. Using the principle of maximum parsimony, we can score phylogenetic networks based on the minimum number of state changes across a subset of edges of the network for each character that are required for a given set of characters to realize the input states at the leaves of the networks. Two such subsets of edges of networks are interesting in light of studying evolutionary histories of datasets: (i) the set of all edges of the network, and (ii) the set of all edges of a spanning tree that minimizes the score. The problems of finding the parsimony scores under these two criteria define slightly different mathematical problems that are both NPhard. In this article, we show that both problems, with scores generalized to adding substitution costs between states on the endpoints of the edges, can be solved exactly using dynamic programming. We show that our algorithms require O(mpk) storage at each vertex (per character), where k is the number of states the character can take, p is the number of reticulate vertices in the network, m = k for the problem with edge set (i), and m = 2 for the problem with edge set (ii). This establishes an O(nmpk2) algorithm for both the problems (n is the number of leaves in the network), which are extensions of Sankoff's algorithm for finding the parsimony scores for phylogenetic trees. We will discuss improvements in the complexities and show that for phylogenetic networks whose underlying undirected graphs have disjoint cycles, the storage at each vertex can be reduced to O(mk), thus making the algorithm polynomial for this class of networks. We will present some properties of the two approaches and guidance on choosing between the criteria, as well as traverse through the network space using either of the definitions. We show that our methodology provides an effective means to study a wide variety of datasets. © Copyright 2014, Mary Ann Liebert, Inc. 2014."



Jialiang Yang,
Stefan Grünewald,
Yifei Xu and
XiuFeng Wan. Quartetbased methods to reconstruct phylogenetic networks. In BMC Systems Biology, Vol. 80(21), 2014. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program QuartetMethods, Program QuartetNet, Program SplitsTree, reconstruction. Note: http://dx.doi.org/10.1186/17520509821
.
Toggle abstract
"Background: Phylogenetic networks are employed to visualize evolutionary relationships among a group of nucleotide sequences, genes or species when reticulate events like hybridization, recombination, reassortant and horizontal gene transfer are believed to be involved. In comparison to traditional distancebased methods, quartetbased methods consider more information in the reconstruction process and thus have the potential to be more accurate.Results: We introduce QuartetSuite, which includes a set of new quartetbased methods, namely QuartetS, QuartetA, and QuartetM, to reconstruct phylogenetic networks from nucleotide sequences. We tested their performances and compared them with other popular methods on two simulated nucleotide sequence data sets: one generated from a tree topology and the other from a complicated evolutionary history containing three reticulate events. We further validated these methods to two real data sets: a bacterial data set consisting of seven concatenated genes of 36 bacterial species and an influenza data set related to recently emerging H7N9 low pathogenic avian influenza viruses in China.Conclusion: QuartetS, QuartetA, and QuartetM have the potential to accurately reconstruct evolutionary scenarios from simple branching trees to complicated networks containing many reticulate events. These methods could provide insights into the understanding of complicated biological evolutionary processes such as bacterial taxonomy and reassortant of influenza viruses. © 2014 Yang et al.; licensee BioMed Central Ltd."



Kevin J. Liu,
Jingxuan Dai,
Kathy Truong,
Ying Song,
Michael H. Kohn and
Luay Nakhleh. An HMMBased Comparative Genomic Framework for Detecting Introgression in Eukaryotes. In PLoS ONE, Vol. 10(6):e1003649, 2014. Keywords: explicit network, from network, phylogenetic network, phylogeny, Program PhyloNetHMM. Note: http://arxiv.org/abs/1310.7989.
Toggle abstract
"One outcome of interspecific hybridization and subsequent effects of evolutionary forces is introgression, which is the integration of genetic material from one species into the genome of an individual in another species. The evolution of several groups of eukaryotic species has involved hybridization, and cases of adaptation through introgression have been already established. In this work, we report on PhyloNetHMMa new comparative genomic framework for detecting introgression in genomes. PhyloNetHMM combines phylogenetic networks with hidden Markov models (HMMs) to simultaneously capture the (potentially reticulate) evolutionary history of the genomes and dependencies within genomes. A novel aspect of our work is that it also accounts for incomplete lineage sorting and dependence across loci. Application of our model to variation data from chromosome 7 in the mouse (Mus musculus domesticus) genome detected a recently reported adaptive introgression event involving the rodent poison resistance gene Vkorc1, in addition to other newly detected introgressed genomic regions. Based on our analysis, it is estimated that about 9% of all sites within chromosome 7 are of introgressive origin (these cover about 13 Mbp of chromosome 7, and over 300 genes). Further, our model detected no introgression in a negative control data set. We also found that our model accurately detected introgression and other evolutionary processes from synthetic data sets simulated under the coalescent model with recombination, isolation, and migration. Our work provides a powerful framework for systematic analysis of introgression while simultaneously accounting for dependence across sites, point mutations, recombination, and ancestral polymorphism. © 2014 Liu et al."









Leo van Iersel,
Steven Kelk,
Nela Lekic and
Celine Scornavacca. A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees. In BMCB, Vol. 15(127):112, 2014. Keywords: agreement forest, approximation, explicit network, from rooted trees, phylogenetic network, phylogeny, Program CycleKiller, Program TerminusEst, reconstruction. Note: http://dx.doi.org/10.1186/1471210515127.



JohannMattis List,
Shijulal NelsonSathi,
Hans Geisler and
William Martin. Networks of lexical borrowing and lateral gene transfer in language and genome evolution. In BioEssays, Vol. 36(2):141150, 2014. Keywords: explicit network, minimal lateral network, phylogenetic network, Program lingpy. Note: http://dx.doi.org/10.1002/bies.201300096.
Toggle abstract
"Like biological species, languages change over time. As noted by Darwin, there are many parallels between language evolution and biological evolution. Insights into these parallels have also undergone change in the past 150 years. Just like genes, words change over time, and language evolution can be likened to genome evolution accordingly, but what kind of evolution? There are fundamental differences between eukaryotic and prokaryotic evolution. In the former, natural variation entails the gradual accumulation of minor mutations in alleles. In the latter, lateral gene transfer is an integral mechanism of natural variation. The study of language evolution using biological methods has attracted much interest of late, most approaches focusing on language tree construction. These approaches may underestimate the important role that borrowing plays in language evolution. Network approaches that were originally designed to study lateral gene transfer may provide more realistic insights into the complexities of language evolution. Editor's suggested further reading in BioEssays Linguistic evidence supports date for Homeric epics. © 2014 The Authors. BioEssays Published by WILEY Periodicals, Inc."



Juan Wang. A new algorithm to construct phylogenetic networks from trees. In Genetics and Molecular Research, Vol. 13(1):14561464, 2014. Keywords: explicit network, from clusters, heuristic, phylogenetic network, Program LNetwork, Program QuickCass, reconstruction. Note: http://dx.doi.org/10.4238/2014.March.6.4.
Toggle abstract
"Developing appropriate methods for constructing phylogenetic networks from tree sets is an important problem, and much research is currently being undertaken in this area. BIMLR is an algorithm that constructs phylogenetic networks from tree sets. The algorithm can construct a much simpler network than other available methods. Here, we introduce an improved version of the BIMLR algorithm, QuickCass. QuickCass changes the selection strategy of the labels of leaves below the reticulate nodes, i.e., the nodes with an indegree of at least 2 in BIMLR. We show that QuickCass can construct simpler phylogenetic networks than BIMLR. Furthermore, we show that QuickCass is a polynomialtime algorithm when the output network that is constructed by QuickCass is binary. © FUNPECRP."



Matthieu Willems,
Nadia Tahiri and
Vladimir Makarenkov. A new efficient algorithm for inferring explicit hybridization networks following the NeighborJoining principle. In JBCB, Vol. 12(5), 2014. Keywords: explicit network, from distances, heuristic, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Several algorithms and software have been developed for inferring phylogenetic trees. However, there exist some biological phenomena such as hybridization, recombination, or horizontal gene transfer which cannot be represented by a tree topology. We need to use phylogenetic networks to adequately represent these important evolutionary mechanisms. In this article, we present a new efficient heuristic algorithm for inferring hybridization networks from evolutionary distance matrices between species. The famous NeighborJoining concept and the leastsquares criterion are used for building networks. At each step of the algorithm, before joining two given nodes, we check if a hybridization event could be related to one of them or to both of them. The proposed algorithm finds the exact tree solution when the considered distance matrix is a tree metric (i.e. it is representable by a unique phylogenetic tree). It also provides very good hybrids recovery rates for large trees (with 32 and 64 leaves in our simulations) for both distance and sequence types of data. The results yielded by the new algorithm for real and simulated datasets are illustrated and discussed in detail. © Imperial College Press."







Joel Sjöstrand,
Ali Tofigh,
Vincent Daubin,
Lars Arvestad,
Bengt Sennblad and
Jens Lagergren. A Bayesian Method for Analyzing Lateral Gene Transfer. In Systematic Biology, Vol. 63(3):409420, 2014. Keywords: bayesian, duplication, from rooted trees, from sequences, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program JPrIMEDLTRS, reconstruction. Note: http://dx.doi.org/10.1093/sysbio/syu007.



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.





Katharina Huber and
Vincent Moulton. Encoding and Constructing 1Nested Phylogenetic Networks with Trinets. In ALG, Vol. 66(3):714738, 2013. Keywords: explicit network, from trinets, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://arxiv.org/abs/1110.0728.
Toggle abstract
"Phylogenetic networks are a generalization of phylogenetic trees that are used in biology to represent reticulate or nontreelike evolution. Recently, several algorithms have been developed which aim to construct phylogenetic networks from biological data using triplets, i.e. binary phylogenetic trees on 3element subsets of a given set of species. However, a fundamental problem with this approach is that the triplets displayed by a phylogenetic network do not necessarily uniquely determine or encode the network. Here we propose an alternative approach to encoding and constructing phylogenetic networks, which uses phylogenetic networks on 3element subsets of a set, or trinets, rather than triplets. More specifically, we show that for a special, wellstudied type of phylogenetic network called a 1nested network, the trinets displayed by a 1nested network always encode the network. We also present an efficient algorithm for deciding whether a dense set of trinets (i.e. one that contains a trinet on every 3element subset of a set) can be displayed by a 1nested network or not and, if so, constructs that network. In addition, we discuss some potential new directions that this new approach opens up for constructing and comparing phylogenetic networks. © 2012 Springer Science+Business Media, LLC."



Stefan Grünewald,
Andreas Spillner,
Sarah Bastkowski,
Anja Bögershausen and
Vincent Moulton. SuperQ: Computing Supernetworks from Quartets. In TCBB, Vol. 10(1):151160, 2013. Keywords: abstract network, circular split system, from quartets, heuristic, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, Program SuperQ, software, split network.
Toggle abstract
"Supertrees are a commonly used tool in phylogenetics to summarize collections of partial phylogenetic trees. As a generalization of supertrees, phylogenetic supernetworks allow, in addition, the visual representation of conflict between the trees that is not possible to observe with a single tree. Here, we introduce SuperQ, a new method for constructing such supernetworks (SuperQ is freely available at >www.uea.ac.uk/computing/superq.). It works by first breaking the input trees into quartet trees, and then stitching these together to form a special kind of phylogenetic network, called a split network. This stitching process is performed using an adaptation of the QNet method for split network reconstruction employing a novel approach to use the branch lengths from the input trees to estimate the branch lengths in the resulting network. Compared with previous supernetwork methods, SuperQ has the advantage of producing a planar network. We compare the performance of SuperQ to the Zclosure and Qimputation supernetwork methods, and also present an analysis of some published data sets as an illustration of its applicability. © 20042012 IEEE."



Teresa Piovesan and
Steven Kelk. A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees. In TCBB, Vol. 10(1):1825, 2013. Keywords: FPT, from rooted trees, phylogenetic network, phylogeny, Program TerminusEst, reconstruction. Note: http://arxiv.org/abs/1207.6090.
Toggle abstract
"Here, we present a new fixed parameter tractable algorithm to compute the hybridization number (r) of two rooted, not necessarily binary phylogenetic trees on taxon set (X) in time ((6r r) · poly(n)), where (n= X). The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on (X), and several insights from the softwired clusters literature. This yields a surprisingly simple and practical boundedsearch algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem. © 20042012 IEEE."



Stephen J. Willson. Reconstruction of certain phylogenetic networks from their treeaverage distances. In BMB, Vol. 75(10):18401878, 2013. Keywords: explicit network, from distances, galled tree, normal network, phylogenetic network, phylogeny, unicyclic network. Note: http://www.public.iastate.edu/~swillson/TreeAverageReconPaper9.pdf.
Toggle abstract
"Trees are commonly utilized to describe the evolutionary history of a collection of biological species, in which case the trees are called phylogenetic trees. Often these are reconstructed from data by making use of distances between extant species corresponding to the leaves of the tree. Because of increased recognition of the possibility of hybridization events, more attention is being given to the use of phylogenetic networks that are not necessarily trees. This paper describes the reconstruction of certain such networks from the treeaverage distances between the leaves. For a certain class of phylogenetic networks, a polynomialtime method is presented to reconstruct the network from the treeaverage distances. The method is proved to work if there is a single reticulation cycle. © 2013 Society for Mathematical Biology."







Jialiang Yang,
Stefan Grünewald and
XiuFeng Wan. QuartetNet: A Quartet Based Method to Reconstruct Phylogenetic Networks. In MBE, Vol. 30(5):12061217, 2013. Keywords: from quartets, phylogenetic network, phylogeny, Program QuartetNet, reconstruction.
Toggle abstract
"Phylogenetic networks can model reticulate evolutionary events such as hybridization, recombination, and horizontal gene transfer. However, reconstructing such networks is not trivial. Popular characterbased methods are computationally inefficient, whereas distancebased methods cannot guarantee reconstruction accuracy because pairwise genetic distances only reflect partial information about a reticulate phylogeny. To balance accuracy and computational efficiency, here we introduce a quartetbased method to construct a phylogenetic network from a multiple sequence alignment. Unlike distances that only reflect the relationship between a pair of taxa, quartets contain information on the relationships among four taxa; these quartets provide adequate capacity to infer a more accurate phylogenetic network. In applications to simulated and biological data sets, we demonstrate that this novel method is robust and effective in reconstructing reticulate evolutionary events and it has the potential to infer more accurate phylogenetic distances than other conventional phylogenetic network construction methods such as NeighborJoining, NeighborNet, and Split Decomposition. This method can be used in constructing phylogenetic networks from simple evolutionary events involving a few reticulate events to complex evolutionary histories involving a large number of reticulate events. A software called QuartetNet is implemented and available at http://sysbio.cvm.msstate.edu/QuartetNet/. © 2013 The Author."



ThiHau Nguyen,
Vincent Ranwez,
Stéphanie Pointet,
AnneMuriel Chifolleau Arigon,
JeanPhilippe Doyon and
Vincent Berry. Reconciliation and local gene tree rearrangement can be of mutual profit. In ALMOB, Vol. 8(12), 2013. Keywords: duplication, explicit network, from rooted trees, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program Mowgli, Program MowgliNNI, Program Prunier, reconstruction, software.
Toggle abstract
"Background: Reconciliation methods compare gene trees and species trees to recover evolutionary events such as duplications, transfers and losses explaining the history and composition of genomes. It is wellknown that gene trees inferred from molecular sequences can be partly erroneous due to incorrect sequence alignments as well as phylogenetic reconstruction artifacts such as long branch attraction. In practice, this leads reconciliation methods to overestimate the number of evolutionary events. Several methods have been proposed to circumvent this problem, by collapsing the unsupported edges and then resolving the obtained multifurcating nodes, or by directly rearranging the binary gene trees. Yet these methods have been defined for models of evolution accounting only for duplications and losses, i.e. can not be applied to handle prokaryotic gene families.Results: We propose a reconciliation method accounting for gene duplications, losses and horizontal transfers, that specifically takes into account the uncertainties in gene trees by rearranging their weakly supported edges. Rearrangements are performed on edges having a low confidence value, and are accepted whenever they improve the reconciliation cost. We prove useful properties on the dynamic programming matrix used to compute reconciliations, which allows to speedup the tree space exploration when rearrangements are generated by Nearest Neighbor Interchanges (NNI) edit operations. Experiments on synthetic data show that gene trees modified by such NNI rearrangements are closer to the correct simulated trees and lead to better event predictions on average. Experiments on real data demonstrate that the proposed method leads to a decrease in the reconciliation cost and the number of inferred events. Finally on a dataset of 30 k gene families, this reconciliation method shows a ranking of prokaryotic phyla by transfer rates identical to that proposed by a different approach dedicated to transfer detection [BMCBIOINF 11:324, 2010, PNAS 109(13):49624967, 2012].Conclusions: Prokaryotic gene trees can now be reconciled with their species phylogeny while accounting for the uncertainty of the gene tree. More accurate and more precise reconciliations are obtained with respect to previous parsimony algorithms not accounting for such uncertainties [LNCS 6398:93108, 2010, BIOINF 28(12): i283i291, 2012].A software implementing the method is freely available at http://www.atgcmontpellier.fr/Mowgli/. © 2013 Nguyen et al.; licensee BioMed Central Ltd."



Mukul S. Bansal,
Guy Banay,
Timothy J. Harlow,
J. Peter Gogarten and
Ron Shamir. Systematic inference of highways of horizontal gene transfer in prokaryotes. In BIO, Vol. 29(5):571579, 2013. Keywords: duplication, explicit network, from species tree, from unrooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program HiDe, Program RANGERDTL, reconstruction. Note: http://people.csail.mit.edu/mukul/Bansal_Highways_Bioinformatics_2013.pdf.



Yun Yu,
R. Matthew Barnett and
Luay Nakhleh. Parsimonious Inference of Hybridization in the Presence of Incomplete Lineage Sorting. In Systematic Biology, Vol. 62(5):738751, 2013. Keywords: from network, from rooted trees, hybridization, lineage sorting, parsimony, phylogenetic network, phylogeny, Program PhyloNet, reconstruction.
Toggle abstract
"Hybridization plays an important evolutionary role in several groups of organisms. A phylogenetic approach to detect hybridization entails sequencing multiple loci across the genomes of a group of species of interest, reconstructing their gene trees, and taking their differences as indicators of hybridization. However, methods that follow this approach mostly ignore population effects, such as incomplete lineage sorting (ILS). Given that hybridization occurs between closely related organisms, ILS may very well be at play and, hence, must be accounted for in the analysis framework. To address this issue, we present a parsimony criterion for reconciling gene trees within the branches of a phylogenetic network, and a local search heuristic for inferring phylogenetic networks from collections of genetree topologies under this criterion. This framework enables phylogenetic analyses while accounting for both hybridization and ILS. Further, we propose two techniques for incorporating information about uncertainty in genetree estimates. Our simulation studies demonstrate the good performance of our framework in terms of identifying the location of hybridization events, as well as estimating the proportions of genes that underwent hybridization. Also, our framework shows good performance in terms of efficiency on handling large data sets in our experiments. Further, in analysing a yeast data set, we demonstrate issues that arise when analysing real data sets. Although a probabilistic approach was recently introduced for this problem, and although parsimonious reconciliations have accuracy issues under certain settings, our parsimony framework provides a much more computationally efficient technique for this type of analysis. Our framework now allows for genomewide scans for hybridization, while also accounting for ILS. [Phylogenetic networks; hybridization; incomplete lineage sorting; coalescent; multilabeled trees.] © 2013 The Author(s). All rights reserved."



Juan Wang,
Maozu Guo,
Xiaoyan Liu,
Yang Liu,
Chunyu Wang,
Linlin Xing and
Kai Che. LNETWORK: An Efficient and Effective Method for Constructing Phylogenetic Networks. In BIO, Vol. 29(18):22692276, 2013. Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, Program LNetwork, reconstruction, software.
Toggle abstract
"Motivation: The evolutionary history of species is traditionally represented with a rooted phylogenetic tree. Each tree comprises a set of clusters, i.e. subsets of the species that are descended from a common ancestor. When rooted phylogenetic trees are built from several different datasets (e.g. from different genes), the clusters are often conflicting. These conflicting clusters cannot be expressed as a simple phylogenetic tree; however, they can be expressed in a phylogenetic network. Phylogenetic networks are a generalization of phylogenetic trees that can account for processes such as hybridization, horizontal gene transfer and recombination, which are difficult to represent in standard treelike models of evolutionary histories. There is currently a large body of research aimed at developing appropriate methods for constructing phylogenetic networks from cluster sets. The Cass algorithm can construct a much simpler network than other available methods, but is extremely slow for large datasets or for datasets that need lots of reticulate nodes. The networks constructed by Cass are also greatly dependent on the order of input data, i.e. it generally derives different phylogenetic networks for the same dataset when different input orders are used.Results: In this study, we introduce an improved Cass algorithm, Lnetwork, which can construct a phylogenetic network for a given set of clusters. We show that Lnetwork is significantly faster than Cass and effectively weakens the influence of input data order. Moreover, we show that Lnetwork can construct a much simpler network than most of the other available methods. © The Author 2013."



Juan Wang,
Maozu Guo,
Linlin Xing,
Kai Che,
Xiaoyan Liu and
Chunyu Wang. BIMLR: A Method for Constructing Rooted Phylogenetic Networks from Rooted Phylogenetic Trees. In Gene, Vol. 527(1):344351, 2013. Keywords: explicit network, from clusters, from rooted trees, phylogenetic network, phylogeny, Program BIMLR, Program Dendroscope, reconstruction, software.
Toggle abstract
"Rooted phylogenetic trees constructed from different datasets (e.g. from different genes) are often conflicting with one another, i.e. they cannot be integrated into a single phylogenetic tree. Phylogenetic networks have become an important tool in molecular evolution, and rooted phylogenetic networks are able to represent conflicting rooted phylogenetic trees. Hence, the development of appropriate methods to compute rooted phylogenetic networks from rooted phylogenetic trees has attracted considerable research interest of late. The CASS algorithm proposed by van Iersel et al. is able to construct much simpler networks than other available methods, but it is extremely slow, and the networks it constructs are dependent on the order of the input data. Here, we introduce an improved CASS algorithm, BIMLR. We show that BIMLR is faster than CASS and less dependent on the input data order. Moreover, BIMLR is able to construct much simpler networks than almost all other methods. BIMLR is available at http://nclab.hit.edu.cn/wangjuan/BIMLR/. © 2013 Elsevier B.V."



ZhiZhong Chen and
Lusheng Wang. An Ultrafast Tool for Minimum Reticulate Networks. In JCB, Vol. 20(1):3841, 2013. Keywords: agreement forest, explicit network, from rooted trees, phylogenetic network, phylogeny, Program ultraNet, reconstruction. Note: http://www.cs.cityu.edu.hk/~lwang/research/jcb2013.pdf.
Toggle abstract
"Due to hybridization events in evolution, studying different genes of a set of species may yield two or more related but different phylogenetic trees for the set of species. In this case, we want to combine the trees into a reticulate network with the fewest hybridization events. In this article, we develop a software tool (named UltraNet) for several fundamental problems related to the construction of minimum reticulate networks from two or more phylogenetic trees. Our experimental results show that UltraNet is much faster than all previous tools for these problems. © 2013 Mary Ann Liebert, Inc."







Alexey A. Morozov,
Yuri P. Galachyants and
Yelena V. Likhoshway. Inferring Phylogenetic Networks from Gene Order Data. In BMRI, Vol. 2013(503193):17, 2013. Keywords: abstract network, from distances, from gene order, NeighborNet, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split decomposition, split network.
Toggle abstract
"Existing algorithms allow us to infer phylogenetic networks from sequences (DNA, protein or binary), sets of trees, and distance matrices, but there are no methods to build them using the gene order data as an input. Here we describe several methods to build split networks from the gene order data, perform simulation studies, and use our methods for analyzing and interpreting different real gene order datasets. All proposed methods are based on intermediate data, which can be generated from genome structures under study and used as an input for network construction algorithms. Three intermediates are used: set of jackknife trees, distance matrix, and binary encoding. According to simulations and case studies, the best intermediates are jackknife trees and distance matrix (when used with NeighborNet algorithm). Binary encoding can also be useful, but only when the methods mentioned above cannot be used. © 2013 Alexey Anatolievich Morozov et al."



Celine Scornavacca,
Paprotny Wojciech,
Vincent Berry and
Vincent Ranwez. Representing a set of reconciliations in a compact way. In JBCB, Vol. 11(2):1250025, 2013. Keywords: duplication, explicit network, from network, from rooted trees, from species tree, phylogeny, Program GraphDTL, Program TERA, visualization. Note: http://hallirmm.ccsd.cnrs.fr/lirmm00818801.
Toggle abstract
"Comparative genomic studies are often conducted by reconciliation analyses comparing gene and species trees. One of the issues with reconciliation approaches is that an exponential number of optimal scenarios is possible. The resulting complexity is masked by the fact that a majority of reconciliation software pick up a random optimal solution that is returned to the enduser. However, the alternative solutions should not be ignored since they tell different stories that parsimony considers as viable as the output solution. In this paper, we describe a polynomial space and time algorithm to build a minimum reconciliation grapha graph that summarizes the set of all most parsimonious reconciliations. Amongst numerous applications, it is shown how this graph allows counting the number of nonequivalent most parsimonious reconciliations. © 2013 Imperial College Press."



Luay Nakhleh. Computational approaches to species phylogeny inference and gene tree reconciliation. In Trends in Ecology and Evolution, Vol. 28(12):719728, 2013. Keywords: from rooted trees, from species tree, phylogenetic network, phylogeny, reconstruction, survey. Note: http://bioinfo.cs.rice.edu/sites/bioinfo.cs.rice.edu/files/TREENakhleh13.pdf.
Toggle abstract
"An intricate relation exists between gene trees and species phylogenies, due to evolutionary processes that act on the genes within and across the branches of the species phylogeny. From an analytical perspective, gene trees serve as character states for inferring accurate species phylogenies, and species phylogenies serve as a backdrop against which gene trees are contrasted for elucidating evolutionary processes and parameters. In a 1997 paper, Maddison discussed this relation, reviewed the signatures left by three major evolutionary processes on the gene trees, and surveyed parsimony and likelihood criteria for utilizing these signatures to elucidate computationally this relation. Here, I review progress that has been made in developing computational methods for analyses under these two criteria, and survey remaining challenges. © 2013 Elsevier Ltd."



ThiHau Nguyen,
Vincent Ranwez,
Vincent Berry and
Celine Scornavacca. Support Measures to Estimate the Reliability of Evolutionary Events Predicted by Reconciliation Methods. In PLoS ONE, Vol. 8(10):e73667, 2013. Keywords: duplication, from rooted trees, from species tree, phylogenetic network, phylogeny, polynomial, Program GraphDTL, reconstruction. Note: http://dx.doi.org/10.1371/journal.pone.0073667.
Toggle abstract
"The genome content of extant species is derived from that of ancestral genomes, distorted by evolutionary events such as gene duplications, transfers and losses. Reconciliation methods aim at recovering such events and at localizing them in the species history, by comparing gene family trees to species trees. These methods play an important role in studying genome evolution as well as in inferring orthology relationships. A major issue with reconciliation methods is that the reliability of predicted evolutionary events may be questioned for various reasons: Firstly, there may be multiple equally optimal reconciliations for a given species treegene tree pair. Secondly, reconciliation methods can be misled by inaccurate gene or species trees. Thirdly, predicted events may fluctuate with method parameters such as the cost or rate of elementary events. For all of these reasons, confidence values for predicted evolutionary events are sorely needed. It was recently suggested that the frequency of each event in the set of all optimal reconciliations could be used as a support measure. We put this proposition to the test here and also consider a variant where the support measure is obtained by additionally accounting for suboptimal reconciliations. Experiments on simulated data show the relevance of event supports computed by both methods, while resorting to suboptimal sampling was shown to be more effective. Unfortunately, we also show that, unlike the majorityrule consensus tree for phylogenies, there is no guarantee that a single reconciliation can contain all events having above 50% support. In this paper, we detail how to rely on the reconciliation graph to efficiently identify the median reconciliation. Such median reconciliation can be found in polynomial time within the potentially exponential set of most parsimonious reconciliations. © 2013 Nguyen et al."



Mukul S. Bansal,
Eric J. Alm and
Manolis Kellis. Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss. In JCB, Vol. 20(10):738754, 2013. Keywords: duplication, from rooted trees, from species tree, loss, phylogenetic network, phylogeny, Program RANGERDTL, reconstruction. Note: http://www.engr.uconn.edu/~mukul/Bansal_JCB2013.pdf.
Toggle abstract
"Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplicationloss (DL) reconciliation leads to a unique maximumparsimony solution, duplicationtransferloss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn 2) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution. © 2013 Mary Ann Liebert, Inc."





Alberto Apostolico,
Matteo Comin,
Andreas W. M. Dress and
Laxmi Parida. Ultrametric networks: a new tool for phylogenetic analysis. In Algorithms for Molecular Biology, Vol. 8(7):110, 2013. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program Ultranet. Note: http://dx.doi.org/10.1186/1748718887.
Toggle abstract
"Background: The large majority of optimization problems related to the inference of distancebased trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.Results: This paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availability: http://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html. © 2013 Apostolico et al.; licensee BioMed Central Ltd."



Mehdi Layeghifard,
Pedro R. PeresNeto and
Vladimir Makarenkov. Inferring explicit weighted consensus networks to represent alternative evolutionary histories. In BMCEB, Vol. 13(274):125, 2013. Keywords: explicit network, from rooted trees, from species tree, phylogenetic network, phylogeny, Program ConsensusNetwork, reconstruction. Note: http://dx.doi.org/10.1186/1471214813274.
Toggle abstract
"Background: The advent of molecular biology techniques and constant increase in availability of genetic material have triggered the development of many phylogenetic tree inference methods. However, several reticulate evolution processes, such as horizontal gene transfer and hybridization, have been shown to blur the species evolutionary history by causing discordance among phylogenies inferred from different genes. Methods. To tackle this problem, we hereby describe a new method for inferring and representing alternative (reticulate) evolutionary histories of species as an explicit weighted consensus network which can be constructed from a collection of gene trees with or without prior knowledge of the species phylogeny. Results: We provide a way of building a weighted phylogenetic network for each of the following reticulation mechanisms: diploid hybridization, intragenic recombination and complete or partial horizontal gene transfer. We successfully tested our method on some synthetic and real datasets to infer the abovementioned evolutionary events which may have influenced the evolution of many species. Conclusions: Our weighted consensus network inference method allows one to infer, visualize and validate statistically major conflicting signals induced by the mechanisms of reticulate evolution. The results provided by the new method can be used to represent the inferred conflicting signals by means of explicit and easytointerpret phylogenetic networks. © 2013 Layeghifard et al.; licensee BioMed Central Ltd."



Gergely J. Szöllösi,
Eric Tannier,
Nicolas Lartillot and
Vincent Daubin. Lateral Gene Transfer from the Dead. In Systematic Biology, Vol. 62(3):386397, 2013. Keywords: duplication, lateral gene transfer, likelihood, loss, phylogeny, Program TERA, reconstruction. Note: http://dx.doi.org/10.1093/sysbio/syt003.
Toggle abstract
"In phylogenetic studies, the evolution of molecular sequences is assumed to have taken place along the phylogeny traced by the ancestors of extant species. In the presence of lateral gene transfer, however, this may not be the case, because the species lineage from which a gene was transferred may have gone extinct or not have been sampled. Because it is not feasible to specify or reconstruct the complete phylogeny of all species, we must describe the evolution of genes outside the represented phylogeny by modeling the speciation dynamics that gave rise to the complete phylogeny. We demonstrate that if the number of sampled species is small compared with the total number of existing species, the overwhelming majority of gene transfers involve speciation to and evolution along extinct or unsampled lineages. We show that the evolution of genes along extinct or unsampled lineages can to good approximation be treated as those of independently evolving lineages described by a few global parameters. Using this result, we derive an algorithm to calculate the probability of a gene tree and recover the maximumlikelihood reconciliation given the phylogeny of the sampled species. Examining 473 nearuniversal gene families from 36 cyanobacteria, we find that nearly a third of transfer events (28%) appear to have topological signatures of evolution along extinct species, but only approximately 6% of transfers trace their ancestry to before the common ancestor of the sampled cyanobacteria. © 2013 The Author(s)."



Gergely J. Szöllösi,
Wojciech Rosikiewicz,
Bastien Boussau,
Eric Tannier and
Vincent Daubin. Efficient Exploration of the Space of Reconciled Gene Trees. In Systematic Biology, Vol. 62(6):901912, 2013. Keywords: duplication, explicit network, lateral gene transfer, likelihood, loss, phylogeny, Program ALE, reconstruction. Note: http://arxiv.org/abs/1306.2167.
Toggle abstract
"Gene trees record the combination of genelevel events, such as duplication, transfer and loss (DTL), and specieslevel events, such as speciation and extinction. Gene treespecies tree reconciliation methods model these processes by drawing gene trees into the species tree using a series of gene and specieslevel events. The reconstruction of gene trees based on sequence alone almost always involves choosing between statistically equivalent or weakly distinguishable relationships that could be much better resolved based on a putative species tree. To exploit this potential for accurate reconstruction of gene trees, the space of reconciled gene trees must be explored according to a joint model of sequence evolution and gene treespecies tree reconciliation. Here we present amalgamated likelihood estimation (ALE), a probabilistic approach to exhaustively explore all reconciled gene trees that can be amalgamated as a combination of clades observed in a sample of gene trees. We implement the ALE approach in the context of a reconciliation model (Szöllo{double acute}si et al. 2013), which allows for the DTL of genes. We use ALE to efficiently approximate the sum of the joint likelihood over amalgamations and to find the reconciled gene tree that maximizes the joint likelihood among all such trees. We demonstrate using simulations that gene trees reconstructed using the joint likelihood are substantially more accurate than those reconstructed using sequence alone. Using realistic gene tree topologies, branch lengths, and alignment sizes, we demonstrate that ALE produces more accurate gene trees even if the model of sequence evolution is greatly simplified. Finally, examining 1099 gene families from 36 cyanobacterial genomes we find that joint likelihoodbased inference results in a striking reduction in apparent phylogenetic discord, with respectively. 24%, 59%, and 46% reductions in the mean numbers of duplications, transfers, and losses per gene family. The open source implementation of ALE is available from https://github.com/ssolo/ALE.git. © The Author(s) 2013."







Philippe Gambette and
Katharina Huber. On Encodings of Phylogenetic Networks of Bounded Level. In JOMB, Vol. 65(1):157180, 2012. Keywords: characterization, explicit network, from clusters, from rooted trees, from triplets, galled tree, identifiability, level k phylogenetic network, phylogenetic network, uniqueness, weak hierarchy. Note: http://hal.archivesouvertes.fr/hal00609130/en/.
Toggle abstract
"Phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Like phylogenetic trees, such networks canonically induce collections of phylogenetic trees, clusters, and triplets, respectively. Thus it is not surprising that many network approaches aim to reconstruct a phylogenetic network from such collections. Related to the wellstudied perfect phylogeny problem, the following question is of fundamental importance in this context: When does one of the above collections encode (i. e. uniquely describe) the network that induces it? For the large class of level1 (phylogenetic) networks we characterize those level1 networks for which an encoding in terms of one (or equivalently all) of the above collections exists. In addition, we show that three known distance measures for comparing phylogenetic networks are in fact metrics on the resulting subclass and give the diameter for two of them. Finally, we investigate the related concept of indistinguishability and also show that many properties enjoyed by level1 networks are not satisfied by networks of higher level. © 2011 SpringerVerlag."



Stephen J. Willson. CSD Homomorphisms Between Phylogenetic Networks. In TCBB, Vol. 9(4), 2012. Keywords: explicit network, from network, from quartets, phylogenetic network. Note: http://www.public.iastate.edu/~swillson/Relationships11IEEE.pdf, preliminary version entitled Relationships Among Phylogenetic Networks.
Toggle abstract
"Since Darwin, species trees have been used as a simplified description of the relationships which summarize the complicated network N of reality. Recent evidence of hybridization and lateral gene transfer, however, suggest that there are situations where trees are inadequate. Consequently it is important to determine properties that characterize networks closely related to N and possibly more complicated than trees but lacking the full complexity of N. A connected surjective digraph map (CSD) is a map f from one network N to another network M such that every arc is either collapsed to a single vertex or is taken to an arc, such that f is surjective, and such that the inverse image of a vertex is always connected. CSD maps are shown to behave well under composition. It is proved that if there is a CSD map from N to M, then there is a way to lift an undirected version of M into N, often with added resolution. A CSD map from N to M puts strong constraints on N. In general, it may be useful to study classes of networks such that, for any N, there exists a CSD map from N to some standard member of that class. © 2012 IEEE."



Steven Kelk,
Celine Scornavacca and
Leo van Iersel. On the elusiveness of clusters. In TCBB, Vol. 9(2):517534, 2012. Keywords: explicit network, from clusters, from rooted trees, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, Program Clustistic, reconstruction, software. Note: http://arxiv.org/abs/1103.1834.







Andreas Spillner,
Binh T. Nguyen and
Vincent Moulton. Constructing and Drawing Regular Planar Split Networks. In TCBB, Vol. 9(2):395407, 2012. Keywords: abstract network, from splits, phylogenetic network, phylogeny, reconstruction, visualization. Note: slides and presentation available at http://www.newton.ac.uk/programmes/PLG/seminars/062111501.html.
Toggle abstract
"Split networks are commonly used to visualize collections of bipartitions, also called splits, of a finite set. Such collections arise, for example, in evolutionary studies. Split networks can be viewed as a generalization of phylogenetic trees and may be generated using the SplitsTree package. Recently, the NeighborNet method for generating split networks has become rather popular, in part because it is guaranteed to always generate a circular split system, which can always be displayed by a planar split network. Even so, labels must be placed on the "outside" of the network, which might be problematic in some applications. To help circumvent this problem, it can be helpful to consider socalled flat split systems, which can be displayed by planar split networks where labels are allowed on the inside of the network too. Here, we present a new algorithm that is guaranteed to compute a minimal planar split network displaying a flat split system in polynomial time, provided the split system is given in a certain format. We will also briefly discuss two heuristics that could be useful for analyzing phylogeographic data and that allow the computation of flat split systems in this format in polynomial time. © 2006 IEEE."



 