Who is Who in Phylogenetic Networks

Publications of Year 2005

Article (Journal)

1 Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005. Keywords: agreement forest, from rooted trees, NP complete, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.         Toggle abstract "The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees." 2 Dave MacLeod, Robert L. Charlebois, W. Ford Doolittle and Eric Bapteste. Deduction of probable events of lateral gene transfer through comparison of phylogenetic trees by recursive consolidation and rearrangement. In BMCEB, Vol. 5(27), 2005. Keywords: explicit network, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program HorizStory, reconstruction, software. Note: http://dx.doi.org/10.1186/1471-2148-5-27.         Toggle abstract "Background: When organismal phylogenies based on sequences of single marker genes are poorly resolved, a logical approach is to add more markers, on the assumption that weak but congruent phylogenetic signal will be reinforced in such multigene trees. Such approaches are valid only when the several markers indeed have identical phylogenies, an issue which many multigene methods (such as the use of concatenated gene sequences or the assembly of supertrees) do not directly address. Indeed, even when the true history is a mixture of vertical descent for some genes and lateral gene transfer (LGT) for others, such methods produce unique topologies. Results: We have developed software that aims to extract evidence for vertical and lateral inheritance from a set of gene trees compared against an arbitrary reference tree. This evidence is then displayed as a synthesis showing support over the tree for vertical inheritance, overlaid with explicit lateral gene transfer (LGT) events inferred to have occurred over the history of the tree. Like splits-tree methods, one can thus identify nodes at which conflict occurs. Additionally one can make reasonable inferences about vertical and lateral signal, assigning putative donors and recipients. Conclusion: A tool such as ours can serve to explore the reticulated dimensionality of molecular evolution, by dissecting vertical and lateral inheritance at high resolution. By this, we mean that individual nodes can be examined not only for congruence, but also for coherence in light of LGT. We assert that our tools will facilitate the comparison of phylogenetic trees, and the interpretation of conflicting data. © 2005 MacLeod et al; licensee BioMed Central Ltd." 3 Victor Kunin, Leon Goldovsky, Nikos Darzentas and Christos A. Ouzounis. The net of life: Reconstructing the microbial phylogenetic network. In GR, Vol. 15:954-959, 2005. Note: http://dx.doi.org/10.1101/gr.3666505.         Toggle abstract "It has previously been suggested that the phylogeny of microbial species might be better described as a network containing vertical and horizontal gene transfer (HGT) events. Yet, all phylogenetic reconstructions so far have presented microbial trees rather than networks. Here, we present a first attempt to reconstruct such an evolutionary network, which we term the "net of life." We use available tree reconstruction methods to infer vertical inheritance, and use an ancestral state inference algorithm to map HGT events on the tree. We also describe a weighting scheme used to estimate the number of genes exchanged between pairs of organisms. We demonstrate that vertical inheritance constitutes the bulk of gene transfer on the tree of life. We term the bulk of horizontal gene flow between tree nodes as "vines," and demonstrate that multiple but mostly tiny vines interconnect the tree. Our results strongly suggest that the HGT network is a scale-free graph, a finding with important implications for genome evolution. We propose that genes might propagate extremely rapidly across microbial species through the HGT network, using certain organisms as hubs. ©2005 by Cold Spring Harbor Laboratory Press." 4 Derek Ruths and Luay Nakhleh. Recombination and phylogeny: effects and detection. In IJBRA, Pages 202-212, 2005. Note: http://www.cs.rice.edu/~nakhleh/Papers/IJBRA05.pdf.         5 David A. Morrison. Networks in phylogenetic analysis: new tools for population biology. In IJP, Vol. 35:567-582, 2005. Keywords: median network, NeighborNet, phylogenetic network, phylogeny, population genetics, Program Network, Program Spectronet, Program SplitsTree, Program T REX, Program TCS, reconstruction, reticulogram, split decomposition, survey. Note: http://hem.fyristorg.com/acacia/papers/networks.pdf.         6 Yun S. Song and Jotun Hein. Constructing Minimal Ancestral Recombination Graphs. In JCB, Vol. 12(2):147-169, 2005. Keywords: ARG, minimum number, recombination. Note: http://www.eecs.berkeley.edu/~yss/Pub/SH-JCB05.pdf.         7 Luay Nakhleh, Tandy Warnow, C. Randal Linder and Katherine St. John. Reconstructing reticulate evolution in species - theory and practice. In JCB, Vol. 12(6):796-811, 2005. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/NWLSjcb.pdf.         8 Mihaela Baroni, Stefan Grünewald, Vincent Moulton and Charles Semple. Bounding the number of hybridization events for a consistent evolutionary history. In JOMB, Vol. 51(2):171-182, 2005. Keywords: agreement forest, bound, explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BGMS05.pdf.         Toggle abstract "Evolutionary processes such as hybridisation, lateral gene transfer, and recombination are all key factors in shaping the structure of genes and genomes. However, since such processes are not always best represented by trees, there is now considerable interest in using more general networks instead. For example, in recent studies it has been shown that networks can be used to provide lower bounds on the number of recombination events and also for the number of lateral gene transfers that took place in the evolutionary history of a set of molecular sequences. In this paper we describe the theoretical performance of some related bounds that result when merging pairs of trees into networks. © Springer-Verlag 2005." 9 Richard C. Winkworth, David Bryant, Peter J. Lockhart, David Havell and Vincent Moulton. Biogeographic Interpretation of Splits Graphs: Least Squares Optimization of Branch Lengths. In Systematic Biology, Vol. 54(1):56-65, 2005. Keywords: abstract network, from distances, from network, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://www.math.auckland.ac.nz/~bryant/Papers/05Biogeographic.pdf.         10 Barbara R. Holland, Frédéric Delsuc and Vincent Moulton. Visualizing Conflicting Evolutionary Hypotheses in Large Collections of Trees: Using Consensus Networks to Study the Origins of Placentals and Hexapods. In Systematic Biology, Vol. 54(1):66-76, 2005. Keywords: consensus. Note: http://hal-sde.archives-ouvertes.fr/halsde-00193050/fr/.         Toggle abstract "Many phylogenetic methods produce large collections of trees as opposed to a single tree, which allows the exploration of support for various evolutionary hypotheses. However, to be useful, the information contained in large collections of trees should be summarized; frequently this is achieved by constructing a consensus tree. Consensus trees display only those signals that are present in a large proportion of the trees. However, by their very nature consensus trees require that any conflicts between the trees are necessarily disregarded. We present a method that extends the notion of consensus trees to allow the visualization of conflicting hypotheses in a consensus network. We demonstrate the utility of this method in highlighting differences amongst maximum likelihood bootstrap values and Bayesian posterior probabilities in the placental mammal phylogeny, and also in comparing the phylogenetic signal contained in amino acid versus nucleotide characters for hexapod monophyly. Copyright © Society of Systematic Biologists." 11 Insa Cassens, Patrick Mardulyn and Michel C. Milinkovitch. Evaluating Intraspecific Network Construction Methods Using Simulated Sequence Data: Do Existing Algorithms Outperform the Global Maximum Parsimony Approach? In Systematic Biology, Vol. 54(3):363-372, 2005. Keywords: abstract network, evaluation, from unrooted trees, haplotype network, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program TCS, reconstruction, software. Note: http://www.lanevol.org/LANE/publications_files/Cassens_etal_SystBio_2005.pdf.         12 Martyn Kennedy, Barbara R. Holland, Russel D. Gray and Hamish G. Spencer. Untangling Long Branches: Identifying Conflicting Phylogenetic Signals Using Spectral Analysis, Neighbor-Net, and Consensus Networks. In Systematic Biology, Vol. 54(4):620-633, 2005. Keywords: abstract network, consensus, NeighborNet, phylogenetic network, phylogeny. Note: http://awcmee.massey.ac.nz/people/bholland/pdf/Kennedy_etal_2005.pdf.         13 Bastienne Vriesendorp and Freek T. Bakker. Reconstructing patterns of reticulate evolution in angiosperms: what can we do? In Taxon, Vol. 54(3):593-604, 2005. Note: results cited in http://library.wur.nl/wda/dissertations/dis4239.pdf.         14 Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In TCS, Vol. 335(1):93-107, 2005. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf.         Toggle abstract "We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level-f phylogenetic networks N1,N2 satisfying f=O(logn); more precisely, its running time is O(|V(N1)|·|V(N2)|·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}. © 2005 Elsevier B.V. All rights reserved."

