Who is Who in Phylogenetic Networks

Publications related to 'SPR distance' : The SPR distance between two trees is the minimum number of "Subtree Pruning and Regrafting" moves required to convert one tree into the other. Warning: a sequence of SPR moves does not always correspond to a time-consistent sequence of gene transfer events (the SPR distance is a lower bound of the hybridization number as proved in Baroni et al. 2005)   Order by:   Type | Year

Only And Or     related to:

Associated keywords

agreement-forest approximation APX-hard bound distance-between-networks evaluation explicit-network FPT from-clusters from-network from-rooted-trees from-trees from-unrooted-trees heuristic hybridization inapproximability integer-linear-programming lateral-gene-transfer minimum-number NNI-distance NNI-moves normal-network NP-complete orientation phylogenetic-network phylogeny polynomial Program-EEEP Program-HorizStory Program-HybridInterleave Program-HybridNumber Program-LatTrans Program-PhyloNet Program-SPRDist reconstruction regular-network reticulation-visible-network software SPR-distance statistical-model TBR-distance tree-based-network tree-child-network

Article (Journal)

1 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." 2 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." 3 Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914-918, 2007. Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.         4 Mihaela Baroni, Charles Semple and Mike Steel. A framework for representing reticulate evolution. In ACOM, Vol. 8:398-401, 2004. Keywords: explicit network, from clusters, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSS04.pdf.         Toggle abstract "Acyclic directed graphs (ADGs) are increasingly being viewed as more appropriate for representing certain evolutionary relationships, particularly in biology, than rooted trees. In this paper, we develop a framework for the analysis of these graphs which we call hybrid phylogenies. We are particularly interested in the problem whereby one is given a set of phylogenetic trees and wishes to determine a hybrid phylogeny that 'embeds' each of these trees and which requires the smallest number of hybridisation events. We show that this quantity can be greatly reduced if additional species are involved, and investigate other combinatorial aspects of this and related questions." 5 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." 6 Peter J. Humphries and Charles Semple. Note on the hybridization number and subtree distance in phylogenetics. In Applied Mathematics Letters, Vol. 22(4):611-615, 2009. Keywords: explicit network, minimum number, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/HS08.pdf.         7 Lavanya Kannan, Hua Li and Arcady Mushegian. A Polynomial-Time Algorithm Computing Lower and Upper Bounds of the Rooted Subtree Prune and Regraft Distance. In JCB, Vol. 18(5):743-757, 2011. Keywords: bound, minimum number, polynomial, SPR distance. Note: http://dx.doi.org/10.1089/cmb.2010.0045.         Toggle abstract "Rooted, leaf-labeled trees are used in biology to represent hierarchical relationships of various entities, most notably the evolutionary history of molecules and organisms. Rooted Subtree Prune and Regraft (rSPR) operation is a tree rearrangement operation that is used to transform a tree into another tree that has the same set of leaf labels. The minimum number of rSPR operations that transform one tree into another is denoted by drSPR and gives a measure of dissimilarity between the trees, which can be used to compare trees obtained by different approaches, or, in the context of phylogenetic analysis, to detect horizontal gene transfer events by finding incongruences between trees of different evolving characters. The problem of computing the exact d rSPR measure is NP-hard, and most algorithms resort to finding sequences of rSPR operations that are sufficient for transforming one tree into another, thereby giving upper bound heuristics for the distance. In this article, we present an O(n4) recursive algorithm D-Clust that gives both lower bound and upper bound heuristics for the distance between trees with n shared leaves and also gives a sequence of operations that transforms one tree into another. Our experiments on simulated pairs of trees containing up to 100 leaves showed that the two bounds are almost equal for small distances, thereby giving the nearly-precise actual value, and that the upper bound tends to be close to the upper bounds given by other approaches for all pairs of trees. © Copyright 2011, Mary Ann Liebert, Inc. 2011." 8 Chris Whidden, Robert G. Beiko and Norbert Zeh. Fixed-Parameter Algorithms for Maximum Agreement Forests. In SICOMP, Vol. 42(4):1431-1466, 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 fixed-parameter 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 prune-and-regraft 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 depth-bounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems. © 2013 Society for Industrial and Applied Mathematics." 9 Andrew R. Francis, Katharina Huber, Vincent Moulton and Taoyang Wu. Bounds for phylogenetic network space metrics. In JOMB, Vol. 76(5):1229-1248, 2018. Keywords: bound, distance between networks, from network, NNI distance, NNI moves, phylogenetic network, phylogeny, SPR distance, TBR distance. Note: https://arxiv.org/abs/1702.05609.         10 Magnus Bordewich, Simone Linz and Charles Semple. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. In JTB, Vol. 423:1-12, 2017. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, reticulation-visible network, SPR distance, tree-based network, tree-child network. Note: https://simonelinz.files.wordpress.com/2017/04/bls171.pdf.         11 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.1-21, 2017. Keywords: distance between networks, explicit network, from network, NNI distance, NNI moves, phylogenetic network, phylogeny, SPR distance. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01572624/en/.         12 Remie Janssen, Mark Jones, Péter L. Erdös, Leo van Iersel and Celine Scornavacca. Exploring the tiers of rooted phylogenetic network space using tail moves. In BMB, Vol. 80(8):2177-2208, 2018. Keywords: distance between networks, explicit network, from network, NNI moves, orientation, phylogenetic network, phylogeny, SPR distance. Note: https://arxiv.org/abs/1708.07656.         13 Jonathan Klawitter. The SNPR neighbourhood of tree-child networks. In JGAA, Vol. 22(2):329-355, 2018. Keywords: distance between networks, phylogenetic network, phylogeny, SPR distance, tree-child network. Note: https://arxiv.org/abs/1707.09579         14 Jonathan Klawitter. The agreement distance of rooted phylogenetic networks. In DMTCS, Vol. 21(3):19.1-24, 2019. Keywords: agreement forest, distance between networks, explicit network, from network, phylogenetic network, phylogeny, SPR distance. Note: https://arxiv.org/abs/1806.05800.         15 Jonathan Klawitter and Simone Linz. On the Subnet Prune and Regraft Distance. In ELJC, Vol. 26(2):P2.3.1-23, 2019. Keywords: agreement forest, explicit network, phylogenetic network, phylogeny, reticulation-visible network, SPR distance, tree-based network, tree-child network. Note: https://arxiv.org/abs/1805.07839.

