1
|
De Maio N, Alekseyenko AV, Coleman-Smith WJ, Pardi F, Suchard MA, Tamuri AU, Truszkowski J, Goldman N. A phylogenetic approach for weighting genetic sequences. BMC Bioinformatics 2021; 22:285. [PMID: 34049487 PMCID: PMC8164272 DOI: 10.1186/s12859-021-04183-8] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/04/2020] [Accepted: 05/04/2021] [Indexed: 11/22/2022] Open
Abstract
BACKGROUND Many important applications in bioinformatics, including sequence alignment and protein family profiling, employ sequence weighting schemes to mitigate the effects of non-independence of homologous sequences and under- or over-representation of certain taxa in a dataset. These schemes aim to assign high weights to sequences that are 'novel' compared to the others in the same dataset, and low weights to sequences that are over-represented. RESULTS We formalise this principle by rigorously defining the evolutionary 'novelty' of a sequence within an alignment. This results in new sequence weights that we call 'phylogenetic novelty scores'. These scores have various desirable properties, and we showcase their use by considering, as an example application, the inference of character frequencies at an alignment column-important, for example, in protein family profiling. We give computationally efficient algorithms for calculating our scores and, using simulations, show that they are versatile and can improve the accuracy of character frequency estimation compared to existing sequence weighting schemes. CONCLUSIONS Our phylogenetic novelty scores can be useful when an evolutionarily meaningful system for adjusting for uneven taxon sampling is desired. They have numerous possible applications, including estimation of evolutionary conservation scores and sequence logos, identification of targets in conservation biology, and improving and measuring sequence alignment accuracy.
Collapse
Affiliation(s)
- Nicola De Maio
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
| | - Alexander V. Alekseyenko
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
- Present Address: Department of Public Health Sciences, Medical University of South Carolina, Charleston, SC USA
| | - William J. Coleman-Smith
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
| | - Fabio Pardi
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
- Present Address: LIRMM, University of Montpellier, CNRS, Montpellier, France
| | - Marc A. Suchard
- Departments of Biostatistics, Biomathematics and Human Genetics, University of California, Los Angeles, CA USA
| | - Asif U. Tamuri
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
- Present Address: Research IT Services, University College London, London, UK
| | - Jakub Truszkowski
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
- Present Address: RBC Borealis AI, Waterloo, ON Canada
| | - Nick Goldman
- European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK
| |
Collapse
|
2
|
Hu Y, Fan H, Chen Y, Chang J, Zhan X, Wu H, Zhang B, Wang M, Zhang W, Yang L, Hou X, Shen X, Pan T, Wu W, Li J, Hu H, Wei F. Spatial patterns and conservation of genetic and phylogenetic diversity of wildlife in China. SCIENCE ADVANCES 2021; 7:eabd5725. [PMID: 33523945 PMCID: PMC10671236 DOI: 10.1126/sciadv.abd5725] [Citation(s) in RCA: 27] [Impact Index Per Article: 9.0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/29/2020] [Accepted: 12/03/2020] [Indexed: 06/12/2023]
Abstract
Genetic diversity and phylogenetic diversity reflect the evolutionary potential and history of species, respectively. However, the levels and spatial patterns of genetic and phylogenetic diversity of wildlife at the regional scale have largely remained unclear. Here, we performed meta-analyses of genetic diversity in Chinese terrestrial vertebrates based on three genetic markers and investigated their phylogenetic diversity based on a dated phylogenetic tree of 2461 species. We detected strong positive spatial correlations among mitochondrial DNA-based genetic diversity, phylogenetic diversity, and species richness. Moreover, the terrestrial vertebrates harbored higher genetic and phylogenetic diversity in South China and Southwest China than in other regions. Last, climatic factors (precipitation and temperature) had significant positive effects while altitude and human population density had significant negative impacts on levels of mitochondrial DNA-based genetic diversity in most cases. Our findings will help guide national-level genetic diversity conservation plans and a post-2020 biodiversity conservation framework.
Collapse
Affiliation(s)
- Yibo Hu
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- University of Chinese Academy of Sciences, Beijing, China
- Center for Excellence in Animal Evolution and Genetics, Chinese Academy of Sciences, Kunming, China
| | - Huizhong Fan
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
| | - Youhua Chen
- Chengdu Institute of Biology, Chinese Academy of Sciences, Chengdu, China
| | - Jiang Chang
- State Key Laboratory of Environmental Criteria and Risk Assessment, Chinese Research Academy of Environmental Sciences, Beijing, China
| | - Xiangjiang Zhan
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- Center for Excellence in Animal Evolution and Genetics, Chinese Academy of Sciences, Kunming, China
| | - Hua Wu
- Institute of Evolution and Ecology, School of Life Sciences, Central China Normal University, Wuhan, China
| | - Baowei Zhang
- School of Life Sciences, Anhui University, Hefei, China
| | - Meng Wang
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- University of Chinese Academy of Sciences, Beijing, China
| | - Wenyan Zhang
- University of Chinese Academy of Sciences, Beijing, China
- Chengdu Institute of Biology, Chinese Academy of Sciences, Chengdu, China
| | - Lin Yang
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- University of Chinese Academy of Sciences, Beijing, China
| | - Xian Hou
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- University of Chinese Academy of Sciences, Beijing, China
| | - Xing Shen
- Institute of Evolution and Ecology, School of Life Sciences, Central China Normal University, Wuhan, China
| | - Tao Pan
- School of Life Sciences, Anhui University, Hefei, China
| | - Wei Wu
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China
- University of Chinese Academy of Sciences, Beijing, China
| | - Jun Li
- Institute of Evolution and Ecology, School of Life Sciences, Central China Normal University, Wuhan, China
| | - Haihua Hu
- State Key Laboratory of Systematic and Evolutionary Botany, Institute of Botany, Chinese Academy of Sciences, Beijing, China
| | - Fuwen Wei
- CAS Key Laboratory of Animal Ecology and Conservation Biology, Institute of Zoology, Chinese Academy of Sciences, Beijing, China.
- University of Chinese Academy of Sciences, Beijing, China
- Center for Excellence in Animal Evolution and Genetics, Chinese Academy of Sciences, Kunming, China
- Southern Marine Science and Engineering Guangdong Laboratory (Guangzhou), Guangdong, China
| |
Collapse
|
3
|
Abstract
The human microbiome is the ensemble of genes in the microbes that live inside and on the surface of humans. Because microbial sequencing information is now much easier to come by than phenotypic information, there has been an explosion of sequencing and genetic analysis of microbiome samples. Much of the analytical work for these sequences involves phylogenetics, at least indirectly, but methodology has developed in a somewhat different direction than for other applications of phylogenetics. In this article, I review the field and its methods from the perspective of a phylogeneticist, as well as describing current challenges for phylogenetics coming from this type of work.
Collapse
Affiliation(s)
- Frederick A Matsen
- Program in Computational Biology, Fred Hutchinson Cancer Research Center, Seattle, WA 91802, USA
| |
Collapse
|
4
|
McCoy CO, Matsen FA. Abundance-weighted phylogenetic diversity measures distinguish microbial community states and are robust to sampling depth. PeerJ 2013; 1:e157. [PMID: 24058885 PMCID: PMC3775626 DOI: 10.7717/peerj.157] [Citation(s) in RCA: 42] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/01/2013] [Accepted: 08/20/2013] [Indexed: 12/17/2022] Open
Abstract
In microbial ecology studies, the most commonly used ways of investigating alpha (within-sample) diversity are either to apply non-phylogenetic measures such as Simpson’s index to Operational Taxonomic Unit (OTU) groupings, or to use classical phylogenetic diversity (PD), which is not abundance-weighted. Although alpha diversity measures that use abundance information in a phylogenetic framework do exist, they are not widely used within the microbial ecology community. The performance of abundance-weighted phylogenetic diversity measures compared to classical discrete measures has not been explored, and the behavior of these measures under rarefaction (sub-sampling) is not yet clear. In this paper we compare the ability of various alpha diversity measures to distinguish between different community states in the human microbiome for three different datasets. We also present and compare a novel one-parameter family of alpha diversity measures, BWPDθ, that interpolates between classical phylogenetic diversity (PD) and an abundance-weighted extension of PD. Additionally, we examine the sensitivity of these phylogenetic diversity measures to sampling, via computational experiments and by deriving a closed form solution for the expectation of phylogenetic quadratic entropy under re-sampling. On the three datasets, a phylogenetic measure always performed best, and two abundance-weighted phylogenetic diversity measures were the only measures ranking in the top four across all datasets. OTU-based measures, on the other hand, are less effective in distinguishing community types. In addition, abundance-weighted phylogenetic diversity measures are less sensitive to differing sampling intensity than their unweighted counterparts. Based on these results we encourage the use of abundance-weighted phylogenetic diversity measures, especially for cases such as microbial ecology where species delimitation is difficult.
Collapse
Affiliation(s)
- Connor O McCoy
- Fred Hutchinson Cancer Research Center , Seattle, WA , United States
| | | |
Collapse
|
5
|
Göker M, Klenk HP. Phylogeny-driven target selection for large-scale genome-sequencing (and other) projects. Stand Genomic Sci 2013; 8:360-74. [PMID: 23991265 PMCID: PMC3746418 DOI: 10.4056/sigs.3446951] [Citation(s) in RCA: 42] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/03/2023] Open
Abstract
Despite the steadily decreasing costs of genome sequencing, prioritizing organisms for sequencing remains important in large-scale projects. Phylogeny-based selection is of interest to identify those organisms whose genomes can be expected to differ most from those that have already been sequenced. Here, we describe a method that infers a phylogenetic scoring independent of which set of organisms has previously been targeted, which is computationally simple and easy to apply in practice. The scoring itself, as well as pre- and post-processing of the data, is illustrated using two real-world examples in which the method has already been applied for selecting targets for genome sequencing. These projects are the JGI CSP Genomic Encyclopedia of Bacteria and Archaea phase I, targeting 1,000 type strains, and, on a smaller-scale, the phylogenomics of the Roseobacter clade. Potential artifacts of the method are discussed and compared to a selection approach based on the taxonomic classification.
Collapse
Affiliation(s)
- Markus Göker
- Leibniz Institute DSMZ – German Collection of Microorganisms and Cell Cultures, Braunschweig, Germany
| | - Hans-Peter Klenk
- Leibniz Institute DSMZ – German Collection of Microorganisms and Cell Cultures, Braunschweig, Germany
| |
Collapse
|
6
|
Nipperess DA, Matsen FA. The mean and variance of phylogenetic diversity under rarefaction. Methods Ecol Evol 2013; 4:566-572. [PMID: 23833701 DOI: 10.1111/2041-210x.12042] [Citation(s) in RCA: 43] [Impact Index Per Article: 3.9] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/21/2022]
Abstract
Phylogenetic diversity (PD) depends on sampling depth, which complicates the comparison of PD between samples of different depth. One approach to dealing with differing sample depth for a given diversity statistic is to rarefy, which means to take a random subset of a given size of the original sample. Exact analytical formulae for the mean and variance of species richness under rarefaction have existed for some time but no such solution exists for PD.We have derived exact formulae for the mean and variance of PD under rarefaction. We confirm that these formulae are correct by comparing exact solution mean and variance to that calculated by repeated random (Monte Carlo) subsampling of a dataset of stem counts of woody shrubs of Toohey Forest, Queensland, Australia. We also demonstrate the application of the method using two examples: identifying hotspots of mammalian diversity in Australasian ecoregions, and characterising the human vaginal microbiome.There is a very high degree of correspondence between the analytical and random subsampling methods for calculating mean and variance of PD under rarefaction, although the Monte Carlo method requires a large number of random draws to converge on the exact solution for the variance.Rarefaction of mammalian PD of ecoregions in Australasia to a common standard of 25 species reveals very different rank orderings of ecoregions, indicating quite different hotspots of diversity than those obtained for unrarefied PD. The application of these methods to the vaginal microbiome shows that a classical score used to quantify bacterial vaginosis is correlated with the shape of the rarefaction curve.The analytical formulae for the mean and variance of PD under rarefaction are both exact and more efficient than repeated subsampling. Rarefaction of PD allows for many applications where comparisons of samples of different depth is required.
Collapse
Affiliation(s)
- David A Nipperess
- Department of Biological Sciences, Faculty of Science, Macquarie University, NSW, 2109, Australia, + 61 2 9850 6950
| | | |
Collapse
|
7
|
Abstract
The phylogenetic diversity (PD) of a set of species is a measure of the evolutionary distance among the species in the collection, based on a phylogenetic tree. Such a tree is composed of a root, internal nodes, and leaves that correspond to the set of taxa under study. With each edge of the tree is associated a non-negative branch length (evolutionary distance). If a particular survival probability is associated with each taxon, the PD measure becomes the expected PD measure. In the Noah's Ark Problem (NAP) introduced by Weitzman (1998), these survival probabilities can be increased at some cost. The problem is to determine how best to allocate a limited amount of resources to maximize the expected PD of the considered species. It is easy to formulate the NAP as a (difficult) nonlinear 0-1 programming problem. The aim of this article is to show that a general version of the NAP (GNAP) can be solved simply and efficiently with any set of edge weights and any set of survival probabilities by using standard mixed-integer linear programming software. The crucial point to move from a nonlinear program in binary variables to a mixed-integer linear program, is to approximate the logarithmic function by the lower envelope of a set of tangents to the curve. Solving the obtained mixed-integer linear program provides not only a near-optimal solution but also an upper bound on the value of the optimal solution. We also applied this approach to a generalization of the nature reserve problem (GNRP) that consists of selecting a set of regions to be conserved so that the expected PD of the set of species present in these regions is maximized. In this case, the survival probabilities of different taxa are not independent of each other. Computational results are presented to illustrate potentialities of the approach. Near-optimal solutions with hypothetical phylogenetic trees comprising about 4000 taxa are obtained in a few seconds or minutes of computing time for the GNAP, and in about 30 min for the GNRP. In all the cases the average guarantee varies from 0% to 1.20%.
Collapse
Affiliation(s)
- Alain Billionnet
- Laboratoire CEDRIC, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise 1, square de la Résistance, 91025 Evry cedex, France.
| |
Collapse
|
8
|
Hickey G, Blanchette M, Carmi P, Maheshwari A, Zeh N. An approximation algorithm for the Noah's Ark problem with random feature loss. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011; 8:551-556. [PMID: 20479502 DOI: 10.1109/tcbb.2010.37] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/29/2023]
Abstract
The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.
Collapse
Affiliation(s)
- Glenn Hickey
- School of Computer Science,McGill University, 3480 University Street, McConnell Engineering Building, Room 318, Montreal, QC H3A 2A7, Canada.
| | | | | | | | | |
Collapse
|
9
|
Ommeh S, Budd A, Ngara MV, Njaci I, de Villiers EP. Basic Molecular Evolution Workshop - A trans-African virtual training course. Bioessays 2011; 33:243-7. [DOI: 10.1002/bies.201000139] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/11/2022]
|
10
|
Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. J Math Biol 2011; 64:69-85. [PMID: 21301849 DOI: 10.1007/s00285-011-0405-9] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/04/2010] [Revised: 01/17/2011] [Indexed: 12/24/2022]
Abstract
Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time [Formula: see text] -approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1 - 1/e)-approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al.
Collapse
|
11
|
Plazzi F, Ferrucci RR, Passamonti M. Phylogenetic representativeness: a new method for evaluating taxon sampling in evolutionary studies. BMC Bioinformatics 2010; 11:209. [PMID: 20423512 PMCID: PMC2871275 DOI: 10.1186/1471-2105-11-209] [Citation(s) in RCA: 28] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/22/2009] [Accepted: 04/27/2010] [Indexed: 11/10/2022] Open
Abstract
Background Taxon sampling is a major concern in phylogenetic studies. Incomplete, biased, or improper taxon sampling can lead to misleading results in reconstructing evolutionary relationships. Several theoretical methods are available to optimize taxon choice in phylogenetic analyses. However, most involve some knowledge about the genetic relationships of the group of interest (i.e., the ingroup), or even a well-established phylogeny itself; these data are not always available in general phylogenetic applications. Results We propose a new method to assess taxon sampling developing Clarke and Warwick statistics. This method aims to measure the "phylogenetic representativeness" of a given sample or set of samples and it is based entirely on the pre-existing available taxonomy of the ingroup, which is commonly known to investigators. Moreover, our method also accounts for instability and discordance in taxonomies. A Python-based script suite, called PhyRe, has been developed to implement all analyses we describe in this paper. Conclusions We show that this method is sensitive and allows direct discrimination between representative and unrepresentative samples. It is also informative about the addition of taxa to improve taxonomic coverage of the ingroup. Provided that the investigators' expertise is mandatory in this field, phylogenetic representativeness makes up an objective touchstone in planning phylogenetic studies.
Collapse
Affiliation(s)
- Federico Plazzi
- Department of "Biologia Evoluzionistica Sperimentale", University of Bologna, Via Selmi 3, 40126 Bologna, Italy.
| | | | | |
Collapse
|
12
|
Abstract
A new initiative provides comparative genomicists with a more complete picture of genome diversity. Here we discuss the improved sampling strategy.
Collapse
|
13
|
Wu D, Hugenholtz P, Mavromatis K, Pukall R, Dalin E, Ivanova NN, Kunin V, Goodwin L, Wu M, Tindall BJ, Hooper SD, Pati A, Lykidis A, Spring S, Anderson IJ, D'haeseleer P, Zemla A, Singer M, Lapidus A, Nolan M, Copeland A, Han C, Chen F, Cheng JF, Lucas S, Kerfeld C, Lang E, Gronow S, Chain P, Bruce D, Rubin EM, Kyrpides NC, Klenk HP, Eisen JA. A phylogeny-driven genomic encyclopaedia of Bacteria and Archaea. Nature 2010; 462:1056-60. [PMID: 20033048 DOI: 10.1038/nature08656] [Citation(s) in RCA: 716] [Impact Index Per Article: 51.1] [Reference Citation Analysis] [Abstract] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/03/2009] [Accepted: 10/30/2009] [Indexed: 02/01/2023]
Abstract
Sequencing of bacterial and archaeal genomes has revolutionized our understanding of the many roles played by microorganisms. There are now nearly 1,000 completed bacterial and archaeal genomes available, most of which were chosen for sequencing on the basis of their physiology. As a result, the perspective provided by the currently available genomes is limited by a highly biased phylogenetic distribution. To explore the value added by choosing microbial genomes for sequencing on the basis of their evolutionary relationships, we have sequenced and analysed the genomes of 56 culturable species of Bacteria and Archaea selected to maximize phylogenetic coverage. Analysis of these genomes demonstrated pronounced benefits (compared to an equivalent set of genomes randomly selected from the existing database) in diverse areas including the reconstruction of phylogenetic history, the discovery of new protein families and biological properties, and the prediction of functions for known genes from other organisms. Our results strongly support the need for systematic 'phylogenomic' efforts to compile a phylogeny-driven 'Genomic Encyclopedia of Bacteria and Archaea' in order to derive maximum knowledge from existing microbial genome data as well as from genome sequences to come.
Collapse
Affiliation(s)
- Dongying Wu
- DOE Joint Genome Institute, Walnut Creek, California 94598, USA
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Collapse
|
14
|
Cadotte MW, Jonathan Davies T, Regetz J, Kembel SW, Cleland E, Oakley TH. Phylogenetic diversity metrics for ecological communities: integrating species richness, abundance and evolutionary history. Ecol Lett 2010; 13:96-105. [DOI: 10.1111/j.1461-0248.2009.01405.x] [Citation(s) in RCA: 282] [Impact Index Per Article: 20.1] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/29/2022]
|
15
|
Affiliation(s)
- Bui Quang Minh
- Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Medical University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Veterinary University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
| | - Steffen Klaere
- Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Medical University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Veterinary University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Department of Mathematics, University of Auckland, Private Bag 92019, Auckland Mail Centre, Auckland 1142, New Zealand
| | - Arndt von Haeseler
- Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Medical University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
- Veterinary University of Vienna, Dr.-Bohr-Gasse 9/6, 1030 Vienna, Austria
| |
Collapse
|
16
|
Minh BQ, Pardi F, Klaere S, von Haeseler A. Budgeted phylogenetic diversity on circular split systems. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2009; 6:22-29. [PMID: 19179696 DOI: 10.1109/tcbb.2008.54] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/27/2023]
Abstract
In the last 15 years, Phylogenetic Diversity (PD) has gained interest in the community of conservation biologists as a surrogate measure for assessing biodiversity. We have recently proposed two approaches to select taxa for maximizing PD, namely PD with budget constraints and PD on split systems. In this paper, we will unify these two strategies and present a dynamic programming algorithm to solve the unified framework of selecting taxa with maximal PD under budget constraints on circular split systems. An improved algorithm will also be given if the underlying split system is a tree.
Collapse
Affiliation(s)
- Bui Quang Minh
- Center for Integrative Bioinformatics Vienna (CIBIV), Vienna.
| | | | | | | |
Collapse
|
17
|
Faith DP. Threatened species and the potential loss of phylogenetic diversity: conservation scenarios based on estimated extinction probabilities and phylogenetic risk analysis. CONSERVATION BIOLOGY : THE JOURNAL OF THE SOCIETY FOR CONSERVATION BIOLOGY 2008; 22:1461-1470. [PMID: 18798854 DOI: 10.1111/j.1523-1739.2008.01068.x] [Citation(s) in RCA: 85] [Impact Index Per Article: 5.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/26/2023]
Abstract
New species conservation strategies, including the EDGE of Existence (EDGE) program, have expanded threatened species assessments by integrating information about species' phylogenetic distinctiveness. Distinctiveness has been measured through simple scores that assign shared credit among species for evolutionary heritage represented by the deeper phylogenetic branches. A species with a high score combined with a high extinction probability receives high priority for conservation efforts. Simple hypothetical scenarios for phylogenetic trees and extinction probabilities demonstrate how such scoring approaches can provide inefficient priorities for conservation. An existing probabilistic framework derived from the phylogenetic diversity measure (PD) properly captures the idea of shared responsibility for the persistence of evolutionary history. It avoids static scores, takes into account the status of close relatives through their extinction probabilities, and allows for the necessary updating of priorities in light of changes in species threat status. A hypothetical phylogenetic tree illustrates how changes in extinction probabilities of one or more species translate into changes in expected PD. The probabilistic PD framework provided a range of strategies that moved beyond expected PD to better consider worst-case PD losses. In another example, risk aversion gave higher priority to a conservation program that provided a smaller, but less risky, gain in expected PD. The EDGE program could continue to promote a list of top species conservation priorities through application of probabilistic PD and simple estimates of current extinction probability. The list might be a dynamic one, with all the priority scores updated as extinction probabilities change. Results of recent studies suggest that estimation of extinction probabilities derived from the red list criteria linked to changes in species range sizes may provide estimated probabilities for many different species. Probabilistic PD provides a framework for single-species assessment that is well-integrated with a broader measurement of impacts on PD owing to climate change and other factors.
Collapse
Affiliation(s)
- Daniel P Faith
- The Australian Museum, 6 College Street, Sydney, NSW 2010, Australia.
| |
Collapse
|
18
|
Spillner A, Nguyen BT, Moulton V. Computing phylogenetic diversity for split systems. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2008; 5:235-244. [PMID: 18451432 DOI: 10.1109/tcbb.2007.70260] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/26/2023]
Abstract
In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size n. We show that for general split systems this problem is NP-hard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal O(n) time algorithm for phylogenetic trees and an O(n log n + nk) time algorithm for choosing an optimal subset of size k relative to a circular split system.
Collapse
Affiliation(s)
- Andreas Spillner
- School of Computer Sciences, University of East Anglia, Norwich, Uk.
| | | | | |
Collapse
|
19
|
Bordewich M, Semple C. Nature reserve selection problem: a tight approximation algorithm. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2008; 5:275-280. [PMID: 18451436 DOI: 10.1109/tcbb.2007.70252] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/26/2023]
Abstract
The Nature Reserve Selection Problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to conserve so that the phylogenetic diversity of the set of species contained within those regions is maximized. Recently, it was shown in a paper by Moulton et al. that this problem is NP-hard. In this paper, we establish a tight polynomial-time approximation algorithm for the Nature Reserve Section Problem. Furthermore, we resolve a question on the computational complexity of a related problem left open in Moulton et al.
Collapse
Affiliation(s)
- Magnus Bordewich
- Department of Computer Science, University of Durham, Durham, UK
| | | |
Collapse
|
20
|
Redding DW, Hartmann K, Mimoto A, Bokal D, DeVos M, Mooers AØ. Evolutionarily distinctive species often capture more phylogenetic diversity than expected. J Theor Biol 2008; 251:606-15. [DOI: 10.1016/j.jtbi.2007.12.006] [Citation(s) in RCA: 92] [Impact Index Per Article: 5.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/28/2007] [Revised: 11/26/2007] [Accepted: 12/11/2007] [Indexed: 11/28/2022]
|
21
|
Faller B, Pardi F, Steel M. Distribution of phylogenetic diversity under random extinction. J Theor Biol 2007; 251:286-96. [PMID: 18199459 DOI: 10.1016/j.jtbi.2007.11.034] [Citation(s) in RCA: 22] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/02/2007] [Revised: 11/26/2007] [Accepted: 11/29/2007] [Indexed: 11/19/2022]
Abstract
Phylogenetic diversity is a measure for describing how much of an evolutionary tree is spanned by a subset of species. If one applies this to the unknown subset of current species that will still be present at some future time, then this 'future phylogenetic diversity' provides a measure of the impact of various extinction scenarios in biodiversity conservation. In this paper, we study the distribution of future phylogenetic diversity under a simple model of extinction (a generalized 'field of bullets' model). We show that the distribution of future phylogenetic diversity converges to a normal distribution as the number of species grows, under mild conditions, which are necessary. We also describe an algorithm to compute the distribution efficiently, provided the edge lengths are integral, and briefly outline the significance of our findings for biodiversity conservation.
Collapse
Affiliation(s)
- Beáta Faller
- Department of Mathematics and Statistics, Biomathematics Research Centre, University of Canterbury, Christchurch, New Zealand.
| | | | | |
Collapse
|