Skip Navigation

Systematic Biology 2005 54(4):527-529; doi:10.1080/10635150590947023
This Article
Right arrow Full Text Freely available
Right arrow FREE Full Text (PDF) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (15)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Steel, M.
Right arrow Search for Related Content
PubMed
Right arrow Articles by Steel, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© 2005 Society of Systematic Biologists

Phylogenetic Diversity and the Greedy Algorithm

Mike Steel

Allan Wilson Centre for Molecular Ecology and Evolution, Biomathematics Research Centre, University of Canterbury Christchurch, New Zealand E-mail m.steel{at}math.canterbury.ac.nz

Edited by Dan Faith: Associate Editor


  Abstract

Given a phylogenetic tree with leaves labeled by a collection of species, and with weighted edges, the "phylogenetic diversity" of any subset of the species is the sum of the edge weights of the minimal subtree connecting the species. This measure is relevant in biodiversity conservation where one may wish to compare different subsets of species according to how much evolutionary variation they encompass. In this note we show that phylogenetic diversity has an attractive mathematical property that ensures that we can solve the following problem easily by the greedy algorithm: find a subset of the species of any given size k of maximal phylogenetic diversity. We also describe an extension of this result that also allows weights to be assigned to species

Keywords: Biodiversity conservation; greedy algorithm; phylogenetic diversity

Received June 10, 2004; Revised October 2, 2004; Accepted October 2, 2004
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Syst BiolHome page
B. Q. Minh, S. Klaere, and A. von Haeseler
Taxon Selection under Split Diversity
Syst Biol, December 1, 2009; 58(6): 586 - 594.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
M. Bordewich, A. G. Rodrigo, and C. Semple
Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution
Syst Biol, December 1, 2008; 57(6): 825 - 834.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
D. P. Faith
Phylogeny and Conservation
Syst Biol, August 1, 2007; 56(4): 690 - 694.
[Full Text] [PDF]

Home page
 Syst BiolHome page
F. Pardi and N. Goldman
Resource-Aware Taxon Selection for Maximizing Phylogenetic Diversity
Syst Biol, June 1, 2007; 56(3): 431 - 444.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
B. Q. Minh, S. Klaere, and A. von Haeseler
Phylogenetic Diversity within Seconds
Syst Biol, October 1, 2006; 55(5): 769 - 773.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
K. Hartmann and M. Steel
Maximizing Phylogenetic Diversity in Biodiversity Conservation: Greedy Solutions to the Noah's Ark Problem
Syst Biol, August 1, 2006; 55(4): 644 - 651.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
L. A. Lewis and P. O. Lewis
Unearthing the Molecular Phylodiversity of Desert Soil Green Algae (Chlorophyta)
Syst Biol, December 1, 2005; 54(6): 936 - 947.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.