IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2018 · 12 citations · 11 references
Life SciencesBiologyEvolutionary BiologyBiogeographyMolecular EvolutionPhylogeneticsEvolutionary RelationshipsPhylogenetic AnalysisPhylogenetic Tree ReconstructionTree ReconciliationCophylogenetic ReconciliationDuplication Transfer Loss ModelsEvent-based ReconciliationMaximum ParsimonyPhylogenetic ReconciliationPolynomial Time ComplexityPolynomial-time AlgorithmsReconciliation Algorithms
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.
11
Rapid evolutionary innovation during an Archaean genetic expansion
Lawrence A. David, Eric J. Alm · Nature · 2010 · 429 citations · Full text
Jane: a new tool for the cophylogeny reconstruction problem
Chris Conow, Daniel C. Fielder, Yaniv Ovadia et al. · Algorithms for Molecular Biology · 2010 · 411 citations · Full text
The Cophylogeny Reconstruction Problem Is NP-Complete
Yaniv Ovadia, Daniel C. Fielder, Chris Conow et al. · Journal of Computational Biology · 2010 · 74 citations