| |
    
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.
|
|
| |
|
| |
 
Marc Thuillard and
Didier Fraix-Burnet. Phylogenetic Trees and Networks Reduce to Phylogenies on Binary States: Does It Furnish an Explanation to the Robustness of Phylogenetic Trees against Lateral Transfers? In Evolutionary Bioinformatics, Vol. 11:213-221, 2015. [Abstract]
Keywords: circular split system, explicit network, from multistate characters, outerplanar, perfect, phylogenetic network, phylogeny, planar, polynomial, reconstruction, split.
Note: http://dx.doi.org/10.4137%2FEBO.S28158.
|
|
| |
   
Ran Libeskind-Hadas,
Yi-Chieh Wu,
Mukul S. Bansal and
Manolis Kellis. Pareto-optimal phylogenetic tree reconciliation. In ISMB14, Vol. 30:i87-i95 of BIO, 2014.
Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Xscape, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/btu289.
Toggle abstract
"Motivation: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem. Results: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies. © 2014 The Author. Published by Oxford University Press. All rights reserved."
|
|
| |
   
Mukul S. Bansal,
Guy Banay,
Timothy J. Harlow,
J. Peter Gogarten and
Ron Shamir. Systematic inference of highways of horizontal gene transfer in prokaryotes. In BIO, Vol. 29(5):571-579, 2013.
Keywords: duplication, explicit network, from species tree, from unrooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program HiDe, Program RANGER-DTL, reconstruction.
Note: http://people.csail.mit.edu/mukul/Bansal_Highways_Bioinformatics_2013.pdf.
|
|
| |
    
Juan Wang,
Maozu Guo,
Xiaoyan Liu,
Yang Liu,
Chunyu Wang,
Linlin Xing and
Kai Che. LNETWORK: An Efficient and Effective Method for Constructing Phylogenetic Networks. In BIO, Vol. 29(18):2269-2276, 2013.
Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, Program LNetwork, reconstruction, software.
Toggle abstract
"Motivation: The evolutionary history of species is traditionally represented with a rooted phylogenetic tree. Each tree comprises a set of clusters, i.e. subsets of the species that are descended from a common ancestor. When rooted phylogenetic trees are built from several different datasets (e.g. from different genes), the clusters are often conflicting. These conflicting clusters cannot be expressed as a simple phylogenetic tree; however, they can be expressed in a phylogenetic network. Phylogenetic networks are a generalization of phylogenetic trees that can account for processes such as hybridization, horizontal gene transfer and recombination, which are difficult to represent in standard tree-like models of evolutionary histories. There is currently a large body of research aimed at developing appropriate methods for constructing phylogenetic networks from cluster sets. The Cass algorithm can construct a much simpler network than other available methods, but is extremely slow for large datasets or for datasets that need lots of reticulate nodes. The networks constructed by Cass are also greatly dependent on the order of input data, i.e. it generally derives different phylogenetic networks for the same dataset when different input orders are used.Results: In this study, we introduce an improved Cass algorithm, Lnetwork, which can construct a phylogenetic network for a given set of clusters. We show that Lnetwork is significantly faster than Cass and effectively weakens the influence of input data order. Moreover, we show that Lnetwork can construct a much simpler network than most of the other available methods. © The Author 2013."
|
|
| |
|
| |
  
Benjamin Albrecht,
Celine Scornavacca,
Alberto Cenci and
Daniel H. Huson. Fast computation of minimum hybridization networks. In BIO, Vol. 28(2):191-197, 2012.
Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/btr618.
Toggle abstract
"Motivation: Hybridization events in evolution may lead to incongruent gene trees. One approach to determining possible interspecific hybridization events is to compute a hybridization network that attempts to reconcile incongruent gene trees using a minimum number of hybridization events. Results: We describe how to compute a representative set of minimum hybridization networks for two given bifurcating input trees, using a parallel algorithm and provide a user-friendly implementation. A simulation study suggests that our program performs significantly better than existing software on biologically relevant data. Finally, we demonstrate the application of such methods in the context of the evolution of the Aegilops/Triticum genera. Availability and implementation: The algorithm is implemented in the program Dendroscope 3, which is freely available from www.dendroscope.org and runs on all three major operating systems. © The Author 2011. Published by Oxford University Press. All rights reserved."
|
|
| |
Mukul S. Bansal,
Eric J. Alm and
Manolis Kellis. Efficient Algorithms for the Reconciliation Problem with Gene Duplication, Horizontal Transfer, and Loss. In ISMB12, Vol. 28(12):i283-i291 of BIO, 2012.
Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Angst, Program Mowgli, Program RANGER-DTL, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/bts225.
Toggle abstract
"Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods. © The Author(s) 2012. Published by Oxford University 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."
|
|
| |
    
