Who is Who in Phylogenetic Networks

Publications related to 'loss'   Order by:   Type | Year

Only And Or     related to:

Associated keywords

bayesian branch-length duplication dynamic-programming explicit-network FPT from-multilabeled-tree from-network from-rooted-trees from-sequences from-species-tree from-unrooted-trees integer-linear-programming lateral-gene-transfer LGT-network likelihood loss NP-complete parsimony phylogenetic-network phylogeny polynomial Program-ALE Program-Angst Program-ecceTERA Program-ILPEACE Program-JPrIME-DLTRS Program-Mowgli Program-Notung Program-RANGER-DTL Program-SylvX Program-TERA Program-TreeFix-DTL Program-Xscape reconstruction software uniqueness visualization

Article (Journal)

1 Ali Tofigh, Mike Hallett and Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517-535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.         Toggle abstract "The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios. © 2011 IEEE." 2 Pawel Górecki. H-trees: a model of evolutionary scenario with horizontal gene transfer. In Fundamenta Informaticae, Vol. 103:105-128, 2010. Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, uniqueness.         3 Mukul S. Bansal, Eric J. Alm and Manolis Kellis. Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss. In JCB, Vol. 20(10):738-754, 2013. Keywords: duplication, from rooted trees, from species tree, loss, phylogenetic network, phylogeny, Program RANGER-DTL, reconstruction. Note: http://www.engr.uconn.edu/~mukul/Bansal_JCB2013.pdf.         Toggle abstract "Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication-loss (DL) reconciliation leads to a unique maximum-parsimony solution, duplication-transfer-loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn 2) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution. © 2013 Mary Ann Liebert, Inc." 4 Gergely J. Szöllösi, Eric Tannier, Nicolas Lartillot and Vincent Daubin. Lateral Gene Transfer from the Dead. In Systematic Biology, Vol. 62(3):386-397, 2013. Keywords: duplication, lateral gene transfer, likelihood, loss, phylogeny, Program TERA, reconstruction. Note: http://dx.doi.org/10.1093/sysbio/syt003.         Toggle abstract "In phylogenetic studies, the evolution of molecular sequences is assumed to have taken place along the phylogeny traced by the ancestors of extant species. In the presence of lateral gene transfer, however, this may not be the case, because the species lineage from which a gene was transferred may have gone extinct or not have been sampled. Because it is not feasible to specify or reconstruct the complete phylogeny of all species, we must describe the evolution of genes outside the represented phylogeny by modeling the speciation dynamics that gave rise to the complete phylogeny. We demonstrate that if the number of sampled species is small compared with the total number of existing species, the overwhelming majority of gene transfers involve speciation to and evolution along extinct or unsampled lineages. We show that the evolution of genes along extinct or unsampled lineages can to good approximation be treated as those of independently evolving lineages described by a few global parameters. Using this result, we derive an algorithm to calculate the probability of a gene tree and recover the maximum-likelihood reconciliation given the phylogeny of the sampled species. Examining 473 near-universal gene families from 36 cyanobacteria, we find that nearly a third of transfer events (28%) appear to have topological signatures of evolution along extinct species, but only approximately 6% of transfers trace their ancestry to before the common ancestor of the sampled cyanobacteria. © 2013 The Author(s)." 5 Gergely J. Szöllösi, Wojciech Rosikiewicz, Bastien Boussau, Eric Tannier and Vincent Daubin. Efficient Exploration of the Space of Reconciled Gene Trees. In Systematic Biology, Vol. 62(6):901-912, 2013. Keywords: duplication, explicit network, lateral gene transfer, likelihood, loss, phylogeny, Program ALE, reconstruction. Note: http://arxiv.org/abs/1306.2167.         Toggle abstract "Gene trees record the combination of gene-level events, such as duplication, transfer and loss (DTL), and species-level events, such as speciation and extinction. Gene tree-species tree reconciliation methods model these processes by drawing gene trees into the species tree using a series of gene and species-level events. The reconstruction of gene trees based on sequence alone almost always involves choosing between statistically equivalent or weakly distinguishable relationships that could be much better resolved based on a putative species tree. To exploit this potential for accurate reconstruction of gene trees, the space of reconciled gene trees must be explored according to a joint model of sequence evolution and gene tree-species tree reconciliation. Here we present amalgamated likelihood estimation (ALE), a probabilistic approach to exhaustively explore all reconciled gene trees that can be amalgamated as a combination of clades observed in a sample of gene trees. We implement the ALE approach in the context of a reconciliation model (Szöllo{double acute}si et al. 2013), which allows for the DTL of genes. We use ALE to efficiently approximate the sum of the joint likelihood over amalgamations and to find the reconciled gene tree that maximizes the joint likelihood among all such trees. We demonstrate using simulations that gene trees reconstructed using the joint likelihood are substantially more accurate than those reconstructed using sequence alone. Using realistic gene tree topologies, branch lengths, and alignment sizes, we demonstrate that ALE produces more accurate gene trees even if the model of sequence evolution is greatly simplified. Finally, examining 1099 gene families from 36 cyanobacterial genomes we find that joint likelihood-based inference results in a striking reduction in apparent phylogenetic discord, with respectively. 24%, 59%, and 46% reductions in the mean numbers of duplications, transfers, and losses per gene family. The open source implementation of ALE is available from https://github.com/ssolo/ALE.git. © The Author(s) 2013." 6 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." 7 Joel Sjöstrand, Ali Tofigh, Vincent Daubin, Lars Arvestad, Bengt Sennblad and Jens Lagergren. A Bayesian Method for Analyzing Lateral Gene Transfer. In Systematic Biology, Vol. 63(3):409-420, 2014. Keywords: bayesian, duplication, from rooted trees, from sequences, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program JPrIME-DLTRS, reconstruction. Note: http://dx.doi.org/10.1093/sysbio/syu007.         8 Vincent Ranwez, Celine Scornavacca, Jean-Philippe Doyon and Vincent Berry. Inferring gene duplications, transfers and losses can be done in a discrete framework. In JOMB, Vol. 72(7):1811-1844, 2016. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction.         9 Gergely J. Szöllösi, Adrián Arellano Davín, Eric Tannier, Vincent Daubin and Bastien Boussau. Genome-scale phylogenetic analysis finds extensive gene transfer among fungi. In Philosophical Transactions of the Royal Society of London B: Biological Sciences, Vol. 370(1678):1-11, 2015. Keywords: duplication, from sequences, lateral gene transfer, loss, phylogenetic network, phylogeny, Program ALE, reconstruction. Note: http://dx.doi.org/10.1098/rstb.2014.0335.         10 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.         11 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.         12 Celine Scornavacca, Joan Carles Pons and Gabriel Cardona. Fast algorithm for the reconciliation of gene trees and LGT networks. In JTB, Vol. 418:129-137, 2017. Keywords: duplication, explicit network, from network, from rooted trees, lateral gene transfer, LGT network, loss, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.         13 Edwin Jacox, Cédric Chauve, Gergely J. Szöllösi, Yann Ponty and Celine Scornavacca. EcceTERA: comprehensive gene tree-species tree reconciliation using parsimony. In BIO, Vol. 32(13):2056-2058, 2016. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, parsimony, phylogenetic network, phylogeny, polynomial, Program ecceTERA. Note: https://doi.org/10.1093/bioinformatics/btw105.         14 Edwin Jacox, Mathias Weller, Eric Tannier and Celine Scornavacca. Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses. In BIO, Vol. 33(7):980-987, 2017. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btw778.

