


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. Uprooted Phylogenetic Networks. In BMB, Vol. 79(9):20222048, 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.



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.



Sha Zhu and
James H. Degnan. Displayed Trees Do Not Determine Distinguishability Under the Network Multispecies Coalescent. In SB, Vol. 66(2):283298, 2017. Keywords: branch length, coalescent, explicit network, from network, likelihood, phylogenetic network, phylogeny, Program Hybridcoal, Program HybridLambda, Program PhyloNet, software, uniqueness. Note: presentation available at https://www.youtube.com/watch?v=JLYGTfEZG7g.



Andreas Gunawan,
Bhaskar DasGupta and
Louxin Zhang. A decomposition theorem and two algorithms for reticulationvisible networks. In Information and Computation, Vol. 252:161175, 2017. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulationvisible network, tree containment.. Note: https://www.cs.uic.edu/~dasgupta/resume/publ/papers/Infor_Comput_IC4848_final.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.









Magnus Bordewich,
Charles Semple and
Nihan Tokac. Constructing treechild networks from distance matrices. In Algorithmica, 2017. Keywords: compressed network, explicit network, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, tree child network, uniqueness. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSN17.pdf, to appear.



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.







Philippe Gambette,
Andreas Gunawan,
Anthony Labarre,
Stéphane Vialette and
Louxin Zhang. Solving the Tree Containment Problem in Linear Time for Nearly Stable Phylogenetic Networks. In DAM, 2017. Keywords: explicit network, from network, from rooted trees, nearlystable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://halupecupem.archivesouvertes.fr/hal01575001/en/, to appear.



Philippe Gambette,
Leo van Iersel,
Mark Jones,
Manuel Lafond,
Fabio Pardi and
Celine Scornavacca. Rearrangement Moves on Rooted Phylogenetic Networks. In PLoS Computational Biology, Vol. 13(8):e1005611.121, 2017. Keywords: distance between networks, explicit network, from network, NNI distance, phylogenetic network, phylogeny, SPR distance. Note: https://halupecupem.archivesouvertes.fr/hal01572624/en/.







Han Lai,
Maureen Stolzer and
Dannie Durand. Fast Heuristics for Resolving Weakly Supported Branches Using Duplication, Transfers, and Losses. In RECOMBCG17, Vol. 10562:298320 of LNCS, Springer, 2017. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction.



Sarah Bastkowski,
Daniel Mapleson,
Andreas Spillner,
Taoyang Wu,
Monika Balvociute and
Vincent Moulton. SPECTRE: a Suite of PhylogEnetiC Tools for Reticulate Evolution. 2017. Keywords: abstract network, NeighborNet, phylogenetic network, phylogeny, Program FlatNJ, Program QNet, Program SplitsTree, reconstruction, software, split network. Note: https://doi.org/10.1101/169177.







Klaus Schliep,
Alastair J. Potts,
David A. Morrison and
Guido W. Grimm. Intertwining phylogenetic trees and networks. In Methods in Ecology and Evolution, Vol. 8(10):12121220, 2017. Keywords: abstract network, from network, from unrooted trees, phylogenetic network, phylogeny, split network, visualization. Note: http://dx.doi.org/10.1111/2041210X.12760.













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.



Katharina Huber,
Vincent Moulton,
Mike Steel and
Taoyang Wu. Folding and unfolding phylogenetic trees and networks. In JOMB, Vol. 73(6):17611780, 2016. Keywords: compressed network, explicit network, FUstable network, NP complete, phylogenetic network, phylogeny, tree containment, tree sibling network. Note: http://arxiv.org/abs/1506.04438.



Steven Kelk,
Leo van Iersel,
Celine Scornavacca and
Mathias Weller. Phylogenetic incongruence through the lens of Monadic Second Order logic. In JGAA, Vol. 20(2):189215, 2016. Keywords: agreement forest, explicit network, FPT, from rooted trees, hybridization, minimum number, MSOL, phylogenetic network, phylogeny, reconstruction. Note: http://jgaa.info/accepted/2016/KelkIerselScornavaccaWeller2016.20.2.pdf.





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 PLoS ONE, 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.



Mareike Fischer,
Leo van Iersel,
Steven Kelk and
Celine Scornavacca. On Computing The Maximum Parsimony Score Of A Phylogenetic Network. In SIDMA, Vol. 29(1):559585, 2015. Keywords: APX hard, cluster containment, explicit network, FPT, from network, from sequences, integer linear programming, level k phylogenetic network, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, Program MPNet, reconstruction, software. Note: http://arxiv.org/abs/1302.2430.





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.





Quan Nguyen and
Teemu Roos. Likelihoodbased inference of phylogenetic networks from sequence data by PhyloDAG. In ALCOB15, Vol. 9199:126140 of LNCS, springer, 2015. Keywords: BIC, explicit network, from sequences, likelihood, phylogenetic network, phylogeny, Program PhyloDAG, reconstruction, software. Note: http://www.cs.helsinki.fi/u/ttonteri/pub/alcob2015.pdf.





