Who is Who in Phylogenetic Networks

Publications of Year 2006

Article (Journal)

1 Stephen J. Willson. Unique solvability of certain hybrid networks from their distances. In ACOM, Vol. 10(1):165-178, 2006. Keywords: from distances, from network, labeling, phylogenetic network, phylogeny. Note: http://www.public.iastate.edu/~swillson/Solvability.pdf.         2 Mihaela Baroni and Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.         Toggle abstract "We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg." 3 Patricia Buendia and Giri Narasimhan. Serial NetEvolve: A flexible utility for generating serially-sampled sequences along a tree or recombinant network. In BIO, Vol. 18(22):2313-2314, 2006. Keywords: generation, phylogenetic network, phylogeny, Program Serial NetEvolve, Program Treevolve, recombination, software. Note: http://dx.doi.org/10.1093/bioinformatics/btl387.         Toggle abstract "Summary: Serial NetEvolve is a flexible simulation program that generates DNA sequences evolved along a tree or recombinant network. It offers a user-friendly Windows graphical interface and a Windows or Linux simulator with a diverse selection of parameters to control the evolutionary model. Serial NetEvolve is a modification of the Treevolve program with the following additional features: simulation of serially-sampled data, the choice of either a clock-like or a variable rate model of sequence evolution, sampling from the internal nodes and the output of the randomly generated tree or network in our newly proposed NeTwick format. © 2006 Oxford University Press." 4 Monique M. Morin and Bernard M. E. Moret. NetGen: generating phylogenetic networks with diploid hybrids. In BIO, Vol. 22(15):1921-1923, 2006. Keywords: generation, hybridization, Program NetGen, software. Note: http://dx.doi.org/10.1093/bioinformatics/btl191.         Toggle abstract "Summary: NetGen is an event-driven simulator that creates phylogenetic networks by extending the birth-death model to include diploid hybridizations. DNA sequences are evolved in conjunction with the topology, enabling hybridization decisions to be based on contemporary evolutionary distances. NetGen supports variable rate lineages, root sequence specification, outgroup generation and many other options. This note describes the NetGen application and proposes an extension of the Newick format to accommodate phylogenetic networks. © 2006 Oxford University Press." 5 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Maximum Likelihood of Phylogenetic Networks. In BIO, Vol. 22(21):2604-2611, 2006. Keywords: explicit network, likelihood, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/NetworksML06.pdf, supplementary material: http://www.cs.rice.edu/~nakhleh/Papers/Supp-ML.pdf.         6 Stephen J. Willson. Unique Reconstruction of Tree-Like Phylogenetic Networks from Distances Between Leaves. In BMB, Vol. 68:919-944, 2006. Keywords: explicit network, from distances, identifiability, mrca network, phylogenetic network, phylogeny, reconstruction. Note: http://www.public.iastate.edu/~swillson/BMB05-07.rev8.pdf.         7 Robert G. Beiko and Nicholas Hamilton. Phylogenetic identification of lateral genetic transfer events. In BMCEB, Vol. 6(15), 2006. Keywords: evaluation, from rooted trees, from unrooted trees, lateral gene transfer, Program EEEP, Program HorizStory, Program LatTrans, reconstruction, software, SPR distance. Note: http://dx.doi.org/10.1186/1471-2148-6-15.         Toggle abstract "Background: Lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. Where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. An 'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft (SPR) operations, but finding the optimal such set of operations is NP-hard for comparisons between rooted trees, and may be so for unrooted trees as well. Results: Efficient Evaluation of Edit Paths (EEEP) is a new tree comparison algorithm that uses evolutionarily reasonable constraints to identify and eliminate many unproductive search avenues, reducing the time required to solve many edit path problems. The performance of EEEP compares favourably to that of other algorithms when applied to strictly bifurcating trees with specified numbers of SPR operations. We also used EEEP to recover edit paths from over 19 000 unrooted, incompletely resolved protein trees containing up to 144 taxa as part of a large phylogenomic study. While inferred protein trees were far more similar to a reference supertree than random trees were to each other, the phylogenetic distance spanned by random versus inferred transfer events was similar, suggesting that real transfer events occur most frequently between closely related organisms, but can span large phylogenetic distances as well. While most of the protein trees examined here were very similar to the reference supertree, requiring zero or one edit operations for reconciliation, some trees implied up to 40 transfer events within a single orthologous set of proteins. Conclusion: Since sequence trees typically have no implied root and may contain unresolved or multifurcating nodes, the strategy implemented in EEEP is the most appropriate for phylogenomic analyses. The high degree of consistency among inferred protein trees shows that vertical inheritance is the dominant pattern of evolution, at least for the set of organisms considered here. However, the edit paths inferred using EEEP suggest an important role for genetic transfer in the evolution of microbial genomes as well. © 2006Beiko and Hamilton; licensee BioMed Central Ltd." 8 Ying-Jun He, Trinh N. D. Huynh, Jesper Jansson and Wing-Kin Sung. Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets. In JBCB, Vol. 4(1):59-74, 2006. Note: http://www.df.lth.se/~jj/Publications/forb_triplets7_JBCB2006.pdf.         Toggle abstract "To construct a phylogenetic tree or phylogenetic network for describing the evolutionary history of a set of species is a well-studied problem in computational biology. One previously proposed method to infer a phylogenetic tree/network for a large set of species is by merging a collection of known smaller phylogenetic trees on overlapping sets of species so that no (or as little as possible) branching information is lost. However, little work has been done so far on inferring a phylogenetic tree/network from a specified set of trees when in addition, certain evolutionary relationships among the species are known to be highly unlikely. In this paper, we consider the problem of constructing a phylogenetic tree/network which is consistent with all of the rooted triplets in a given set C and none of the rooted triplets in another given set F. Although NP-hard in the general case, we provide some efficient exact and approximation algorithms for a number of biologically meaningful variants of the problem. © Imperial College Press." 9 Ho-Leung Chan, Jesper Jansson, Tak-Wah Lam and Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807-832, 2006. Keywords: explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf.         Toggle abstract "Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press." 10 Arvind Gupta, Ján Manuch, Xiaohong Zhao and Ladislav Stacho. Characterization of the existence of galled-tree networks. In JBCB, Vol. 4(6):1309-1328, 2006. Keywords: characterization, galled tree. Note: http://www.pims.math.ca/~manuch/papers/characterization_JBCB2006.pdf.         11 Bhaskar DasGupta, Sergio Ferrarini, Uthra Gopalakrishnan and Nisha Raj Paryani. Inapproximability results for the lateral gene transfer problem. In JCO, Vol. 11(4):387-405, 2006. Keywords: approximation, from rooted trees, from species tree, inapproximability, lateral gene transfer, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.uic.edu/~dasgupta/resume/publ/papers/t-scenario-3-reviewed-3.pdf.         12 Vincent Moulton and Katharina Huber. Phylogenetic networks from multi-labelled trees. In JOMB, Vol. 52(5):613-632, 2006. Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction. Note: http://www.uea.ac.uk/~a043878/jmb.pdf.         Toggle abstract "It is now quite well accepted that the evolutionary past of certain species is better represented by phylogenetic networks as opposed to trees. For example, polyploids are typically thought to have resulted through hybridization and duplication, processes that are probably not best represented as bifurcating speciation events. Based on the knowledge of a multi-labelled tree relating collection of polyploids, we present a canonical construction of a phylogenetic network that exhibits the tree. In addition, we prove that the resulting network is in some well-defined sense a minimal network having this property. © Springer-Verlag 2006." 13 Daniel H. Huson and David Bryant. Application of Phylogenetic Networks in Evolutionary Studies. In MBE, Vol. 23(2):254-267, 2006. Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, survey. Note: http://dx.doi.org/10.1093/molbev/msj030, software available from www.splitstree.org.         Toggle abstract "The evolutionary history of a set of taxa is usually represented by a phylogenetic tree, and this model has greatly facilitated the discussion and testing of hypotheses. However, it is well known that more complex evolutionary scenarios are poorly described by such models. Further, even when evolution proceeds in a tree-like manner, analysis of the data may not be best served by using methods that enforce a tree structure but rather by a richer visualization of the data to evaluate its properties, at least as an essential first step. Thus, phylogenetic networks should be employed when reticulate events such as hybridization, horizontal gene transfer, recombination, or gene duplication and loss are believed to be involved, and, even in the absence of such events, phylogenetic networks have a useful role to play. This article reviews the terminology used for phylogenetic networks and covers both split networks and reticulate networks, how they are defined, and how they can be interpreted. Additionally, the article outlines the beginnings of a comprehensive statistical framework for applying split network methods. We show how split networks can represent confidence sets of trees and introduce a conservative statistical test for whether the conflicting signal in a network is treelike. Finally, this article describes a new program, SplitsTree4, an interactive and comprehensive tool for inferring different types of phylogenetic networks from sequences, distances, and trees. © The Author 2005. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." 14 Mohd Abdul Hai Zahid, Ankush Mittal and Ramesh C. Joshi. A pattern recognition-based approach for phylogenetic network construction with constrained recombination. In Pattern Recognition, Vol. 39:2312-2322, 2006. Note: http://www.isical.ac.in/~zahid_t/publications/papers/revision 2.pdf.         15 Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):1098-1121, 2006. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf.         Toggle abstract "This paper considers the problem of determining whether a given set Τ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input Τ is dense, we solve the problem in O(|Τ|) time, which is optimal since the size of the input is Θ(|Τ|). In comparison, the previously fastest algorithm for this problem runs in O(|Τ|2) time. We also develop an optimal O(|Τ|)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with Τ, where L is the set of leaf labels in Τ, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set Τ of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 ·|Τ| of the rooted triplets in Τ. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in Τ. © 2006 Society for Industrial and Applied Mathematics." 16 Mihaela Baroni, Charles Semple and Mike Steel. Hybrids in Real Time. In Systematic Biology, Vol. 55(1):46-56, 2006. Keywords: agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network. Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf.         Toggle abstract "We describe some new and recent results that allow for the analysis and representation of reticulate evolution by nontree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. Copyright © Society of Systematic Biologists." 17 Charles Semple and Mike Steel. Unicyclic networks: compatibility and enumeration. In TCBB, Vol. 3(1):84-91, 2006. Keywords: counting, explicit network, galled tree, unicyclic network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/SS06.pdf.         18 Yun S. Song. A Concise Necessary and Sufficient Condition for the Existence of a Galled-Tree. In TCBB, Vol. 3(2):186-191, 2006. Keywords: characterization, from sequences, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.eecs.berkeley.edu/~yss/Pub/nasc4gall.pdf.         19 Sergey Bereg and Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In TCBB, Vol. 3(4), 2006. Note: http://www.utdallas.edu/~yzhang/Homepage/Papers/prep-tcbb.pdf.         Toggle abstract A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The ultrametric condition is very restrictive. In this paper we study phylogenetic networks that can be constructed assuming the molecular clock hypothesis. We characterize distance matrices that admit such networks for 3 and 4 taxa. We also design two algorithms for constructing networks optimizing the least-squares fit. 20 Jesper Jansson and Wing-Kin Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In TCS, Vol. 363(1):60-68, 2006. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt8_TCS2006.pdf.         Toggle abstract "We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O (| T |2) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O (| T |5 / 3)-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets. © 2006 Elsevier B.V. All rights reserved." 21 Esra Erdem, Vladimir Lifschitz and Don Ringe. Temporal phylogenetic networks and logic programming. In Theory and Practice of Logic Programming, Vol. 6:539-558, 2006. Note: http://arxiv.org/abs/cs/0508129v1.         22 Kim McBreen and Peter J. Lockhart. Reconstructing reticulate evolutionary histories of plants. In Trends in Plant Science, Vol. 11(8):103-122, 2006. Note: http://www.aseanbiodiversity.info/Abstract/51006032.pdf.