InProceedings

15 Ying-Jun He, Trinh N. D. Huynh, Jesper Jansson and Wing-Kin Sung. Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets. In APBC05, Pages 339-348, 2005. Note: https://dflund.se/~jj/Publications/forb_triplets4_APBC2005.pdf.         16 Sergey Bereg and Kathryn Bean. Constructing Phylogenetic Networks from Trees. In BIBE05, Pages 299-305, 2005. Keywords: evaluation, from distances, phylogenetic network, phylogeny, Program SplitsTree, Program T REX, reconstruction, split, split network. Note: http://dx.doi.org/10.1109/BIBE.2005.19.         Toggle abstract We present a new method of constructing a phylogenetic network from a given phylogenetic tree. It is based on a procedure that locally improves the tree. The procedure is quite general and can be applied to phylogenetic networks. By repeating local improvements user can introduce a given number of recombination cycles. A sequence of networks with decreasing distance deviation can be generated. The algorithm is efficient and shows a good performance on an example with plants. This is due to the fact that the update in every step is local and optimal. © 2005 IEEE. 17 Sergey Bereg and Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In BIBE05, Pages 320-323, 2005. Note: http://dx.doi.org/10.1109/BIBE.2005.46.         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 design an efficient algorithm for a special class of phylogenetic networks that can detect the existence of a network and constructs it. © 2005 IEEE. 18 Luay Nakhleh, Derek Ruths and Li-San Wang. RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer. In COCOON05, Vol. 3595:84-93 of LNCS, springer, 2005. Keywords: from rooted trees, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/COCOON05.pdf.         19 Luay Nakhleh, Guohua Jin, Fengmei Zhao and John Mellor-Crummey. Reconstructing Phylogenetic Networks Using Maximum Parsimony. In CSB05, Pages 93-102, 2005. Keywords: parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/CSB05.pdf.         20 Daniel H. Huson and Tobias Kloepper. Computing recombination networks from binary sequences. In ECCB05, Vol. 21(suppl. 2):ii159-ii165 of BIO, 2005. Keywords: from sequences, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1126.         Toggle abstract "Motivation:Phylogenetic networks are becoming an important tool in molecular evolution, as the evolutionary role of reticulate events, such as hybridization, horizontal gene transfer and recombination, is becoming more evident, and as the available data is dramatically increasing in quantity and quality. Results: This paper addresses the problem of computing a most parsimonious recombination network for an alignment of binary sequences that are assumed to have arisen under the 'infinite sites' model of evolution with recombinations. Using the concept of a splits network as the underlying datastructure, this paper shows how a recent method designed for the computation of hybridization networks can be extended to also compute recombination networks. A robust implementation of the approach is provided and is illustrated using a number of real biological datasets. © The Author 2005. Published by Oxford University Press. All rights reserved." 21 Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In ISAAC04, Vol. 3341:581-593 of LNCS, springer, 2005. Keywords: dynamic programming, MASN, nested network, NP complete, phylogenetic network, phylogeny, polynomial. Note: http://www.df.lth.se/~jj/Publications/nested7_ISAAC2004.pdf.         22 Cam Thach Nguyen, Nguyen Bao Nguyen and Wing-Kin Sung. Fast Algorithms for computing the Tripartition-based Distance between Phylogenetic Networks. In ISAAC05, Pages 402-411, 2005. Keywords: distance between networks, phylogenetic network, phylogeny, tripartition distance. Note: http://www.cs.washington.edu/homes/ncthach/Papers/ISAAC2006.pdf.         23 Yun S. Song, Yufeng Wu and Dan Gusfield. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution. In ISMB05, Vol. 21:i413-i422 of BIO, 2005. Keywords: integer linear programming, minimum number, Program HapBound, Program SHRUB, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1033.         Toggle abstract "Motivation: We are interested in studying the evolution of DNA single nucleotide polymorphism sequences which have undergone (meiotic) recombination. For a given set of sequences, computing the minimum number of recombinations needed to explain the sequences (with one mutation per site) is a standard question of interest, but it has been shown to be NP-hard, and previous algorithms that compute it exactly work either only on very small datasets or on problems with special structure. Results: In this paper, we present efficient, practical methods for computing both upper and lower bounds on the minimum number of needed recombinations, and for constructing evolutionary histories that explain the input sequences. We study in detail the efficiency and accuracy of these algorithms on both simulated and real data sets. The algorithms produce very close upper and lower bounds, which match exactly in a surprisingly wide range of data. Thus, with the use of new, very effective lower bounding methods and an efficient algorithm for computing upper bounds, this approach allows the efficient, exact computation of the minimum number of needed recombinations, with high frequency in a large range of data. When upper and lower bounds match, evolutionary histories found by our algorithm correspond to the most parsimonious histories. © The Author 2005. Published by Oxford University Press. All rights reserved." 24 Luay Nakhleh and Li-San Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919-926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.         25 Ho-Leung Chan, Jesper Jansson, Tak-Wah Lam and Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In MFCS05, Vol. 3618:224-235 of LNCS, springer, 2005. Keywords: from distances, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/11549345_20.         26 Wei-Shun Su, Tso-Ching Lee and Yaw-Ling Lin. Efficient Algorithms for Constructing Phylogenetic Networks with Restricted Recombinations. In NCS05, Pages 1-7, 2005. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, reconstruction. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.168.6735.         27 Elena Dubrova. Phylogenetic networks with edge-disjoint recombination cycles. In Proceedings of SPIE Bioengineered and Bioinspired Systems II (SPIE-BBS II), Vol. 5839:381-388, 2005. Keywords: galled tree, phylogenetic network, polynomial, site consistency. Note: http://dx.doi.org/10.1117/12.607910.         Toggle abstract "Phylogenetic analysis is a branch of biology that establishes the evolutionary relationships between living organisms. The goal of phylogenetic analysis is to determine the order and approximate timing of speciation events in the evolution of a given set of species. Phylogenetic networks allow to represent evolutionary histories that include events like recombination and hybridization. In this paper, we introduce a class of phylogenetic networks called extended galled-trees in which recombination cycles share no edge. We show that the site consistency problem, which is NP-hard in general, can be solved in polynomial time for this class of phylogenetic networks." 28 Bhaskar DasGupta, Sergio Ferrarini, Uthra Gopalakrishnan and Nisha Raj Paryani. Inapproximability results for the lateral gene transfer problem. In Proceedings of the Ninth Italian Conference on Theoretical Computer Science (ICTCS'05), Pages 182-195, springer, 2005. 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/ictcs-final.pdf.         29 Mohd Abdul Hai Zahid, Ankush Mittal and Ramesh C. Joshi. A Classification Based Approach for Root Unknown Phylogenetic Networks under Constrained Recombination. In Proceedings of the Second International Conference on Distributed Computing and Internet Technology (ICDCIT'05), Vol. 3816:592-603, 2005. Note: http://www.isical.ac.in/~zahid_t/publications/papers/paper_ICDCIT.pdf.         30 Dan Gusfield and Vikas Bansal. A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In RECOMB05, Vol. 3500:217-232 of LNCS, springer, 2005. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, polynomial, recombination, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/gusfieldrecomb.pdf.         31 Daniel H. Huson, Tobias Kloepper, Peter J. Lockhart and Mike Steel. Reconstruction of Reticulate Networks from Gene Trees. In RECOMB05, Vol. 3500:233-249 of LNCS, springer, 2005. Keywords: from rooted trees, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://dx.doi.org/10.1007/11415770_18.         32 Trinh N. D. Huynh, Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265-280 of LNCS, springer, 2005. Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction. Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.         33 Vineet Bafna and Vikas Bansal. Improved recombination lower bounds for haplotype data. In RECOMB05, Vol. 3500:569-584 of LNCS, springer, 2005. Keywords: bound, minimum number, phylogeny, recombination. Note: http://www.cse.ucsd.edu/users/vbafna/pub/recomblb05.pdf.         34 Dung Nguyen, Alix Boc and Vladimir Makarenkov. HGT-Simulator : logiciel pour simuler des transferts horizontaux. In SFC05, 2005. Note: http://lacim.uqam.ca/~sfc05/Articles/Nguyen_%20Boc_Makarenkov.pdf.         35 Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SODA05, Pages 349-358, 2005. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://portal.acm.org/citation.cfm?id=1070481.         36 Luay Nakhleh and Li-San Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:82-99 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.         37 Rune Lyngsø, Yun S. Song and Jotun Hein. Minimum Recombination Histories by Branch and Bound. In WABI05, Vol. 3692:239-250 of LNCS, springer, 2005. Keywords: ARG, branch and bound, from sequences, minimum number, Program Beagle, recombination, reconstruction, software. Note: http://www.cs.ucdavis.edu/~yssong/Pub/WABI05-239.pdf.