Maureen Stolzer,
Han Lai,
Minli Xu,
Deepa Sathaye,
Benjamin Vernot and
Dannie Durand. Inferring Duplications, Losses, Transfers, and Incomplete Lineage Sorting with Non-Binary Species Trees. In ECCB12, Vol. 28(18):i409-i415 of BIO, 2012.
Keywords: duplication, explicit network, from rooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/bts386.
Toggle abstract
"Motivation: Gene duplication (D), transfer (T), loss (L) and incomplete lineage sorting (I) are crucial to the evolution of gene families and the emergence of novel functions.The history of these events can be inferred via comparison of gene and species trees, a process called reconciliation, yet current reconciliation algorithms model only a subset of these evolutionary processes. Results: We present an algorithm to reconcile a binary gene tree with a nonbinary species tree under a DTLI parsimony criterion. This is the first reconciliation algorithm to capture all four evolutionary processes driving tree incongruence and the first to reconcile nonbinary species trees with a transfer model. Our algorithm infers all optimal solutions and reports complete, temporally feasible event histories, giving the gene and species lineages in which each event occurred. It is fixed-parameter tractable, with polytime complexity when the maximum species outdegree is fixed. Application of our algorithms to prokaryotic and eukaryotic data show that use of an incomplete event model has substantial impact on the events inferred and resulting biological conclusions. © The Author(s) 2012. Published by Oxford University Press."
|
|
| |
Klaus Schliep. Phangorn: Phylogenetic analysis in R. In Bioinformatics, Vol. 27(4):592-593, 2011.
Keywords: abstract network, from distances, phylogenetic network, Program Phangorn, software, split, split network.
Note: http://dx.doi.org/10.1093/bioinformatics/btq706.
Toggle abstract
"Summary: phangorn is a package for phylogenetic reconstruction and analysis in the R language. Previously it was only possible to estimate phylogenetic trees with distance methods in R. phangorn, now offers the possibility of reconstructing phylogenies with distance based methods, maximum parsimony or maximum likelihood (ML) and performing Hadamard conjugation. Extending the general ML framework, this package provides the possibility of estimating mixture and partition models. Furthermore, phangorn offers several functions for comparing trees, phylogenetic models or splits, simulating character data and performing congruence analyses. © The Author(s) 2010. Published by Oxford University Press."
|
|
| |
Celine Scornavacca,
Franziska Zickmann and
Daniel H. Huson. Tanglegrams for Rooted Phylogenetic Trees and Networks. In ISMB11, Vol. 27(13):i248-i256 of BIO, 2011.
Keywords: from network, heuristic, phylogenetic network, phylogeny, Program Dendroscope, tanglegram, visualization.
Note: http://dx.doi.org/10.1093/bioinformatics/btr210.
Toggle abstract
"Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks. Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets. © The Author(s) 2011. Published by Oxford University Press."
|
|
| |
 
Jean-Philippe Doyon,
Vincent Ranwez,
Vincent Daubin and
Vincent Berry. Models, algorithms and programs for phylogeny reconciliation. In Briefings in Bioinformatics, Vol. 12(5):392-400, 2011.
Keywords: explicit network, lateral gene transfer, phylogenetic network, phylogeny, reconstruction, survey.
Toggle abstract
"Gene sequences contain a goldmine of phylogenetic information. But unfortunately for taxonomists this information does not only tell the story of the species from which it was collected. Genes have their own complex histories which record speciation events, of course, but also many other events. Among them, gene duplications, transfers and losses are especially important to identify. These events are crucial to account for when reconstructing the history of species, and they play a fundamental role in the evolution of genomes, the diversification of organisms and the emergence of new cellular functions.We review reconciliations between gene and species trees, which are rigorous approaches for identifying duplications, transfers and losses that mark the evolution of a gene family. Existing reconciliation models and algorithms are reviewed and difficulties in modeling gene transfers are discussed. We also compare different reconciliation programs along with their advantages and disadvantages. © The Author 2011. Published by Oxford University Press."
|
|
| |
 
