Who is Who in Phylogenetic Networks

Publications list	Showing 481 - 510 (752 total)

481 Stefan Grünewald, Andreas Spillner, Kristoffer Forslund and Vincent Moulton. Constructing Phylogenetic Supernetworks from Quartets. In WABI08, Vol. 5251:284-295 of LNCS, springer, 2008. Keywords: abstract network, from quartets, from unrooted trees, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, reconstruction, split network. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_24.         Toggle abstract "In phylogenetics it is common practice to summarize collections of partial phylogenetic trees in the form of supertrees. Recently it has been proposed to construct phylogenetic supernetworks as an alternative to supertrees as these allow the representation of conflicting information in the trees, information that may not be representable in a single tree. Here we introduce SuperQ, a new method for constructing such supernetworks. It works by breaking the input trees into quartet trees, and stitching together the resulting set to form a network. The stitching process is performed using an adaptation of the QNet method for phylogenetic network reconstruction. In addition to presenting the new method, we illustrate the applicability of SuperQ to three data sets and discuss future directions for testing and development. © 2008 Springer-Verlag Berlin Heidelberg." 482 Iyad A. Kanj, Luay Nakhleh and Ge Xia. The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms. In ALG, Vol. 51(2):99-128, 2008. Keywords: perfect, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/algorithmica.pdf.         483 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks. In BIO, Vol. 24(13):1481-1488, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network. Note: http://dx.doi.org/10.1093/bioinformatics/btn231.         Toggle abstract "Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this articlea distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)." 484 Hadas Birin, Zohar Gal-Or, Isaac Elias and Tamir Tuller. Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion. In BIO, Vol. 24(6):826-832, 2008. Note: http://dx.doi.org/10.1093/bioinformatics/btn024.         Toggle abstract "Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input. Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets. © The Author 2008. Published by Oxford University Press. All rights reserved." 485 Stefan Grünewald, Katharina Huber and Qiong Wu. Two novel closure rules for constructing phylogenetic super-networks. In BMB, Vol. 70(7):1906-1924, 2008. Keywords: abstract network, from splits, from unrooted trees, phylogenetic network, phylogeny, Program MY CLOSURE, reconstruction, supernetwork. Note: http://arxiv.org/abs/0709.0283, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/huber/.         Toggle abstract "A contemporary and fundamental problem faced by many evolutionary biologists is how to puzzle together a collection P of partial trees (leaf-labeled trees whose leaves are bijectively labeled by species or, more generally, taxa, each supported by, e.g., a gene) into an overall parental structure that displays all trees in P. This already difficult problem is complicated by the fact that the trees in P regularly support conflicting phylogenetic relationships and are not on the same but only overlapping taxa sets. A desirable requirement on the sought after parental structure, therefore, is that it can accommodate the observed conflicts. Phylogenetic networks are a popular tool capable of doing precisely this. However, not much is known about how to construct such networks from partial trees, a notable exception being the Z-closure super-network approach, which is based on the Z-closure rule, and the Q-imputation approach. Although attractive approaches, they both suffer from the fact that the generated networks tend to be multidimensional making it necessary to apply some kind of filter to reduce their complexity. To avoid having to resort to a filter, we follow a different line of attack in this paper and develop closure rules for generating circular phylogenetic networks which have the attractive property that they can be represented in the plane. In particular, we introduce the novel Y-(closure) rule and show that this rule on its own or in combination with one of Meacham's closure rules (which we call the M-rule) has some very desirable theoretical properties. In addition, we present a case study based on Rivera et al. "ring of life" to explore the reconstructive power of the M- and Y-rule and also reanalyze an Arabidopsis thaliana data set. © 2008 Society for Mathematical Biology." 486 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. A Perl Package and an Alignment Tool for Phylogenetic Networks. In BMCB, Vol. 9:175, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree sibling network, tree-child network. Note: http://dx.doi.org/10.1186/1471-2105-9-175.         Toggle abstract "Background: Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of evolutionary events acting at the population level, like recombination between genes, hybridization between lineages, and lateral gene transfer. While most phylogenetics tools implement a wide range of algorithms on phylogenetic trees, there exist only a few applications to work with phylogenetic networks, none of which are open-source libraries, and they do not allow for the comparative analysis of phylogenetic networks by computing distances between them or aligning them. Results: In order to improve this situation, we have developed a Perl package that relies on the BioPerl bundle and implements many algorithms on phylogenetic networks. We have also developed a Java applet that makes use of the aforementioned Perl package and allows the user to make simple experiments with phylogenetic networks without having to develop a program or Perl script by him or herself. Conclusion: The Perl package is available as part of the BioPerl bundle, and can also be downloaded. A web-based application is also available (see availability and requirements). The Perl package includes full documentation of all its features. © 2008 Cardona et al; licensee BioMed Central Ltd." 487 Cuong Than, Derek Ruths and Luay Nakhleh. PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships. In BMCB, Vol. 9(322), 2008. Keywords: Program PhyloNet, software. Note: http://dx.doi.org/10.1186/1471-2105-9-322.         Toggle abstract "Background: Phylogenies, i.e., the evolutionary histories of groups of taxa, play a major role in representing the interrelationships among biological entities. Many software tools for reconstructing and evaluating such phylogenies have been proposed, almost all of which assume the underlying evolutionary history to be a tree. While trees give a satisfactory first-order approximation for many families of organisms, other families exhibit evolutionary mechanisms that cannot be represented by trees. Processes such as horizontal gene transfer (HGT), hybrid speciation, and interspecific recombination, collectively referred to as reticulate evolutionary events, result in networks, rather than trees, of relationships. Various software tools have been recently developed to analyze reticulate evolutionary relationships, which include SplitsTree4, LatTrans, EEEP, HorizStory, and T-REX. Results: In this paper, we report on the PhyloNet software package, which is a suite of tools for analyzing reticulate evolutionary relationships, or evolutionary networks, which are rooted, directed, acyclic graphs, leaf-labeled by a set of taxa. These tools can be classified into four categories: (1) evolutionary network representation: reading/writing evolutionary networks in a newly devised compact form; (2) evolutionary network characterization: analyzing evolutionary networks in terms of three basic building blocks - trees, clusters, and tripartitions; (3) evolutionary network comparison: comparing two evolutionary networks in terms of topological dissimilarities, as well as fitness to sequence evolution under a maximum parsimony criterion; and (4) evolutionary network reconstruction: reconstructing an evolutionary network from a species tree and a set of gene trees. Conclusion: The software package, PhyloNet, offers an array of utilities to allow for efficient and accurate analysis of evolutionary networks. The software package will help significantly in analyzing large data sets, as well as in studying the performance of evolutionary network reconstruction methods. Further, the software package supports the proposed eNewick format for compact representation of evolutionary networks, a feature that allows for efficient interoperability of evolutionary network software tools. Currently, all utilities in PhyloNet are invoked on the command line. © 2008 Than et al; licensee BioMed Central Ltd." 488 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Extended Newick: It is Time for a Standard Representation. In BMCB, Vol. 9:532, 2008. Keywords: evaluation, explicit network, phylogenetic network, Program Bio PhyloNetwork, Program Dendroscope, Program NetGen, Program PhyloNet, Program SplitsTree, Program TCS, visualization. Note: http://bioinfo.uib.es/media/uploaded/bmc-2008-enewick-sub.pdf.         489 Miguel Arenas and David Posada. Recodon: Coalescent simulation of coding DNA sequences with recombination, migration and demography. In BMCB, Vol. 8(458), 2008. Keywords: coalescent, generation, Program Recodon, software. Note: http://dx.doi.org/10.1186/1471-2105-8-458.         Toggle abstract "Background: Coalescent simulations have proven very useful in many population genetics studies. In order to arrive to meaningful conclusions, it is important that these simulations resemble the process of molecular evolution as much as possible. To date, no single coalescent program is able to simulate codon sequences sampled from populations with recombination, migration and growth. Results: We introduce a new coalescent program, called Recodon, which is able to simulate samples of coding DNA sequences under complex scenarios in which several evolutionary forces can interact simultaneously (namely, recombination, migration and demography). The basic codon model implemented is an extension to the general time-reversible model of nucleotide substitution with a proportion of invariable sites and among-site rate variation. In addition, the program implements non-reversible processes and mixtures of different codon models. Conclusion: Recodon is a flexible tool for the simulation of coding DNA sequences under realistic evolutionary models. These simulations can be used to build parameter distributions for testing evolutionary hypotheses using experimental data. Recodon is written in C, can run in parallel, and is freely available from http://darwin.uvigo.es/. © 2007 Arenas and Posada; licensee BioMed Central Ltd." 490 Tobias Kloepper and Daniel H. Huson. Drawing explicit phylogenetic networks and their integration into SplitsTree. In BMCEB, Vol. 8(22), 2008. Keywords: explicit network, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://dx.doi.org/10.1186/1471-2148-8-22.         Toggle abstract "Background. SplitsTree provides a framework for the calculation of phylogenetic trees and networks. It contains a wide variety of methods for the import/export, calculation and visualization of phylogenetic information. The software is developed in Java and implements a command line tool as well as a graphical user interface. Results. In this article, we present solutions to two important problems in the field of phylogenetic networks. The first problem is the visualization of explicit phylogenetic networks. To solve this, we present a modified version of the equal angle algorithm that naturally integrates reticulations into the layout process and thus leads to an appealing visualization of these networks. The second problem is the availability of explicit phylogenetic network methods for the general user. To advance the usage of explicit phylogenetic networks by biologists further, we present an extension to the SplitsTree framework that integrates these networks. By addressing these two problems, SplitsTree is among the first programs that incorporates implicit and explicit network methods together with standard phylogenetic tree methods in a graphical user interface environment. Conclusion. In this article, we presented an extension of SplitsTree 4 that incorporates explicit phylogenetic networks. The extension provides a set of core classes to handle explicit phylogenetic networks and a visualization of these networks. © 2008 Kloepper and Huson; licensee BioMed Central Ltd." 491 Barbara R. Holland, Steffi Benthin, Peter J. Lockhart, Vincent Moulton and Katharina Huber. Using supernetworks to distinguish hybridization from lineage-sorting. In BMCEB, Vol. 8(202), 2008. Keywords: explicit network, from unrooted trees, hybridization, lineage sorting, phylogenetic network, phylogeny, reconstruction, supernetwork. Note: http://dx.doi.org/10.1186/1471-2148-8-202.         Toggle abstract "Background. A simple and widely used approach for detecting hybridization in phylogenies is to reconstruct gene trees from independent gene loci, and to look for gene tree incongruence. However, this approach may be confounded by factors such as poor taxon-sampling and/or incomplete lineage-sorting. Results. Using coalescent simulations, we investigated the potential of supernetwork methods to differentiate between gene tree incongruence arising from taxon sampling and incomplete lineage-sorting as opposed to hybridization. For few hybridization events, a large number of independent loci, and well-sampled taxa across these loci, we found that it was possible to distinguish incomplete lineage-sorting from hybridization using the filtered Z-closure and Q-imputation supernetwork methods. Moreover, we found that the choice of supernetwork method was less important than the choice of filtering, and that count-based filtering was the most effective filtering technique. Conclusion. Filtered supernetworks provide a tool for detecting and identifying hybridization events in phylogenies, a tool that should become increasingly useful in light of current genome sequencing initiatives and the ease with which large numbers of independent gene loci can be determined using new generation sequencing technologies. © 2008 Holland et al; licensee BioMed Central Ltd." 492 Andreas W. M. Dress, Katharina Huber, Jacobus Koolen and Vincent Moulton. Compatible decompositions and block realizations of finite metrics. In EJC, Vol. 29(7):1617-1633, 2008. Keywords: abstract network, block realization, from distances, phylogenetic network, phylogeny, realization, reconstruction. Note: http://www.ims.nus.edu.sg/preprints/2007-21.pdf.         Toggle abstract "Given a metric D defined on a finite set X, we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in RX × X), D = ∑d ∈ D d holds, and there exist points x, x′ ∈ X for any two distinct metrics d, d′ in D such that d (x, y) d′ (x′, y) = 0 holds for every y ∈ X. In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d ∈ D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers. © 2007 Elsevier Ltd. All rights reserved." 493 Stephen J. Willson. Reconstruction of certain phylogenetic networks from the genomes at their leaves. In JTB, Vol. 252(2):185-376, 2008. Keywords: labeling, polynomial. Note: http://www.public.iastate.edu/~swillson/ReconstructNormalHomopap6.pdf.         Toggle abstract "A network N is a rooted acyclic digraph. A base-set X for N is a subset of vertices including the root (or outgroup), all leaves, and all vertices of outdegree 1. A simple model of evolution is considered in which all characters are binary and in which back-mutations occur only at hybrid vertices. It is assumed that the genome is known for each member of the base-set X. If the network is known and is assumed to be "normal," then it is proved that the genome of every vertex is uniquely determined and can be explicitly reconstructed. Under additional hypotheses involving time-consistency and separation of the hybrid vertices, the network itself can also be reconstructed from the genomes of all members of X. An explicit polynomial-time procedure is described for performing the reconstruction. © 2008 Elsevier Ltd. All rights reserved." 494 Miguel Arenas, Gabriel Valiente and David Posada. Characterization of reticulate networks based on the coalescent with recombination. In MBE, Vol. 25(12):2517-2520, 2008. Keywords: coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree sibling network, tree-child network. Note: http://dx.doi.org/10.1093/molbev/msn219.         Toggle abstract "Phylogenetic networks aim to represent the evolutionary history of taxa. Within these, reticulate networks are explicitly able to accommodate evolutionary events like recombination, hybridization, or lateral gene transfer. Although several metrics exist to compare phylogenetic networks, they make several assumptions regarding the nature of the networks that are not likely to be fulfilled by the evolutionary process. In order to characterize the potential disagreement between the algorithms and the biology, we have used the coalescent with recombination to build the type of networks produced by reticulate evolution and classified them as regular, tree sibling, tree child, or galled trees. We show that, as expected, the complexity of these reticulate networks is a function of the population recombination rate. At small recombination rates, most of the networks produced are already more complex than regular or tree sibling networks, whereas with moderate and large recombination rates, no network fit into any of the standard classes. We conclude that new metrics still need to be devised in order to properly compare two phylogenetic networks that have arisen from reticulating evolutionary process. © 2008 The Authors." 495 Supriya Munshaw and Thomas B. Kepler. An Information-Theoretic Method for the Treatment of Plural Ancestry in Phylogenetics. In MBE, Vol. 25(6):1199-1208, 2008. Keywords: explicit network, from sequences, heuristic, phylogenetic network, reconstruction, simulated annealing, software. Note: http://dx.doi.org/10.1093/molbev/msn066.         Toggle abstract "In the presence of recombination and gene conversion, a given genomic segment may inherit information from 2 distinct immediate ancestors. The importance of this type of molecular inheritance has become increasingly clear over the years, and the potential for erroneous inference when it is not accounted for in the statistical model is well documented. Yet, the inclusion of plural ancestry (PA) in phylogenetic analysis is still not routine. This omission is due to the greater difficulty of phylogenetic inference on general acyclic graphs compared that on with trees and the accompanying computational burden. We have developed a technique for phylogenetic inference in the presence of PA based on the principle of minimum description length, which assigns a cost - the description length - to each network topology given the observed sequence data. The description length combines the cost of poor data fit and model complexity in terms of information. This device allows us to search through network topologies to minimize the total description length. By comparing the best models obtained with and without PA, one can determine whether or not recombination has played an active role in the evolution of the genes under investigation, identify those genes that appear to be mosaic, and infer the phylogenetic network that best represents the history of the alignment. We show that the method performs well on simulated data and demonstrate its application on HIV env gene sequence data from 8 human subjects. The software implementation of the method is available upon request. © The Author 2008. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." 496 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Tripartitions do not always discriminate phylogenetic networks. In MBIO, Vol. 211(2):356-370, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree-child network, tripartition distance. Note: http://arxiv.org/abs/0707.2376, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/valiente/.         Toggle abstract "Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of non-treelike evolutionary events, like recombination, hybridization, or lateral gene transfer. In a recent series of papers devoted to the study of reconstructibility of phylogenetic networks, Moret, Nakhleh, Warnow and collaborators introduced the so-called tripartition metric for phylogenetic networks. In this paper we show that, in fact, this tripartition metric does not satisfy the separation axiom of distances (zero distance means isomorphism, or, in a more relaxed version, zero distance means indistinguishability in some specific sense) in any of the subclasses of phylogenetic networks where it is claimed to do so. We also present a subclass of phylogenetic networks whose members can be singled out by means of their sets of tripartitions (or even clusters), and hence where the latter can be used to define a meaningful metric. © 2007 Elsevier Inc. All rights reserved." 497 Steven M. Woolley, David Posada and Keith A. Crandall. A Comparison of Phylogenetic Network Methods Using Computer Simulation. In PLoS ONE, Vol. 3(4):e1913, 2008. Keywords: abstract network, distance between networks, evaluation, median network, MedianJoining, minimum spanning network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program SHRUB, Program SplitsTree, Program TCS, split decomposition. Note: http://dx.doi.org/10.1371/journal.pone.0001913.         Toggle abstract "Background: We present a series of simulation studies that explore the relative performance of several phylogenetic network approaches (statistical parsimony, split decomposition, union of maximum parsimony trees, neighbor-net, simulated history recombination upper bound, median-joining, reduced median joining and minimum spanning network) compared to standard tree approaches (neighbor-joining and maximum parsimony) in the presence and absence of recombination. Principal Findings: In the absence of recombination, all methods recovered the correct topology and branch lengths nearly all of the time when the subtitution rate was low, except for minimum spanning networks, which did considerably worse. At a higher substitution rate, maximum parsimony and union of maximum parsimony trees were the most accurate. With recombination, the ability to infer the correct topology was halved for all methods and no method could accurately estimate branch lengths. Conclusions: Our results highlight the need for more accurate phylogenetic network methods and the importance of detecting and accounting for recombination in phylogenetic studies. Furthermore, we provide useful information for choosing a network algorithm and a framework in which to evaluate improvements to existing methods and novel algorithms developed in the future. © 2008 Woolley et al." 498 Tal Dagan, Yael Artzy-Randrup and William Martin. Modular networks and cumulative impact of lateral transfer in prokaryote genome evolution. In PNAS, Vol. 105:10039-10044, 2008. Keywords: from sequences, from species tree, heuristic, lateral gene transfer, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1073/pnas.0800679105.         Toggle abstract "Lateral gene transfer is an important mechanism of natural variation among prokaryotes, but the significance of its quantitative contribution to genome evolution is debated. Here, we report networks that capture both vertical and lateral components of evolutionary history among 539,723 genes distributed across 181 sequenced prokaryotic genomes. Partitioning of these networks by an eigenspectrum analysis identifies community structure in prokaryotic gene-sharing networks, the modules of which do not correspond to a strictly hierarchical prokaryotic classification. Our results indicate that, on average, at least 81 ± 15% of the genes in each genome studied were involved in lateral gene transfer at some point in their history, even though they can be vertically inherited after acquisition, uncovering a substantial cumulative effect of lateral gene transfer on longer evolutionary time scales. © 2008 by The National Academy of Sciences of the USA." 499 James B. Whitfield, Sydney A. Cameron, Daniel H. Huson and Mike Steel. Filtered Z-Closure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees. In Systematic Biology, Vol. 57(6):939-947, 2008. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, split, split network, supernetwork. Note: http://www.life.uiuc.edu/scameron/pdfs/Filtered%20Z-closure%20SystBiol.pdf.         500 Philippe Gambette and Daniel H. Huson. Improved Layout of Phylogenetic Networks. In TCBB, Vol. 5(3):472-479, 2008. Keywords: abstract network, heuristic, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00309694/en/.         Toggle abstract "Split networks are increasingly being used in phylogenetic analysis. Usually, a simple equal-angle algorithm is used to draw such networks, producing layouts that leave much room for improvement. Addressing the problem of producing better layouts of split networks, this paper presents an algorithm for maximizing the area covered by the network, describes an extension of the equal-daylight algorithm to networks, looks into using a spring embedder, and discusses how to construct rooted split networks. © 2008 IEEE." 501 Andreas Spillner, Binh T. Nguyen and Vincent Moulton. Computing phylogenetic diversity for split systems. In TCBB, Vol. 5(2):235-244, 2008. Keywords: abstract network, diversity, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1109/TCBB.2007.70260, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0906/spillner/.         Toggle abstract "In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size $n$. We show that for general split systems this problem is NP-hard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal $O(n)$ time algorithm for phylogenetic trees and an $O(nlog n + n k)$ time algorithm for choosing an optimal subset of size $k$ relative to a circular split system. © 2006 IEEE." 502 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In TCS, Vol. 401:153-164, 2008. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf.         503 Yuanyi Zhang, Lichen Bao and Sergey Bereg. Optimizing Split Networks. 2007. Note: UC Dallas Computer Science Technical Report UTDCS-08-07.         504 Monique M. Morin. Phylogenetic Networks: Simulation, Characterization, and Reconstruction. PhD thesis, The University of New Mexico, U.S.A., 2007. Keywords: evaluation, explicit network, hybridization, lateral gene transfer, phylogenetic network, phylogeny, Program NetGen, simulation, software. Note: http://www.cs.unm.edu/~morin/morin_phd.pdf.         505 Tamir Tuller and Sagi Snir. The NET-HMM: a HMM Based Likelihood Model for Evolutionary Networks. 2007. Keywords: lateral gene transfer, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model. Note: Poster presented at the eleventh Annual International Conference on Research in Computational Molecular Biology (RECOMB'07), http://www.qb3.org/recomb07/posters/Tuller013043013RECOMB_HMM1.pdf.         506 Alice Lesser. Optimal and Hereditarily Optimal Realizations of Metric Spaces. PhD thesis, Uppsala University, Sweden, 2007. Keywords: from distances, optimal realization, phylogenetic network, phylogeny, realization. Note: http://www.diva-portal.org/diva/getDocument?urn_nbn_se_uu_diva-8297-2__fulltext.pdf.         507 Bastienne Vriesendorp. Phylogenenetworks, exploring reticulate evolution and its consequences for phylogenetic reconstruction. PhD thesis, Wageningen University, The Netherlands, 2007. Keywords: consensus, distance between networks, evaluation, hybridization, median network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program SplitsTree, split decomposition, survey. Note: http://library.wur.nl/wda/dissertations/dis4239.pdf.         508 Yuanyi Zhang. Optimization Algorithms for Phylogenetic Networks. PhD thesis, University of Texas at Dallas, U.S.A., 2007. Keywords: abstract network, explicit network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://proquest.umi.com/pqdlink?did=1421626541&sid=1&Fmt=6&clientId=176295&RQT=309&VName=PQD.         509 Andreas W. M. Dress, Katharina Huber, Jacobus Koolen and Vincent Moulton. An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces. In COCOA07, Vol. 4616:4-10 of LNCS, springer, 2007. Keywords: from distances. Note: http://dx.doi.org/10.1007/978-3-540-73556-4_3.         510 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.