| |
   
Leo van Iersel,
Steven Kelk,
Giorgios Stamoulis,
Leen Stougie and
Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. In ALG, Vol. 80(11):2993-3022, 2018.
Keywords: explicit network, FPT, from network, from unrooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, tree containment.
Note: https://hal.inria.fr/hal-01599716.
|
|
| |
  
Magnus Bordewich,
Charles Semple and
Nihan Tokac. Constructing tree-child networks from distance matrices. In Algorithmica, Vol. 80(8):2240-2259, 2018.
Keywords: compressed network, explicit network, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, tree child network, uniqueness.
Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSN17.pdf.
|
|
| |
     
Sarah Bastkowski,
Daniel Mapleson,
Andreas Spillner,
Taoyang Wu,
Monika Balvociute and
Vincent Moulton. SPECTRE: a Suite of PhylogEnetiC Tools for Reticulate Evolution. In BIO, Vol. 34(6):1057-1058, 2018.
Keywords: abstract network, NeighborNet, phylogenetic network, phylogeny, Program FlatNJ, Program QNet, Program SplitsTree, reconstruction, software, split network.
Note: https://doi.org/10.1101/169177.
|
|
| |
|
| |
 
Misagh Kordi and
Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In TCBB, Vol. 14(3):587-599, 2017.
Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://compbio.engr.uconn.edu/papers/Kordi_DTLreconciliationPreprint2015.pdf.
|
|
| |
  
Bingxin Lu,
Louxin Zhang and
Hon Wai Leong. A program to compute the soft Robinson-Foulds distance between phylogenetic networks. In APBC17, Vol. 18(Suppl. 2):111 of BMC Genomics, 2017.
Keywords: cluster containment, distance between networks, explicit network, exponential algorithm, from network, phylogenetic network, phylogeny, Program icelu-PhyloNetwork.
Note: http://dx.doi.org/10.1186/s12864-017-3500-5.
|
|
| |
   
Klaus Schliep,
Alastair J. Potts,
David A. Morrison and
Guido W. Grimm. Intertwining phylogenetic trees and networks. In Methods in Ecology and Evolution, Vol. 8(10):1212-1220, 2017.
Keywords: abstract network, from network, from unrooted trees, phylogenetic network, phylogeny, split network, visualization.
Note: http://dx.doi.org/10.1111/2041-210X.12760.
|
|
| |
  
Kuang-Yu Chang,
Yun Cui,
Siu-Ming Yiu and
Wing-Kai Hon. Reconstructing One-Articulated Networks with Distance Matrices. In ISBRA17, Vol. 10330:34-45 of LNCS, Springer, 2017.
Keywords: explicit network, from distances, k-reticulated, phylogenetic network, phylogeny, reconstruction.
Note: https://link.springer.com/content/pdf/10.1007%2F978-3-319-59575-7.pdf#page=100.
|
|
| |
    
François Chevenet,
Jean-Philippe Doyon,
Celine Scornavacca,
Edwin Jacox,
Emmanuelle Jousselin and
Vincent Berry. SylvX: a viewer for phylogenetic tree reconciliations. In BIO, Vol. 32(4):608-610, 2016.
Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program SylvX, software, visualization.
Note: https://www.researchgate.net/profile/Emmanuelle_Jousselin/publication/283446016_SylvX_a_viewer_for_phylogenetic_tree_reconciliations/links/5642146108aec448fa621efa.pdf.
|
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
Misagh Kordi and
Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In ISBRA15, Vol. 9096:187-198 of LNCS, springer, 2015.
Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://compbio.engr.uconn.edu/papers/Kordi_ISBRA2015.pdf.
|
|
| |
 