InProceedings

16 Cuong Than and Luay Nakhleh. SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions. In APBC08, Pages 251-260, 2008. Keywords: evaluation, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/apbc08.pdf.         17 Yufeng Wu and Jiayin Wang. Fast Computation of the Exact Hybridization Number of Two Phylogenetic Trees. In ISBRA10, Vol. 6053:203-214 of LNCS, springer, 2010. Keywords: agreement forest, explicit network, from rooted trees, hybridization, integer linear programming, minimum number, phylogenetic network, phylogeny, Program HybridNumber, Program SPRDist, SPR distance. Note: http://www.engr.uconn.edu/~ywu/Papers/ISBRA10WuWang.pdf.         Toggle abstract "Hybridization is a reticulate evolutionary process. An established problem on hybridization is computing the minimum number of hybridization events, called the hybridization number, needed in the evolutionary history of two phylogenetic trees. This problem is known to be NP-hard. In this paper, we present a new practical method to compute the exact hybridization number. Our approach is based on an integer linear programming formulation. Simulation results on biological and simulated datasets show that our method (as implemented in program SPRDist) is more efficient and robust than an existing method. © 2010 Springer-Verlag Berlin Heidelberg." 18 Hyun Jung Park, Guohua Jin and Luay Nakhleh. Algorithmic strategies for estimating the amount of reticulation from a collection of gene trees. In CSB10, 2010. Keywords: bound, from rooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/ParkEtAl-CSB2010.pdf.         19 Chris Whidden, Robert G. Beiko and Norbert Zeh. Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments. In Proceedings of the ninth International Symposium on Experimental Algorithms (SEA'10), Vol. 6049:141-153 of LNCS, springer, 2010. Keywords: agreement forest, explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, SPR distance. Note: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2010-03.pdf.         Toggle abstract "We improve on earlier FPT algorithms for computing a rooted maximum agreement forest (MAF) or a maximum acyclic agreement forest (MAAF) of a pair of phylogenetic trees. Their sizes give the subtree-prune-and-regraft (SPR) distance and the hybridization number of the trees, respectively. We introduce new branching rules that reduce the running time of the algorithms from O(3 kn) and O(3 kn log n) to O(2.42 kn) and O(2.42 kn log n), respectively. In practice, the speed up may be much more than predicted by the worst-case analysis.We confirm this intuition experimentally by computing MAFs for simulated trees and trees inferred from protein sequence data. We show that our algorithm is orders of magnitude faster and can handle much larger trees and SPR distances than the best previous methods, treeSAT and sprdist. © Springer-Verlag Berlin Heidelberg 2010."

MastersThesis

20 Chris Whidden. A Unifying View on Approximation and FPT of Agreement Forests. Master's thesis, Dalhousie University, Canada, 2009. Keywords: agreement forest, approximation, explicit network, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://web.cs.dal.ca/~whidden/MCSThesis09.pdf.

PhdThesis

21 Simone Linz. Reticulation in evolution. PhD thesis, Heinrich-Heine-University, Düsseldorf, Germany, 2008. Keywords: agreement forest, FPT, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, SPR distance, statistical model. Note: http://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=8505.         22 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.