Distance metrics for ranked evolutionary trees.
Ontology highlight
ABSTRACT:
SUBMITTER: Kim J
PROVIDER: S-EPMC7682335 | biostudies-literature | 2020 Nov
REPOSITORIES: biostudies-literature
Publications
Distance metrics for ranked evolutionary trees.
Kim Jaehee J Rosenberg Noah A NA Palacios Julia A JA
Proceedings of the National Academy of Sciences of the United States of America 20201102 46
Genealogical tree modeling is essential for estimating evolutionary parameters in population genetics and phylogenetics. Recent mathematical results concerning ranked genealogies without leaf labels unlock opportunities in the analysis of evolutionary trees. In particular, comparisons between ranked genealogies facilitate the study of evolutionary processes of different organisms sampled at multiple time periods. We propose metrics on ranked tree shapes and ranked genealogies for lineages isochr ...[more]
Similar Datasets
Project description:MotivationThere has been recent increased interest in using algorithmic methods to infer the evolutionary tree underlying the developmental history of a tumor. Quantitative measures that compare such trees are vital to a number of different applications including benchmarking tree inference methods and evaluating common inheritance patterns across patients. However, few appropriate distance measures exist, and those that do have low resolution for differentiating trees or do not fully account for the complex relationship between tree topology and the inheritance of the mutations labeling that topology.ResultsHere, we present two novel distance measures, Common Ancestor Set distance (CASet) and Distinctly Inherited Set Comparison distance (DISC), that are specifically designed to account for the subclonal mutation inheritance patterns characteristic of tumor evolutionary trees. We apply CASet and DISC to multiple simulated datasets and two breast cancer datasets and show that our distance measures allow for more nuanced and accurate delineation between tumor evolutionary trees than existing distance measures.Availability and implementationImplementations of CASet and DISC are freely available at: https://bitbucket.org/oesperlab/stereodist.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC7141873 | biostudies-literature
Project description:MotivationThe acquisition of somatic mutations by a tumor can be modeled by a type of evolutionary tree. However, it is impossible to observe this tree directly. Instead, numerous algorithms have been developed to infer such a tree from different types of sequencing data. But such methods can produce conflicting trees for the same patient, making it desirable to have approaches that can combine several such tumor trees into a consensus or summary tree. We introduce The Weighted m-Tumor Tree Consensus Problem (W-m-TTCP) to find a consensus tree among multiple plausible tumor evolutionary histories, each assigned a confidence weight, given a specific distance measure between tumor trees. We present an algorithm called TuELiP that is based on integer linear programming which solves the W-m-TTCP, and unlike other existing consensus methods, allows the input trees to be weighted differently.ResultsOn simulated data we show that TuELiP outperforms two existing methods at correctly identifying the true underlying tree used to create the simulations. We also show that the incorporation of weights can lead to more accurate tree inference. On a Triple-Negative Breast Cancer dataset, we show that including confidence weights can have important impacts on the consensus tree identified.AvailabilityAn implementation of TuELiP and simulated datasets are available at https://bitbucket.org/oesperlab/consensus-ilp/src/main/.
| S-EPMC10311318 | biostudies-literature
Project description:Accurate subject-specific vascular network reconstruction is a critical task for the hemodynamic analysis of cerebroarterial circulation. Vascular skeletonization and computational mesh generation for large sections of cerebrovascular trees from magnetic resonance angiography (MRA) is an error-prone, operator-dependent, and very time-consuming task. Validation of reconstructed computational models is essential to ascertain their accuracy and precision, which directly relates to the confidence of CFD computations performed on these meshes. The aim of this study is to generate an imaging segmentation pipeline to validate and quantify the spatial accuracy of computational models of subject-specific cerebral arterial trees. We used a recently introduced parametric structured mesh (PSM) generation method to automatically reconstruct six subject-specific cerebral arterial trees containing 1364 vessels and 571 bifurcations. By automatically extracting sampling frames for all vascular segments and bifurcations, we quantify the spatial accuracy of PSM against the original MRA images. Our comprehensive study correlates lumen area, pixel-based statistical analysis, area overlap and centerline accuracy measurements. In addition, we propose a new metric, the pointwise offset surface distance metric (PSD), to quantify the spatial alignment between dimensions of reconstructed arteries and bifurcations with in-vivo data with the ability to quantify the over- and under-approximation of the reconstructed models. Accurate reconstruction of vascular trees can a practical process tool for morphological analysis of large patient data banks, such as medical record files in hospitals, or subject-specific hemodynamic simulations of the cerebral arterial circulation.
| S-EPMC6181589 | biostudies-literature
Project description:MotivationReconstructing evolutionary histories of biological entities, such as genes, cells, organisms, populations, and species, from phenotypic and molecular sequencing data is central to many biological, palaeontological, and biomedical disciplines. Typically, due to uncertainties and incompleteness in data, the true evolutionary history (phylogeny) is challenging to estimate. Statistical modelling approaches address this problem by introducing and studying probability distributions over all possible evolutionary histories, but can also introduce uncertainties due to misspecification. In practice, computational methods are deployed to learn those distributions typically by sampling them. This approach, however, is fundamentally challenging as it requires designing and implementing various statistical methods over a space of phylogenetic trees (or treespace). Although the problem of developing statistics over a treespace has received substantial attention in the literature and numerous breakthroughs have been made, it remains largely unsolved. The challenge of solving this problem is 2-fold: a treespace has nontrivial often counter-intuitive geometry implying that much of classical Euclidean statistics does not immediately apply; many parametrizations of treespace with promising statistical properties are computationally hard, so they cannot be used in data analyses. As a result, there is no single conventional method for estimating even the most fundamental statistics over any treespace, such as mean and variance, and various heuristics are used in practice. Despite the existence of numerous tree summary methods to approximate means of probability distributions over a treespace based on its geometry, and the theoretical promise of this idea, none of the attempts resulted in a practical method for summarizing tree samples.ResultsIn this paper, we present a tree summary method along with useful properties of our chosen treespace while focusing on its impact on phylogenetic analyses of real datasets. We perform an extensive benchmark study and demonstrate that our method outperforms currently most popular methods with respect to a number of important 'quality' statistics. Further, we apply our method to three empirical datasets ranging from cancer evolution to linguistics and find novel insights into corresponding evolutionary problems in all of them. We hence conclude that this treespace is a promising candidate to serve as a foundation for developing statistics over phylogenetic trees analytically, as well as new computational tools for evolutionary data analyses.Availability and implementationAn implementation is available at https://github.com/bioDS/Centroid-Code.
| S-EPMC11364146 | biostudies-literature
Project description:SummaryPRANC computes the Probabilities of RANked gene tree topologies under the multispecies coalescent. A ranked gene tree is a gene tree accounting for the temporal ordering of internal nodes. PRANC can also estimate the maximum likelihood (ML) species tree from a sample of ranked or unranked gene tree topologies. It estimates the ML tree with estimated branch lengths in coalescent units.Availability and implementationPRANC is written in C++ and freely available at github.com/anastasiiakim/PRANC.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC7750968 | biostudies-literature
Project description:There is no doubt that distance is the principal parameter that sets the order of magnitude for electron-tunneling rates in proteins. However, there continue to be varying ways to measure electron-tunneling distances in proteins. This distance uncertainty blurs the issue of whether the intervening protein medium has been naturally selected to speed or slow any particular electron-tunneling reaction. For redox cofactors lacking metals, an edge of the cofactor can be defined that approximates the extent in space that includes most of the wavefunction associated with its tunneling electron. Beyond this edge, the wavefunction tails off much more dramatically in space. The conjugated porphyrin ring seems a reasonable edge for the metal-free pheophytins and bacteriopheophytins of photosynthesis. For a metal containing redox cofactor such as heme, an appropriate cofactor edge is more ambiguous. Electron-tunneling distance may be measured from the conjugated heme macrocycle edge or from the metal, which can be up to 4.8 A longer. In a typical protein medium, such a distance difference normally corresponds to a approximately 1000 fold decrease in tunneling rate. To address this ambiguity, we consider both natural heme protein electron transfer and light-activated electron transfer in ruthenated heme proteins. We find that the edge of the conjugated heme macrocycle provides a reliable and useful tunneling distance definition consistent with other biological electron-tunneling reactions. Furthermore, with this distance metric, heme axially- and edge-oriented electron transfers appear similar and equally well described by a simple square barrier tunneling model. This is in contrast to recent reports for metal-to-metal metrics that require exceptionally poor donor/acceptor couplings to explain heme axially-oriented electron transfers.
| S-EPMC2536628 | biostudies-literature
Project description:Identifying coevolving positions in protein sequences has myriad applications, ranging from understanding and predicting the structure of single molecules to generating proteome-wide predictions of interactions. Algorithms for detecting coevolving positions can be classified into two categories: tree-aware, which incorporate knowledge of phylogeny, and tree-ignorant, which do not. Tree-ignorant methods are frequently orders of magnitude faster, but are widely held to be insufficiently accurate because of a confounding of shared ancestry with coevolution. We conjectured that by using a null distribution that appropriately controls for the shared-ancestry signal, tree-ignorant methods would exhibit equivalent statistical power to tree-aware methods. Using a novel t-test transformation of coevolution metrics, we systematically compared four tree-aware and five tree-ignorant coevolution algorithms, applying them to myoglobin and myosin. We further considered the influence of sequence recoding using reduced-state amino acid alphabets, a common tactic employed in coevolutionary analyses to improve both statistical and computational performance.Consistent with our conjecture, the transformed tree-ignorant metrics (particularly Mutual Information) often outperformed the tree-aware metrics. Our examination of the effect of recoding suggested that charge-based alphabets were generally superior for identifying the stabilizing interactions in alpha helices. Performance was not always improved by recoding however, indicating that the choice of alphabet is critical.The results suggest that t-test transformation of tree-ignorant metrics can be sufficient to control for patterns arising from shared ancestry.
| S-EPMC2637866 | biostudies-other
Project description:BackgroundPhylogenetic tree comparison metrics are an important tool in the study of evolution, and hence the definition of such metrics is an interesting problem in phylogenetics. In a paper in Taxon fifty years ago, Sokal and Rohlf proposed to measure quantitatively the difference between a pair of phylogenetic trees by first encoding them by means of their half-matrices of cophenetic values, and then comparing these matrices. This idea has been used several times since then to define dissimilarity measures between phylogenetic trees but, to our knowledge, no proper metric on weighted phylogenetic trees with nested taxa based on this idea has been formally defined and studied yet. Actually, the cophenetic values of pairs of different taxa alone are not enough to single out phylogenetic trees with weighted arcs or nested taxa.ResultsFor every (rooted) phylogenetic tree T, let its cophenetic vectorφ(T) consist of all pairs of cophenetic values between pairs of taxa in T and all depths of taxa in T. It turns out that these cophenetic vectors single out weighted phylogenetic trees with nested taxa. We then define a family of cophenetic metrics dφ,p by comparing these cophenetic vectors by means of Lp norms, and we study, either analytically or numerically, some of their basic properties: neighbors, diameter, distribution, and their rank correlation with each other and with other metrics.ConclusionsThe cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed in O(n2) time, where n stands for the number of taxa. The metrics dφ,1 and dφ,2 have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics. The diameter of dφ,p, for p⩾1 , is in O(n(p+2)/p), and thus for low p they are more discriminative, having a wider range of values.
| S-EPMC3716993 | biostudies-literature
Project description:Multi-regional sequencing provides new opportunities to investigate genetic heterogeneity within or between common tumors from an evolutionary perspective. Several state-of-the-art methods have been proposed for reconstructing cancer evolutionary trees based on multi-regional sequencing data to develop models of cancer evolution. However, there have been few studies on comparisons of a set of cancer evolutionary trees. We propose a clustering method (phyC) for cancer evolutionary trees, in which sub-groups of the trees are identified based on topology and edge length attributes. For interpretation, we also propose a method for evaluating the sub-clonal diversity of trees in the clusters, which provides insight into the acceleration of sub-clonal expansion. Simulation showed that the proposed method can detect true clusters with sufficient accuracy. Application of the method to actual multi-regional sequencing data of clear cell renal carcinoma and non-small cell lung cancer allowed for the detection of clusters related to cancer type or phenotype. phyC is implemented with R(≥3.2.2) and is available from https://github.com/ymatts/phyC.
| S-EPMC5432190 | biostudies-literature
Project description:The most widely used evolutionary model for phylogenetic trees is the equal-rates Markov (ERM) model. A problem is that the ERM model predicts less imbalance than observed for trees inferred from real data; in fact, the observed imbalance tends to fall between the values predicted by the ERM model and those predicted by the proportional-to-distinguishable-arrangements (PDA) model. Here, a continuous multi-rate (MR) family of evolutionary models is presented which contains entire subfamilies corresponding to both the PDA and ERM models. Furthermore, this MR family covers an entire range from 'completely balanced' to 'completely unbalanced' models. In particular, the MR family contains other known evolutionary models. The MR family is very versatile and virtually free of assumptions on the character of evolution; yet it is highly susceptible to rigorous analyses. In particular, such analyses help to uncover adaptability, quasi-stabilization and prolonged stasis as major possible causes of the imbalance. However, the MR model is functionally simple and requires only three parameters to reproduce the observed imbalance.
| S-EPMC1691382 | biostudies-literature