Yun Yu and
Luay Nakhleh. A Distance-Based Method for Inferring Phylogenetic Networks in the Presence of Incomplete Lineage Sorting. In ISBRA15, Vol. 9096:378-389 of LNCS, springer, 2015.
Keywords: bootstrap, explicit network, from distances, heuristic, incomplete lineage sorting, phylogenetic network, phylogeny, reconstruction.
Note: http://bioinfo.cs.rice.edu/sites/bioinfo.cs.rice.edu/files/YuNakhleh-ISBRA15.pdf.
|
|
| |
|
| |
Yun Yu and
Luay Nakhleh. A maximum pseudo-likelihood approach for phylogenetic networks. In RECOMB-CG15, Vol. 16(Suppl 10)(S10):1-10 of BMC Genomics, BioMed Central, 2015.
Keywords: explicit network, from rooted trees, hybridization, incomplete lineage sorting, likelihood, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, tripartition distance.
Note: http://dx.doi.org/10.1186/1471-2164-16-S10-S10.
|
|
| |
|
| |
Ward C Wheeler. Phyletic groups on networks. In Cladistics, Vol. 30(4):447-451, 2014.
Keywords: explicit network, from network, phylogenetic network, phylogeny.
Note: http://dx.doi.org/10.1111/cla.12062.
Toggle abstract
"Three additional phyletic group types, "periphyletic," "epiphyletic", and "anaphyletic" (in addition to Hennigian mono-, para-, and polyphyletic) are defined in terms of trees and phylogenetic networks (trees with directed reticulate edges) via a generalization of the algorithmic definitions of Farris. These designations concern groups defined as monophyletic on trees, but with additional gains or losses of members from network edges. These distinctions should be useful in discussion of systems with non-vertical inheritance such as recombination between viruses, horizontal exchange between bacteria, hybridization in plants and animals, as well as human linguistic evolution. Examples are illustrated with Indo-European language groups. © The Willi Hennig Society 2013."
|
|
| |
Sarah Bastkowski,
Andreas Spillner and
Vincent Moulton. Fishing for minimum evolution trees with Neighbor-Nets. In IPL, Vol. 114(1-2):3-18, 2014.
Keywords: circular split system, from distances, NeighborNet, phylogeny, polynomial.
Toggle abstract
"In evolutionary biology, biologists commonly use a phylogenetic tree to represent the evolutionary history of some set of species. A common approach taken to construct such a tree is to search through the space of all possible phylogenetic trees on the set so as to find one that optimizes some score function, such as the minimum evolution criterion. However, this is hampered by the fact that the space of phylogenetic trees is extremely large in general. Interestingly, an alternative approach, which has received somewhat less attention in the literature, is to instead search for trees within some set of bipartitions or splits of the set of species in question. Here we consider the problem of searching through a set of splits that is circular. Such sets can, for example, be generated by the NeighborNet algorithm for constructing phylogenetic networks. More specifically, we present an O(n4) time algorithm for finding an optimal minimum evolution tree in a circular set of splits on a set of species of size n. In addition, using simulations, we compare the performance of this algorithm when applied to NeighborNet output with that of FastME, a leading method for searching for minimum evolution trees in tree space. We find that, even though a circular set of splits represents just a tiny fraction of the total number of possible splits of a set, the trees obtained from circular sets compare quite favorably with those obtained with FastME, suggesting that the approach could warrant further investigation. © 2013 Elsevier B.V."
|
|
| |
Lavanya Kannan and
Ward C Wheeler. Exactly Computing the Parsimony Scores on Phylogenetic Networks Using Dynamic Programming. In JCB, Vol. 21(4):303-319, 2014.
Keywords: explicit network, exponential algorithm, from network, from sequences, parsimony, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Scoring a given phylogenetic network is the first step that is required in searching for the best evolutionary framework for a given dataset. Using the principle of maximum parsimony, we can score phylogenetic networks based on the minimum number of state changes across a subset of edges of the network for each character that are required for a given set of characters to realize the input states at the leaves of the networks. Two such subsets of edges of networks are interesting in light of studying evolutionary histories of datasets: (i) the set of all edges of the network, and (ii) the set of all edges of a spanning tree that minimizes the score. The problems of finding the parsimony scores under these two criteria define slightly different mathematical problems that are both NP-hard. In this article, we show that both problems, with scores generalized to adding substitution costs between states on the endpoints of the edges, can be solved exactly using dynamic programming. We show that our algorithms require O(mpk) storage at each vertex (per character), where k is the number of states the character can take, p is the number of reticulate vertices in the network, m = k for the problem with edge set (i), and m = 2 for the problem with edge set (ii). This establishes an O(nmpk2) algorithm for both the problems (n is the number of leaves in the network), which are extensions of Sankoff's algorithm for finding the parsimony scores for phylogenetic trees. We will discuss improvements in the complexities and show that for phylogenetic networks whose underlying undirected graphs have disjoint cycles, the storage at each vertex can be reduced to O(mk), thus making the algorithm polynomial for this class of networks. We will present some properties of the two approaches and guidance on choosing between the criteria, as well as traverse through the network space using either of the definitions. We show that our methodology provides an effective means to study a wide variety of datasets. © Copyright 2014, Mary Ann Liebert, Inc. 2014."
|
|
| |
   
Kevin J. Liu,
Jingxuan Dai,
Kathy Truong,
Ying Song,
Michael H. Kohn and
Luay Nakhleh. An HMM-Based Comparative Genomic Framework for Detecting Introgression in Eukaryotes. In PLoS ONE, Vol. 10(6):e1003649, 2014.
Keywords: explicit network, from network, phylogenetic network, phylogeny, Program PhyloNet-HMM.
Note: http://arxiv.org/abs/1310.7989.
Toggle abstract
"One outcome of interspecific hybridization and subsequent effects of evolutionary forces is introgression, which is the integration of genetic material from one species into the genome of an individual in another species. The evolution of several groups of eukaryotic species has involved hybridization, and cases of adaptation through introgression have been already established. In this work, we report on PhyloNet-HMM-a new comparative genomic framework for detecting introgression in genomes. PhyloNet-HMM combines phylogenetic networks with hidden Markov models (HMMs) to simultaneously capture the (potentially reticulate) evolutionary history of the genomes and dependencies within genomes. A novel aspect of our work is that it also accounts for incomplete lineage sorting and dependence across loci. Application of our model to variation data from chromosome 7 in the mouse (Mus musculus domesticus) genome detected a recently reported adaptive introgression event involving the rodent poison resistance gene Vkorc1, in addition to other newly detected introgressed genomic regions. Based on our analysis, it is estimated that about 9% of all sites within chromosome 7 are of introgressive origin (these cover about 13 Mbp of chromosome 7, and over 300 genes). Further, our model detected no introgression in a negative control data set. We also found that our model accurately detected introgression and other evolutionary processes from synthetic data sets simulated under the coalescent model with recombination, isolation, and migration. Our work provides a powerful framework for systematic analysis of introgression while simultaneously accounting for dependence across sites, point mutations, recombination, and ancestral polymorphism. © 2014 Liu et al."
|
|
| |
|
| |
Juan Wang. A new algorithm to construct phylogenetic networks from trees. In Genetics and Molecular Research, Vol. 13(1):1456-1464, 2014.
Keywords: explicit network, from clusters, heuristic, phylogenetic network, Program LNetwork, Program QuickCass, reconstruction.
Note: http://dx.doi.org/10.4238/2014.March.6.4.
Toggle abstract
"Developing appropriate methods for constructing phylogenetic networks from tree sets is an important problem, and much research is currently being undertaken in this area. BIMLR is an algorithm that constructs phylogenetic networks from tree sets. The algorithm can construct a much simpler network than other available methods. Here, we introduce an improved version of the BIMLR algorithm, QuickCass. QuickCass changes the selection strategy of the labels of leaves below the reticulate nodes, i.e., the nodes with an indegree of at least 2 in BIMLR. We show that QuickCass can construct simpler phylogenetic networks than BIMLR. Furthermore, we show that QuickCass is a polynomial-time algorithm when the output network that is constructed by QuickCass is binary. © FUNPEC-RP."
|
|
| |
|
| |
|
| |
 