Zhi-Zhong Chen and
Lusheng Wang. HybridNET: a tool for constructing hybridization networks. In BIO, Vol. 26(22):2912-2913, 2010.
Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNET, software.
Note: http://rnc.r.dendai.ac.jp/~chen/papers/note2.pdf.
Toggle abstract
"Motivations: When reticulation events occur, the evolutionary history of a set of existing species can be represented by a hybridization network instead of an evolutionary tree. When studying the evolutionary history of a set of existing species, one can obtain a phylogenetic tree of the set of species with high confidence by looking at a segment of sequences or a set of genes. When looking at another segment of sequences, a different phylogenetic tree can be obtained with high confidence too. This indicates that reticulation events may occur. Thus, we have the following problem: given two rooted phylogenetic trees on a set of species that correctly represent the tree-like evolution of different parts of their genomes, what is the hybridization network with the smallest number of reticulation events to explain the evolution of the set of species under consideration? Results: We develop a program, named HybridNet, for constructing a hybridization network with the minimum number of reticulate vertices from two input trees. We first implement the O(3dn)-time algorithm by Whidden et al. for computing a maximum (acyclic) agreement forest. Our program can output all the maximum (acyclic) agreement forests. We then augment the program so that it can construct an optimal hybridization network for each given maximum acyclic agreement forest. To our knowledge, this is the first time that optimal hybridization networks can be rapidly constructed. © The Author 2010. Published by Oxford University Press. All rights reserved."
|
|
| |
|
| |
  
Leo van Iersel,
Steven Kelk,
Regula Rupp and
Daniel H. Huson. Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters. In ISMB10, Vol. 26(12):i124-i131 of BIO, 2010.
Keywords: from clusters, level k phylogenetic network, Program Dendroscope, Program HybridInterleave, Program HybridNumber, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/btq202, with proofs: http://arxiv.org/abs/0910.3082.
Toggle abstract
"Phylogenetic trees are widely used to display estimates of how groups of species are evolved. Each phylogenetic tree can be seen as a collection of clusters, subgroups of the species that evolved from a common ancestor. When phylogenetic trees are obtained for several datasets (e.g. for different genes), then their clusters are often contradicting. Consequently, the set of all clusters of such a dataset cannot be combined into a single phylogenetic tree. Phylogenetic networks are a generalization of phylogenetic trees that can be used to display more complex evolutionary histories, including reticulate events, such as hybridizations, recombinations and horizontal gene transfers. Here, we present the new CASS algorithm that can combine any set of clusters into a phylogenetic network. We show that the networks constructed by CASS are usually simpler than networks constructed by other available methods. Moreover, we show that CASS is guaranteed to produce a network with at most two reticulations per biconnected component, whenever such a network exists. We have implemented CASS and integrated it into the freely available Dendroscope software. Contact: l.j.j.v.iersel@gmail.com. Supplementary information: Supplementary data are available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press."
|
|
| |
Yufeng Wu. Close Lower and Upper Bounds for the Minimum Reticulate Network of Multiple Phylogenetic Trees. In ISMB10, Vol. 26(12):i140-i148 of BIO, 2010.
Keywords: explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program PIRN, software.
Note: http://dx.doi.org/10.1093/bioinformatics/btq198.
Toggle abstract
"Motivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions. Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets. Availability: A software tool, PIRN, is available for download from the web page: http://www.engr.uconn.edu/ywu. Contact: ywu@engr.uconn.edu. Supplementary information: Supplementary data is available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press."
|
|
| |
  
