Phylogenetic Diversity Rankings in the Face of Extinctions: The Robustness of the Fair Proportion Index.

Planning for the protection of species often involves difficult choices about which species to prioritize, given constrained resources. One way of prioritizing species is to consider their "evolutionary distinctiveness," (ED) that is, their relative evolutionary isolation on a phylogenetic tree. Several evolutionary isolation metrics or phylogenetic diversity indices have been introduced in the literature, among them the so-called Fair Proportion (FP) index (also known as the ED score). This index apportions the total diversity of a tree among all leaves, thereby providing a simple prioritization criterion for conservation. Here, we focus on the prioritization order obtained from the FP index and analyze the effects of species extinction on this ranking. More precisely, we analyze the extent to which the ranking order may change when some species go extinct and the FP index is recomputed for the remaining taxa. We show that for each phylogenetic tree, there are edge lengths such that the extinction of one leaf per cherry completely reverses the ranking. Moreover, we show that even if only the lowest-ranked species goes extinct, the ranking order may drastically change. We end by analyzing the effects of these two extinction scenarios (extinction of the lowest-ranked species and extinction of one leaf per cherry) for a collection of empirical and simulated trees. In both cases, we can observe significant changes in the prioritization orders, highlighting the empirical relevance of our theoretical findings. [Biodiversity conservation; Fair Proportion index; phylogenetic diversity; species prioritization.].

Effects of discordance between species and gene trees on phylogenetic diversity conservation.

Phylogenetic diversity indices such as the Fair Proportion (FP) index are frequently discussed as prioritization criteria in biodiversity conservation. They rank species according to their contribution to overall diversity by taking into account the unique and shared evolutionary history of each species as indicated by its placement in an underlying phylogenetic tree. Traditionally, phylogenetic trees were inferred from single genes and the resulting gene trees were assumed to be a valid estimate for the species tree, i.e., the "true" evolutionary history of the species under consideration. However, nowadays it is common to sequence whole genomes of hundreds or thousands of genes, and it is often the case that conflicting genealogical histories exist in different genes throughout the genome, resulting in discordance between individual gene trees and the species tree. Here, we analyze the effects of gene and species tree discordance on prioritization decisions based on the FP index. In particular, we consider the ranking order of taxa induced by (i) The FP index on a species tree, and (ii) The expected FP index across all gene tree histories associated with the species tree. On the one hand, we show that for particular tree shapes, the two rankings always coincide. On the other hand, we show that for all leaf numbers greater than or equal to five, there exist species trees for which the two rankings differ. Finally, we illustrate the variability in the rankings obtained from the FP index across different gene tree and species tree estimates for an empirical multilocus mammal data set.

Discrete coalescent trees.

In many phylogenetic applications, such as cancer and virus evolution, time trees, evolutionary histories where speciation events are timed, are inferred. Of particular interest are clock-like trees, where all leaves are sampled at the same time and have equal distance to the root. One popular approach to model clock-like trees is coalescent theory, which is used in various tree inference software packages. Methodologically, phylogenetic inference methods require a tree space over which the inference is performed, and the geometry of this space plays an important role in statistical and computational aspects of tree inference algorithms. It has recently been shown that coalescent tree spaces possess a unique geometry, different from that of classical phylogenetic tree spaces. Here we introduce and study a space of discrete coalescent trees. They assume that time is discrete, which is natural in many computational applications. This tree space is a generalisation of the previously studied ranked nearest neighbour interchange space, and is built upon tree-rearrangement operations. We generalise existing results about ranked trees, including an algorithm for computing distances in polynomial time, and in particular provide new results for both the space of discrete coalescent trees and the space of ranked trees. We establish several geometrical properties of these spaces and show how these properties impact various algorithms used in phylogenetic analyses. Our tree space is a discretisation of a previously introduced time tree space, called t-space, and hence our results can be used to approximate solutions to various open problems in t-space.

The Space of Tree-Based Phylogenetic Networks.