Jittat Fakcharoenphol,
Tanee Kumpijit and
Attakorn Putwattana. A Faster Algorithm for the Tree Containment Problem for Binary Nearly Stable Phylogenetic Networks. In Proceedings of the The 12th International Joint Conference on Computer Science and Software Engineering (JCSSE'15), Pages 337342, IEEE, 2015. Keywords: dynamic programming, explicit network, from network, from rooted trees, nearlystable network, phylogenetic network, phylogeny, polynomial, tree containment.



Yun Yu and
Luay Nakhleh. A DistanceBased Method for Inferring Phylogenetic Networks in the Presence of Incomplete Lineage Sorting. In ISBRA15, Vol. 9096:378389 of LNCS, springer, 2015. Keywords: bootstrap, explicit network, from distances, heuristic, incomplete lineage sorting, phylogenetic network, phylogeny, reconstruction. Note: http://bioinfo.cs.rice.edu/sites/bioinfo.cs.rice.edu/files/YuNakhlehISBRA15.pdf.



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.





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



Yun Yu and
Luay Nakhleh. A maximum pseudolikelihood approach for phylogenetic networks. In RECOMBCG15, Vol. 16(Suppl 10)(S10):110 of BMC Genomics, BioMed Central, 2015. Keywords: explicit network, from rooted trees, hybridization, incomplete lineage sorting, likelihood, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, tripartition distance. Note: http://dx.doi.org/10.1186/1471216416S10S10.



Sha Zhu,
James H. Degnan,
Sharyn J. Goldstein and
Bjarki Eldon. HybridLambda: simulation of multiple merger and Kingman gene genealogies in species networks and species trees. In BMCB, Vol. 16(292):17, 2015. Keywords: explicit network, from network, phylogenetic network, phylogeny, Program HybridLambda, simulation, software. Note: http://dx.doi.org/10.1186/s128590150721y.









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.











Jessica W. Leigh and
David Bryant. PopART: fullfeature software for haplotype network construction. In Methods in Ecology and Evolution, Vol. 6(9):11101116, 2015. Keywords: abstract network, from sequences, haplotype network, MedianJoining, phylogenetic network, phylogeny, population genetics, Program PopART, Program TCS, software. Note: http://dx.doi.org/10.1111/2041210X.12410.



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.



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





Leo van Iersel and
Steven Kelk. Kernelizations for the hybridization number problem on multiple nonbinary trees. In WG14, Vol. 8747:299311 of LNCS, springer, 2014. Keywords: explicit network, from rooted trees, kernelization, minimum number, phylogenetic network, phylogeny, Program Treeduce, reconstruction. Note: http://arxiv.org/abs/1311.4045.



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



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













Vladimir Makarenkov,
Alix Boc and
Pierre Legendre. A New Algorithm for Inferring Hybridization Events Based on the Detection of Horizontal Gene Transfers. In
Fuad Aleskerov,
Boris Goldengorin and
Panos M. Pardalos editors, Clusters, Orders, and Trees: Methods and Applications, Vol. 92 of Springer Optimization and Its Applications, Springer, 2014. Keywords: explicit network, phylogenetic network, phylogeny, reconstruction.



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.



Monika Balvociute,
Andreas Spillner and
Vincent Moulton. FlatNJ: A Novel NetworkBased Approach to Visualize Evolutionary and Biogeographical Relationships. In Systematic Biology, Vol. 63(3):383396, 2014. Keywords: abstract network, flat, phylogenetic network, phylogeny, Program FlatNJ, Program SplitsTree, split network. Note: http://dx.doi.org/10.1093/sysbio/syu001.
Toggle abstract
"Split networks are a type of phylogenetic network that allow visualization of conflict in evolutionary data. We present a new method for constructing such networks called FlatNetJoining (FlatNJ). A key feature of FlatNJ is that it produces networks that can be drawn in the plane in which labels may appear inside of the network. For complex data sets that involve, for example, nonneutral molecular markers, this can allow additional detail to be visualized as compared to previous methods such as split decomposition and NeighborNet. We illustrate the application of FlatNJ by applying it to whole HIV genome sequences, where recombination has taken place, fluorescent proteins in corals, where ancestral sequences are present, and mitochondrial DNA sequences from gall wasps, where biogeographical relationships are of interest. We find that the networks generated by FlatNJ can facilitate the study of genetic variation in the underlying molecular sequence data and, in particular, may help to investigate processes such as intralocus recombination. FlatNJ has been implemented in Java and is freely available at www.uea.ac.uk/computing/software/ flatnj. [flat split system; NeighborNet; Phylogenetic network; QNet; split; split network.] © The Author(s) 2014."



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





Zhijiang Li. FixedParameter Algorithm for Hybridization Number of Two Multifurcating Trees. Master's thesis, Dalhousie University, Canada, 2014. Keywords: agreement forest, explicit network, FPT, from rooted trees, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://hdl.handle.net/10222/53976.



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











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



Leo van Iersel and
Simone Linz. A quadratic kernel for computing the hybridization number of multiple trees. In IPL, Vol. 113:318323, 2013. Keywords: explicit network, FPT, from rooted trees, kernelization, minimum number, phylogenetic network, phylogeny, Program Clustistic, Program MaafB, Program PIRN, reconstruction. Note: http://arxiv.org/abs/1203.4067, poster.
Toggle abstract
"It has recently been shown that the NPhard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixedparameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixedparameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel. © 2013 Elsevier B.V."



Chris Whidden,
Robert G. Beiko and
Norbert Zeh. FixedParameter Algorithms for Maximum Agreement Forests. In SICOMP, Vol. 42(4):14311466, 2013. Keywords: agreement forest, explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, SPR distance. Note: http://arxiv.org/abs/1108.2664, slides.
Toggle abstract
"We present new and improved fixedparameter algorithms for computing maximum agreement forests of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree pruneandregraft distance and, if the agreement forest is acyclic, to their hybridization number. These distance measures are essential tools for understanding reticulate evolution. Our algorithm for computing maximum acyclic agreement forests is the first depthbounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems. © 2013 Society for Industrial and Applied Mathematics."



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



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



Yufeng Wu. An Algorithm for Constructing Parsimonious Hybridization Networks with Multiple Phylogenetic Trees. In RECOMB13, Vol. 7821:291303 of LNCS, springer, 2013. Keywords: explicit network, exponential algorithm, from rooted trees, phylogenetic network, phylogeny, Program PIRN, reconstruction. Note: http://www.engr.uconn.edu/~ywu/Papers/ExactNetRecomb2013.pdf.
Toggle abstract
"Phylogenetic network is a model for reticulate evolution. Hybridization network is one type of phylogenetic network for a set of discordant gene trees, and "displays" each gene tree. A central computational problem on hybridization networks is: given a set of gene trees, reconstruct the minimum (i.e. most parsimonious) hybridization network that displays each given gene tree. This problem is known to be NPhard, and existing approaches for this problem are either heuristics or make simplifying assumptions (e.g. work with only two input trees or assume some topological properties). In this paper, we develop an exact algorithm (called PIRNC ) for inferring the minimum hybridization networks from multiple gene trees. The PIRNC algorithm does not rely on structural assumptions. To the best of our knowledge, PIRN C is the first exact algorithm for this formulation. When the number of reticulation events is relatively small (say four or fewer), PIRNC runs reasonably efficient even for moderately large datasets. For building more complex networks, we also develop a heuristic version of PIRNC called PIRNCH. Simulation shows that PIRNCH usually produces networks with fewer reticulation events than those by an existing method. © 2013 SpringerVerlag."







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.



Eric Bapteste,
Leo van Iersel,
Axel Janke,
Scott Kelchner,
Steven Kelk,
James O. McInerney,
David A. Morrison,
Luay Nakhleh,
Mike Steel,
Leen Stougie and
James B. Whitfield. Networks: expanding evolutionary thinking. In Trends in Genetics, Vol. 29(8):439441, 2013. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction. Note: http://bioinf.nuim.ie/wpcontent/uploads/2013/06/BaptesteTiG2013.pdf.
Toggle abstract
"Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes. © 2013 Elsevier Ltd."



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



ThiHau Nguyen. Réconciliations: corriger des arbres de gènes et inférer la fiabilité des événements évolutifs. PhD thesis, Université Montpellier 2, France, 2013. Keywords: duplication, explicit network, from rooted trees, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program Mowgli, Program MowgliNNI, reconstruction. Note: http://www.biumontpellier.fr/florabium/servlet/DocumentFileManager?source=ged&document=ged:IDOCS:247665&resolution=&recordId=theses%3ABIU_THESE%3A1789&file=.









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



Chris Whidden. Efficient Computation and Application of Maximum Agreement Forests. PhD thesis, Dalhousie University, Canada, 2013. Keywords: agreement forest, explicit network, FPT, from rooted trees, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://hdl.handle.net/10222/35349.





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.



Jeremy G. Sumner,
Barbara R. Holland and
Peter D. Jarvis. The algebra of the general Markov model on phylogenetic trees and networks. In BMB, Vol. 74(4):858880, 2012. Keywords: abstract network, phylogenetic network, phylogeny, split, split network, statistical model. Note: http://arxiv.org/abs/1012.5165.
Toggle abstract
"It is known that the Kimura 3ST model of sequence evolution on phylogenetic trees can be extended quite naturally to arbitrary split systems. However, this extension relies heavily on mathematical peculiarities of the associated Hadamard transformation, and providing an analogous augmentation of the general Markov model has thus far been elusive. In this paper, we rectify this shortcoming by showing how to extend the general Markov model on trees to include incompatible edges; and even further to more general network models. This is achieved by exploring the algebra of the generators of the continuoustime Markov chain together with the "splitting" operator that generates the branching process on phylogenetic trees. For simplicity, we proceed by discussing the two state case and then show that our results are easily extended to more states with little complication. Intriguingly, upon restriction of the two state general Markov model to the parameter space of the binary symmetric model, our extension is indistinguishable from the Hadamard approach only on trees; as soon as any incompatible splits are introduced the two approaches give rise to differing probability distributions with disparate structure. Through exploration of a simple example, we give an argument that our extension to more general networks has desirable properties that the previous approaches do not share. In particular, our construction allows for convergent evolution of previously divergent lineages; a property that is of significant interest for biological applications. © 2011 Society for Mathematical Biology."



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



Paul Phipps and
Sergey Bereg. Optimizing Phylogenetic Networks for Circular Split Systems. In TCBB, Vol. 9(2):535547, 2012. Keywords: abstract network, from distances, from splits, phylogenetic network, phylogeny, Program PhippsNetwork, reconstruction, software.
Toggle abstract
"We address the problem of realizing a given distance matrix by a planar phylogenetic network with a minimum number of faces. With the help of the popular software SplitsTree4, we start by approximating the distance matrix with a distance metric that is a linear combination of circular splits. The main results of this paper are the necessary and sufficient conditions for the existence of a network with a single face. We show how such a network can be constructed, and we present a heuristic for constructing a network with few faces using the first algorithm as the base case. Experimental results on biological data show that this heuristic algorithm can produce phylogenetic networks with far fewer faces than the ones computed by SplitsTree4, without affecting the approximation of the distance matrix. © 2012 IEEE."



Andreas Spillner and
Vincent Moulton. Optimal algorithms for computing edge weights in planar splitnetworks. In Journal of Applied Mathematics and Computing, Vol. 39(12):113, 2012. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://dx.doi.org/10.1007/s121900110506z.
Toggle abstract
"In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graphtheoretical structures represent collections of weighted bipartitions or splits of a finite set, and provide a means to display conflicting evolutionary signals. The weights associated to the splits are used to scale the edges in the network and are often computed using some distance matrix associated with the data. In this paper we present optimal polynomial time algorithms for three basic problems that arise in this context when computing split weights for planar splitnetworks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outerlabeled planar networks). As part of our analysis, we also derive a Crofton formula for full flat split systems, structures that naturally arise when constructing planar splitnetworks. © 2011 Korean Society for Computational and Applied Mathematics."



Magnus Bordewich and
Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):6985, 2012. Keywords: abstract network, approximation, diversity, phylogenetic network, polynomial, split network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS11.pdf.
Toggle abstract
"Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NPhard. However, it was recently shown that, for each setting, there is a polynomialtime (11/e)approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomialtime (11/e)approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al. © 2011 SpringerVerlag."



