CaltechAUTHORS
  A Caltech Library Service

Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model

Haack, Jordan and Zupke, Eli and Ramirez, Andrew and Wu, Yi-Chieh and Libeskind-Hadas, Ran (2019) Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16 (1). pp. 14-22. ISSN 1545-5963. https://resolver.caltech.edu/CaltechAUTHORS:20180629-100131573

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180629-100131573

Abstract

Phylogenetic tree reconciliation is widely used in the fields of molecular evolution, cophylogenetics, parasitology, and biogeography to study the evolutionary histories of pairs of entities. In these contexts, reconciliation is often performed using maximum parsimony under the Duplication-Transfer-Loss (DTL) event model. In general, the number of maximum parsimony reconciliations (MPRs) can grow exponentially with the size of the trees. While a number of previous efforts have been made to count the number of MPRs, find representative MPRs, and compute the frequencies of events across the space of MPRs, little is known about the structure of MPR space. In particular, how different are MPRs in terms of the events that they comprise? One way to address this question is to compute the diameter of MPR space, defined to be the maximum number of DTL events that distinguish any two MPRs in the solution space. We show how to compute the diameter of MPR space in polynomial time and then apply this algorithm to a large biological dataset to study the variability of events.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/TCBB.2018.2849732DOIArticle
ORCID:
AuthorORCID
Ramirez, Andrew0000-0001-7878-8190
Libeskind-Hadas, Ran0000-0001-9120-1948
Additional Information:© 2018 IEEE. Manuscript received 16 Mar. 2018; revised 29 May 2018; accepted 16 June 2018. Date of publication 22 June 2018; date of current version 4 Feb. 2019. This work was funded by the US National Science Foundation under Grant Number IIS-1419739 to R.L.H. and by startup funds from the Dean of Faculty of Harvey Mudd College to Y.W. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the US National Science Foundation. The authors gratefully acknowledge the valuable comments and suggestions of the anonymous reviewers and of Melissa Grueter.
Funders:
Funding AgencyGrant Number
NSFIIS-1419739
Harvey Mudd CollegeUNSPECIFIED
Subject Keywords:Phylogenetics, tree reconciliation, Duplication-Transfer-Loss model
Issue or Number:1
Record Number:CaltechAUTHORS:20180629-100131573
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180629-100131573
Official Citation:J. Haack, E. Zupke, A. Ramirez, Y. Wu and R. Libeskind-Hadas, "Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model," in IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 16, no. 1, pp. 14-22, 1 Jan.-Feb. 2019. doi: 10.1109/TCBB.2018.2849732
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87467
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:29 Jun 2018 17:24
Last Modified:03 Oct 2019 19:56

Repository Staff Only: item control page