InProceedings

23 Iyad A. Kanj, Luay Nakhleh and Ge Xia. Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms. In COCOON06, Vol. 4112:299-308 of LNCS, springer, 2006. Note: http://www.cs.rice.edu/~nakhleh/Papers/cocoon06.pdf.         24 Yufeng Wu and Dan Gusfield. Efficient Computation of Minimum Recombination with Genotypes (not Haplotypes) In CSB06, Pages 147-156, 2006. Note: http://www.lifesciencessociety.org/CSB2006/Papers/131_Wu.pdf.         25 Vladimir Makarenkov, Alix Boc, Charles Delwiche, Alpha B. Diallo and Hervé Philippe. New Efficient Algorithm for Modeling Partial and Complete Gene Transfer Scenarios. In IFCS06, Pages 341-349, springer, 2006. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/IFCS_2006_M_et_al.pdf.         26 Cuong Than, Derek Ruths, Hideki Innan and Luay Nakhleh. Identifiability Issues in Phylogeny-Based Detection of Horizontal Gene Transfer. In Proceedings of the Fourth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'06), Vol. 4205:215-229 of LNCS, springer, 2006. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg06-final.pdf.         27 Juan Diego Trujillo and Carlos Cotta. An Evolutionary Approach to the Inference of Phylogenetic Networks. In Proceedings of the ninth Conference on Parallel Problem Solving from Nature (PPSN'IX), Vol. 4193:332-341 of LNCS, springer, 2006. Note: http://www.lcc.uma.es/~ccottap/papers/trujillo06ppsn.pdf.         28 Barbara R. Holland, Lars S. Jermiin and Vincent Moulton. Improved Consensus Network Techniques for Genome-Scale Phylogeny. In Proceedings of the SMBE Tri-National Young Investigators' Workshop 2005 (SMBE'05), Vol. 23(5):848-855 of MBE, 2006. Keywords: consensus. Note: http://dx.doi.org/10.1093/molbev/msj061.         29 Daniel H. Huson, Mike Steel and James B. Whitfield. Reducing Distortion in Phylogenetic Networks. In WABI06, Vol. 4175:150-161 of LNCS, springer, 2006. Keywords: phylogenetic network, reconstruction. Note: http://www.math.canterbury.ac.nz/~m.steel/research/Non_UC/files/distortion.pdf.