Celine Scornavacca,
Simone Linz and
Benjamin Albrecht. A first step towards computing all hybridization networks for two rooted binary phylogenetic trees. In JCB, Vol. 19:12271242, 2012. Keywords: agreement forest, explicit network, FPT, from rooted trees, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction. Note: http://arxiv.org/abs/1109.3268.
Toggle abstract
"Recently, considerable effort has been put into developing fast algorithms to reconstruct a rooted phylogenetic network that explains two rooted phylogenetic trees and has a minimum number of hybridization vertices. With the standard app1235roach to tackle this problem being combinatorial, the reconstructed network is rarely unique. From a biological point of view, it is therefore of importance to not only compute one network, but all possible networks. In this article, we make a first step toward approaching this goal by presenting the first algorithmcalled allMAAFsthat calculates all maximumacyclicagreement forests for two rooted binary phylogenetic trees on the same set of taxa. © Copyright 2012, Mary Ann Liebert, Inc. 2012."



ZhiZhong Chen and
Lusheng Wang. Algorithms for Reticulate Networks of Multiple Phylogenetic Trees. In TCBB, Vol. 9(2):372384, 2012. Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program CMPT, Program MaafB, reconstruction, software. Note: http://rnc.r.dendai.ac.jp/~chen/papers/rMaaf.pdf.
Toggle abstract
"A reticulate network N of multiple phylogenetic trees may have nodes with two or more parents (called reticulation nodes). There are two ways to define the reticulation number of N. One way is to define it as the number of reticulation nodes in N in this case, a reticulate network with the smallest reticulation number is called an optimal typeI reticulate network of the trees. The better way is to define it as the total number of parents of reticulation nodes in N minus the number of reticulation nodes in N ; in this case, a reticulate network with the smallest reticulation number is called an optimal typeII reticulate network of the trees. In this paper, we first present a fast fixedparameter algorithm for constructing one or all optimal typeI reticulate networks of multiple phylogenetic trees. We then use the algorithm together with other ideas to obtain an algorithm for estimating a lower bound on the reticulation number of an optimal typeII reticulate network of the input trees. To our knowledge, these are the first fixedparameter algorithms for the problems. We have implemented the algorithms in ANSI C, obtaining programs CMPT and MaafB. Our experimental data show that CMPT can construct optimal typeI reticulate networks rapidly and MaafB can compute better lower bounds for optimal typeII reticulate networks within shorter time than the previously best program PIRN designed by Wu. © 2006 IEEE."