InProceedings

15 Mike Hallett, Jens Lagergren and Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347-356, 2004. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.nada.kth.se/~jensl/p164-hallett.pdf.         16 Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316-325, 2004. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.pdf.         17 Jean-Philippe Doyon, Celine Scornavacca, Konstantin Yu Gorbunov, Gergely J. Szöllösi, Vincent Ranwez and Vincent Berry. An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications, and transfers. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'10), Vol. 6398:93-108 of LNCS, springer, 2011. Keywords: branch length, duplication, dynamic programming, explicit network, from multilabeled tree, from species tree, from unrooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Mowgli, reconstruction. Note: http://www.lirmm.fr/~vberry/Publis/MPR-DoyonEtAl.pdf, software available at http://www.atgc-montpellier.fr/MPR/.         Toggle abstract "Tree reconciliation methods aim at estimating the evolutionary events that cause discrepancy between gene trees and species trees. We provide a discrete computational model that considers duplications, transfers and losses of genes. The model yields a fast and exact algorithm to infer time consistent and most parsimonious reconciliations. Then we study the conditions under which parsimony is able to accurately infer such events. Overall, it performs well even under realistic rates, transfers being in general less accurately recovered than duplications. An implementation is freely available at http://www.atgc- montpellier.fr/MPR. © 2010 Springer-Verlag." 18 Pawel Górecki and Jerzy Tiuryn. Inferring evolutionary scenarios in the duplication, loss and horizontal gene transfer model. In Logic and Program Semantics, Vol. 7230:83-105 of LNCS, springer, 2012. Keywords: duplication, explicit network, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/978-3-642-29485-3_7.         Toggle abstract "An H-tree is a formal model of evolutionary scenario. It can be used to represent any processes with gene duplication and loss, horizontal gene transfer (HGT) and speciation events. The model of H-trees, introduced in [26], is an extension of the duplication-loss model (DL-model). Similarly to its ancestor, it has a number of interesting mathematical and biological properties. It is, however, more computationally complex than the DL-model. In this paper, we primarily address the problem of inferring H-trees that are compatible with a given gene tree and a given phylogeny of species with HGTs. These results create a mathematical and computational foundation for a more general and practical problem of inferring HGTs from given gene and species trees with HGTs. We also demonstrate how our model can be used to support HGT hypotheses based on empirical data sets. © 2012 Springer-Verlag Berlin Heidelberg." 19 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." 20 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." 21 Mukul S. Bansal, Eric J. Alm and Manolis Kellis. Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss. In RECOMB13, Vol. 7821:1-13 of LNCS, springer, 2013. Keywords: duplication, from rooted trees, from species tree, loss, phylogenetic network, phylogeny, polynomial, Program RANGER-DTL, reconstruction. Note: http://people.csail.mit.edu/mukul/Bansal_RECOMB2013.pdf.         Toggle abstract "Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While Duplication-Loss (DL) reconciliation leads to a unique maximum-parsimony solution, Duplication-Transfer-Loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult the infer the true evolutionary history of the gene family. Here, we present an effective, efficient, and scalable method for dealing with this fundamental problem in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn 2) time, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mapping and event assignments, and to investigate the impact of varying event costs. © 2013 Springer-Verlag." 22 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." 23 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.         24 Han Lai, Maureen Stolzer and Dannie Durand. Fast Heuristics for Resolving Weakly Supported Branches Using Duplication, Transfers, and Losses. In RECOMB-CG17, Vol. 10562:298-320 of LNCS, Springer, 2017. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction.