Stefan Grünewald,
Andreas Spillner,
Sarah Bastkowski,
Anja Bögershausen and
Vincent Moulton. SuperQ: Computing Supernetworks from Quartets. In TCBB, Vol. 10(1):151-160, 2013.
Keywords: abstract network, circular split system, from quartets, heuristic, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, Program SuperQ, software, split network.
Toggle abstract
"Supertrees are a commonly used tool in phylogenetics to summarize collections of partial phylogenetic trees. As a generalization of supertrees, phylogenetic supernetworks allow, in addition, the visual representation of conflict between the trees that is not possible to observe with a single tree. Here, we introduce SuperQ, a new method for constructing such supernetworks (SuperQ is freely available at >www.uea.ac.uk/computing/superq.). It works by first breaking the input trees into quartet trees, and then stitching these together to form a special kind of phylogenetic network, called a split network. This stitching process is performed using an adaptation of the QNet method for split network reconstruction employing a novel approach to use the branch lengths from the input trees to estimate the branch lengths in the resulting network. Compared with previous supernetwork methods, SuperQ has the advantage of producing a planar network. We compare the performance of SuperQ to the Z-closure and Q-imputation supernetwork methods, and also present an analysis of some published data sets as an illustration of its applicability. © 2004-2012 IEEE."
|
|
| |
   
Hoa Vu,
Francis Chin,
Wing-Kai Hon,
Henry Leung,
Kunihiko Sadakane,
Wing-Kin Sung and
Siu-Ming Yiu. Reconstructing k-Reticulated Phylogenetic Network from a Set of Gene Trees. In ISBRA13, Vol. 7875:112-124 of LNCS, springer, 2013.
Keywords: from rooted trees, k-reticulated, phylogenetic network, phylogeny, polynomial, Program ARTNET, Program CMPT, reconstruction.
Note: http://grid.cs.gsu.edu/~xguo9/publications/2013_Cloud%20computing%20for%20de%20novo%20metagenomic%20sequence%20assembly.pdf#page=123.
Toggle abstract
"The time complexity of existing algorithms for reconstructing a level-x phylogenetic network increases exponentially in x. In this paper, we propose a new classification of phylogenetic networks called k-reticulated network. A k-reticulated network can model all level-k networks and some level-x networks with x > k. We design algorithms for reconstructing k-reticulated network (k = 1 or 2) with minimum number of hybrid nodes from a set of m binary trees, each with n leaves in O(mn 2) time. The implication is that some level-x networks with x > k can now be reconstructed in a faster way. We implemented our algorithm (ARTNET) and compared it with CMPT. We show that ARTNET outperforms CMPT in terms of running time and accuracy. We also consider the case when there does not exist a 2-reticulated network for the input trees. We present an algorithm computing a maximum subset of the species set so that a new set of subtrees can be combined into a 2-reticulated network. © 2013 Springer-Verlag."
|
|
| |
Yun Yu,
R. Matthew Barnett and
Luay Nakhleh. Parsimonious Inference of Hybridization in the Presence of Incomplete Lineage Sorting. In Systematic Biology, Vol. 62(5):738-751, 2013.
Keywords: from network, from rooted trees, hybridization, lineage sorting, parsimony, phylogenetic network, phylogeny, Program PhyloNet, reconstruction.
Toggle abstract
"Hybridization plays an important evolutionary role in several groups of organisms. A phylogenetic approach to detect hybridization entails sequencing multiple loci across the genomes of a group of species of interest, reconstructing their gene trees, and taking their differences as indicators of hybridization. However, methods that follow this approach mostly ignore population effects, such as incomplete lineage sorting (ILS). Given that hybridization occurs between closely related organisms, ILS may very well be at play and, hence, must be accounted for in the analysis framework. To address this issue, we present a parsimony criterion for reconciling gene trees within the branches of a phylogenetic network, and a local search heuristic for inferring phylogenetic networks from collections of gene-tree topologies under this criterion. This framework enables phylogenetic analyses while accounting for both hybridization and ILS. Further, we propose two techniques for incorporating information about uncertainty in gene-tree estimates. Our simulation studies demonstrate the good performance of our framework in terms of identifying the location of hybridization events, as well as estimating the proportions of genes that underwent hybridization. Also, our framework shows good performance in terms of efficiency on handling large data sets in our experiments. Further, in analysing a yeast data set, we demonstrate issues that arise when analysing real data sets. Although a probabilistic approach was recently introduced for this problem, and although parsimonious reconciliations have accuracy issues under certain settings, our parsimony framework provides a much more computationally efficient technique for this type of analysis. Our framework now allows for genome-wide scans for hybridization, while also accounting for ILS. [Phylogenetic networks; hybridization; incomplete lineage sorting; coalescent; multi-labeled trees.] © 2013 The Author(s). All rights reserved."
|
|
| |
 