Sophie Abby,
Eric Tannier,
Manolo Gouy and
Vincent Daubin. Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests. In BMCB, Vol. 11:324, 2010.
Keywords: explicit network, from rooted trees, from species tree, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program EEEP, Program PhyloNet, Program Prunier, reconstruction, software.
Note: http://www.biomedcentral.com/1471-2105/11/324.
Toggle abstract
"Background: To understand the evolutionary role of Lateral Gene Transfer (LGT), accurate methods are needed to identify transferred genes and infer their timing of acquisition. Phylogenetic methods are particularly promising for this purpose, but the reconciliation of a gene tree with a reference (species) tree is computationally hard. In addition, the application of these methods to real data raises the problem of sorting out real and artifactual phylogenetic conflict.Results: We present Prunier, a new method for phylogenetic detection of LGT based on the search for a maximum statistical agreement forest (MSAF) between a gene tree and a reference tree. The program is flexible as it can use any definition of "agreement" among trees. We evaluate the performance of Prunier and two other programs (EEEP and RIATA-HGT) for their ability to detect transferred genes in realistic simulations where gene trees are reconstructed from sequences. Prunier proposes a single scenario that compares to the other methods in terms of sensitivity, but shows higher specificity. We show that LGT scenarios carry a strong signal about the position of the root of the species tree and could be used to identify the direction of evolutionary time on the species tree. We use Prunier on a biological dataset of 23 universal proteins and discuss their suitability for inferring the tree of life.Conclusions: The ability of Prunier to take into account branch support in the process of reconciliation allows a gain in complexity, in comparison to EEEP, and in accuracy in comparison to RIATA-HGT. Prunier's greedy algorithm proposes a single scenario of LGT for a gene family, but its quality always compares to the best solutions provided by the other algorithms. When the root position is uncertain in the species tree, Prunier is able to infer a scenario per root at a limited additional computational cost and can easily run on large datasets.Prunier is implemented in C++, using the Bio++ library and the phylogeny program Treefinder. It is available at: http://pbil.univ-lyon1.fr/software/prunier. © 2010 Abby et al; licensee BioMed Central Ltd."
|
|
| |
|
| |
 
Daniel H. Huson,
Regula Rupp,
Vincent Berry,
Philippe Gambette and
Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009.
Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction.
Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.
Toggle abstract
"Motivation: Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. Results: In this article, we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves successively solving instances of two different NP-complete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. © 2009 The Author(s)."
|
|
| |
   
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."
|
|
| |
|
| |
|
| |
   
Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks. In BIO, Vol. 24(13):1481-1488, 2008.
Keywords: distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network.
Note: http://dx.doi.org/10.1093/bioinformatics/btn231.
Toggle abstract
"Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this articlea distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)."
|
|
| |
  
Hadas Birin,
Zohar Gal-Or,
Isaac Elias and
Tamir Tuller. Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion. In BIO, Vol. 24(6):826-832, 2008.
Note: http://dx.doi.org/10.1093/bioinformatics/btn024.
Toggle abstract
"Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input. Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets. © The Author 2008. Published by Oxford University Press. All rights reserved."
|
|
| |
|
| |
Maria S. Poptsova and
J. Peter Gogarten. The power of phylogenetic approaches to detect horizontally transferred genes. In BMCEB, Vol. 7(45), 2007.
Keywords: evaluation, from rooted trees, lateral gene transfer, Program EEEP.
Note: http://dx.doi.org/10.1186/1471-2148-7-45.
Toggle abstract
"Background. Horizontal gene transfer plays an important role in evolution because it sometimes allows recipient lineages to adapt to new ecological niches. High genes transfer frequencies were inferred for prokaryotic and early eukaryotic evolution. Does horizontal gene transfer also impact phylogenetic reconstruction of the evolutionary history of genomes and organisms? The answer to this question depends at least in part on the actual gene transfer frequencies and on the ability to weed out transferred genes from further analyses. Are the detected transfers mainly false positives, or are they the tip of an iceberg of many transfer events most of which go undetected by current methods? Results. Phylogenetic detection methods appear to be the method of choice to infer gene transfers, especially for ancient transfers and those followed by orthologous replacement. Here we explore how well some of these methods perform using in silico transfers between the terminal branches of a gamma proteobacterial, genome based phylogeny. For the experiments performed here on average the AU test at a 5% significance level detects 90.3% of the transfers and 91% of the exchanges as significant. Using the Robinson-Foulds distance only 57.7% of the exchanges and 60% of the donations were identified as significant. Analyses using bipartition spectra appeared most successful in our test case. The power of detection was on average 97% using a 70% cut-off and 94.2% with 90% cut-off for identifying conflicting bipartitions, while the rate of false positives was below 4.2% and 2.1% for the two cut-offs, respectively. For all methods the detection rates improved when more intervening branches separated donor and recipient. Conclusion. Rates of detected transfers should not be mistaken for the actual transfer rates; most analyses of gene transfers remain anecdotal. The method and significance level to identify potential gene transfer events represent a trade-off between the frequency of erroneous identification (false positives) and the power to detect actual transfer events. © 2007 Poptsova and Gogarten; licensee BioMed Central Ltd."
|
|
| |
 