InBook

38 David Bryant. Extending tree models to splits networks. In Lior Pachter and Bernd Sturmfels editors, Algebraic Statistics for Computational Biology, Pages 322-334, Cambridge University Press, 2005. Keywords: abstract network, from splits, likelihood, phylogenetic network, phylogeny, split, split network, statistical model. Note: http://www.math.auckland.ac.nz/~bryant/Papers/05ascbChapter.pdf.         39 Jotun Hein, Mikkel H. Schierup and Carsten Wiuf. The coalescent with recombination. In Gene Genealogies, Variation and Evolution, Pages 127-171, Oxford University Press, 2005.         40 Vincent Moulton and Katharina Huber. Phylogenetic Networks. In Olivier Gascuel editor, Mathematics of evolution and phylogeny, Pages 178-200, Oxford University Press, 2005.

MastersThesis

41 Derek Ruths. Applications of phylogenetic incongruence to detecting and reconstructing interspecific recombination and horizontal gene transfer. Master's thesis, Rice University, U.S.A., 2005. Keywords: explicit network, from rooted trees, from species tree, heuristic, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://hdl.handle.net/1911/17912.

Misc

42 Dan Gusfield. On the Full-Decomposition Optimality Conjecture for Phylogenetic Networks. 2005. Keywords: characterization, explicit network, from sequences, phylogenetic network, reconstruction. Note: UC Davis Computer Science Technical Report CSE-2005, http://wwwcsif.cs.ucdavis.edu/~gusfield/fullydecomp.pdf.