Who is Who in Phylogenetic Networks

Publications list	Showing 361 - 390 (752 total)

361 Daniel H. Huson and Celine Scornavacca. A survey of combinatorial methods for phylogenetic networks. In Genome Biology and Evolution, Vol. 3:23-35, 2011. Keywords: phylogenetic network, survey. Note: http://dx.doi.org/10.1093/gbe/evq077.         Toggle abstract "The evolutionary history of a set of species is usually described by a rooted phylogenetic tree. Although it is generally undisputed that bifurcating speciation events and descent with modifications are major forces of evolution, there is a growing belief that reticulate events also have a role to play. Phylogenetic networks provide an alternative to phylogenetic trees and may be more suitable for data sets where evolution involves significant amounts of reticulate events, such as hybridization, horizontal gene transfer, or recombination. In this article, we give an introduction to the topic of phylogenetic networks, very briefly describing the fundamental concepts and summarizing some of the most important combinatorial methods that are available for their computation. © 2010 The Author(s)." 362 Marc Thuillard and Vincent Moulton. Identifying and reconstructing lateral transfers from distance matrices by combining the Minimum Contradiction Method and Neighbor-Net. In JBCB, Vol. 9(4):453-470, 2011. Keywords: from distances, lateral gene transfer, minimum contradiction, NeighborNet, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1142/S0219720011005409, slides available at http://www.newton.ac.uk/programmes/PLG/seminars/062015501.html.         Toggle abstract "Identifying lateral gene transfers is an important problem in evolutionary biology. Under a simple model of evolution, the expected values of an evolutionary distance matrix describing a phylogenetic tree fulfill the so-called Kalmanson inequalities. The Minimum Contradiction method for identifying lateral gene transfers exploits the fact that lateral transfers may generate large deviations from the Kalmanson inequalities. Here a new approach is presented to deal with such cases that combines the Neighbor-Net algorithm for computing phylogenetic networks with the Minimum Contradiction method. A subset of taxa, prescribed using Neighbor-Net, is obtained by measuring how closely the Kalmanson inequalities are fulfilled by each taxon. A criterion is then used to identify the taxa, possibly involved in a lateral transfer between nonconsecutive taxa. We illustrate the utility of the new approach by applying it to a distance matrix for Archaea, Bacteria, and Eukaryota. © 2011 Imperial College Press." 363 Josh Voorkamp né Collins, Simone Linz and Charles Semple. Quantifying hybridization in realistic time. In JCB, Vol. 18(10):1305-1318, 2011. Keywords: explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, software. Note: http://wwwcsif.cs.ucdavis.edu/~linzs/CLS10_interleave.pdf, software available at http://www.math.canterbury.ac.nz/~c.semple/software.shtml.         Toggle abstract "Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulation-for example, horizontal gene transfer, hybridization, or recombination-has influenced the evolution for a set of present-day species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NP-hard and also fixed-parameter tractable problem. In this article, we give a new fixed-parameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleaving-a technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixed-parameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm that has previously been implemented. © 2011, Mary Ann Liebert, Inc." 364 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." 365 Mukul S. Bansal, Guy Banay, J. Peter Gogarten and Ron Shamir. Detecting Highways of Horizontal Gene Transfer. In JCB, Vol. 18(9):1087-1114, 2011. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://people.csail.mit.edu/mukul/HighwayFull_preprint.pdf.         Toggle abstract "In a horizontal gene transfer (HGT) event, a gene is transferred between two species that do not have an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species and m input quartet trees, we give an efficient O(m+n 2)-time algorithm for detecting highways, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method. © 2011, Mary Ann Liebert, Inc." 366 Leo van Iersel and Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245-255, 2011. Keywords: APX hard, explicit network, from clusters, from rooted trees, from sequences, from triplets, level k phylogenetic network, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1004.5332.         Toggle abstract "Rooted phylogenetic networks are used to model non-treelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some well-defined sense simultaneously represents them all. We review these four models and investigate how they are related. Motivated by the parsimony principle, one often aims to construct a network that contains as few reticulations (non-treelike evolutionary events) as possible. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary (i.e. fully resolved) trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several computational complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge. © 2010 Elsevier Ltd." 367 Gergely J. Szöllösi and Vincent Daubin. Modeling Gene Family Evolution and Reconciling Phylogenetic Discord. In Evolutionary Genomics, Statistical and Computational Methods, Volume 2, Methods in Molecular Biology, Vol. 856:29-51, Chapter 2, springer, 2011. Keywords: duplication, from multilabeled tree, lateral gene transfer, likelihood, phylogeny, reconstruction, statistical model. Note: ArXiv version entitled The pattern and process of gene family evolution.         Toggle abstract "Large-scale databases are available that contain homologous gene families constructed from hundreds of complete genome sequences from across the three domains of life. Here, we discuss the approaches of increasing complexity aimed at extracting information on the pattern and process of gene family evolution from such datasets. In particular, we consider the models that invoke processes of gene birth (duplication and transfer) and death (loss) to explain the evolution of gene families. First, we review birth-and-death models of family size evolution and their implications in light of the universal features of family size distribution observed across different species and the three domains of life. Subsequently, we proceed to recent developments on models capable of more completely considering information in the sequences of homologous gene families through the probabilistic reconciliation of the phylogenetic histories of individual genes with the phylogenetic history of the genomes in which they have resided. To illustrate the methods and results presented, we use data from the HOGENOM database, demonstrating that the distribution of homologous gene family sizes in the genomes of the eukaryota, archaea, and bacteria exhibits remarkably similar shapes. We show that these distributions are best described by models of gene family size evolution, where for individual genes the death (loss) rate is larger than the birth (duplication and transfer) rate but new families are continually supplied to the genome by a process of origination. Finally, we use probabilistic reconciliation methods to take into consideration additional information from gene phylogenies, and find that, for prokaryotes, the majority of birth events are the result of transfer. © 2012 Springer Science+Business Media, LLC." 368 Alix Boc and Vladimir Makarenkov. Towards an accurate identification of mosaic genes and partial horizontal gene transfers. In NAR, Vol. 39(21):e144, 2011. Keywords: explicit network, from sequences, lateral gene transfer, phylogenetic network, phylogeny, Program T REX, reconstruction. Note: http://dx.doi.org/10.1093/nar/gkr735.         Toggle abstract "Many bacteria and viruses adapt to varying environmental conditions through the acquisition of mosaic genes. A mosaic gene is composed of alternating sequence polymorphisms either belonging to the host original allele or derived from the integrated donor DNA. Often, the integrated sequence contains a selectable genetic marker (e.g. marker allowing for antibiotic resistance). An effective identification of mosaic genes and detection of corresponding partial horizontal gene transfers (HGTs) are among the most important challenges posed by evolutionary biology. We developed a method for detecting partial HGT events and related intragenic recombination giving rise to the formation of mosaic genes. A bootstrap procedure incorporated in our method is used to assess the support of each predicted partial gene transfer. The proposed method can be also applied to confirm or discard complete (i.e. traditional) horizontal gene transfers detected by any HGT inferring method. While working on a full-genome scale, the new method can be used to assess the level of mosaicism in the considered genomes as well as the rates of complete and partial HGT underlying their evolution. © 2011 The Author(s)." 369 Lawrence A. David and Eric J. Alm. Rapid evolutionary innovation during an Archaean genetic expansion. In Nature, Vol. 469:93-96, 2011. Keywords: duplication, dynamic programming, from multilabeled tree, from rooted trees, from species tree, parsimony, phylogenetic network, phylogeny, Program Angst. Note: http://dx.doi.org/10.1038/nature09649, Program Angst described here.         370 Yun Yu, Cuong Than, James H. Degnan and Luay Nakhleh. Coalescent Histories on Phylogenetic Networks and Detection of Hybridization Despite Incomplete Lineage Sorting. In Systematic Biology, Vol. 60(2):138-149, 2011. Keywords: coalescent, hybridization, lineage sorting, reconstruction, statistical model. Note: http://www.cs.rice.edu/~nakhleh/Papers/YuEtAl-SB11.pdf.         Toggle abstract "Analyses of the increasingly available genomic data continue to reveal the extent of hybridization and its role in the evolutionary diversification of various groups of species. We show, through extensive coalescent-based simulations of multilocus data sets on phylogenetic networks, how divergence times before and after hybridization events can result in incomplete lineage sorting with gene tree incongruence signatures identical to those exhibited by hybridization. Evolutionary analysis of such data under the assumption of a species tree model can miss all hybridization events, whereas analysis under the assumption of a species network model would grossly overestimate hybridization events. These issues necessitate a paradigm shift in evolutionary analysis under these scenarios, from a model that assumes a priori a single source of gene tree incongruence to one that integrates multiple sources in a unifying framework. We propose a framework of coalescence within the branches of a phylogenetic network and show how this framework can be used to detect hybridization despite incomplete lineage sorting. We apply the model to simulated data and show that the signature of hybridization can be revealed as long as the interval between the divergence times of the species involved in hybridization is not too small. We reanalyze a data set of 106 loci from 7 in-group Saccharomyces species for which a species tree with no hybridization has been reported in the literature. Our analysis supports the hypothesis that hybridization occurred during the evolution of this group, explaining a large amount of the incongruence in the data. Our findings show that an integrative approach to gene tree incongruence and its reconciliation is needed. Our framework will help in systematically analyzing genomic data for the occurrence of hybridization and elucidating its evolutionary role. [Coalescent history; incomplete lineage sorting; hybridization; phylogenetic network.]. © 2011 The Author(s)." 371 Ali Tofigh, Mike Hallett and Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517-535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.         Toggle abstract "The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios. © 2011 IEEE." 372 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Comparison of Galled Trees. In TCBB, Vol. 8(2):410-427, 2011. Note: http://arxiv.org/abs/0906.1166.         Toggle abstract "Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial-time algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods. © 2011 IEEE." 373 Katharina Huber, Leo van Iersel, Steven Kelk and Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks. In TCBB, Vol. 8(3):607-620, 2011. Keywords: explicit network, from triplets, galled tree, generation, heuristic, phylogenetic network, phylogeny, Program LEV1ATHAN, Program Lev1Generator, reconstruction, software. Note: http://arxiv.org/abs/0910.4067.         Toggle abstract "Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks-a type of network slightly more general than a phylogenetic tree-from triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of Lev1athan is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that Lev1athan is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise. © 2011 IEEE." 374 Philippe Gambette. Méthodes combinatoires de reconstruction de réseaux phylogénétiques. PhD thesis, Université Montpellier 2, France, 2010. Keywords: abstract network, characterization, circular split system, explicit network, FPT, from clusters, from triplets, integer linear programming, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, Program Dendroscope, pyramid, reconstruction, split network, weak hierarchy. Note: http://tel.archives-ouvertes.fr/tel-00608342/en/.         375 Gabriel Cardona, Mercè Llabrés and Francesc Rosselló. A metric for galled networks. 2010. Keywords: distance between networks, explicit network, from network, galled network, phylogenetic network, phylogeny. Note: http://arxiv4.library.cornell.edu/abs/1009.0652.         376 Cuong Than. Inference of parsimonious species phylogenies from multi-locus data. PhD thesis, Rice University, U.S.A., 2010. Keywords: explicit network, from sequences, parsimony, phylogenetic network, phylogeny, reconstruction. Note: http://hdl.handle.net/1911/62177.         377 Binh T. Nguyen. Novel Split-Based Approaches to Computing Phylogenetic Diversity and Planar Split Networks. PhD thesis, University of East Anglia, U.K., 2010. Keywords: abstract network, diversity, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: https://ueaeprints.uea.ac.uk/id/eprint/34218.         378 Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara and Gabriel Valiente. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks. In CPM10, Vol. 6129:190-201 of LNCS, springer, 2010. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread. Note: http://hdl.handle.net/10119/9859, slides available at http://cs.nyu.edu/parida/CPM2010/MainPage_files/18.pdf.         Toggle abstract "The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2 with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time. © Springer-Verlag Berlin Heidelberg 2010." 379 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.         380 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." 381 Leo van Iersel, Steven Kelk, Regula Rupp and Daniel H. Huson. Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters. In ISMB10, Vol. 26(12):i124-i131 of BIO, 2010. Keywords: from clusters, level k phylogenetic network, Program Dendroscope, Program HybridInterleave, Program HybridNumber, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btq202, with proofs: http://arxiv.org/abs/0910.3082.         Toggle abstract "Phylogenetic trees are widely used to display estimates of how groups of species are evolved. Each phylogenetic tree can be seen as a collection of clusters, subgroups of the species that evolved from a common ancestor. When phylogenetic trees are obtained for several datasets (e.g. for different genes), then their clusters are often contradicting. Consequently, the set of all clusters of such a dataset cannot be combined into a single phylogenetic tree. Phylogenetic networks are a generalization of phylogenetic trees that can be used to display more complex evolutionary histories, including reticulate events, such as hybridizations, recombinations and horizontal gene transfers. Here, we present the new CASS algorithm that can combine any set of clusters into a phylogenetic network. We show that the networks constructed by CASS are usually simpler than networks constructed by other available methods. Moreover, we show that CASS is guaranteed to produce a network with at most two reticulations per biconnected component, whenever such a network exists. We have implemented CASS and integrated it into the freely available Dendroscope software. Contact: l.j.j.v.iersel@gmail.com. Supplementary information: Supplementary data are available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press." 382 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." 383 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." 384 David A. Morrison. Phylogenetic networks in systematic biology (and elsewhere) In R.M. Mohan editor, Research Advances in Systematic Biology, Global Research Network, Trivandrum, India, 2010. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction, survey.         385 Luay Nakhleh. Evolutionary phylogenetic networks: models and issues. In L. Heath and N. Ramakrishnan editors, The Problem Solving Handbook for Computational Biology and Bioinformatics, Springer, 2010. Keywords: phylogenetic network, phylogeny, survey. Note: http://www.cs.rice.edu/~nakhleh/Papers/HeathRamakrishnanBookChapter.pdf.         386 Gabriel Cardona, Mercè Llabrés and Francesc Rosselló. Two Results on Distances for Phylogenetic Networks. In Advances in Intelligent and Soft Computing, Vol. 74:93-100, 2010. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, tree sibling network. Note: http://www.merilibrary.com/books/bioinformatics/advances%20in%20bioinformatics.pdf#page=103.         387 Zhi-Zhong Chen and Lusheng Wang. HybridNET: a tool for constructing hybridization networks. In BIO, Vol. 26(22):2912-2913, 2010. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNET, software. Note: http://rnc.r.dendai.ac.jp/~chen/papers/note2.pdf.         Toggle abstract "Motivations: When reticulation events occur, the evolutionary history of a set of existing species can be represented by a hybridization network instead of an evolutionary tree. When studying the evolutionary history of a set of existing species, one can obtain a phylogenetic tree of the set of species with high confidence by looking at a segment of sequences or a set of genes. When looking at another segment of sequences, a different phylogenetic tree can be obtained with high confidence too. This indicates that reticulation events may occur. Thus, we have the following problem: given two rooted phylogenetic trees on a set of species that correctly represent the tree-like evolution of different parts of their genomes, what is the hybridization network with the smallest number of reticulation events to explain the evolution of the set of species under consideration? Results: We develop a program, named HybridNet, for constructing a hybridization network with the minimum number of reticulate vertices from two input trees. We first implement the O(3dn)-time algorithm by Whidden et al. for computing a maximum (acyclic) agreement forest. Our program can output all the maximum (acyclic) agreement forests. We then augment the program so that it can construct an optimal hybridization network for each given maximum acyclic agreement forest. To our knowledge, this is the first time that optimal hybridization networks can be rapidly constructed. © The Author 2010. Published by Oxford University Press. All rights reserved." 388 Joel Velasco and Elliott Sober. Testing for Treeness: Lateral Gene Transfer, Phylogenetic Inference, and Model Selection. In Biology and Philosophy, Vol. 25(4):675-687, 2010. Keywords: explicit network, model selection, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://joelvelasco.net/Papers/velascosober-testingfortreeness.pdf.         Toggle abstract "A phylogeny that allows for lateral gene transfer (LGT) can be thought of as a strictly branching tree (all of whose branches are vertical) to which lateral branches have been added. Given that the goal of phylogenetics is to depict evolutionary history, we should look for the best supported phylogenetic network and not restrict ourselves to considering trees. However, the obvious extensions of popular tree-based methods such as maximum parsimony and maximum likelihood face a serious problem-if we judge networks by fit to data alone, networks that have lateral branches will always fit the data at least as well as any network that restricts itself to vertical branches. This is analogous to the well-studied problem of overfitting data in the curve-fitting problem. Analogous problems often have analogous solutions and we propose to treat network inference as a case of model selection and use the Akaike Information Criterion (AIC). Strictly tree-like networks are more parsimonious than those that postulate lateral as well as vertical branches. This leads to the conclusion that we should not always infer LGT events whenever it would improve our fit-to-data, but should do so only when the improved fit is larger than the penalty for adding extra lateral branches. © 2010 Springer Science+Business Media B.V." 389 Robert G. Beiko. Gene sharing and genome evolution: networks in trees and trees in networks. In Biology and Philosophy, Vol. 25(4):659-673, 2010. Keywords: abstract network, explicit network, from rooted trees, galled network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, reconstruction, split network, survey. Note: http://dx.doi.org/10.1007/s10539-010-9217-3.         Toggle abstract "Frequent lateral genetic transfer undermines the existence of a unique "tree of life" that relates all organisms. Vertical inheritance is nonetheless of vital interest in the study of microbial evolution, and knowing the "tree of cells" can yield insights into ecological continuity, the rates of change of different cellular characters, and the evolutionary plasticity of genomes. Notwithstanding within-species recombination, the relationships most frequently recovered from genomic data at shallow to moderate taxonomic depths are likely to reflect cellular inheritance. At the same time, it is clear that several types of 'average signals' from whole genomes can be highly misleading, and the existence of a central tendency must not be taken as prima facie evidence of vertical descent. Phylogenetic networks offer an attractive solution, since they can be formulated in ways that mitigate the misleading aspects of hybrid evolutionary signals in genomes. But the connections in a network typically show genetic relatedness without distinguishing between vertical and lateral inheritance of genetic material. The solution may lie in a compromise between strict tree-thinking and network paradigms: build a phylogenetic network, but identify the set of connections in the network that are potentially due to vertical descent. Even if a single tree cannot be unambiguously identified, choosing a subnetwork of putative vertical connections can still lead to drastic reductions in the set of candidate vertical hypotheses. © 2010 Springer Science+Business Media B.V." 390 Stephen J. Willson. Properties of normal phylogenetic networks. In BMB, Vol. 72(2):340-358, 2010. Keywords: normal network, phylogenetic network, phylogeny, regular network. Note: http://www.public.iastate.edu/~swillson/RestrictionsOnNetworkspap9.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/willson/.         Toggle abstract "A phylogenetic network is a rooted acyclic digraph with vertices corresponding to taxa. Let X denote a set of vertices containing the root, the leaves, and all vertices of outdegree 1. Regard X as the set of vertices on which measurements such as DNA can be made. A vertex is called normal if it has one parent, and hybrid if it has more than one parent. The network is called normal if it has no redundant arcs and also from every vertex there is a directed path to a member of X such that all vertices after the first are normal. This paper studies properties of normal networks. Under a simple model of inheritance that allows homoplasies only at hybrid vertices, there is essentially unique determination of the genomes at all vertices by the genomes at members of X if and only if the network is normal. This model is a limiting case of more standard models of inheritance when the substitution rate is sufficiently low. Various mathematical properties of normal networks are described. These properties include that the number of vertices grows at most quadratically with the number of leaves and that the number of hybrid vertices grows at most linearly with the number of leaves. © 2009 Society for Mathematical Biology."