Zhi-Zhong Chen and
Lusheng Wang. An Ultrafast Tool for Minimum Reticulate Networks. In JCB, Vol. 20(1):38-41, 2013.
Keywords: agreement forest, explicit network, from rooted trees, phylogenetic network, phylogeny, Program ultra-Net, reconstruction.
Note: http://www.cs.cityu.edu.hk/~lwang/research/jcb2013.pdf.
Toggle abstract
"Due to hybridization events in evolution, studying different genes of a set of species may yield two or more related but different phylogenetic trees for the set of species. In this case, we want to combine the trees into a reticulate network with the fewest hybridization events. In this article, we develop a software tool (named UltraNet) for several fundamental problems related to the construction of minimum reticulate networks from two or more phylogenetic trees. Our experimental results show that UltraNet is much faster than all previous tools for these problems. © 2013 Mary Ann Liebert, Inc."
|
|
| |
|
| |
   
Alberto Apostolico,
Matteo Comin,
Andreas W. M. Dress and
Laxmi Parida. Ultrametric networks: a new tool for phylogenetic analysis. In Algorithms for Molecular Biology, Vol. 8(7):1-10, 2013.
Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program Ultranet.
Note: http://dx.doi.org/10.1186/1748-7188-8-7.
Toggle abstract
"Background: The large majority of optimization problems related to the inference of distance-based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.Results: This paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availability: http://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html. © 2013 Apostolico et al.; licensee BioMed Central Ltd."
|
|
| |
|
| |
Sarah Bastkowski. From Trees to Networks and Back. PhD thesis, University of East Anglia, 2013.
Keywords: abstract network, NeighborNet, phylogenetic network, phylogeny, Program FlatNJ, Program QNet, Program SplitsTree, reconstruction, software, split network.
Note: http://spectre-suite-of-phylogenetic-tools-for-reticulate-evolution.readthedocs.io/en/latest/_downloads/spectre_bastkowskis_thesis.pdf.
|
|
| |
|
| |
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."
|
|
| |
Yun Yu,
James H. Degnan and
Luay Nakhleh. The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection. In PLoS Genetics, Vol. 8(4):e1002660, 2012.
Keywords: AIC, BIC, explicit network, hybridization, phylogenetic network, phylogeny, statistical model.
Note: http://dx.doi.org/10.1371/journal.pgen.1002660.
Toggle abstract
"Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa. © 2012 Yu et al."
|
|
| |
Hyun Jung Park and
Luay Nakhleh. MURPAR: A fast heuristic for inferring parsimonious phylogenetic networks from multiple gene trees. In ISBRA12, Vol. 7292:213-224 of LNCS, springer, 2012.
Keywords: explicit network, from unrooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, software.
Note: https://www.researchgate.net/profile/Hyun_Jung_Park2/publication/262318595_MURPAR_A_Fast_Heuristic_for_Inferring_Parsimonious_Phylogenetic_Networks_from_Multiple_Gene_Trees/links/54b7e7b50cf269d8cbf58cc4.pdf.
Toggle abstract
"Phylogenetic networks provide a graphical representation of evolutionary histories that involve non-treelike evolutionary events, such as horizontal gene transfer (HGT). One approach for inferring phylogenetic networks is based on reconciling gene trees, assuming all incongruence among the gene trees is due to HGT. Several mathematical results and algorithms, both exact and heuristic, have been introduced to construct and analyze phylogenetic networks. Here, we address the computational problem of inferring phylogenetic networks with minimum reticulations from a collection of gene trees. As this problem is known to be NP-hard even for a pair of gene trees, the problem at hand is very hard. In this paper, we present an efficient heuristic, MURPAR, for inferring a phylogenetic network from a collection of gene trees by using pairwise reconciliations of trees in the collection. Given the development of efficient and accurate methods for pairwise gene tree reconciliations, MURPAR inherits this efficiency and accuracy. Further, the method includes a formulation for combining pairwise reconciliations that is naturally amenable to an efficient integer linear programming (ILP) solution. We show that MURPAR produces more accurate results than other methods and is at least as fast, when run on synthetic and biological data. We believe that our method is especially important for rapidly obtaining estimates of genome-scale evolutionary histories that can be further refined by more detailed and compute-intensive methods. © 2012 Springer-Verlag."
|
|
| |
Lavanya Kannan and
Ward C Wheeler. Maximum Parsimony on Phylogenetic Networks. In ALMOB, Vol. 7:9, 2012.
Keywords: dynamic programming, explicit network, from sequences, heuristic, parsimony, phylogenetic network, phylogeny.
Note: http://dx.doi.org/10.1186/1748-7188-7-9.
Toggle abstract
"Background: Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a character-based approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past.Results: In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain well-known algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores.Conclusion: The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an in-built cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network. © 2012 Kannan and Wheeler; licensee BioMed Central Ltd."
|
|
| |
 
Katharina Huber,
Vincent Moulton,
Andreas Spillner,
Sabine Storandt and
Radoslaw Suchecki. Computing a consensus of multilabeled trees. In ALENEX12, Pages 84-92, 2012.
Keywords: duplication, explicit network, exponential algorithm, phylogenetic network, phylogeny.
Note: http://siam.omnibooksonline.com/2012ALENEX/data/papers/020.pdf.
Toggle abstract
In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential run-time in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.
|
|
| |
Zhi-Zhong Chen,
Fei Deng and
Lusheng Wang. Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers. In TCBB, Vol. 9(5):1515-1528, 2012.
Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction.
Note: http://www.cs.cityu.edu.hk/~lwang/research/tcbb2012c.pdf.
Toggle abstract
"We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m+3 k/c n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m+2.78 k/cn). © 2004-2012 IEEE."
|
|
| |
 
