Who is Who in Phylogenetic Networks

Publications related to 'approximation' : See Wikipedia.   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network agreement-forest approximation APX-hard diversity explicit-network FPT from-binets from-network from-rooted-trees from-sequences from-species-tree from-subnetworks from-triplets galled-tree heuristic hybridization inapproximability lateral-gene-transfer level-k-phylogenetic-network minimum-number NP-complete parsimony phylogenetic-network phylogeny polynomial Program-CycleKiller Program-Dendroscope Program-HybridNET Program-Nepal Program-TerminusEst recombination reconstruction software split-network SPR-distance

Article (Journal)

1 Jaroslaw Byrka, Pawel Gawrychowski, Katharina Huber and Steven Kelk. Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. In Journal of Discrete Algorithms, Vol. 8(1):65-75, 2010. Keywords: approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/0710.3258.         Toggle abstract "The study of phylogenetic networks is of great interest to computational evolutionary biology and numerous different types of such structures are known. This article addresses the following question concerning rooted versions of phylogenetic networks. What is the maximum value of p ∈ [0, 1] such that for every input set T of rooted triplets, there exists some network N such that at least p | T | of the triplets are consistent with N? We call an algorithm that computes such a network (where p is maximum) worst-case optimal. Here we prove that the set containing all triplets (the full triplet set) in some sense defines p. Moreover, given a network N that obtains a fraction p′ for the full triplet set (for any p′), we show how to efficiently modify N to obtain a fraction ≥ p′ for any given triplet set T. We demonstrate the power of this insight by presenting a worst-case optimal result for level-1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p ≥ 0.61. We emphasize that, because we are taking | T | as a (trivial) upper bound on the size of an optimal solution for each specific input T, the results in this article do not exclude the existence of approximation algorithms that achieve approximation ratio better than p. Finally, we note that all the results in this article also apply to weighted triplet sets. © 2009 Elsevier B.V. All rights reserved." 2 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.         3 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." 4 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.         5 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In DAM, Vol. 104:281-300, 2000. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759.         Toggle abstract "Background: 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. Even for binary trees, exact solvers struggle to solve instances with reticulation number larger than 40-50.Results: Here we present CycleKiller and NonbinaryCycleKiller, the first methods to produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations.Conclusions: Using simulations, we demonstrate that these algorithms run quickly for large and difficult instances, producing solutions that are very close to optimality. As a spin-off from our simulations we also present TerminusEst, which is the fastest exact method currently available that can handle nonbinary trees: this is used to measure the accuracy of the NonbinaryCycleKiller algorithm. All three methods are based on extensions of previous theoretical work (SIDMA 26(4):1635-1656, TCBB 10(1):18-25, SIDMA 28(1):49-66) and are publicly available. We also apply our methods to real data. © 2014 van Iersel et al.; licensee BioMed Central Ltd." 6 Magnus Bordewich and Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):69-85, 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 NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1-1/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 polynomial-time (1-1/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 Springer-Verlag." 7 Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Celine Scornavacca and Leen Stougie. Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set. In SIDMA, Vol. 26(4):1635-1656, 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 polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time 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 NP-complete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomial-time 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." 8 Leo van Iersel, Steven Kelk, Nela Lekic and Leen Stougie. Approximation algorithms for nonbinary agreement forests. In SIDMA, Vol. 28(1):49-66, 2014. Keywords: agreement forest, approximation, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1210.3211.         Toggle abstract "Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4opoly(n)) time, where n = |X| and k is the number of components of the agreement forest minus one. Moreover, we show that a c-approximation algorithm for nonbinary maf and a d-approximation algorithm for the classical problem Directed Feedback Vertex Set (dfvs) can be combined to yield a d(c+3)-approximation for nonbinary maaf. The algorithms for maf have been implemented and made publicly available. © 2014 Society for Industrial and Applied Mathematics." 9 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):1-12, 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/1471-2105-15-127.         10 Leo van Iersel, Vincent Moulton, Eveline De Swart and Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):1135-1154, 2017. Keywords: approximation, explicit network, from binets, from subnetworks, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/s11538-017-0275-4.

InProceedings

11 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.         12 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. A New Linear-time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance. In ISBRA07, Vol. 4463:61-72 of LNCS, springer, 2007. Keywords: approximation, heuristic, parsimony, phylogenetic network, phylogeny, Program Nepal. Note: http://www.cs.rice.edu/~nakhleh/Papers/isbra07.pdf.         13 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.         14 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In CPM98, Vol. 1448:174-188 of LNCS, springer, 1998. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1007/BFb0030789.         15 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(430-440) 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 exponential-time 2-approximation (or 4-approximation 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 Springer-Verlag." 16 Chris Whidden and Norbert Zeh. A Unifying View on Approximation and FPT of Agreement Forests. In WABI09, Vol. 5724:390-402 of LNCS, Springer, 2009. Keywords: agreement forest, approximation, explicit network, FPT, minimum number, phylogenetic network, phylogeny, reconstruction. Note: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2009-02.pdf.         Toggle abstract "We provide a unifying view on the structure of maximum (acyclic) agreement forests of rooted and unrooted phylogenies. This enables us to obtain linear- or O(n log n)-time 3-approximation and improved fixed-parameter algorithms for the subtree prune and regraft distance between two rooted phylogenies, the tree bisection and reconnection distance between two unrooted phylogenies, and the hybridization number of two rooted phylogenies. © 2009 Springer Berlin Heidelberg."

MastersThesis

17 Puspal Bhabak. Improving the approximation ratio of the maximum agreement forest (MAF) on k trees and estimating the approximation ratio of the acyclic-MAF on k trees. Master's thesis, University of Windsor, Canada, 2011. Keywords: agreement forest, approximation, explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction. Note: http://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=1315&context=etd.         18 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.

Misc

19 Puspal Bhabak and Asish Mukhopadhyay. A 3-factor approximation algorithm for a Minimum Acyclic Agreement Forest on k rooted, binary phylogenetic trees. 2014. Keywords: agreement forest, approximation, explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1407.7125.