Who is Who in Phylogenetic Networks

Publications list	Showing 451 - 480 (752 total)

451 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Comparison of tree-child phylogenetic networks. In TCBB, Vol. 6(4):552-569, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Bio PhyloNetwork, Program PhyloNetwork, tree sibling network, tree-child network. Note: http://arxiv.org/abs/0708.3499.         Toggle abstract "Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a tree-child phylogenetic network from its path multiplicity vectors, for computing the distance between two tree-child phylogenetic networks and for aligning a pair of tree-child phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/ phylonetworks/mudistance/. © 2009 IEEE." 452 Daniel H. Huson. Drawing Rooted Phylogenetic Networks. In TCBB, Vol. 6(1):103-109, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, visualization. Note: http://dx.doi.org/10.1109/TCBB.2008.58.         Toggle abstract "The evolutionary history of a collection of species is usually represented by a phylogenetic tree. Sometimes, phylogenetic networks are used as a means of representing reticulate evolution or of showing uncertainty and incompatibilities in evolutionary datasets. This is often done using unrooted phylogenetic networks such as split networks, due in part, to the availability of software (SplitsTree) for their computation and visualization. In this paper we discuss the problem of drawing rooted phylogenetic networks as cladograms or phylograms in a number of different views that are commonly used for rooted trees. Implementations of the algorithms are available in new releases of the Dendroscope and SplitsTree programs. © 2006 IEEE." 453 Simone Linz and Charles Semple. Hybridization in non-binary trees. In TCBB, Vol. 6(1):30-45, 2009. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/LS08.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw03/1220/linz/.         454 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Metrics for phylogenetic networks I: Generalizations of the Robinson-Foulds metric. In TCBB, Vol. 6(1):46-61, 2009. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, time consistent network, tree-child network, tripartition distance. Note: http://dx.doi.org/10.1109/TCBB.2008.70.         Toggle abstract "The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the first in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we study three metrics that have already been introduced in the literature: the Robinson-Foulds distance, the tripartitions distance and the $mu$-distance. They generalize to networks the classical Robinson-Foulds or partition distance for phylogenetic trees. We analyze the behavior of these metrics by studying their least and largest values and when they achieve them. As a by-product of this study, we obtain tight bounds on the size of a tree-child time consistent phylogenetic network. © 2006 IEEE." 455 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Metrics for phylogenetic networks II: Nodal and triplets metrics. In TCBB, Vol. 6(3):454-469, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1109/TCBB.2008.127.         Toggle abstract "The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree- child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of tree-child time consistent phylogenetic networks by induction, but also to generate all tree-child time consistent phylogenetic networks with a given number of leaves. © 2009 IEEE." 456 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. On Nakhleh's metric for reduced phylogenetic networks. In TCBB, Vol. 6(4):629-638, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: Preliminary versions: http://arxiv.org/abs/0809.0110 and http://arxiv.org/abs/0801.2354v1.         Toggle abstract "We prove that Nakhleh's metric for reduced phylogenetic networks is also a metric on the classes of tree-child phylogenetic networks, semibinary tree-sibling time consistent phylogenetic networks, and multilabeled phylogenetic trees. We also prove that it separates distinguishable phylogenetic networks. In this way, it becomes the strongest dissimilarity measure for phylogenetic networks available so far. Furthermore, we propose a generalization of that metric that separates arbitrary phylogenetic networks. © 2009 IEEE." 457 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-time Heuristic. In TCBB, Vol. 6(3):495-505, 2009. Keywords: explicit network, heuristic, parsimony, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb-MP.pdf.         458 Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing Level-2 Phylogenetic Networks from Triplets. In TCBB, Vol. 6(4):667-681, 2009. Note: http://www.win.tue.nl/~liersel/level2full.pdf.         459 Bui Quang Minh, Fabio Pardi, Steffen Klaere and Arndt von Haeseler. Budgeted Phylogenetic Diversity on Circular Split Systems. In TCBB, Vol. 6(1):22-29, 2009. Keywords: abstract network, circular split system, dynamic programming, from network, phylogenetic network, polynomial, split, split network. Note: http://dx.doi.org/10.1109/TCBB.2008.54.         Toggle abstract "In the last 15 years, Phylogenetic Diversity (PD) has gained interest in the community of conservation biologists as a surrogate measure for assessing biodiversity. We have recently proposed two approaches to select taxa for maximizing PD, namely PD with budget constraints and PD on split systems. In this paper, we will unify these two strategies and present a dynamic programming algorithm to solve the unified framework of selecting taxa with maximal PD under budget constraints on circular split systems. An improved algorithm will also be given if the underlying split system is a tree. © 2006 IEEE." 460 Simon Joly, Patricia A. McLenachan and Peter J. Lockhart. A Statistical Approach for Distinguishing Hybridization and Incomplete Lineage Sorting. In The American Naturalist, Vol. 174(2):E54-E70, 2009. Keywords: hybridization, lineage sorting, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://www.plantevolution.org/pdf/Joly&al_2009_AmNat.pdf.         Toggle abstract "The extent and evolutionary significance of hybridization is difficult to evaluate because of the difficulty in distinguishing hybridization from incomplete lineage sorting. Here we present a novel parametric approach for statistically distinguishing hybridization from incomplete lineage sorting based on minimum genetic distances of a nonrecombining locus. It is based on the idea that the expected minimum genetic distance between sequences from two species is smaller for some hybridization events than for incomplete lineage sorting scenarios. When applied to empirical data sets, distributions can be generated for the minimum interspecies distances expected under incomplete lineage sorting using coalescent simulations. If the observed distance between sequences from two species is smaller than its predicted distribution, incomplete lineage sorting can be rejected and hybridization inferred. We demonstrate the power of the method using simulations and illustrate its application on New Zealand alpine buttercups (Ranunculus). The method is robust and complements existing approaches. Thus it should allow biologists to assess with greater accuracy the importance of hybridization in evolution. © 2009 by The University of Chicago." 461 Chen Meng and Laura S. Kubatko. Detecting hybrid speciation in the presence of incomplete lineage sorting using gene tree incongruence: A model. In Theoretical Population Biology, Vol. 75(1):35-45, 2009. Keywords: bayesian, coalescent, from network, from rooted trees, hybridization, likelihood, lineage sorting, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1016/j.tpb.2008.10.004.         Toggle abstract "The application of phylogenetic inference methods, to data for a set of independent genes sampled randomly throughout the genome, often results in substantial incongruence in the single-gene phylogenetic estimates. Among the processes known to produce discord between single-gene phylogenies, two of the best studied in a phylogenetic context are hybridization and incomplete lineage sorting. Much recent attention has focused on the development of methods for estimating species phylogenies in the presence of incomplete lineage sorting, but phylogenetic models that allow for hybridization have been more limited. Here we propose a model that allows incongruence in single-gene phylogenies to be due to both hybridization and incomplete lineage sorting, with the goal of determining the contribution of hybridization to observed gene tree incongruence in the presence of incomplete lineage sorting. Using our model, we propose methods for estimating the extent of the role of hybridization in both a likelihood and a Bayesian framework. The performance of our methods is examined using both simulated and empirical data. © 2008 Elsevier Inc. All rights reserved." 462 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.         463 Tobias Kloepper. Algorithms for the Calculation and Visualisation of Phylogenetic Networks. PhD thesis, Eberhard-Karls-Universität Tübingen, Germany, 2008. Keywords: from rooted trees, from sequences, from unrooted trees, galled network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization. Note: https://publikationen.uni-tuebingen.de/xmlui/handle/10900/49159.         464 Anthony Labarre. Combinatorial aspects of genome rearrangements and haplotype networks. PhD thesis, Université Libre de Bruxelles, Belgium, 2008. Keywords: abstract network, from unrooted trees, haplotype network, phylogenetic network, phylogeny, reconstruction. Note: http://homepages.ulb.ac.be/~alabarre/publications/phd-thesis.pdf.         465 Jaroslaw Byrka. Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria. PhD thesis, Eindhoven University of Technology, Netherlands, 2008. Note: http://disopt.epfl.ch/webdav/site/disopt/users/191068/public/phdthesis_byrka.pdf.         466 Birgit Gemeinholzer. Phylogenetic networks. In Björn H. Junker and Falk Schreiber editors, Analysis of Biological Networks, Pages 255-282, John Wiley and Sons Ltd, 2008. Keywords: survey. Note: http://www.amazon.com/gp/reader/0470041447/.         467 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.         468 Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi and Giancarlo Mauri. The Comparison of Phylogenetic Networks: Algorithms and Complexity. In Ion Mandoiu and Alexander Zelikovsky editors, Bioinformatics Algorithms, John Wiley and Sons Ltd, 2008. Keywords: phylogenetic network, phylogeny. Note: http://www.amazon.com/gp/reader/0470097736/.         469 Lichen Bao and Sergey Bereg. Clustered SplitsNetworks. In COCOA08, Vol. 5165:469-478 of LNCS, springer, 2008. Keywords: abstract network, from distances, NeighborNet, realization, reconstruction. Note: http://dx.doi.org/10.1007/978-3-540-85097-7_44, slides available at http://www.utdallas.edu/~besp/cocoa08talk.pdf.         Toggle abstract "We address the problem of constructing phylogenetic networks using two criteria: the number of cycles and the fit value of the network. Traditionally the fit value is the main objective for evaluating phylogenetic networks. However, a small number of cycles in a network is desired and pointed out in several publications. We propose a new phylogenetic network called CS-network and a method for constructing it. The method is based on the well-known splitstree method. A CS-network contains a face which is k-cycle, k ≥ 3 (not as splitstree). We discuss difficulties of using non-parallelogram faces in splitstree networks. Our method involves clustering and optimization of weights of the network edges. The algorithm for constructing the underlying graph (except the optimization step) has a polynomial time. Experimental results show a good performance of our algorithm. © Springer-Verlag Berlin Heidelberg 2008." 470 Wing-Kin Sung. Constructing a Galled Phylogenetic Network. In Ming-Yang Kao editor, Encyclopedia of Algorithms, Springer Reference, 2008. Keywords: explicit network, from triplets, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/978-0-387-30162-4_92.         471 Leo van Iersel and Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ISAAC08, Vol. 5369:472-483 of LNCS, springer, 2008. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic. Note: http://arxiv.org/abs/0805.1859.         472 Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In Oleg N. Terikhovsky and William N. Burton editors, New Topics in Theoretical Computer Science, Pages 119-141, Nova Publishers, 2008. Keywords: dynamic programming, MASN, nested network, phylogenetic network, phylogeny, polynomial. Note: http://www.df.lth.se/~jj/Publications/nested12_NTTCS2008_corrected.pdf.         473 Ernst Althaus and Rouven Naujoks. Reconstructing Phylogenetic Networks with One Recombination. In Proceedings of the seventh International Workshop on Experimental Algorithms (WEA'08), Vol. 5038:275-288 of LNCS, springer, 2008. Keywords: enumeration, explicit network, exponential algorithm, from sequences, generation, parsimony, phylogenetic network, phylogeny, reconstruction, unicyclic network. Note: http://dx.doi.org/10.1007/978-3-540-68552-4_21.         Toggle abstract "In this paper we propose a new method for reconstructing phylogenetic networks under the assumption that recombination events have occurred rarely. For a fixed number of recombinations, we give a generalization of the maximum parsimony criterion. Furthermore, we describe an exact algorithm for one recombination event and show that in this case our method is not only able to identify the recombined sequence but also to reliably reconstruct the complete evolutionary history. © 2008 Springer-Verlag Berlin Heidelberg." 474 Cuong Than, Guohua Jin and Luay Nakhleh. Integrating Sequence and Topology for Efficient and Accurate Detection of Horizontal Gene Transfer. In Proceedings of the Sixth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'08), Vol. 5267:113-127 of LNCS, springer, 2008. Keywords: bootstrap, explicit network, from rooted trees, from sequences, lateral gene transfer, phylogenetic network, phylogeny, Program Nepal, Program PhyloNet, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg-08.pdf, slides available at http://igm.univ-mlv.fr/RCG08/RCG08slides/Cuong_Than_RCG08.pdf.         475 Victoria Kusherbaeva and Nikolay Vyahhi. Stochastic Approach to Binary Matrix Partitioning for Phylogenetic Networks. In Proceedings of the SYRCODIS 2008 Colloquium on Databases and Information Systems (SYRCoDIS'08), Vol. 355 of CEUR Workshop Proceedings, 2008. Keywords: clustering, phylogenetic network, phylogeny, reconstruction. Note: http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-355/kusherbaeva.pdf.         476 Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 of LNCS, springer, 2008. Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction. Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.         Toggle abstract "Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE." 477 Rune Lyngsø, Yun S. Song and Jotun Hein. Accurate Computation of Likelihoods in the Coalescent with Recombination via Parsimony. In RECOMB08, Vol. 4955:463-477 of LNCS, springer, 2008. Keywords: coalescent, likelihood, phylogenetic network, phylogeny, recombination, statistical model. Note: http://dx.doi.org/10.1007/978-3-540-78839-3_41.         Toggle abstract "Understanding the variation of recombination rates across a given genome is crucial for disease gene mapping and for detecting signatures of selection, to name just a couple of applications. A widely-used method of estimating recombination rates is the maximum likelihood approach, and the problem of accurately computing likelihoods in the coalescent with recombination has received much attention in the past. A variety of sampling and approximation methods have been proposed, but no single method seems to perform consistently better than the rest, and there still is great value in developing better statistical methods for accurately computing likelihoods. So far, with the exception of some two-locus models, it has remained unknown how the true likelihood exactly behaves as a function of model parameters, or how close estimated likelihoods are to the true likelihood. In this paper, we develop a deterministic, parsimony-based method of accurately computing the likelihood for multi-locus input data of moderate size. We first find the set of all ancestral configurations (ACs) that occur in evolutionary histories with at most k crossover recombinations. Then, we compute the likelihood by summing over all evolutionary histories that can be constructed only using the ACs in that set. We allow for an arbitrary number of crossing over, coalescent and mutation events in a history, as long as the transitions stay within that restricted set of ACs. For given parameter values, by gradually increasing the bound k until the likelihood stabilizes, we can obtain an accurate estimate of the likelihood. At least for moderate crossover rates, the algorithm-based method described here opens up a new window of opportunities for testing and fine-tuning statistical methods for computing likelihoods. © 2008 Springer-Verlag Berlin Heidelberg." 478 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Phylogenetic Networks: Justification, Models, Distances and Algorithms. In VI Jornadas de Matemática Discreta y Algorítmica (JMDA'08), 2008. Keywords: distance between networks, mu distance, phylogenetic network, phylogeny, polynomial, survey, time consistent network, tree-child network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_61-1.pdf.         479 Daniel H. Huson and Regula Rupp. Summarizing Multiple Gene Trees Using Cluster Networks. In WABI08, Vol. 5251:296-305 of LNCS, springer, 2008. Keywords: abstract network, from clusters, from rooted trees, phylogenetic network, phylogeny, polynomial, Program Dendroscope. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_25, slides from the MIEP Conference available at http://www.lirmm.fr/MIEP08/slides/11_13_rupp.pdf.         Toggle abstract "The result of a multiple gene tree analysis is usually a number of different tree topologies that are each supported by a significant proportion of the genes. We introduce the concept of a cluster network that can be used to combine such trees into a single rooted network, which can be drawn either as a cladogram or phylogram. In contrast to split networks, which can grow exponentially in the size of the input, cluster networks grow only quadratically. A cluster network is easily computed using a modification of the tree-popping algorithm, which we call network-popping. The approach has been implemented as part of the Dendroscope tree-drawing program and its application is illustrated using data and results from three recent studies on large numbers of gene trees. © 2008 Springer-Verlag Berlin Heidelberg." 480 Sagi Snir and Tamir Tuller. Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In WABI08, Vol. 5251:354-368 of LNCS, springer, 2008. Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_30.         Toggle abstract "Horizontal Gene Transfer (HGT) is the event of transferring genetic material from one lineage in the evolutionary tree to a different lineage. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Although the prevailing assumption is of complete HGT, cases of partial HGT (which are also named chimeric HGT) where only part of a gene is horizontally transferred, have also been reported, albeit less frequently. In this work we suggest a new probabilistic model for analyzing and modeling phylogenetic networks, the NET-HMM. This new model captures the biologically realistic assumption that neighboring sites of DNA or amino acid sequences are not independent, which increases the accuracy of the inference. The model describes the phylogenetic network as a Hidden Markov Model (HMM), where each hidden state is related to one of the network's trees. One of the advantages of the NET-HMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NET-HMM, devise efficient algorithms for solving a set of problems related to it, and implement them in software. We also provide a novel complementary significance test for evaluating the fitness of a model (NET-HMM) to a given data set. Using NET-HMM we are able to answer interesting biological questions, such as inferring the length of partial HGT's and the affected nucleotides in the genomic sequences, as well as inferring the exact location of HGT events along the tree branches. These advantages are demonstrated through the analysis of synthetical inputs and two different biological inputs. © 2008 Springer-Verlag Berlin Heidelberg."