Shlomo Moran,
Sagi Snir and
Wing-Kin Sung. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds. In ACM Transactions on Algorithms, Vol. 7(4), 2011.
Keywords: evaluation, galled tree, phylogenetic network.
Note: http://www.cs.technion.ac.il/~moran/r/PS/gnets-TOA-7Feb2007.pdf.
Toggle abstract
"A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as convex recoloring (CR).While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest. © 2011 ACM."
|
|
| |
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."
|
|
| |
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)."
|
|
| |
Alethea Rea. Statistical approaches to phylogenetic networks, recombination and testing of incongruence. PhD thesis, The University of Auckland, New Zealand, 2011.
Keywords: abstract network, AIC, BIC, phylogenetic network, phylogeny, split, split network, statistical model.
Note: https://researchspace.auckland.ac.nz/handle/2292/67624.
|
|
| |
 
Louxin Zhang,
Yen Kaow Ng,
Taoyang Wu and
Yu Zheng. Network model and efficient method for detecting relative duplications or horizontal gene transfers. In ICCABS11, Pages 214-219, 2011.
Keywords: dynamic programming, explicit network, from network, from rooted trees, from species tree, phylogenetic network, phylogeny, polynomial, reconstruction.
Toggle abstract
"Background: Horizontal gene transfer and gene duplication are two significant forces behind genome evolution. As more and more well-supported examples of HGTs are being revealed, there is a growing awareness that HGT is more widespread than previously thought, occurring often not only within bacteria, but also between species remotely related such as bacteria and plants or plants and animals. Although a substantial number of genomic sequences are known, HGT inference remains challenging. Parsimony-based inferences of HGT events are typically NP-hard under the framework of gene tree and species tree comparison; it is even more timeconsuming if the maximum likelihood approach is used. The fact that gene tree and species tree incongruence can be further confounded by gene duplication and gene loss events motivates us to incorporate considerations for these events into our inference of HGT events. Similarly, it will be beneficial if known HGT events are considered in the inference of gene duplications and gene losses. © 2011 IEEE."
|
|
| |
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.
|
|
| |
|
| |
     
