| |
|
| |
  
Hans-Jürgen Bandelt,
Vincent Macaulay and
Martin Richards. Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA. In MPE, Vol. 16:8-28, 2000.
Keywords: from sequences, from splits, median network, phylogenetic network, phylogeny, reconstruction.
Note: http://www.stats.gla.ac.uk/~vincent/papers/speedy.pdf.
Toggle abstract
"Molecular data sets characterized by few phylogenetically informative characters with a broad spectrum of mutation rates, such as intraspecific control-region sequence variation of human mitochondrial DNA (mtDNA), can be usefully visualized in the form of median networks. Here we provide a step-by-step guide to the construction of such networks by hand. We improve upon a previously implemented algorithm by outlining an efficient parametrized strategy amenable to large data sets, greedy reduction, which makes it possible to reconstruct some of the confounding recurrent mutations. This entails some postprocessing as well, which assists in capturing more parsimonious solutions. To simplify the creation of the resulting network by hand, we describe a speedy approach to network construction, based on a careful planning of the processing order. A coalescent simulation tailored to human mtDNA variation in Eurasia testifies to the usefulness of reduced median networks, while highlighting notorious problems faced by all phylogenetic methods in this context. Finally, we discuss two case studies involving the comparison of characters in the two hypervariable segments of the human mtDNA control region in the light of the worldwide control-region sequence database, as well as additional restriction fragment length polymorphism information. We conclude that only a minority of the mutations that hit the second segment occur at sites that would have a mutation rate comparable to those at most sites in the first segment. Discarding the known 'noisy' sites of the second segment enhances the analysis. (C) 2000 Academic Press."
|
|
| |
  
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."
|
|
| |
   
Katharina Huber,
Michael Langton,
David Penny,
Vincent Moulton and
Mike Hendy. Spectronet: A package for computing spectra and median networks. In ABIO, Vol. 1(3):159-161, 2004.
Keywords: from splits, median network, phylogenetic network, phylogeny, Program Spectronet, software, split, visualization.
Note: http://citeseer.ist.psu.edu/631776.html.
Toggle abstract
Spectronet is a package that uses various methods for exploring and visualising complex evolutionary signals. Given an alignment in NEXUS format, the package works by computing a collection of weighted splits or bipartitions of the taxa and then allows the user to interactively analyse the resulting collection using tools such as Lento-plots and median networks. The package is highly interactive and available for PCs.
|
|
| |
 
Ulrik Brandes and
Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009.
Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.
Toggle abstract
"A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved."
|
|
| |
Alain Guénoche. Graphical Representation of a Boolean Array. In Computers and the Humanities, Vol. 20(4):277-281, 1986.
Keywords: from splits, median network, reconstruction.
Note: http://dx.doi.org/10.1007/BF02400118.
Toggle abstract
"In this paper, we represent a boolean array of data with a median connected graph. Vertices are the different lines of the array plus virtual monomials, and an edge links two vertices that are different for only one variable. We describe an algorithm to compute this graph, that is an exact representation of the symmetrical difference distance between lines, and we show an application to Bronze age pins. © 1986 Paradigm Press, Inc."
|
|
| |
 
Andreas Spillner,
Binh T. Nguyen and
Vincent Moulton. Constructing and Drawing Regular Planar Split Networks. In TCBB, Vol. 9(2):395-407, 2012.
Keywords: abstract network, from splits, phylogenetic network, phylogeny, reconstruction, visualization.
Note: slides and presentation available at http://www.newton.ac.uk/programmes/PLG/seminars/062111501.html.
Toggle abstract
"Split networks are commonly used to visualize collections of bipartitions, also called splits, of a finite set. Such collections arise, for example, in evolutionary studies. Split networks can be viewed as a generalization of phylogenetic trees and may be generated using the SplitsTree package. Recently, the NeighborNet method for generating split networks has become rather popular, in part because it is guaranteed to always generate a circular split system, which can always be displayed by a planar split network. Even so, labels must be placed on the "outside" of the network, which might be problematic in some applications. To help circumvent this problem, it can be helpful to consider so-called flat split systems, which can be displayed by planar split networks where labels are allowed on the inside of the network too. Here, we present a new algorithm that is guaranteed to compute a minimal planar split network displaying a flat split system in polynomial time, provided the split system is given in a certain format. We will also briefly discuss two heuristics that could be useful for analyzing phylogeographic data and that allow the computation of flat split systems in this format in polynomial time. © 2006 IEEE."
|
|
| |
 
Paul Phipps and
Sergey Bereg. Optimizing Phylogenetic Networks for Circular Split Systems. In TCBB, Vol. 9(2):535-547, 2012.
Keywords: abstract network, from distances, from splits, phylogenetic network, phylogeny, Program PhippsNetwork, reconstruction, software.
Toggle abstract
"We address the problem of realizing a given distance matrix by a planar phylogenetic network with a minimum number of faces. With the help of the popular software SplitsTree4, we start by approximating the distance matrix with a distance metric that is a linear combination of circular splits. The main results of this paper are the necessary and sufficient conditions for the existence of a network with a single face. We show how such a network can be constructed, and we present a heuristic for constructing a network with few faces using the first algorithm as the base case. Experimental results on biological data show that this heuristic algorithm can produce phylogenetic networks with far fewer faces than the ones computed by SplitsTree4, without affecting the approximation of the distance matrix. © 2012 IEEE."
|
|
| |
 
Philippe Gambette,
Katharina Huber and
Guillaume Scholz. Uprooted Phylogenetic Networks. In BMB, Vol. 79(9):2022-2048, 2017.
Keywords: circular split system, explicit network, from splits, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction, split network, uniqueness.
Note: http://arxiv.org/abs/1511.08387.
|
|
|
|
- forked on GitHub.