Phylogenetic networks are generalizations of phylogenetic trees that allow the representation of reticulation events such as horizontal gene transfer or hybridization, and can also represent uncertainty in inference. A subclass of these, tree-based phylogenetic networks, have been introduced to capture the extent to which reticulate evolution nevertheless broadly follows tree-like patterns. Several important operations that change a general phylogenetic network have been developed in recent years and are important for allowing algorithms to move around spaces of networks; a vital ingredient in finding an optimal network given some biological data. A key such operation is the nearest neighbour interchange, or NNI. While it is already known that the space of unrooted phylogenetic networks is connected under NNI, it has been unclear whether this also holds for the subspace of tree-based networks. In this paper, we show that the space of unrooted tree-based phylogenetic networks is indeed connected under the NNI operation. We do so by explicitly showing how to get from one such network to another one without losing tree-basedness along the way. Moreover, we introduce some new concepts, for instance "shoat networks", and derive some interesting aspects concerning tree-basedness. Last, we use our results to derive an upper bound on the size of the space of tree-based networks.

On the minimum value of the Colless index and the bifurcating trees that achieve it.

Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted bifurcating trees, introduced by Colless (Syst Zool 31:100-104, 1982). While many of its statistical properties under different probabilistic models for phylogenetic trees have already been established, little is known about its minimum value and the trees that achieve it. In this manuscript, we fill this gap in the literature. To begin with, we derive both recursive and closed expressions for the minimum Colless index of a tree with n leaves. Surprisingly, these expressions show a connection between the minimum Colless index and the so-called Blancmange curve, a fractal curve. We then fully characterize the tree shapes that achieve this minimum value and we introduce both an algorithm to generate them and a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index.

On the uniqueness of the maximum parsimony tree for data with up to two substitutions: An extension of the classic Buneman theorem in phylogenetics.

One of the main aims of phylogenetics is the reconstruction of the correct evolutionary tree when data concerning the underlying species set are given. These data typically come in the form of DNA, RNA or protein alignments, which consist of various characters (also often referred to as sites). Often, however, tree reconstruction methods based on criteria like maximum parsimony may fail to provide a unique tree for a given dataset, or, even worse, reconstruct the 'wrong' tree (i.e. a tree that differs from the one that generated the data). On the other hand it has long been known that if the alignment consists of all the characters that correspond to edges of a particular tree, i.e. they all require exactly k=1 substitution to be realized on that tree, then this tree will be recovered by maximum parsimony methods. This is based on Buneman's theorem in mathematical phylogenetics. It is the goal of the present manuscript to extend this classic result as follows: We prove that if an alignment consists of all characters that require exactly k=2 substitutions on a particular tree, this tree will always be the unique maximum parsimony tree (and we also show that this can be generalized to characters which require at most k=2 substitutions). In particular, this also proves a conjecture based on a recently published observation by Goloboff et al. affirmatively for the special case of k=2.

Second-line chemotherapy in biliary tract cancer: Outcome and prognostic factors.

BACKGROUND & AIMS: The prognosis of biliary tract cancer (BTC) is poor. Standard treatment for advanced BTC is a chemotherapy (CT) with gemcitabine and cisplatin. Phase III evidence for a second-line (2L) CT is lacking. We aimed to investigate the feasibility of a 2L CT, to estimate the outcome and to identify prognostic markers. METHODS: Patients of our institution with advanced BTC between 2000 and 2015 receiving CT were included. Data were analysed in univariate and multivariate analysis. RESULTS: Three-hundred and fifteen and 144 patients (45.7%) received first-line (1L) and 2L CT respectively. The OS of patients receiving 2L CT was 16.67 and 9.9 months from the beginning of 1L and 2L CT respectively. The overall response rate and the disease control rate after 3 months were 9.7% and 33.6% respectively. Adverse events of grade 3 or more were observed in 26.1%. One patient died of gemcitabine-related haemolytic uraemic syndrome. Age of more than 70 years was not associated with a poor outcome. In multivariate analysis, CEA levels of >3 µg/L (P = 0.004, hazard ratio [HR] 1.89, 95% CI 1.22, 2.91), cholinesterase (CHE) levels of <5 kU/L (P = 0.001, HR 2.11, 95% CI 1.34, 3.31) and leukocytosis (P = 0.001, HR 2.90, 95% CI 1.51, 5.56) were associated with poor survival. CONCLUSIONS: Despite a relevant toxicity, our data suggest that 2L CT may be feasible in fit BTC patients. CEA elevation, leukocytosis and low CHE levels are unfavourable prognostic markers. Results from prospective randomized trials are urgently awaited.

On the Shapley Value of Unrooted Phylogenetic Trees.