Marta Melé,
Asif Javed,
Marc Pybus,
Francesc Calafell,
Laxmi Parida,
Jaume Bertranpetit and
Genographic Consortium. A New Method to Reconstruct Recombination Events at a Genomic Scale. In PLoS Computational Biology, Vol. 6(11):e1001010, 2010.
Keywords: explicit network, from sequences, phylogenetic network, phylogeny.
Note: http://dx.doi.org/10.1371/journal.pcbi.1001010.
Toggle abstract
"Recombination is one of the main forces shaping genome diversity, but the information it generates is often overlooked. A recombination event creates a junction between two parental sequences that may be transmitted to the subsequent generations. Just like mutations, these junctions carry evidence of the shared past of the sequences. We present the IRiS algorithm, which detects past recombination events from extant sequences and specifies the place of each recombination and which are the recombinants sequences. We have validated and calibrated IRiS for the human genome using coalescent simulations replicating standard human demographic history and a variable recombination rate model, and we have finetuned IRiS parameters to simultaneously optimize for false discovery rate, sensitivity, and accuracy in placing the recombination events in the sequence. Newer recombinations overwrite traces of past ones and our results indicate more recent recombinations are detected by IRiS with greater sensitivity. IRiS analysis of the MS32 region, previously studied using sperm typing, showed good concordance with estimated recombination rates. We also applied IRiS to haplotypes for 18 X-chromosome regions in HapMap Phase 3 populations. Recombination events detected for each individual were recoded as binary allelic states and combined into recotypes. Principal component analysis and multidimensional scaling based on recotypes reproduced the relationships between the eleven HapMap Phase III populations that can be expected from known human population history, thus further validating IRiS. We believe that our new method will contribute to the study of the distribution of recombination events across the genomes and, for the first time, it will allow the use of recombination as genetic marker to study human genetic variation. © 2010 Mele ́ et al."
|
|
| |
Sagi Snir and
Edward Trifonov. A Novel Technique for Detecting Putative Horizontal Gene Transfer in the Sequence Space. In JCB, Vol. 17(11):1535-1548, 2010.
Keywords: from sequences, phylogenetic network, phylogeny, reconstruction.
Note: http://research.haifa.ac.il/~ssagi/published%20papers/JCB-HGT.pdf.
Toggle abstract
"Horizontal transfer (HT) is the event of a DNA sequence being transferred between species not by inheritance. This phenomenon violates the tree-like evolution of the species under study turning the trees into networks. At the sequence level, HT offers basic characteristics that enable not only clear identification and distinguishing from other sequence similarity cases but also the possibility of dating the events. We developed a novel, self-contained technique to identify relatively recent horizontal transfer elements (HTEs) in the sequences. Appropriate formalism allows one to obtain confidence values for the events detected. The technique does not rely on such problematic prerequisites as reliable phylogeny and/or statistically justified pairwise sequence alignment. In conjunction with the unique properties of HT, it gives rise to a two-level sequence similarity algorithm that, to the best of our knowledge, has not been explored. From evolutionary perspective, the novelty of the work is in the combination of small scale and large scale mutational events. The technique is employed on both simulated and real biological data. The simulation results show high capability of discriminating between HT and conserved regions. On the biological data, the method detected documented HTEs along with their exact locations in the recipient genomes. Supplementary Material is available online at www.libertonline.com/cmb. Copyright 2010, Mary Ann Liebert, Inc."
|
|
| |
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.
|
|
| |
Sagi Snir and
Tamir Tuller. The NET-HMM approach: Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In JBCB, Vol. 7(4):625-644, 2009.
Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model.
Note: http://research.haifa.ac.il/~ssagi/published%20papers/Snir-NET-HMM-JBCB-2009.pdf.
Toggle abstract
"Horizontal gene transfer (HGT) is the event of transferring genetic material from one lineage in the evolutionary tree to a different lineage. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Although the prevailing assumption is of complete HGT, cases of partial HGT (which are also named chimeric HGT) where only part of a gene is horizontally transferred, have also been reported, albeit less frequently. In this work we suggest a new probabilistic model, the NET-HMM, for analyzing and modeling phylogenetic networks. This new model captures the biologically realistic assumption that neighboring sites of DNA or amino acid sequences are not independent, which increases the accuracy of the inference. The model describes the phylogenetic network as a Hidden Markov Model (HMM), where each hidden state is related to one of the network's trees. One of the advantages of the NET-HMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NET-HMM, devise efficient algorithms for solving a set of problems related to it, and implement them in software. We also provide a novel complementary significance test for evaluating the fitness of a model (NET-HMM) to a given dataset. Using NET-HMM, we are able to answer interesting biological questions, such as inferring the length of partial HGT's and the affected nucleotides in the genomic sequences, as well as inferring the exact location of HGT events along the tree branches. These advantages are demonstrated through the analysis of synthetical inputs and three different biological inputs. © 2009 Imperial College Press."
|
|
| |
|
| |
Martin Lott,
Andreas Spillner,
Katharina Huber and
Vincent Moulton. PADRE: A Package for Analyzing and Displaying Reticulate Evolution. In BIO, Vol. 25(9):1199-1200, 2009.
Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction, software.
Note: http://dx.doi.org/10.1093/bioinformatics/btp133.
Toggle abstract
"Recent advances in gene sequencing for polyploid species, coupled with standard phylogenetic tree reconstruction, leads to gene trees in which the same species can label several leaves. Such multi-labeled trees are then used to reconstruct the evolutionary history of the polyploid species in question. However, this reconstruction process requires new techniques that are not available in current phylogenetic software packages. Here, we describe the software package PADRE (Package for Analyzing and Displaying Reticulate Evolution) that implements such techniques, allowing the reconstruction of complex evolutionary histories for polyploids in the form of phylogenetic networks. © The Author 2009. Published by Oxford University Press. All rights reserved."
|
|
| |
Laxmi Parida,
Asif Javed,
Marta Melé,
Francesc Calafell,
Jaume Bertranpetit and
Genographic Consortium. Minimizing recombinations in consensus networks for phylogeographic studies. In BMCB, Vol. 10(Suppl 1):S72, 2009.
Note: Selected papers from the Seventh Asia-Pacific Bioinformatics Conference (APBC 2009), http://dx.doi.org/10.1186/1471-2105-10-S1-S72.
Toggle abstract
"Background: We address the problem of studying recombinational variations in (human) populations. In this paper, our focus is on one computational aspect of the general task: Given two networks G1 and G2, with both mutation and recombination events, defined on overlapping sets of extant units the objective is to compute a consensus network G3 with minimum number of additional recombinations. We describe a polynomial time algorithm with a guarantee that the number of computed new recombination events is within = sz(G1, G2) (function sz is a well-behaved function of the sizes and topologies of G1 and G2) of the optimal number of recombinations. To date, this is the best known result for a network consensus problem. Results: Although the network consensus problem can be applied to a variety of domains, here we focus on structure of human populations. With our preliminary analysis on a segment of the human Chromosome X data we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. These results have been verified independently using traditional manual procedures. To the best of our knowledge, this is the first recombinations-based characterization of human populations. Conclusion: We show that our mathematical model identifies recombination spots in the individual haplotypes; the aggregate of these spots over a set of haplotypes defines a recombinational landscape that has enough signal to detect continental as well as population divide based on a short segment of Chromosome X. In particular, we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. The agreement with mutation-based analysis can be viewed as an indirect validation of our results and the model. Since the model in principle gives us more information embedded in the networks, in our future work, we plan to investigate more non-traditional questions via these structures computed by our methodology. © 2009 Parida et al; licensee BioMed Central Ltd."
|
|
| |
 
