| |
  
Jeremy G. Sumner,
Barbara R. Holland and
Peter D. Jarvis. The algebra of the general Markov model on phylogenetic trees and networks. In BMB, Vol. 74(4):858-880, 2012.
Keywords: abstract network, phylogenetic network, phylogeny, split, split network, statistical model.
Note: http://arxiv.org/abs/1012.5165.
Toggle abstract
"It is known that the Kimura 3ST model of sequence evolution on phylogenetic trees can be extended quite naturally to arbitrary split systems. However, this extension relies heavily on mathematical peculiarities of the associated Hadamard transformation, and providing an analogous augmentation of the general Markov model has thus far been elusive. In this paper, we rectify this shortcoming by showing how to extend the general Markov model on trees to include incompatible edges; and even further to more general network models. This is achieved by exploring the algebra of the generators of the continuous-time Markov chain together with the "splitting" operator that generates the branching process on phylogenetic trees. For simplicity, we proceed by discussing the two state case and then show that our results are easily extended to more states with little complication. Intriguingly, upon restriction of the two state general Markov model to the parameter space of the binary symmetric model, our extension is indistinguishable from the Hadamard approach only on trees; as soon as any incompatible splits are introduced the two approaches give rise to differing probability distributions with disparate structure. Through exploration of a simple example, we give an argument that our extension to more general networks has desirable properties that the previous approaches do not share. In particular, our construction allows for convergent evolution of previously divergent lineages; a property that is of significant interest for biological applications. © 2011 Society for Mathematical Biology."
|
|
| |
  
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."
|
|
| |
Andreas Spillner and
Vincent Moulton. Optimal algorithms for computing edge weights in planar split-networks. In Journal of Applied Mathematics and Computing, Vol. 39(1-2):1-13, 2012.
Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network.
Note: http://dx.doi.org/10.1007/s12190-011-0506-z.
Toggle abstract
"In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graph-theoretical structures represent collections of weighted bipartitions or splits of a finite set, and provide a means to display conflicting evolutionary signals. The weights associated to the splits are used to scale the edges in the network and are often computed using some distance matrix associated with the data. In this paper we present optimal polynomial time algorithms for three basic problems that arise in this context when computing split weights for planar split-networks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outer-labeled planar networks). As part of our analysis, we also derive a Crofton formula for full flat split systems, structures that naturally arise when constructing planar split-networks. © 2011 Korean Society for Computational and Applied Mathematics."
|
|
| |
 
Magnus Bordewich and
Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):69-85, 2012.
Keywords: abstract network, approximation, diversity, phylogenetic network, polynomial, split network.
Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS11.pdf.
Toggle abstract
"Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1-1/e)-approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1-1/e)-approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al. © 2011 Springer-Verlag."
|
|
| |
    
Changiz Eslahchi,
Reza Hassanzadeh,
Ehsan Mottaghi,
Mahnaz Habibi,
Hamid Pezeshk and
Mehdi Sadeghi. Constructing circular phylogenetic networks from weighted quartets using simulated annealing. In MBIO, Vol. 235(2):123-127, 2012.
Keywords: abstract network, from quartets, heuristic, phylogenetic network, phylogeny, Program SAQ-Net, Program SplitsTree, reconstruction, simulated annealing, software, split network.
Note: http://dx.doi.org/10.1016/j.mbs.2011.11.003.
Toggle abstract
"In this paper, we present a heuristic algorithm based on the simulated annealing, SAQ-Net, as a method for constructing phylogenetic networks from weighted quartets. Similar to QNet algorithm, SAQ-Net constructs a collection of circular weighted splits of the taxa set. This collection is represented by a split network. In order to show that SAQ-Net performs better than QNet, we apply these algorithm to both the simulated and actual data sets containing salmonella, Bees, Primates and Rubber data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree4 and compare the results. We find that SAQ-Net produces a better circular ordering and phylogenetic networks than QNet in most cases. SAQ-Net has been implemented in Matlab and is available for download at http://bioinf.cs.ipm.ac.ir/softwares/saq.net. © 2011 Elsevier Inc."
|
|
| |
  