Patricia Buendia and
Giri Narasimhan. Sliding MinPD: Building evolutionary networks of serial samples via an automated recombination detection approach. In BIO, Vol. 23(22):2993-3000, 2007.
Keywords: from sequences, phylogenetic network, phylogeny, Program Sliding MinPD, recombination, recombination detection, serial evolutionary networks, software.
Note: http://dx.doi.org/10.1093/bioinformatics/btm413.
Toggle abstract
"Motivation: Traditional phylogenetic methods assume tree-like evolutionary models and are likely to perform poorly when provided with sequence data from fast-evolving, recombining viruses. Furthermore, these methods assume that all the sequence data are from contemporaneous taxa, which is not valid for serially-sampled data. A more general approach is proposed here, referred to as the Sliding MinPD method, that reconstructs evolutionary networks for serially-sampled sequences in the presence of recombination. Results: Sliding MinPD combines distance-based phylogenetic methods with automated recombination detection based on the best-known sliding window approaches to reconstruct serial evolutionary networks. Its performance was evaluated through comprehensive simulation studies and was also applied to a set of serially-sampled HIV sequences from a single patient. The resulting network organizations reveal unique patterns of viral evolution and may help explain the emergence of disease-associated mutants and drug-resistant strains with implications for patient prognosis and treatment strategies. © The Author 2007. Published by Oxford University Press. All rights reserved."
|
|
| |
  
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.
|
|
| |
 
Monique M. Morin and
Bernard M. E. Moret. NetGen: generating phylogenetic networks with diploid hybrids. In BIO, Vol. 22(15):1921-1923, 2006.
Keywords: generation, hybridization, Program NetGen, software.
Note: http://dx.doi.org/10.1093/bioinformatics/btl191.
Toggle abstract
"Summary: NetGen is an event-driven simulator that creates phylogenetic networks by extending the birth-death model to include diploid hybridizations. DNA sequences are evolved in conjunction with the topology, enabling hybridization decisions to be based on contemporary evolutionary distances. NetGen supports variable rate lineages, root sequence specification, outgroup generation and many other options. This note describes the NetGen application and proposes an extension of the Newick format to accommodate phylogenetic networks. © 2006 Oxford University Press."
|
|
| |
 