Sarah C. Ayling and
Terence A. Brown. Novel methodology for construction and pruning of quasi-median networks. In BMCB, Vol. 9:115, 2009.
Keywords: abstract network, from sequences, median network, phylogenetic network, phylogeny, quasi-median network, reconstruction.
Note: http://dx.doi.org/10.1186/1471-2105-9-115.
Toggle abstract
"BACKGROUND: Visualising the evolutionary history of a set of sequences is a challenge for molecular phylogenetics. One approach is to use undirected graphs, such as median networks, to visualise phylogenies where reticulate relationships such as recombination or homoplasy are displayed as cycles. Median networks contain binary representations of sequences as nodes, with edges connecting those sequences differing at one character; hypothetical ancestral nodes are invoked to generate a connected network which contains all most parsimonious trees. Quasi-median networks are a generalisation of median networks which are not restricted to binary data, although phylogenetic information contained within the multistate positions can be lost during the preprocessing of data. Where the history of a set of samples contain frequent homoplasies or recombination events quasi-median networks will have a complex topology. Graph reduction or pruning methods have been used to reduce network complexity but some of these methods are inapplicable to datasets in which recombination has occurred and others are procedurally complex and/or result in disconnected networks. RESULTS: We address the problems inherent in construction and reduction of quasi-median networks. We describe a novel method of generating quasi-median networks that uses all characters, both binary and multistate, without imposing an arbitrary ordering of the multistate partitions. We also describe a pruning mechanism which maintains at least one shortest path between observed sequences, displaying the underlying relations between all pairs of sequences while maintaining a connected graph. CONCLUSION: Application of this approach to 5S rDNA sequence data from sea beet produced a pruned network within which genetic isolation between populations by distance was evident, demonstrating the value of this approach for exploration of evolutionary relationships."
|
|
| |
Martin Lott. New Methods for Constructing Phylogenetic Networks from Multi-Labelled Trees. PhD thesis, University of East Anglia, U.K., 2009.
Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction, software.
Note: http://www.ic0.net/thesis-martin-final.pdf.
|
|
| |
 
Martin Lott,
Andreas Spillner,
Katharina Huber,
Anna Petri,
Bengt Oxelman and
Vincent Moulton. Inferring polyploid phylogenies from multiply-labeled gene trees. In BMCEB, Vol. 9:216, 2009.
Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction.
Note: http://dx.doi.org/10.1186/1471-2148-9-216.
Toggle abstract
"Background : Gene trees that arise in the context of reconstructing the evolutionary history of polyploid species are often multiply-labeled, that is, the same leaf label can occur several times in a single tree. This property considerably complicates the task of forming a consensus of a collection of such trees compared to usual phylogenetic trees. Results. We present a method for computing a consensus tree of multiply-labeled trees. As with the well-known greedy consensus tree approach for phylogenetic trees, our method first breaks the given collection of gene trees into a set of clusters. It then aims to insert these clusters one at a time into a tree, starting with the clusters that are supported by most of the gene trees. As the problem to decide whether a cluster can be inserted into a multiply-labeled tree is computationally hard, we have developed a heuristic method for solving this problem. Conclusion. We illustrate the applicability of our method using two collections of trees for plants of the genus Silene, that involve several allopolyploids at different levels. © 2009 Lott et al; licensee BioMed Central Ltd."
|
|
| |
|
| |
|
| |
|
| |
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."
|
|
| |
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."
|
|
| |
Sagi Snir and
Tamir Tuller. Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In WABI08, Vol. 5251:354-368 of LNCS, springer, 2008.
Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model.
Note: http://dx.doi.org/10.1007/978-3-540-87361-7_30.
Toggle abstract
"Horizontal Gene Transfer (HGT) is the event of transferring genetic material from one lineage in the evolutionary tree to a different lineage. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Although the prevailing assumption is of complete HGT, cases of partial HGT (which are also named chimeric HGT) where only part of a gene is horizontally transferred, have also been reported, albeit less frequently. In this work we suggest a new probabilistic model for analyzing and modeling phylogenetic networks, the NET-HMM. This new model captures the biologically realistic assumption that neighboring sites of DNA or amino acid sequences are not independent, which increases the accuracy of the inference. The model describes the phylogenetic network as a Hidden Markov Model (HMM), where each hidden state is related to one of the network's trees. One of the advantages of the NET-HMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NET-HMM, devise efficient algorithms for solving a set of problems related to it, and implement them in software. We also provide a novel complementary significance test for evaluating the fitness of a model (NET-HMM) to a given data set. Using NET-HMM we are able to answer interesting biological questions, such as inferring the length of partial HGT's and the affected nucleotides in the genomic sequences, as well as inferring the exact location of HGT events along the tree branches. These advantages are demonstrated through the analysis of synthetical inputs and two different biological inputs. © 2008 Springer-Verlag Berlin Heidelberg."
|
|
| |
Katharina Huber,
Bengt Oxelman,
Martin Lott and
Vincent Moulton. Reconstructing the Evolutionary History of Polyploids from Multilabeled Trees. In MBE, Vol. 23(9):1784-1791, 2007.
Keywords: duplication, explicit network, from multilabeled tree, from trees, phylogenetic network, phylogeny, Program PADRE, reconstruction, software.
Note: http://mbe.oxfordjournals.org/cgi/content/full/23/9/1784.
Toggle abstract
"In recent studies, phylogenetic networks have been derived from so-called multilabeled trees in order to understand the origins of certain polyploids. Although the trees used in these studies were constructed using sophisticated techniques in phylogenetic analysis, the presented networks were inferred using ad hoc arguments that cannot be easily extended to larger, more complicated examples. In this paper, we present a general method for constructing such networks, which takes as input a multilabeled phylogenetic tree and outputs a phylogenetic network with certain desirable properties. To illustrate the applicability of our method, we discuss its use in reconstructing the evolutionary history of plant allopolyploids. We conclude with a discussion concerning possible future directions. The network construction method has been implemented and is freely available for use from http://www.uea.ac.uk/ ∼a043878/padre.html. © The Author 2006. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved."
|
|
| |
Daniel H. Huson. Split networks and Reticulate Networks. In
Olivier Gascuel and
Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 247-276, Oxford University Press, 2007.
Keywords: abstract network, consensus, from rooted trees, from sequences, from splits, from unrooted trees, galled tree, hybridization, phylogenetic network, phylogeny, Program Beagle, Program Spectronet, Program SplitsTree, Program SPNet, recombination, reconstruction, split network, survey.
Note: similar to http://www-ab.informatik.uni-tuebingen.de/research/phylonets/GCB2006.pdf.
|
|
| |
|
| |
Guohua Jin,
Luay Nakhleh,
Sagi Snir and
Tamir Tuller. A New Linear-time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance. In ISBRA07, Vol. 4463:61-72 of LNCS, springer, 2007.
Keywords: approximation, heuristic, parsimony, phylogenetic network, phylogeny, Program Nepal.
Note: http://www.cs.rice.edu/~nakhleh/Papers/isbra07.pdf.
|
|
| |
|
| |
    