Changiz Eslahchi,
Reza Hassanzadeh,
Ehsan Mottaghi,
Mahnaz Habibi,
Hamid Pezeshk and
Mehdi Sadeghi. Constructing circular phylogenetic networks from weighted quartets using simulated annealing. In MBIO, Vol. 235(2):123127, 2012. Keywords: abstract network, from quartets, heuristic, phylogenetic network, phylogeny, Program SAQNet, Program SplitsTree, reconstruction, simulated annealing, software, split network. Note: http://dx.doi.org/10.1016/j.mbs.2011.11.003.
Toggle abstract
"In this paper, we present a heuristic algorithm based on the simulated annealing, SAQNet, as a method for constructing phylogenetic networks from weighted quartets. Similar to QNet algorithm, SAQNet constructs a collection of circular weighted splits of the taxa set. This collection is represented by a split network. In order to show that SAQNet performs better than QNet, we apply these algorithm to both the simulated and actual data sets containing salmonella, Bees, Primates and Rubber data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree4 and compare the results. We find that SAQNet produces a better circular ordering and phylogenetic networks than QNet in most cases. SAQNet has been implemented in Matlab and is available for download at http://bioinf.cs.ipm.ac.ir/softwares/saq.net. © 2011 Elsevier Inc."



Benjamin Albrecht,
Celine Scornavacca,
Alberto Cenci and
Daniel H. Huson. Fast computation of minimum hybridization networks. In BIO, Vol. 28(2):191197, 2012. Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btr618.
Toggle abstract
"Motivation: Hybridization events in evolution may lead to incongruent gene trees. One approach to determining possible interspecific hybridization events is to compute a hybridization network that attempts to reconcile incongruent gene trees using a minimum number of hybridization events. Results: We describe how to compute a representative set of minimum hybridization networks for two given bifurcating input trees, using a parallel algorithm and provide a userfriendly implementation. A simulation study suggests that our program performs significantly better than existing software on biologically relevant data. Finally, we demonstrate the application of such methods in the context of the evolution of the Aegilops/Triticum genera. Availability and implementation: The algorithm is implemented in the program Dendroscope 3, which is freely available from www.dendroscope.org and runs on all three major operating systems. © The Author 2011. Published by Oxford University Press. All rights reserved."



Steven Kelk,
Leo van Iersel,
Nela Lekic,
Simone Linz,
Celine Scornavacca and
Leen Stougie. Cycle killer... qu'estce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set. In SIDMA, Vol. 26(4):16351656, 2012. Keywords: agreement forest, approximation, explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program CycleKiller, reconstruction. Note: http://arxiv.org/abs/1112.5359, about the title.
Toggle abstract
"We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa X has a constant factor polynomialtime approximation if and only if the problem of computing a minimumsize feedback vertex set in a directed graph (DFVS) has a constant factor polynomialtime approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NPcomplete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomialtime approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an O(log r log log r) approximation for the hybridization number where r is the correct value. Copyright © by SIAM."



Philippe Gambette,
Vincent Berry and
Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012. Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network. Note: http://hal.archivesouvertes.fr/hal00678046/en/.
Toggle abstract
"Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of levelk networks. In particular, we give an equivalence theorem between circular split systems and unrooted level1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted levelk phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press."



Yun Yu,
James H. Degnan and
Luay Nakhleh. The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection. In PLoS Genetics, Vol. 8(4):e1002660, 2012. Keywords: AIC, BIC, explicit network, hybridization, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1371/journal.pgen.1002660.
Toggle abstract
"Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa. © 2012 Yu et al."



Hyun Jung Park and
Luay Nakhleh. MURPAR: A fast heuristic for inferring parsimonious phylogenetic networks from multiple gene trees. In ISBRA12, Vol. 7292:213224 of LNCS, springer, 2012. Keywords: explicit network, from unrooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, software. Note: https://www.researchgate.net/profile/Hyun_Jung_Park2/publication/262318595_MURPAR_A_Fast_Heuristic_for_Inferring_Parsimonious_Phylogenetic_Networks_from_Multiple_Gene_Trees/links/54b7e7b50cf269d8cbf58cc4.pdf.
Toggle abstract
"Phylogenetic networks provide a graphical representation of evolutionary histories that involve nontreelike evolutionary events, such as horizontal gene transfer (HGT). One approach for inferring phylogenetic networks is based on reconciling gene trees, assuming all incongruence among the gene trees is due to HGT. Several mathematical results and algorithms, both exact and heuristic, have been introduced to construct and analyze phylogenetic networks. Here, we address the computational problem of inferring phylogenetic networks with minimum reticulations from a collection of gene trees. As this problem is known to be NPhard even for a pair of gene trees, the problem at hand is very hard. In this paper, we present an efficient heuristic, MURPAR, for inferring a phylogenetic network from a collection of gene trees by using pairwise reconciliations of trees in the collection. Given the development of efficient and accurate methods for pairwise gene tree reconciliations, MURPAR inherits this efficiency and accuracy. Further, the method includes a formulation for combining pairwise reconciliations that is naturally amenable to an efficient integer linear programming (ILP) solution. We show that MURPAR produces more accurate results than other methods and is at least as fast, when run on synthetic and biological data. We believe that our method is especially important for rapidly obtaining estimates of genomescale evolutionary histories that can be further refined by more detailed and computeintensive methods. © 2012 SpringerVerlag."