The Shapley value, a solution concept from cooperative game theory, has recently been considered for both unrooted and rooted phylogenetic trees. Here, we focus on the Shapley value of unrooted trees and first revisit the so-called split counts of a phylogenetic tree and the Shapley transformation matrix that allows for the calculation of the Shapley value from the edge lengths of a tree. We show that non-isomorphic trees may have permutation-equivalent Shapley transformation matrices and permutation-equivalent null spaces. This implies that estimating the split counts associated with a tree or the Shapley values of its leaves does not suffice to reconstruct the correct tree topology. We then turn to the use of the Shapley value as a prioritization criterion in biodiversity conservation and compare it to a greedy solution concept. Here, we show that for certain phylogenetic trees, the Shapley value may fail as a prioritization criterion, meaning that the diversity spanned by the top k species (ranked by their Shapley values) cannot approximate the total diversity of all n species.

Statistical Inconsistency of Maximum Parsimony for k-Tuple-Site Data.

One of the main aims of phylogenetics is to reconstruct the "Tree of Life." In this respect, different methods and criteria are used to analyze DNA sequences of different species and to compare them in order to derive the evolutionary relationships of these species. Maximum parsimony is one such criterion for tree reconstruction, and it is the one which we will use in this paper. However, it is well known that tree reconstruction methods can lead to wrong relationship estimates. One typical problem of maximum parsimony is long branch attraction, which can lead to statistical inconsistency. In this work, we will consider a blockwise approach to alignment analysis, namely the so-called k-tuple analyses. For four taxa, it has already been shown that k-tuple-based analyses are statistically inconsistent if and only if the standard character-based (site-based) analyses are statistically inconsistent. So, in the four-taxon case, going from individual sites to k-tuples does not lead to any improvement. However, real biological analyses often consider more than only four taxa. Therefore, we analyze the case of five taxa for 2- and 3-tuple-site data and consider alphabets with two and four elements. We show that the equivalence of single-site data and k-tuple-site data then no longer holds. Even so, we can show that maximum parsimony is statistically inconsistent for k-tuple-site data and five taxa.

On the Accuracy of Ancestral Sequence Reconstruction for Ultrametric Trees with Parsimony.

We examine a mathematical question concerning the reconstruction accuracy of the Fitch algorithm for reconstructing the ancestral sequence of the most recent common ancestor given a phylogenetic tree and sequence data for all taxa under consideration. In particular, for the symmetric four-state substitution model which is also known as Jukes-Cantor model, we answer affirmatively a conjecture of Li, Steel and Zhang which states that for any ultrametric phylogenetic tree and a symmetric model, the Fitch parsimony method using all terminal taxa is more accurate, or at least as accurate, for ancestral state reconstruction than using any particular terminal taxon or any particular pair of taxa. This conjecture had so far only been answered for two-state data by Fischer and Thatte. Here, we focus on answering the biologically more relevant case with four states, which corresponds to ancestral sequence reconstruction from DNA or RNA data.

On the information content of discrete phylogenetic characters.

Phylogenetic inference aims to reconstruct the evolutionary relationships of different species based on genetic (or other) data. Discrete characters are a particular type of data, which contain information on how the species should be grouped together. However, it has long been known that some characters contain more information than others. For instance, a character that assigns the same state to each species groups all of them together and so provides no insight into the relationships of the species considered. At the other extreme, a character that assigns a different state to each species also conveys no phylogenetic signal. In this manuscript, we study a natural combinatorial measure of the information content of an individual character and analyse properties of characters that provide the maximum phylogenetic information, particularly, the number of states such a character uses and how the different states have to be distributed among the species or taxa of the phylogenetic tree.

Risk estimation for biliary tract cancer: Development and validation of a prognostic score.

BACKGROUND & AIMS: Biliary tract cancer is a rare tumour entity characterized by a poor prognosis. We aimed to identify prognostic factors and create a prognostic score to estimate survival. METHODS: Clinical data of the training set, consisting of 569 patients treated from 2000 to 2010 at Hannover Medical School, were analysed. A prognostic model defining three prognostic risk groups was derived from Cox regression analyses. The score was applied and validated in an independent cohort of 557 patients from four different German centres. RESULTS: Median overall survival (OS) was 14.5 months. If complete resection was performed, the patients had a significantly improved OS (23.9 months; n=242) as compared to patients with non-resectable tumours (9.1 months; n=329, P<.0001). Based on univariable and multivariable analyses of clinical data, a prognostic model was created using variables available before treatment. Those were age, metastasis, C-reactive protein (CRP), international normalized ratio (INR) and bilirubin. The prognostic score distinguished three groups with a median OS of 21.8, 8.6 and 2.6 months respectively. The validation cohort had a median OS of 20.2, 14.0 and 6.5 months respectively. The prognostic impact of the score was independent of the tumour site and of treatment procedures. CONCLUSIONS: Here, we identified prognostic factors and propose a prognostic score to estimate survival, which can be applied to all patients independent of tumour site and before initial treatment. Further validation in prospective trials is required.