Joanna L. Davies,
Frantisek Simancík,
Rune Lyngsø,
Thomas Mailund and
Jotun Hein. On Recombination-Induced Multiple and Simultaneous Coalescent Events. In GEN, Vol. 177:2151-2160, 2007.
Keywords: coalescent, phylogenetic network, phylogeny, recombination, statistical model.
Note: http://dx.doi.org/10.1534/genetics.107.071126.
Toggle abstract
"Coalescent theory deals with the dynamics of how sampled genetic material has spread through a population from a single ancestor over many generations and is ubiquitous in contemporary molecular population genetics. Inherent in most applications is a continuous-time approximation that is derived under the assumption that sample size is small relative to the actual population size. In effect, this precludes multiple and simultaneous coalescent events that take place in the history of large samples. If sequences do not recombine, the number of sequences ancestral to a large sample is reduced sufficiently after relatively few generations such that use of the continuous-time approximation is justified. However, in tracing the history of large chromosomal segments, a large recombination rate per generation will consistently maintain a large number of ancestors. This can create a major disparity between discrete-time and continuous-time models and we analyze its importance, illustrated with model parameters typical of the human genome. The presence of gene conversion exacerbates the disparity and could seriously undermine applications of coalescent theory to complete genomes. However, we show that multiple and simultaneous coalescent events influence global quantities, such as total number of ancestors, but have negligible effect on local quantities, such as linkage disequilibrium. Reassuringly, most applications of the coalescent model with recombination (including association mapping) focus on local quantities. Copyright © 2007 by the Genetics Society of America."
|
|
| |
 
Mihaela Baroni,
Charles Semple and
Mike Steel. Hybrids in Real Time. In Systematic Biology, Vol. 55(1):46-56, 2006.
Keywords: agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network.
Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf.
Toggle abstract
"We describe some new and recent results that allow for the analysis and representation of reticulate evolution by nontree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. Copyright © Society of Systematic Biologists."
|
|
| |
  
Ho-Leung Chan,
Jesper Jansson,
Tak-Wah Lam and
Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807-832, 2006.
Keywords: explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf.
Toggle abstract
"Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press."
|
|
| |
|
| |
Vincent Moulton and
Katharina Huber. Phylogenetic networks from multi-labelled trees. In JOMB, Vol. 52(5):613-632, 2006.
Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction.
Note: http://www.uea.ac.uk/~a043878/jmb.pdf.
Toggle abstract
"It is now quite well accepted that the evolutionary past of certain species is better represented by phylogenetic networks as opposed to trees. For example, polyploids are typically thought to have resulted through hybridization and duplication, processes that are probably not best represented as bifurcating speciation events. Based on the knowledge of a multi-labelled tree relating collection of polyploids, we present a canonical construction of a phylogenetic network that exhibits the tree. In addition, we prove that the resulting network is in some well-defined sense a minimal network having this property. © Springer-Verlag 2006."
|
|
| |
Guohua Jin,
Luay Nakhleh,
Sagi Snir and
Tamir Tuller. Maximum Likelihood of Phylogenetic Networks. In BIO, Vol. 22(21):2604-2611, 2006.
Keywords: explicit network, likelihood, phylogenetic network, phylogeny, Program Nepal, reconstruction.
Note: http://www.cs.rice.edu/~nakhleh/Papers/NetworksML06.pdf, supplementary material: http://www.cs.rice.edu/~nakhleh/Papers/Supp-ML.pdf.
|
|
| |
|
| |
|
| |
   
Richard C. Winkworth,
David Bryant,
Peter J. Lockhart,
David Havell and
Vincent Moulton. Biogeographic Interpretation of Splits Graphs: Least Squares Optimization of Branch Lengths. In Systematic Biology, Vol. 54(1):56-65, 2005.
Keywords: abstract network, from distances, from network, phylogenetic network, phylogeny, reconstruction, split, split network.
Note: http://www.math.auckland.ac.nz/~bryant/Papers/05Biogeographic.pdf.
|
|
| |
|
| |
|
| |
 
Tao Sang and
Yang Zhong. Testing Hybridization Hypotheses Based on Incongruent Gene Trees. In Systematic Biology, Vol. 49(3):422-434, 2000.
Keywords: bootstrap, from rooted trees, hybridization, lateral gene transfer, lineage sorting, phylogenetic network, phylogeny, reconstruction, statistical model.
Note: http://dx.doi.org/10.1080/10635159950127321.
|
|
| |
|
| |
Hans-Jürgen Bandelt and
Andreas W. M. Dress. A relational approach to split decomposition. In
H.-H. Bock,
W. Lenski and
M. M. Richter editors, Information Systems and Data Analysis, Proceedings of the 17th Annual Conference of the Gesellschaft Für Klassifikation (GFKL93), Vol. 42:123-131 of Studies in Classification, Data Analysis, and Knowledge Organization, springer, 1994.
Keywords: characterization, from quartets, phylogenetic network, weakly compatible.
|
|
|
- forked on GitHub.