InBook

30 Guillaume Bourque and Louxin Zhang. Models and Methods in Comparative Genomics. In Chau-Wen Tseng editor, Advances in Computers, Special Volume: Computational Biology, Vol. 68, Elsevier, 2006. Keywords: from distances, from rooted trees, from sequences, galled tree, phylogenetic network, phylogeny, survey. Note: http://www.math.nus.edu.sg/~matzlx/papers/CompGen_ZLX.pdf.         31 Tetsuo Asano, Patricia Evans, Ryuhei Uehara and Gabriel Valiente. Site Consistency in Phylogenetic Networks with Recombination. In C. S. Iliopoulos, K. Park and K. Steinhöfel editors, Algorithms in Bioinformatics, Vol. 6:15-26 of Texts in Algorithmics, College Publications, 2006.         32 Vladimir Makarenkov, Dmytro Kevorkov and Pierre Legendre. Phylogenetic Network Construction Approaches. In Applied Mycology and Biotechnology, Vol. 6:61-97, 2006. Keywords: from distances, hybridization, lateral gene transfer, median network, NeighborNet, netting, Program Arlequin, Program Network, Program Pyramids, Program Reticlad, Program SplitsTree, Program T REX, Program TCS, Program WeakHierarchies, pyramid, reticulogram, split, split decomposition, split network, survey, weak hierarchy. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/MKL_article.pdf.

PhdThesis

33 Pawel Górecki. Detection of horizontal gene transfer. PhD thesis, Warsaw University, Poland, 2006. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.         34 Olivier Gauthier. Utilisation de réseaux en analyse phylogénétique. PhD thesis, Université de Montréal, Canada, 2006. Note: http://igm.univ-mlv.fr/phylnet/PhylogeneticNetworks/docs/GauthierPhdThesis.pdf.