Comparing the rankings obtained from two biodiversity indices: the Fair Proportion Index and the Shapley Value.

The Shapley Value and the Fair Proportion Index of phylogenetic trees have been frequently discussed as prioritization tools in conservation biology. Both indices rank species according to their contribution to total phylogenetic diversity, allowing for a simple conservation criterion. While both indices have their specific advantages and drawbacks, it has recently been shown that both values are closely related. However, as different authors use different definitions of the Shapley Value, the specific degree of relatedness depends on the specific version of the Shapley Value - it ranges from a high correlation index to equality of the indices. In this note, we first give an overview of the different indices. Then we turn our attention to the mere ranking order provided by either of the indices. We compare the rankings obtained from different versions of the Shapley Value for a phylogenetic tree of European amphibians and illustrate their differences. We then undertake further analyses on simulated data and show that even though the chance of two rankings being exactly identical (when obtained from different versions of the Shapley Value) decreases with an increasing number of taxa, the distance between the two rankings converges to zero, i.e., the rankings are becoming more and more alike. Moreover, we introduce our freely available software package FairShapley, which was implemented in Perl and with which all calculations have been performed.

On the quirks of maximum parsimony and likelihood on phylogenetic networks.

Maximum parsimony is one of the most frequently-discussed tree reconstruction methods in phylogenetic estimation. However, in recent years it has become more and more apparent that phylogenetic trees are often not sufficient to describe evolution accurately. For instance, processes like hybridization or lateral gene transfer that are commonplace in many groups of organisms and result in mosaic patterns of relationships cannot be represented by a single phylogenetic tree. This is why phylogenetic networks, which can display such events, are becoming of more and more interest in phylogenetic research. It is therefore necessary to extend concepts like maximum parsimony from phylogenetic trees to networks. Several suggestions for possible extensions can be found in recent literature, for instance the softwired and the hardwired parsimony concepts. In this paper, we analyze the so-called big parsimony problem under these two concepts, i.e. we investigate maximum parsimonious networks and analyze their properties. In particular, we show that finding a softwired maximum parsimony network is possible in polynomial time. We also show that the set of maximum parsimony networks for the hardwired definition always contains at least one phylogenetic tree. Lastly, we investigate some parallels of parsimony to different likelihood concepts on phylogenetic networks.

Ancestral Sequence Reconstruction with Maximum Parsimony.

One of the main aims in phylogenetics is the estimation of ancestral sequences based on present-day data like, for instance, DNA alignments. One way to estimate the data of the last common ancestor of a given set of species is to first reconstruct a phylogenetic tree with some tree inference method and then to use some method of ancestral state inference based on that tree. One of the best-known methods both for tree inference and for ancestral sequence inference is Maximum Parsimony (MP). In this manuscript, we focus on this method and on ancestral state inference for fully bifurcating trees. In particular, we investigate a conjecture published by Charleston and Steel in 1995 concerning the number of species which need to have a particular state, say a, at a particular site in order for MP to unambiguously return a as an estimate for the state of the last common ancestor. We prove the conjecture for all even numbers of character states, which is the most relevant case in biology. We also show that the conjecture does not hold in general for odd numbers of character states, but also present some positive results for this case.

The most parsimonious tree for random data.

Applying a method to reconstruct a phylogenetic tree from random data provides a way to detect whether that method has an inherent bias towards certain tree 'shapes'. For maximum parsimony, applied to a sequence of random 2-state data, each possible binary phylogenetic tree has exactly the same distribution for its parsimony score. Despite this pleasing and slightly surprising symmetry, some binary phylogenetic trees are more likely than others to be a most parsimonious (MP) tree for a sequence of k such characters, as we show. For k=2, and unrooted binary trees on six taxa, any tree with a caterpillar shape has a higher chance of being an MP tree than any tree with a symmetric shape. On the other hand, if we take any two binary trees, on any number of taxa, we prove that this bias between the two trees vanishes as the number of characters k grows. However, again there is a twist: MP trees on six taxa for k=2 random binary characters are more likely to have certain shapes than a uniform distribution on binary phylogenetic trees predicts. Moreover, this shape bias appears, from simulations, to be more pronounced for larger values of k.

