<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Optimizing Phylogenetic Diversity with Ecological Constraints
Beáta Faller1, Charles Semple2, and Dominic Welsh2
1Institute of Mathematics, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary
2Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch 8140, New Zealand
3Merton College, University of Oxford, Merton Street, Oxford OX1 4JD, United Kingdom
Annals of Combinatorics 15 (2) pp.255-266 April, 2011
AMS Subject Classification: 05C05; 92D15
Given an edge-weighted tree T with leaf set X, define the weight of a subset S of X as the sum of the edge-weights of the minimal subtree of T connecting the elements in S. It is known that the problem of selecting subsets of X of a given size to maximize this weight can be solved using a greedy algorithm. This optimization problem arises in conservation biology where the weight is referred to as the phylogenetic diversity of a taxa set S. Here, we consider the extension of this problem whereby we are only interested in selecting subsets of the taxa set that are ecologically “viable”. Such subsets are specified by an acyclic digraph which represents, for example, a food web. This additional constraint makes the problem computationally hard. In this paper, we analyze the complexity of different variations of the
extended problem.
Keywords: phylogenetic tree, phylogenetic diversity, food web


1. Bordewich, M., Rodrigo, A.G., Semple, C.: Selecting taxa to save or sequence: desirable criteria and a greedy solution. Syst. Biol. 57(6), 825–834 (2008)

2. Bordewich, M., Semple, C.: Nature reserve selection problem: a tight approximation algorithm. IEEE/ACMTrans. Comput. Biol. Bioinformatics 5(2), 275–280 (2008)

3. Faith, D.P.: Conservation evaluation and phylogenetic diversity. Biol. Conserv. 61(1), 1–10 (1992)

4. Faith, D.P., Baker, A.M.: Phylogenetic diversity (PD) and biodiversity conservation: some bioinformatics challenges. Evol. Bioinf. Online 2, 121–128 (2006)

5. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

6. van der Heide, C.J., von den Bergh, C., van Ierland, E.C.: ExtendingWeitzman’s economic ranking of biodiversity protection: combining ecological and genetic considerations. Ecol. Econ. 55(2), 218–223 (2005)

7. Holland, B.R.: Evolutionary Analyses of Large Data Sets: Trees and Beyond. PhD thesis, Massey University, New Zealand (2001)

8. Magnanti, T.L.,Wolsey, L.A.: Optimal trees. In: Ball,M.O., et al. (eds.) NetworkModels, Handbook in Operations Research and Management Science, pp. 503–615. Amsterdam, North-Holland (1995)

9. Mohar, B.: Face covers and the genus problem for apex graphs. J. Combin. Theory Ser. B 82(1), 102–117 (2001)

10. Moulton, V., Semple, C., Steel, M.: Optimizing phylogenetic diversity under constraints. J. Theoret. Biol. 246(1), 186–194 (2007)

11. Pardi, F., Goldmann, N.: Species choice for comparative genomics: being greedy works. PLoS Genetics 1(6), #e71 (2005)

12. Robertson, N., Sanders, D., Seymour, P., Thomas, R.: A new proof of the four-colour theorem. Electron. Res. Announc. Amer. Math. Soc. 2(1), 17–25 (1996)

13. Rodrigues, A.S.L., Brooks, T.M., Gaston, K.J.: Integrating phylogenetic diversity in the selection of priority areas for conservation: does it make a difference? In: Purvis, A., Gittleman, J.L., Brooks, T., (eds.) Phylogeny and Conservation, pp. 101–119. Cambridge University Press, New York (2005)

14. Rodrigues, A.S.L., Gaston, K.J.: Maximising phylogenetic diversity in the selection of networks of conservation areas. Biol. Conserv. 105(1), 103–111 (2002)

15. Sarich, V.M., Wilson, A.C.: Immunological time scale for hominid evolution. Science 158(3805), 1200–1203 (1967)

16. Semple, C., Steel, M.: Phylogenetics. Oxford University Press, New York (2003)

17. Spillner, A., Nguyen, B.,Moulton, V.: Computing phylogenetic diversity for split systems. IEEE/ACMTrans. Comput. Biol. Bioinformatics 5(2), 235–244 (2008)

18. Steel, M.: Phylogenetic diversity and the greedy algorithm. Syst. Biol. 54(4), 527–529 (2005)

19. Tait, P.G.: On the colouring of maps. Proc. Roy. Soc. Edinburgh Sect. A 10, 501–503 (1880)

20. Whitfield, J.B., Lockhart, P.J.: Deciphering ancient rapid radiations. Trends Ecology & Evol. 22(5), 258–265 (2007)

21. Witting, L., Tomiuk, J., Loeschcke, V.: Modelling the optimal conservation of interacting species. Ecol. Modell. 125(2-3), 123–144 (2000)

22. Zuckerkandl, E., Pauling, L.B.: Molecular disease, evolution, and genetic heterogeneity. In: Kasha, M., Pullman, B., (eds.) Horizons in Biochemistry, pp. 189–225. Academic Press, New York (1962)