Pawel Górecki and
Jerzy Tiuryn. Inferring evolutionary scenarios in the duplication, loss and horizontal gene transfer model. In Logic and Program Semantics, Vol. 7230:83105 of LNCS, springer, 2012. Keywords: duplication, explicit network, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/9783642294853_7.
Toggle abstract
"An Htree is a formal model of evolutionary scenario. It can be used to represent any processes with gene duplication and loss, horizontal gene transfer (HGT) and speciation events. The model of Htrees, introduced in [26], is an extension of the duplicationloss model (DLmodel). Similarly to its ancestor, it has a number of interesting mathematical and biological properties. It is, however, more computationally complex than the DLmodel. In this paper, we primarily address the problem of inferring Htrees that are compatible with a given gene tree and a given phylogeny of species with HGTs. These results create a mathematical and computational foundation for a more general and practical problem of inferring HGTs from given gene and species trees with HGTs. We also demonstrate how our model can be used to support HGT hypotheses based on empirical data sets. © 2012 SpringerVerlag Berlin Heidelberg."



Mukul S. Bansal,
Eric J. Alm and
Manolis Kellis. Efficient Algorithms for the Reconciliation Problem with Gene Duplication, Horizontal Transfer, and Loss. In ISMB12, Vol. 28(12):i283i291 of BIO, 2012. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Angst, Program Mowgli, Program RANGERDTL, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/bts225.
Toggle abstract
"Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplicationtransferloss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distancedependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000fold speedup over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliationbased gene and species tree reconstruction methods. © The Author(s) 2012. Published by Oxford University Press."