Robert G. Beiko and
Nicholas Hamilton. Phylogenetic identification of lateral genetic transfer events. In BMCEB, Vol. 6(15), 2006.
Keywords: evaluation, from rooted trees, from unrooted trees, lateral gene transfer, Program EEEP, Program HorizStory, Program LatTrans, reconstruction, software, SPR distance.
Note: http://dx.doi.org/10.1186/1471-2148-6-15.
Toggle abstract
"Background: Lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. Where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. An 'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft (SPR) operations, but finding the optimal such set of operations is NP-hard for comparisons between rooted trees, and may be so for unrooted trees as well. Results: Efficient Evaluation of Edit Paths (EEEP) is a new tree comparison algorithm that uses evolutionarily reasonable constraints to identify and eliminate many unproductive search avenues, reducing the time required to solve many edit path problems. The performance of EEEP compares favourably to that of other algorithms when applied to strictly bifurcating trees with specified numbers of SPR operations. We also used EEEP to recover edit paths from over 19 000 unrooted, incompletely resolved protein trees containing up to 144 taxa as part of a large phylogenomic study. While inferred protein trees were far more similar to a reference supertree than random trees were to each other, the phylogenetic distance spanned by random versus inferred transfer events was similar, suggesting that real transfer events occur most frequently between closely related organisms, but can span large phylogenetic distances as well. While most of the protein trees examined here were very similar to the reference supertree, requiring zero or one edit operations for reconciliation, some trees implied up to 40 transfer events within a single orthologous set of proteins. Conclusion: Since sequence trees typically have no implied root and may contain unresolved or multifurcating nodes, the strategy implemented in EEEP is the most appropriate for phylogenomic analyses. The high degree of consistency among inferred protein trees shows that vertical inheritance is the dominant pattern of evolution, at least for the set of organisms considered here. However, the edit paths inferred using EEEP suggest an important role for genetic transfer in the evolution of microbial genomes as well. © 2006Beiko and Hamilton; licensee BioMed Central Ltd."
|
|
| |
Patricia Buendia and
Giri Narasimhan. Serial NetEvolve: A flexible utility for generating serially-sampled sequences along a tree or recombinant network. In BIO, Vol. 18(22):2313-2314, 2006.
Keywords: generation, phylogenetic network, phylogeny, Program Serial NetEvolve, Program Treevolve, recombination, software.
Note: http://dx.doi.org/10.1093/bioinformatics/btl387.
Toggle abstract
"Summary: Serial NetEvolve is a flexible simulation program that generates DNA sequences evolved along a tree or recombinant network. It offers a user-friendly Windows graphical interface and a Windows or Linux simulator with a diverse selection of parameters to control the evolutionary model. Serial NetEvolve is a modification of the Treevolve program with the following additional features: simulation of serially-sampled data, the choice of either a clock-like or a variable rate model of sequence evolution, sampling from the internal nodes and the output of the randomly generated tree or network in our newly proposed NeTwick format. © 2006 Oxford University Press."
|
|
| |
|
| |
Daniel H. Huson and
Tobias Kloepper. Computing recombination networks from binary sequences. In ECCB05, Vol. 21(suppl. 2):ii159-ii165 of BIO, 2005.
Keywords: from sequences, phylogenetic network, phylogeny, recombination.
Note: http://dx.doi.org/10.1093/bioinformatics/bti1126.
Toggle abstract
"Motivation:Phylogenetic networks are becoming an important tool in molecular evolution, as the evolutionary role of reticulate events, such as hybridization, horizontal gene transfer and recombination, is becoming more evident, and as the available data is dramatically increasing in quantity and quality. Results: This paper addresses the problem of computing a most parsimonious recombination network for an alignment of binary sequences that are assumed to have arisen under the 'infinite sites' model of evolution with recombinations. Using the concept of a splits network as the underlying datastructure, this paper shows how a recent method designed for the computation of hybridization networks can be extended to also compute recombination networks. A robust implementation of the approach is provided and is illustrated using a number of real biological datasets. © The Author 2005. Published by Oxford University Press. All rights reserved."
|
|
| |
 
Yun S. Song,
Yufeng Wu and
Dan Gusfield. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution. In ISMB05, Vol. 21:i413-i422 of BIO, 2005.
Keywords: minimum number, Program HapBound, Program SHRUB, recombination.
Note: http://dx.doi.org/10.1093/bioinformatics/bti1033.
Toggle abstract
"Motivation: We are interested in studying the evolution of DNA single nucleotide polymorphism sequences which have undergone (meiotic) recombination. For a given set of sequences, computing the minimum number of recombinations needed to explain the sequences (with one mutation per site) is a standard question of interest, but it has been shown to be NP-hard, and previous algorithms that compute it exactly work either only on very small datasets or on problems with special structure. Results: In this paper, we present efficient, practical methods for computing both upper and lower bounds on the minimum number of needed recombinations, and for constructing evolutionary histories that explain the input sequences. We study in detail the efficiency and accuracy of these algorithms on both simulated and real data sets. The algorithms produce very close upper and lower bounds, which match exactly in a surprisingly wide range of data. Thus, with the use of new, very effective lower bounding methods and an efficient algorithm for computing upper bounds, this approach allows the efficient, exact computation of the minimum number of needed recombinations, with high frequency in a large range of data. When upper and lower bounds match, evolutionary histories found by our algorithm correspond to the most parsimonious histories. © The Author 2005. Published by Oxford University Press. All rights reserved."
|
|
| |
|
| |
|
| |
|
| |
|
|
