Who is Who in Phylogenetic Networks

Publications of Yufeng Wu     Order by:   Type | Year

Associated keywords

agreement-forest ARG bound explicit-network exponential-algorithm from-rooted-trees from-sequences heuristic hybridization integer-linear-programming minimum-number perfect phylogenetic-network phylogeny Program-HapBound Program-HybridNumber Program-PIRN Program-SHRUB Program-SPRDist recombination reconstruction software SPR-distance

Article (Journal)

1 Sajad Mirzaei and Yufeng Wu. Fast Construction of Near Parsimonious Hybridization Networks for Multiple Phylogenetic Trees. In TCBB, Vol. 13(3):565-570, 2016. Keywords: bound, explicit network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program PIRN, reconstruction, software. Note: http://www.engr.uconn.edu/~ywu/Papers/PIRNs-preprint.pdf.         2 Yufeng Wu. An Algorithm for Constructing Parsimonious Hybridization Networks with Multiple Phylogenetic Trees. In JCB, Vol. 20(10):792-804, 2013. Keywords: explicit network, exponential algorithm, from rooted trees, phylogenetic network, phylogeny, Program PIRN, reconstruction.         3 Yufeng Wu and Dan Gusfield. Efficient Computation of Minimum Recombination with Genotypes (not Haplotypes) In JBCB, Vol. 5(2(a)):181-200, 2007. Note: http://dx.doi.org/10.1142/S0219720007002631.         4 Yun S. Song, Zhihong Ding, Dan Gusfield, Charles Langley and Yufeng Wu. Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations. In JCB, Vol. 14(10):1273-1286, 2007. Keywords: ARG, from sequences, phylogenetic network, phylogeny, Program SHRUB, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2007.0096.         Toggle abstract "Meiotic recombination is a fundamental biological event and one of the principal evolutionary forces responsible for shaping genetic variation within species. In addition to its fundamental role, recombination is central to several critical applied problems. The most important example is "association mapping" in populations, which is widely hoped to help find genes that influence genetic diseases (Carlson et al., 2004; Clark, 2003). Hence, a great deal of recent attention has focused on problems of inferring the historical derivation of sequences in populations when both mutations and recombinations have occurred. In the algorithms literature, most of that recent work has been directed to single-crossover recombination. However, gene-conversion is an important, and more common, form of (two-crossover) recombination which has been much less investigated in the algorithms literature. In this paper, we explicitly incorporate gene-conversion into discrete methods to study historical recombination. We are concerned with algorithms for identifying and locating the extent of historical crossing-over and gene-conversion (along with single-nucleotide mutation), and problems of constructing full putative histories of those events. The novel technical issues concern the incorporation of gene-conversion into recently developed discrete methods (Myers and Griffiths, 2003; Song et al., 2005) that compute lower and upper-bound information on the amount of needed recombination without gene-conversion. We first examine the most natural extension of the lower bound methods from Myers and Griffiths (2003), showing that the extension can be computed efficiently, but that this extension can only yield weak lower bounds. We then develop additional ideas that lead to higher lower bounds, and show how to solve, via integer-linear programming, a more biologically realistic version of the lower bound problem. We also show how to compute effective upper bounds on the number of needed single-crossovers and gene-conversions, along with explicit networks showing a putative history of mutations, single-crossovers and gene-conversions. Both lower and upper bound methods can handle data with missing entries, and the upper bound method can be used to infer missing entries with high accuracy. We validate the significance of these methods by showing that they can be effectively used to distinguish simulation-derived sequences generated without gene-conversion from sequences that were generated with gene-conversion. We apply the methods to recently studied sequences of Arabidopsis thaliana, identifying many more regions in the sequences than were previously identified (Plagnol et al., 2006), where gene-conversion may have played a significant role. Demonstration software is available at www.csif.cs.ucdavis.edu/∼gusfield. © 2007 Mary Ann Liebert, Inc."

InProceedings

5 Yufeng Wu. An Algorithm for Constructing Parsimonious Hybridization Networks with Multiple Phylogenetic Trees. In RECOMB13, Vol. 7821:291-303 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 NP-hard, 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 Springer-Verlag." 6 Yufeng Wu. Close Lower and Upper Bounds for the Minimum Reticulate Network of Multiple Phylogenetic Trees. In ISMB10, Vol. 26(12):i140-i148 of BIO, 2010. Keywords: explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program PIRN, software. Note: http://dx.doi.org/10.1093/bioinformatics/btq198.         Toggle abstract "Motivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions. Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets. Availability: A software tool, PIRN, is available for download from the web page: http://www.engr.uconn.edu/ywu. Contact: ywu@engr.uconn.edu. Supplementary information: Supplementary data is available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press." 7 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." 8 Yufeng Wu and Dan Gusfield. A new recombination lower bound and the minimum perfect phylogenetic forest problem. In COCOON07, Vol. 4598:16-26 of LNCS, springer, 2007. Keywords: perfect, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1007/978-3-540-73545-8_5.         9 Yufeng Wu and Dan Gusfield. Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants. In CPM07, Vol. 4580:150-161 of LNCS, springer, 2007. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/CPM2007mosaic.pdf.         10 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.         11 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."