PhdThesis

25 Ali Tofigh. Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression. PhD thesis, KTH Royal Institute of Technology, Sweden, 2009. Keywords: duplication, dynamic programming, from multilabeled tree, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://kth.diva-portal.org/smash/record.jsf?pid=diva2:220830&searchId=1.         26 Yi-Chieh Wu. Computational evolutionary genomics : phylogenomic models spanning domains, genes, individuals, and species. PhD thesis, Massachusetts Institute of Technology, U.S.A., 2014. Keywords: duplication, from sequences, from species tree, lateral gene transfer, loss, phylogeny, Program TreeFix-DTL, reconstruction. Note: http://hdl.handle.net/1721.1/87937.

Misc

27 Ali Tofigh, Joel Sjöstrand, Bengt Sennblad, Lars Arvestad and Jens Lagergren. Detecting LGTs using a novel probabilistic model integrating duplications, LGTs, losses, rate variation, and sequence evolution. 2009. Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://kth.diva-portal.org/smash/record.jsf?searchId=1&pid=diva2:233574.         28 Leo van Iersel, Celine Scornavacca and Steven Kelk. Exact reconciliation of undated trees. 2014. Keywords: duplication, explicit network, integer linear programming, loss, phylogenetic network, phylogeny, Program ILPEACE, reconstruction. Note: https://arxiv.org/abs/1410.7004.