Reza Hassanzadeh,
Changiz Eslahchi and
WingKin Sung. Constructing phylogenetic supernetworks based on simulated annealing. In MPE, Vol. 63(3):738744, 2012. Keywords: abstract network, from unrooted trees, heuristic, phylogenetic network, phylogeny, Program SNSA, reconstruction, simulated annealing, software, split network. Note: http://dx.doi.org/10.1016/j.ympev.2012.02.009.
Toggle abstract
Different partial phylogenetic trees can be derived from different sources of evidence and different methods. One important problem is to summarize these partial phylogenetic trees using a supernetwork. We propose a novel simulated annealing based method called SNSA which uses an optimization function to produce a simple network that still retains a great deal of phylogenetic information. We report the performance of this new method on real and simulated datasets. © 2012 Elsevier Inc.



Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In CPM12, Vol. 7354:385398 of LNCS, springer, 2012. Keywords: distance between networks, explicit network, from network, galled tree, phylogenetic network, phylogeny, polynomial, triplet distance. Note: http://www.df.lth.se/~jj/Publications/d_rt_for_Galled_Trees5_CPM_2012.pdf.
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(n 2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost monochromatic 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 related results that may be of independent interest. © 2012 SpringerVerlag."



Leo van Iersel,
Steven Kelk,
Nela Lekic and
Celine Scornavacca. A practical approximation algorithm for solving massive instances of hybridization number. In WABI12, Vol. 7534(430440) of LNCS, springer, 2012. Keywords: agreement forest, approximation, explicit network, from rooted trees, hybridization, phylogenetic network, phylogeny, Program CycleKiller, Program Dendroscope, Program HybridNET, reconstruction, software. Note: http://arxiv.org/abs/1205.3417.
Toggle abstract
"Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. In practice, exact solvers struggle to solve instances with reticulation number larger than 40. For such instances, one has to resort to heuristics and approximation algorithms. Here we present the algorithm CycleKiller which is the first approximation algorithm that can produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations. Theoretically, the algorithm is an exponentialtime 2approximation (or 4approximation in its fastest mode). However, using simulations we demonstrate that in practice the algorithm runs quickly for large and difficult instances, producing solutions within one percent of optimality. An implementation of this algorithm, which extends the theoretical work of [14], has been made publicly available. © 2012 SpringerVerlag."



Lavanya Kannan and
Ward C Wheeler. Maximum Parsimony on Phylogenetic Networks. In ALMOB, Vol. 7:9, 2012. Keywords: dynamic programming, explicit network, from sequences, heuristic, parsimony, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1186/1748718879.
Toggle abstract
"Background: Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a characterbased approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past.Results: In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain wellknown algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores.Conclusion: The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an inbuilt cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network. © 2012 Kannan and Wheeler; licensee BioMed Central Ltd."



Hyun Jung Park and
Luay Nakhleh. Inference of reticulate evolutionary histories by maximum likelihood:
The performance of information criteria. In RECOMBCG'12, Vol. 13(suppl 19):S12 of BMCB, 2012. Keywords: AIC, BIC, explicit network, heuristic, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://www.biomedcentral.com/14712105/13/S19/S12.



ZhiZhong Chen,
Lusheng Wang and
Satoshi Yamanaka. A fast tool for minimum hybridization networks. In BMCB, Vol. 13:155, 2012. Keywords: agreement forest, explicit network, from rooted trees, phylogenetic network, phylogeny, Program FastHN, reconstruction, software. Note: http://dx.doi.org/10.1186/1471210513155.
Toggle abstract
"Background: Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to combine the two phylogenetic trees into a hybridization network with the fewest hybridization events. This leads to three computational problems, namely, the problem of computing the minimum size of a hybridization network, the problem of constructing one minimum hybridization network, and the problem of enumerating a representative set of minimum hybridization networks. The previously best software tools for these problems (namely, Chen and Wang's HybridNet and Albrecht et al.'s Dendroscope 3) run very slowly for large instances that cannot be reduced to relatively small instances. Indeed, when the minimum size of a hybridization network of two given trees is larger than 23 and the problem for the trees cannot be reduced to relatively smaller independent subproblems, then HybridNet almost always takes longer than 1 day and Dendroscope 3 often fails to complete. Thus, a faster software tool for the problems is in need.Results: We develop a software tool in ANSI C, named FastHN, for the following problems: Computing the minimum size of a hybridization network, constructing one minimum hybridization network, and enumerating a representative set of minimum hybridization networks. We obtain FastHN by refining HybridNet with three ideas. The first idea is to preprocess the input trees so that the trees become smaller or the problem becomes to solve two or more relatively smaller independent subproblems. The second idea is to use a fast algorithm for computing the rSPR distance of two given phylognetic trees to cut more branches of the search tree in the exhaustivesearch stage of the algorithm. The third idea is that during the exhaustivesearch stage of the algorithm, we find two sibling leaves in one of the two forests (obtained from the given trees by cutting some edges) such that they are as far as possible in the other forest. As the result, FastHN always runs much faster than HybridNet. Unlike Dendroscope 3, FastHN is a singlethreaded program. Despite this disadvantage, our experimental data shows that FastHN runs substantially faster than the multithreaded Dendroscope 3 on a PC with multiple cores. Indeed, FastHN can finish within 16 minutes (on average on a Windows7 (x64) desktop PC with i72600 CPU) even if the minimum size of a hybridization network of two given trees is about 25, the trees each have 100 leaves, and the problem for the input trees cannot be reduced to two or more independent subproblems via cluster reductions. It is also worth mentioning that like HybridNet, FastHN does not use much memory (indeed, the amount of memory is at most quadratic in the input size). In contrast, Dendroscope 3 uses a huge amount of memory. Executables of FastHN for Windows XP (x86), Windows 7 (x64), Linux, and Mac OS are available (see the Results and discussion section for details).Conclusions: For both biological datasets and simulated datasets, our experimental results show that FastHN runs substantially faster than HybridNet and Dendroscope 3. The superiority of FastHN in speed over the previous tools becomes more significant as the hybridization number becomes larger. In addition, FastHN uses much less memory than Dendroscope 3 and uses the same amount of memory as HybridNet. © 2012 Chen et al.; licensee BioMed Central Ltd."



Michel Habib and
ThuHien To. Constructing a Minimum Phylogenetic Network from a Dense Triplet Set. In JBCB, Vol. 10(5):1250013, 2012. Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1103.2266.
Toggle abstract
"For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a levelk network having the minimum number of hybrid vertices and consistent with T, if there is any, in time O(T k+1 n⌊4k/3⌋+1). © 2012 Imperial College Press."



Ruogu Sheng and
Sergey Bereg. Approximating Metrics with Planar BoundaryLabeled Phylogenetic Networks. In JBCB, Vol. 10(6):1250017, 2012. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any fivepoint metric can be represented approximately by a planar boundarylabeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundarylabeled networks for any number of taxa. © 2012 Imperial College Press."



Maureen Stolzer,
Han Lai,
Minli Xu,
Deepa Sathaye,
Benjamin Vernot and
Dannie Durand. Inferring Duplications, Losses, Transfers, and Incomplete Lineage Sorting with NonBinary Species Trees. In ECCB12, Vol. 28(18):i409i415 of BIO, 2012. Keywords: duplication, explicit network, from rooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/bts386.
Toggle abstract
"Motivation: Gene duplication (D), transfer (T), loss (L) and incomplete lineage sorting (I) are crucial to the evolution of gene families and the emergence of novel functions.The history of these events can be inferred via comparison of gene and species trees, a process called reconciliation, yet current reconciliation algorithms model only a subset of these evolutionary processes. Results: We present an algorithm to reconcile a binary gene tree with a nonbinary species tree under a DTLI parsimony criterion. This is the first reconciliation algorithm to capture all four evolutionary processes driving tree incongruence and the first to reconcile nonbinary species trees with a transfer model. Our algorithm infers all optimal solutions and reports complete, temporally feasible event histories, giving the gene and species lineages in which each event occurred. It is fixedparameter tractable, with polytime complexity when the maximum species outdegree is fixed. Application of our algorithms to prokaryotic and eukaryotic data show that use of an incomplete event model has substantial impact on the events inferred and resulting biological conclusions. © The Author(s) 2012. Published by Oxford University Press."





Devin Robert Bickner. On normal networks. PhD thesis, Iowa State University, U.S.A., 2012. Keywords: distance between networks, explicit network, from network, from trees, normal network, phylogenetic network, phylogeny, polynomial, reconstruction, SPR distance. Note: http://gradworks.umi.com/3511361.pdf.





Adrià Alcalà Mena. Trivalent Graph isomorphism in polynomial time. Master's thesis, Universidad de Cantabria, Spain, 2012. Keywords: distance between networks, explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, Program SAGE. Note: http://arxiv.org/abs/1209.1040.



Joseph K. Pickrell and
Jonathan K. Pritchard. Inference of Population Splits and Mixtures from GenomeWide Allele Frequency Data. In PLoS Genetics, Vol. 8(11):e1002967, 2012. Keywords: explicit network, heuristic, likelihood, phylogenetic network, phylogeny, population genetics, Program TreeMix. Note: http://dx.doi.org/10.1371/journal.pgen.1002967.
Toggle abstract
"Many aspects of the historical relationships between populations in a species are reflected in genetic data. Inferring these relationships from genetic data, however, remains a challenging task. In this paper, we present a statistical model for inferring the patterns of population splits and mixtures in multiple populations. In our model, the sampled populations in a species are related to their common ancestor through a graph of ancestral populations. Using genomewide allele frequency data and a Gaussian approximation to genetic drift, we infer the structure of this graph. We applied this method to a set of 55 human populations and a set of 82 dog breeds and wild canids. In both species, we show that a simple bifurcating tree does not fully describe the data; in contrast, we infer many migration events. While some of the migration events that we find have been detected previously, many have not. For example, in the human data, we infer that Cambodians trace approximately 16% of their ancestry to a population ancestral to other extant East Asian populations. In the dog data, we infer that both the boxer and basenji trace a considerable fraction of their ancestry (9% and 25%, respectively) to wolves subsequent to domestication and that East Asian toy breeds (the Shih Tzu and the Pekingese) result from admixture between modern toy breeds and "ancient" Asian breeds. Software implementing the model described here, called TreeMix, is available at http://treemix.googlecode.com. © 2012 Pickrell, Pritchard."



Nick J. Patterson,
Priya Moorjani,
Yontao Luo,
Swapan Mallick,
Nadin Rohland,
Yiping Zhan,
Teri Genschoreck,
Teresa Webster and
David Reich. Ancient Admixture in Human History. In Genetics, Vol. 192(3):10651093, 2012. Keywords: explicit network, phylogenetic network, phylogeny, population genetics, Program AdmixTools. Note: http://genetics.med.harvard.edu/reich/Reich_Lab/Welcome_files/2012_Patterson_AncientAdmixture_Genetics.pdf.
Toggle abstract
"Population mixture is an important process in biology. We present a suite of methods for learning about population mixtures, implemented in a software package called ADMIXTOOLS, that support formal tests for whether mixture occurred and make it possible to infer proportions and dates of mixture. We also describe the development of a new single nucleotide polymorphism (SNP) array consisting of 629,433 sites with clearly documented ascertainment that was specifically designed for population genetic analyses and that we genotyped in 934 individuals from 53 diverse populations. To illustrate the methods, we give a number of examples that provide new insights about the history of human admixture. The most striking finding is a clear signal of admixture into northern Europe, with one ancestral population related to presentday Basques and Sardinians and the other related to presentday populations of northeast Asia and the Americas. This likely reflects a history of admixture between Neolithic migrants and the indigenous Mesolithic population of Europe, consistent with recent analyses of ancient bones from Sweden and the sequencing of the genome of the Tyrolean "Iceman." © 2012 by the Genetics Society of America."



Katharina Huber,
Vincent Moulton,
Andreas Spillner,
Sabine Storandt and
Radoslaw Suchecki. Computing a consensus of multilabeled trees. In ALENEX12, Pages 8492, 2012. Keywords: duplication, explicit network, exponential algorithm, phylogenetic network, phylogeny. Note: http://siam.omnibooksonline.com/2012ALENEX/data/papers/020.pdf.
Toggle abstract
In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential runtime in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.



Cayla McBee. Generalizing Fourier Calculus on Evolutionary Trees to Splits Networks. In ISPAN'12, Pages 149155, 2012. Keywords: abstract network, from sequences, phylogenetic network, phylogeny, split network, statistical model.
Toggle abstract
"Biologists have been interested in Phylogenetics, the study of evolutionary relatedness among various groups of organisms, for more than 140 years. In spite of this, it has only been in the last 40 years that advances in technology and the availability of DNA sequences have led to statistical, computational and algorithmic work on determining evolutionary relatedness between organisms. One method of determining historical relationships between organisms is to assume a group based evolutionary model and use a discrete Fourier transform. The 1993 paper 'Fourier Calculus on Evolutionary Trees' by L.A. Szekely, M.A. Steel and P.L. Erdos outlines this process. The transform presented in Szekely et al provides an invertible relationship between phylogenetic trees and expected frequencies of nucleotide patterns in nucleotide sequences. This implies that given a set of nucleotide sequences from various organisms it is possible to construct a phylogenetic tree that represents the historical relationships of those organisms. Some scenarios are poorly described by phylogenetic trees and there are biological and statistical reasons for using networks to model phylogenetic relationships. Given this motivation I have generalized Szekely et al's result to apply to a specific type of phylogenetic network known as a splits network. © 2012 IEEE."





Fenglou Mao,
David Williams,
Olga Zhaxybayeva,
Maria S. Poptsova,
Pascal Lapierre,
J. Peter Gogarten and
Ying Xu. Quartet decomposition server: a platform for analyzing phylogenetic trees. In BMCB, Vol. 13:123, 2012. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program Quartet Decomposition, reconstruction, software, split network.
Toggle abstract
"Background: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes.Results: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu.Conclusions: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts. © 2012 Mao et al.; licensee BioMed Central Ltd."



Donovan H. Parks and
Robert G. Beiko. Measuring Community Similarity with Phylogenetic Networks. In MBE, Vol. 29(12):39473958, 2012. Keywords: abstract network, diversity, phylogenetic network, phylogeny, split network. Note: poster available at http://dparks.wdfiles.com/localfiles/publications/SMBE_BetaDiversity_2011.pdf.
Toggle abstract
"Environmental drivers of biodiversity can be identified by relating patterns of community similarity to ecological factors. Community variation has traditionally been assessed by considering changes in species composition and more recently by incorporating phylogenetic information to account for the relative similarity of taxa. Here, we describe how an important class of measures including BrayCurtis, Canberra, and UniFrac can be extended to allow community variation to be computed on a phylogenetic network. We focus on phylogenetic split systems, networks that are produced by the widely used median network and neighbornet methods, which can represent incongruence in the evolutionary history of a set of taxa. Calculating β diversity over a split system provides a measure of community similarity averaged over uncertainty or conflict in the available phylogenetic signal. Our freely available software, Network Diversity, provides 11 qualitative (presenceabsence, unweighted) and 14 quantitative (weighted) networkbased measures of community similarity that model different aspects of community richness and evenness. We demonstrate the broad applicability of networkbased diversity approaches by applying them to three distinct data sets: pneumococcal isolates from distinct geographic regions, human mitochondrial DNA data from the Indonesian island of Nias, and proteorhodopsin sequences from the Sargasso and Mediterranean Seas. Our results show that major expected patterns of variation for these data sets are recovered using networkbased measures, which indicates that these patterns are robust to phylogenetic uncertainty and conflict. Nonetheless, networkbased measures of community similarity can differ substantially from measures ignoring phylogenetic relationships or from treebased measures when incongruent signals are present in the underlying data. Networkbased measures provide a methodology for assessing the robustness of βdiversity results in light of incongruent phylogenetic signal and allow β diversity to be calculated over widely used network structures such as median networks. © 2012 The Author 2012."



ZhiZhong Chen,
Fei Deng and
Lusheng Wang. Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers. In TCBB, Vol. 9(5):15151528, 2012. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.cityu.edu.hk/~lwang/research/tcbb2012c.pdf.
Toggle abstract
"We give a fixedparameter algorithm for the problem of enumerating all minimumcost LCAreconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m+3 k/c n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCAreconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m+2.78 k/cn). © 20042012 IEEE."





Ali Tofigh,
Mike Hallett and
Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.
Toggle abstract
"The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where socalled DTLscenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTLscenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTLscenarios is NPhard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixedparameter tractable algorithm for finding most parsimonious DTLscenarios. © 2011 IEEE."



Dan Levy and
Lior Pachter. The NeighborNet Algorithm. In Advances in Applied Mathematics, Vol. 47(2):240258, 2011. Keywords: abstract network, circular split system, evaluation, from distances, NeighborNet, phylogenetic network, phylogeny, split network. Note: http://arxiv.org/abs/math/0702515.
Toggle abstract
"The neighborjoining algorithm is a popular phylogenetics method for constructing trees from dissimilarity maps. The neighbornet algorithm is an extension of the neighborjoining algorithm and is used for constructing split networks. We begin by describing the output of neighbornet in terms of the tessellation of M̄0n(R) by associahedra. This highlights the fact that neighbornet outputs a tree in addition to a circular ordering and we explain when the neighbornet tree is the neighborjoining tree. A key observation is that the tree constructed in existing implementations of neighbornet is not a neighborjoining tree. Next, we show that neighbornet is a greedy algorithm for finding circular split systems of minimal balanced length. This leads to an interpretation of neighbornet as a greedy algorithm for the traveling salesman problem. The algorithm is optimal for Kalmanson matrices, from which it follows that neighbornet is consistent and has optimal radius 12. We also provide a statistical interpretation for the balanced length for a circular split system as the length based on weighted least squares estimates of the splits. We conclude with applications of these results and demonstrate the implications of our theorems for a recently published comparison of Papuan and Austronesian languages. © 2010 Elsevier Inc. All rights reserved."



Shlomo Moran,
Sagi Snir and
WingKin Sung. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds. In ACM Transactions on Algorithms, Vol. 7(4), 2011. Keywords: evaluation, galled tree, phylogenetic network. Note: http://www.cs.technion.ac.il/~moran/r/PS/gnetsTOA7Feb2007.pdf.
Toggle abstract
"A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as convex recoloring (CR).While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest. © 2011 ACM."



Katharina Huber,
Leo van Iersel,
Steven Kelk and
Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level1 Phylogenetic Networks. In TCBB, Vol. 8(3):607620, 2011. Keywords: explicit network, from triplets, galled tree, generation, heuristic, phylogenetic network, phylogeny, Program LEV1ATHAN, Program Lev1Generator, reconstruction, software. Note: http://arxiv.org/abs/0910.4067.
Toggle abstract
"Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level1 phylogenetic networksa type of network slightly more general than a phylogenetic treefrom triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponentialtime exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level1 network, it will find such a network. The potential of Lev1athan is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that Lev1athan is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise. © 2011 IEEE."



Josh Voorkamp né Collins,
Simone Linz and
Charles Semple. Quantifying hybridization in realistic time. In JCB, Vol. 18(10):13051318, 2011. Keywords: explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, software. Note: http://wwwcsif.cs.ucdavis.edu/~linzs/CLS10_interleave.pdf, software available at http://www.math.canterbury.ac.nz/~c.semple/software.shtml.
Toggle abstract
"Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulationfor example, horizontal gene transfer, hybridization, or recombinationhas influenced the evolution for a set of presentday species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NPhard and also fixedparameter tractable problem. In this article, we give a new fixedparameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleavinga technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixedparameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm that has previously been implemented. © 2011, Mary Ann Liebert, Inc."



Leo van Iersel and
Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ALG, Vol. 60(2):207235, 2011. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic. Note: http://dx.doi.org/10.1007/s0045300993330.
Toggle abstract
"A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing socalled reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomialtime algorithms for constructing a level1 respectively a level2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(T k+1), if k is a fixed upper bound on the level of the network. © 2009 The Author(s)."



JeanPhilippe Doyon,
Celine Scornavacca,
Konstantin Yu Gorbunov,
Gergely J. Szöllösi,
Vincent Ranwez and
Vincent Berry. An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications, and transfers. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMBCG'10), Vol. 6398:93108 of LNCS, springer, 2011. Keywords: branch length, duplication, dynamic programming, explicit network, from multilabeled tree, from species tree, from unrooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Mowgli, reconstruction. Note: http://www.lirmm.fr/~vberry/Publis/MPRDoyonEtAl.pdf, software available at http://www.atgcmontpellier.fr/MPR/.
Toggle abstract
"Tree reconciliation methods aim at estimating the evolutionary events that cause discrepancy between gene trees and species trees. We provide a discrete computational model that considers duplications, transfers and losses of genes. The model yields a fast and exact algorithm to infer time consistent and most parsimonious reconciliations. Then we study the conditions under which parsimony is able to accurately infer such events. Overall, it performs well even under realistic rates, transfers being in general less accurately recovered than duplications. An implementation is freely available at http://www.atgc montpellier.fr/MPR. © 2010 SpringerVerlag."



Leo van Iersel and
Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245255, 2011. Keywords: APX hard, explicit network, from clusters, from rooted trees, from sequences, from triplets, level k phylogenetic network, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1004.5332.
Toggle abstract
"Rooted phylogenetic networks are used to model nontreelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some welldefined sense simultaneously represents them all. We review these four models and investigate how they are related. Motivated by the parsimony principle, one often aims to construct a network that contains as few reticulations (nontreelike evolutionary events) as possible. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary (i.e. fully resolved) trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several computational complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge. © 2010 Elsevier Ltd."



 