Automated Detection and Counting of Wild Boar in Camera Trap Images.

Camera traps are becoming widely used for wildlife monitoring and management. However, manual analysis of the resulting image sets is labor-intensive, time-consuming and costly. This study shows that automated computer vision techniques can be extremely helpful in this regard, as they can rapidly and automatically extract valuable information from the images. Specific training with a set of 1600 images obtained from a study where wild animals approaching wild boar carcasses were monitored enabled the model to detect five different classes of animals automatically in their natural environment with a mean average precision of 98.11%, namely 'wild boar', 'fox', 'raccoon dog', 'deer' and 'bird'. In addition, sequences of images were automatically analyzed and the number of wild boar visits and respective group sizes were determined. This study may help to improve and speed up the monitoring of the potential spread of African swine fever virus in areas where wild boar are affected.

Non-hereditary Maximum Parsimony trees.

In this paper, we investigate a conjecture by Arndt von Haeseler concerning the Maximum Parsimony method for phylogenetic estimation, which was published by the Newton Institute in Cambridge on a list of open phylogenetic problems in 2007. This conjecture deals with the question whether Maximum Parsimony trees are hereditary. The conjecture suggests that a Maximum Parsimony tree for a particular (DNA) alignment necessarily has subtrees of all possible sizes which are most parsimonious for the corresponding subalignments. We answer the conjecture affirmatively for binary alignments on 5 taxa but also show how to construct examples for which Maximum Parsimony trees are not hereditary. Apart from showing that a most parsimonious tree cannot generally be reduced to a most parsimonious tree on fewer taxa, we also show that compatible most parsimonious quartets do not have to provide a most parsimonious supertree. Last, we show that our results can be generalized to Maximum Likelihood for certain nucleotide substitution models.

Computer Vision for Detection of Body Posture and Behavior of Red Foxes.

The behavior of animals is related to their health and welfare status. The latter plays a particular role in animal experiments, where continuous monitoring is essential for animal welfare. In this study, we focus on red foxes in an experimental setting and study their behavior. Although animal behavior is a complex concept, it can be described as a combination of body posture and activity. To measure body posture and activity, video monitoring can be used as a non-invasive and cost-efficient tool. While it is possible to analyze the video data resulting from the experiment manually, this method is time consuming and costly. We therefore use computer vision to detect and track the animals over several days. The detector is based on a neural network architecture. It is trained to detect red foxes and their body postures, i.e., 'lying', 'sitting', and 'standing'. The trained algorithm has a mean average precision of 99.91%. The combination of activity and posture results in nearly continuous monitoring of animal behavior. Furthermore, the detector is suitable for real-time evaluation. In conclusion, evaluating the behavior of foxes in an experimental setting using computer vision is a powerful tool for cost-efficient real-time monitoring.

Measuring tree balance using symmetry nodes - A new balance index and its extremal properties.

Effects like selection in evolution as well as fertility inheritance in the development of populations can lead to a higher degree of asymmetry in evolutionary trees than expected under a null hypothesis. To identify and quantify such influences, various balance indices were proposed in the phylogenetic literature and have been in use for decades. However, so far no balance index was based on the number of symmetry nodes, even though symmetry nodes play an important role in other areas of mathematical phylogenetics and despite the fact that symmetry nodes are a quite natural way to measure balance or symmetry of a given tree. The aim of this manuscript is thus twofold: First, we will introduce the symmetry nodes index as an index for measuring balance of phylogenetic trees and analyze its extremal properties. We also show that this index can be calculated in linear time. This new index turns out to be a generalization of a simple and well-known balance index, namely the cherry index, as well as a specialization of another, less established, balance index, namely Rogers' J index. Thus, it is the second objective of the present manuscript to compare the new symmetry nodes index to these two indices and to underline its advantages. In order to do so, we will derive some extremal properties of the cherry index and Rogers' J index along the way and thus complement existing studies on these indices. Moreover, we used the programming language R to implement all three indices in the software package symmeTree, which has been made publicly available.