Philippe Gambette,
Vincent Berry and
Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012.
Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, orientation, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network.
Note: http://hal.archives-ouvertes.fr/hal-00678046/en/.
Toggle abstract
"Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press."
|
|
| |
Reza Hassanzadeh,
Changiz Eslahchi and
Wing-Kin Sung. Constructing phylogenetic supernetworks based on simulated annealing. In MPE, Vol. 63(3):738-744, 2012.
Keywords: abstract network, from unrooted trees, heuristic, phylogenetic network, phylogeny, Program SNSA, reconstruction, simulated annealing, software, split network.
Note: http://dx.doi.org/10.1016/j.ympev.2012.02.009.
Toggle abstract
Different partial phylogenetic trees can be derived from different sources of evidence and different methods. One important problem is to summarize these partial phylogenetic trees using a supernetwork. We propose a novel simulated annealing based method called SNSA which uses an optimization function to produce a simple network that still retains a great deal of phylogenetic information. We report the performance of this new method on real and simulated datasets. © 2012 Elsevier Inc.
|
|
| |
Ruogu Sheng and
Sergey Bereg. Approximating Metrics with Planar Boundary-Labeled Phylogenetic Networks. In JBCB, Vol. 10(6):1250017, 2012.
Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa. © 2012 Imperial College Press."
|
|
| |
Cayla McBee. Generalizing Fourier Calculus on Evolutionary Trees to Splits Networks. In ISPAN'12, Pages 149-155, 2012.
Keywords: abstract network, from sequences, phylogenetic network, phylogeny, split network, statistical model.
Toggle abstract
"Biologists have been interested in Phylogenetics, the study of evolutionary relatedness among various groups of organisms, for more than 140 years. In spite of this, it has only been in the last 40 years that advances in technology and the availability of DNA sequences have led to statistical, computational and algorithmic work on determining evolutionary relatedness between organisms. One method of determining historical relationships between organisms is to assume a group based evolutionary model and use a discrete Fourier transform. The 1993 paper 'Fourier Calculus on Evolutionary Trees' by L.A. Szekely, M.A. Steel and P.L. Erdos outlines this process. The transform presented in Szekely et al provides an invertible relationship between phylogenetic trees and expected frequencies of nucleotide patterns in nucleotide sequences. This implies that given a set of nucleotide sequences from various organisms it is possible to construct a phylogenetic tree that represents the historical relationships of those organisms. Some scenarios are poorly described by phylogenetic trees and there are biological and statistical reasons for using networks to model phylogenetic relationships. Given this motivation I have generalized Szekely et al's result to apply to a specific type of phylogenetic network known as a splits network. © 2012 IEEE."
|
|
| |
  
Fenglou Mao,
David Williams,
Olga Zhaxybayeva,
Maria S. Poptsova,
Pascal Lapierre,
J. Peter Gogarten and
Ying Xu. Quartet decomposition server: a platform for analyzing phylogenetic trees. In BMCB, Vol. 13:123, 2012.
Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program Quartet Decomposition, reconstruction, software, split network.
Toggle abstract
"Background: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes.Results: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu.Conclusions: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts. © 2012 Mao et al.; licensee BioMed Central Ltd."
|
|
| |
 
Donovan H. Parks and
Robert G. Beiko. Measuring Community Similarity with Phylogenetic Networks. In MBE, Vol. 29(12):3947-3958, 2012.
Keywords: abstract network, diversity, phylogenetic network, phylogeny, split network.
Note: poster available at http://dparks.wdfiles.com/local--files/publications/SMBE_BetaDiversity_2011.pdf.
Toggle abstract
"Environmental drivers of biodiversity can be identified by relating patterns of community similarity to ecological factors. Community variation has traditionally been assessed by considering changes in species composition and more recently by incorporating phylogenetic information to account for the relative similarity of taxa. Here, we describe how an important class of measures including Bray-Curtis, Canberra, and UniFrac can be extended to allow community variation to be computed on a phylogenetic network. We focus on phylogenetic split systems, networks that are produced by the widely used median network and neighbor-net methods, which can represent incongruence in the evolutionary history of a set of taxa. Calculating β diversity over a split system provides a measure of community similarity averaged over uncertainty or conflict in the available phylogenetic signal. Our freely available software, Network Diversity, provides 11 qualitative (presence-absence, unweighted) and 14 quantitative (weighted) network-based measures of community similarity that model different aspects of community richness and evenness. We demonstrate the broad applicability of network-based diversity approaches by applying them to three distinct data sets: pneumococcal isolates from distinct geographic regions, human mitochondrial DNA data from the Indonesian island of Nias, and proteorhodopsin sequences from the Sargasso and Mediterranean Seas. Our results show that major expected patterns of variation for these data sets are recovered using network-based measures, which indicates that these patterns are robust to phylogenetic uncertainty and conflict. Nonetheless, network-based measures of community similarity can differ substantially from measures ignoring phylogenetic relationships or from tree-based measures when incongruent signals are present in the underlying data. Network-based measures provide a methodology for assessing the robustness of β-diversity results in light of incongruent phylogenetic signal and allow β diversity to be calculated over widely used network structures such as median networks. © 2012 The Author 2012."
|
|
|
- forked on GitHub.