skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Incorporating Hierarchical Characters into Phylogenetic Analysis
Abstract Popular optimality criteria for phylogenetic trees focus on sequences of characters that are applicable to all the taxa. As studies grow in breadth, it can be the case that some characters are applicable for a portion of the taxa and inapplicable for others. Past work has explored the limitations of treating inapplicable characters as missing data, noting that this strategy may favor trees where internal nodes are assigned impossible states, where the arrangement of taxa within subclades is unduly influenced by variation in distant parts of the tree, and/or where taxa that otherwise share most primary characters are grouped distantly. Approaches that avoid the first two problems have recently been proposed. Here, we propose an alternative approach which avoids all three problems. We focus on data matrices that use reductive coding of traits, that is, explicitly incorporate the innate hierarchy induced by inapplicability, and as such our approach extend to hierarchical characters, in general. In the spirit of maximum parsimony, the proposed criterion seeks the phylogenetic tree with the minimal changes across any tree branch, but where changes are defined in terms of dissimilarity metrics that weigh the effects of inapplicable characters. The approach can accommodate binary, multistate, ordered, unordered, and polymorphic characters. We give a polynomial-time algorithm, inspired by Fitch’s algorithm, to score trees under a family of dissimilarity metrics, and prove its correctness. We show that the resulting optimality criteria is computationally hard, by reduction to the NP-hardness of the maximum parsimony optimality criteria. We demonstrate our approach using synthetic and empirical data sets and compare the results with other recently proposed methods for choosing optimal phylogenetic trees when the data includes hierarchical characters. [Character optimization, dissimilarity metrics, hierarchical characters, inapplicable data, phylogenetic tree search.]  more » « less
Award ID(s):
1848145
PAR ID:
10227475
Author(s) / Creator(s):
;
Editor(s):
Wright, April
Date Published:
Journal Name:
Systematic Biology
ISSN:
1063-5157
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Systematic biology)
    Liliana Davalos (Ed.)
    Logical character dependency is a major conceptual and methodological problem in phylogenetic inference of morphological data sets, as it violates the assumption of character independence that is common to all phylogenetic methods. It is more frequently observed in higher-level phylogenies or in data sets characterizing major evolutionary transitions, as these represent parts of the tree of life where (primary) anatomical characters either originate or disappear entirely. As a result, secondary traits related to these primary characters become “inapplicable” across all sampled taxa in which that character is absent. Various solutions have been explored over the last three decades to handle character dependency, such as alternative character coding schemes and, more recently, new algorithmic implementations. However, the accuracy of the proposed solutions, or the impact of character dependency across distinct optimality criteria, has never been directly tested using standard performance measures. Here, we utilize simple and complex simulated morphological data sets analyzed under different maximum parsimony optimization procedures and Bayesian inference to test the accuracy of various coding and algorithmic solutions to character dependency. This is complemented by empirical analyses using a recoded data set on palaeognathid birds. We find that in small, simulated data sets, absent coding performs better than other popular coding strategies available (contingent and multistate), whereas in more complex simulations (larger data sets controlled for different tree structure and character distribution models) contingent coding is favored more frequently. Under contingent coding, a recently proposed weighting algorithm produces the most accurate results for maximum parsimony. However, Bayesian inference outperforms all parsimony-based solutions to handle character dependency due to fundamental differences in their optimization procedures—a simple alternative that has been long overlooked. Yet, we show that the more primary characters bearing secondary (dependent) traits there are in a data set, the harder it is to estimate the true phylogenetic tree, regardless of the optimality criterion, owing to a considerable expansion of the tree parameter space. 
    more » « less
  2. ; ; ; ; (, Journal of Vertebrate Paleontology, Abstracts and Program)
    It is now well established that the end-Cretaceous mass extinction had enormous repercussions for mammalian evolution. Following the extinction, during the Paleocene, mammals started to radiate, occupying new and diverse ecological niches. However, the phylogenetic relationships between the socalled “archaic” mammals of this time, and their position within Placentalia, remain contentious. The Periptychidae are a clade of distinctive “archaic” ungulates, composed of ~17 genera of small to large bodied, highly bunodont, terrestrial herbivores that were among the first placental mammals to appear after the end-Cretaceous mass extinction. Although the Periptychidae has been historically considered a distinctive “condylarth” subgroup, their higherlevel relationships have been rarely tested. Here, we present an inclusive cladistic analysis to determine and test the phylogenetic affinities of Periptychidae and other key Paleocene groups within Placentalia under different cladistic optimality criteria. We scored 140 taxa for 503 dental, cranial and postcranial characters, incorporating new morphological and taxonomic data. The data were then subject to parsimony and Bayesian tree of morphological evolution, running 5000000 generations with samples every 200 generations and discarding 25% of the samples as burn-in. Stationarity was achieved and a 50 percent majority rule consensus tree from the sampled trees was obtained. The parsimony analysis recovered 48 most parsimonious trees. The two consensus trees derived from the different analyses are largely congruent and recover a monophyletic Periptychidae, although the parsimony consensus tree is better resolved. These results are consistent with simulation studies showing that parsimony tends to be more precise (more nodes reconstructed) than Bayesian analyses, although less accurate. The main topological differences between the results relate to the position of poorly known Puercan (earliest Paleocene) species. Our results affirm the monophyly of Periptychidae and its nesting within a group of “condylarths” positioned at the base of Laurasiatheria and closely related to Artiodactyla. Within Periptychidae we found support for the three major subfamilial divisions in both analyses. These results highlight the importance of using different optimality criteria when resolving a phylogeny and provide a new insight into how placental mammals were evolving after the end-Cretaceous extinction. Grant Information: CONICYT PFCHA/DOCTORADO BECAS CHILE/2018, European Research Council Starting Grant (ERC StG 2017, 756226, PalM), National Science Foundation (NSF EAR 1654952, DEB 1654949) 
    more » « less
  3. ; ; ; ; ; ; ; ; ; ; et al (, Applications in Plant Sciences)
    PremiseHybrid capture with high‐throughput sequencing (Hyb‐Seq) is a powerful tool for evolutionary studies. The applicability of an Asteraceae family‐specific Hyb‐Seq probe set and the outcomes of different phylogenetic analyses are investigated here. MethodsHyb‐Seq data from 112 Asteraceae samples were organized into groups at different taxonomic levels (tribe, genus, and species). For each group, data sets of non‐paralogous loci were built and proportions of parsimony informative characters estimated. The impacts of analyzing alternative data sets, removing long branches, and type of analysis on tree resolution and inferred topologies were investigated in tribe Cichorieae. ResultsAlignments of the Asteraceae family‐wide Hyb‐Seq locus set were parsimony informative at all taxonomic levels. Levels of resolution and topologies inferred at shallower nodes differed depending on the locus data set and the type of analysis, and were affected by the presence of long branches. DiscussionThe approach used to build a Hyb‐Seq locus data set influenced resolution and topologies inferred in phylogenetic analyses. Removal of long branches improved the reliability of topological inferences in maximum likelihood analyses. The Astereaceae Hyb‐Seq probe set is applicable at multiple taxonomic depths, which demonstrates that probe sets do not necessarily need to be lineage‐specific. 
    more » « less
  4. ; ; (, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021))
    Carbone, Alessandra; El-Kebir, Mohammed (Ed.)
    The maximum parsimony phylogenetic reconciliation problem seeks to explain incongruity between a gene phylogeny and a species phylogeny with respect to a set of evolutionary events. While the reconciliation problem is well-studied for species and gene trees subject to events such as duplication, transfer, loss, and deep coalescence, recent work has examined species phylogenies that incorporate hybridization and are thus represented by networks rather than trees. In this paper, we show that the problem of computing a maximum parsimony reconciliation for a gene tree and species network is NP-hard even when only considering deep coalescence. This result suggests that future work on maximum parsimony reconciliation for species networks should explore approximation algorithms and heuristics. 
    more » « less
  5. ; (, Biometrika)
    Summary Rooted and ranked phylogenetic trees are mathematical objects that are useful in modelling hierarchical data and evolutionary relationships with applications to many fields such as evolutionary biology and genetic epidemiology. Bayesian phylogenetic inference usually explores the posterior distribution of trees via Markov chain Monte Carlo methods. However, assessing uncertainty and summarizing distributions remains challenging for these types of structures. While labelled phylogenetic trees have been extensively studied, relatively less literature exists for unlabelled trees that are increasingly useful, for example when one seeks to summarize samples of trees obtained with different methods, or from different samples and environments, and wishes to assess the stability and generalizability of these summaries. In our paper, we exploit recently proposed distance metrics of unlabelled ranked binary trees and unlabelled ranked genealogies, or trees equipped with branch lengths, to define the Fréchet mean, variance and interquartile sets as summaries of these tree distributions. We provide an efficient combinatorial optimization algorithm for computing the Fréchet mean of a sample or of distributions on unlabelled ranked tree shapes and unlabelled ranked genealogies. We show the applicability of our summary statistics for studying popular tree distributions and for comparing the SARS-CoV-2 evolutionary trees across different locations during the COVID-19 epidemic in 2020. Our current implementations are publicly available at https://github.com/RSamyak/fmatrix. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email