| |
 
Philippe Gambette and
Katharina Huber. On Encodings of Phylogenetic Networks of Bounded Level. In JOMB, Vol. 65(1):157-180, 2012.
Keywords: characterization, explicit network, from clusters, from rooted trees, from triplets, galled tree, identifiability, level k phylogenetic network, phylogenetic network, uniqueness, weak hierarchy.
Note: http://hal.archives-ouvertes.fr/hal-00609130/en/.
Toggle abstract
"Phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Like phylogenetic trees, such networks canonically induce collections of phylogenetic trees, clusters, and triplets, respectively. Thus it is not surprising that many network approaches aim to reconstruct a phylogenetic network from such collections. Related to the well-studied perfect phylogeny problem, the following question is of fundamental importance in this context: When does one of the above collections encode (i. e. uniquely describe) the network that induces it? For the large class of level-1 (phylogenetic) networks we characterize those level-1 networks for which an encoding in terms of one (or equivalently all) of the above collections exists. In addition, we show that three known distance measures for comparing phylogenetic networks are in fact metrics on the resulting subclass and give the diameter for two of them. Finally, we investigate the related concept of indistinguishability and also show that many properties enjoyed by level-1 networks are not satisfied by networks of higher level. © 2011 Springer-Verlag."
|
|
| |
Stephen J. Willson. CSD Homomorphisms Between Phylogenetic Networks. In TCBB, Vol. 9(4), 2012.
Keywords: explicit network, from network, from quartets, phylogenetic network.
Note: http://www.public.iastate.edu/~swillson/Relationships11IEEE.pdf, preliminary version entitled Relationships Among Phylogenetic Networks.
Toggle abstract
"Since Darwin, species trees have been used as a simplified description of the relationships which summarize the complicated network N of reality. Recent evidence of hybridization and lateral gene transfer, however, suggest that there are situations where trees are inadequate. Consequently it is important to determine properties that characterize networks closely related to N and possibly more complicated than trees but lacking the full complexity of N. A connected surjective digraph map (CSD) is a map f from one network N to another network M such that every arc is either collapsed to a single vertex or is taken to an arc, such that f is surjective, and such that the inverse image of a vertex is always connected. CSD maps are shown to behave well under composition. It is proved that if there is a CSD map from N to M, then there is a way to lift an undirected version of M into N, often with added resolution. A CSD map from N to M puts strong constraints on N. In general, it may be useful to study classes of networks such that, for any N, there exists a CSD map from N to some standard member of that class. © 2012 IEEE."
|
|
| |
  
Steven Kelk,
Celine Scornavacca and
Leo van Iersel. On the elusiveness of clusters. In TCBB, Vol. 9(2):517-534, 2012.
Keywords: explicit network, from clusters, from rooted trees, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, Program Clustistic, reconstruction, software.
Note: http://arxiv.org/abs/1103.1834.
|
|
| |
    
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."
|
|
| |
    
An-Chiang Chu,
Jesper Jansson,
Richard Lemence,
Alban Mancheron and
Kun-Mao Chao. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. In TAMC12, Vol. 7287:177-188 of LNCS, springer, 2012.
Keywords: from triplets, galled network, level k phylogenetic network, phylogenetic network.
Note: preliminary version.
Toggle abstract
"We study the asymptotic behavior of a new type of maximization recurrence, defined as follows. Let k be a positive integer and p k(x) a polynomial of degree k satisfying p k(0) = 0. Define A 0 = 0 and for n ≥ 1, let A n = max 0≤i<n{A i+n kp k(i/n)}. We prove that lim n→∞A n/n n = sup{pk(x)/1-x k : 0≤x<1}. We also consider two closely related maximization recurrences S n and S′ n, defined as S 0 = S′ 0 = 0, and for n ≥ 1, S n = max 0≤i<n{S i + i(n-i)(n-i-1)/2} and S′ n = max 0≤i<n{S′ i + ( 3 n-i) + 2i( 2 n-i) + (n-i)( 2 i)}. We prove that lim n→∞ S′n/3( 3 n) = 2(√3-1)/3 ≈ 0.488033..., resolving an open problem from Bioinformatics about rooted triplets consistency in phylogenetic networks. © 2012 Springer-Verlag."
|
|
| |
Daniel H. Huson and
Celine Scornavacca. Dendroscope 3: An Interactive Tool for Rooted Phylogenetic Trees and Networks. In Systematic Biology, Vol. 61(6):1061-1067, 2012.
Keywords: from rooted trees, from triplets, phylogenetic network, phylogeny, Program Dendroscope, reconstruction, software, visualization.
Toggle abstract
"Dendroscope 3 is a new program for working with rooted phylogenetic trees and networks. It provides a number of methods for drawing and comparing rooted phylogenetic networks, and for computing them from rooted trees. The program can be used interactively or in command-line mode. The program is written in Java, use of the software is free, and installers for all 3 major operating systems can be downloaded from www.dendroscope.org. [Phylogenetic trees; phylogenetic networks; software.] © 2012 The Author(s)."
|
|
| |
 
Michel Habib and
Thu-Hien To. Constructing a Minimum Phylogenetic Network from a Dense Triplet Set. In JBCB, Vol. 10(5):1250013, 2012.
Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://arxiv.org/abs/1103.2266.
Toggle abstract
"For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with T, if there is any, in time O(|T| k+1 n⌊4k/3⌋+1). © 2012 Imperial College Press."
|
|
| |
|
| |
  
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."
|
|
|
- forked on GitHub.