Appendix

Table 3 Objective function and constraints of taxon selection problems for the pheasant example

Maximize

l1 y1 +¼+ l20 y20

(1)

Subject to

Size constraint:

xPB + xPC + xPE + xPG + xPI + xPM + xGG + xGL + xGS + xGV £ k

(2)

Binary constraints:

xi ∈{0,1}∀ taxon i

(3)

ys Î{0,1} "s = 1,..,20

(4)

Split constraints:

yixi∀ taxon i

(5)

y11 £ xPB + xPC

y11 £ xPE + xPG + xPI + xPM + xGG + xGL + xGS + xGV

y12 £ xPB + xPC + xPI

y12 £ xPE + xPG + xPM + xGG + xGL + xGS + xGV

y13 £ xPB + xPC + xPG + xPI

y13 £ xPE + xPM + xGG + xGL + xGS + xGV

y14 £ xPB + xPC + xPG + xPI + xPM

y14 £ xPE + xGG + xGL + xGS + xGV

y15 £ xPB + xPC + xPE + xPG + xPI

y15 £ xPM + xGG + xGL + xGS + xGV

y16 £ xPB + xPC + xPE + xPG + xPI + xPM

y16 £ xGG + xGL + xGS + xGV

y17 £ xPB + xPC + xPE + xPG + xPI + xPM + xGS

y17 £ xGG + xGL + xGV

y18 £ xPB + xPC + xPE + xPG + xPI + xPM + xGG + xGS

y18 £ xGL + xGV

y19 £ xPB + xPC + xPE + xPG + xPI + xPM + xGV

y19 £ xGG + xGL + xGS

y20 £ xPB + xPC + xPE + xPG + xPI + xPM + xGL + xGV

y20 £ xGG + xGS

(continued)

Table 3 (continued)

Budget constraint:

cPB xPB + cPC xPC +¼+ cGV xGV £ B

(6)

Viability constraints:

xPB £ xPE

(7)

xPC £ xGG + xGV

xPG £ xPB

xPI £ xGL

xPM £ xPC + xGL

xGL £ xPB

xGS £ xPM + xPG

xGV £ xGG + xPE

Table 4 Objective function and constraints of reserve selection problems for the pheasant example. Due to the fact that G. gallus is contained in all but one area there are many area-split constraints of the form ys £ zBT + zID + zIN + zLK + zPH + zMY + zTH + zVN . Such constraints are redundant since k ≥ 2, and thus omitted

Maximize

l1 y1 +¼+ l20 y20

(1)

Subject to

Size constraint:

zID + zLK + zBT + zIN + zPH + zMY + zTH + zVN £ k

(8)

Binary constraints:

zr ∈{0,1}∀ area r

(9)

ys Î{0,1} "s = 1,..,20

(4)

Area-split constraints:

y1 £ zBT + zTH

(10)

y2 £ zID

y3 £ zPH

y4 £ zVN

y5 £ zMY

y6 £ zMY

y7 £ zBT + zID + zIN + zPH + zMY + zTH + zVN

y8 £ zLK

y9 £ zIN

y10 £ zID

y11 £ zBT + zID + zTH

y12 £ zBT + zID + zMY + zTH

y13 £ zBT + zID + zMY + zTH + zVN

y14 £ zBT + zID + zMY + zTH + zVN

y15 £ zBT + zID + zPH + zMY + zTH + zVN

y16 £ zBT + zID + zPH + zMY + zTH + zVN

y17 £ zBT + zID + zIN + zPH + zMY + zTH + zVN

y18 £ zBT + zID + zIN + zPH + zMY + zTH + zVN

y18 £ zID + zLK

y19 £ zBT + zID + zPH + zMY + zTH + zVN

y20 £ zBT + zID + zLK + zPH + zMY + zTH + zVN

y20 £ zBT + zID + zIN + zPH + zMY + zTH + zVN

Budget constraint:

cID zID + cLK zLK +¼+ cVN zVN £ B

(11)

References

Ball IR, Possingham HP, Watts M (2009) Marxan and relatives: software for spatial conservation prioritisation. In: Moilanen A, Wilson KA, Possingham HP (eds) Spatial conservation prioritisation: quantitative methods and computational tools. Oxford University Press, New York, pp 185–195

Bandelt HJ, Dress AWM (1992a) A canonical decomposition-theory for metrics on a finite-set.

Adv Math 92:47–105 Bandelt HJ, Dress AWM (1992b) Split decomposition: a new and useful approach to phylogenetic

analysis of distance data. Mol Phylogenet Evol 1:242–252

Billionnet A (2013) Solution of the generalized Noah's Ark problem. Syst Biol 62:147–156 Bordewich M, Semple C (2008) Nature reserve selection problem: a tight approximation algo-

rithm. IEEE/ACM Trans Comput Biol Bioinform 5:275–280 Bordewich M, Rodrigo AG, Semple C (2008) Selecting taxa to save or sequence: desirable criteria

and a greedy solution. Syst Biol 57:825–834

Bordewich M, Semple C, Spillner A (2009) Optimizing phylogenetic diversity across two trees.

Appl Math Lett 22:638–641

Bottrill MC, Joseph LN, Carwardine J, Bode M, Cook C, Game ET, Grantham H, Kark S, Linke S, McDonald-Madden E, Pressey RL, Walker S, Wilson KA, Possingham HP (2008) Is conservation triage just smart decision making? Trends Ecol Evol 23:649–654

Bryant D, Moulton V (2004) Neighbor-net: an agglomerative method for the construction of phylogenetic networks. Mol Biol Evol 21:255–265

Chernomor O, Minh BQ, Forest F, Klaere S, Ingram T, Henzinger M, von Haeseler A (2015) Split diversity in constrained conservation prioritization using integer programming. Methods Ecol Evol 6:83–91

Church RL, Stoms DM, Davis FW (1996) Reserve selection as a maximal covering location problem. Biol Conserv 76:105–112

Cocks KD, Baird IA (1989) Using mathematical-programming to address the multiple reserve selection problem – an example from the Eyre Peninsula, South-Australia. Biol Conserv 49:113–130

CPLEX (2012) IBM ILOG CPLEX optimizer

Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem.

J Oper Res Soc Am 2:393–410

Faith DP (1992) Conservation evaluation and phylogenetic diversity. Biol Conserv 61:1–10

Faith DP, Reid CAM, Hunter J (2004) Integrating phylogenetic diversity, complementarity, and endemism for conservation assessment. Conserv Biol 18:255–261

Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull Am Math Soc 64:275–278

Gurobi Optimization Inc (2013) Gurobi optimizer reference manual

Hartmann K, Steel M (2006) Maximizing phylogenetic diversity in biodiversity conservation: greedy solutions to the Noah's Ark problem. Syst Biol 55:644–651

Hickey G, Carmi P, Maheshwari A, Zeh N (2008) NAPX: a polynomial time approximation scheme for the Noah's Ark problem. Algoritm Bioinforma Wabi 5251:76–86

Huson DH, Bryant D (2006) Application of phylogenetic networks in evolutionary studies. Mol

Biol Evol 23:254–267

Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, Cambridge

Jermiin LS, Jayaswal V, Ababneh F, Robinson J (2008) Phylogenetic model evaluation. In: Keith (ed) Bioinformatics: data, sequences analysis and evolution. Humana Press, Totowa, pp 331–363

Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (2010) 50 years of integer programming 1958–2008: from the early years to the state-ofthe-art. Springer, Heidelberg

Kembel SW, Cowan PD, Helmus MR, Cornwell WK, Morlon H, Ackerly DD, Blomberg SP, Webb CO (2010) Picante: R tools for integrating phylogenies and ecology. Bioinformatics 26:1463–1464

Kimball RT, Braun EL (2008) A multigene phylogeny of Galliformes supports a single origin of erectile ability in non-feathered facial traits. J Avian Biol 39:438–445

Kirkpatrick JB (1983) An iterative method for establishing priorities for the selection of nature reserves: an example from Tasmania. Biol Conserv 25:127–134

May RM (1990) Taxonomy as destiny. Nature 347:129–130

Minh BQ, Klaere S, von Haeseler A (2006) Phylogenetic diversity within seconds. Syst Biol 55:769–773

Minh BQ, Klaere S, von Haeseler A (2009a) Taxon selection under split diversity. Syst Biol 58:586–594

Minh BQ, Pardi F, Klaere S, von Haeseler A (2009b) Budgeted phylogenetic diversity on circular split systems. IEEE/ACM Trans Comput Biol Bioinform 6:22–29

Minh BQ, Klaere S, von Haeseler A (2010) SDA*: a simple and unifying solution to recent bioinformatic challenges for conservation genetics. In: Pham SB, Hoang TH, McKay B, Hirota K (eds) The second international conference on knowledge and systems engineering. IEEE Computer Society, Hanoi, pp 33–37

Minh BQ, Nguyen MAT, von Haeseler A (2013) Ultrafast approximation for phylogenetic bootstrap. Mol Biol Evol 30:1188–1195

Moilanen A, Kujala H, Leathwick JR (2009) The zonation framework and software for conservation prioritization. In: Moilanen A, Wilson KA, Possingham HP (eds) Spatial conservation prioritization: quantitative methods and computational tools. Oxford University Press, New York

Moulton V, Semple C, Steel M (2007) Optimizing phylogenetic diversity under constraints.

J Theor Biol 246:186–194

Pardi F, Goldman N (2005) Species choice for comparative genomics: being greedy works. PLoS

Genet 1:e71

Pardi F, Goldman N (2007) Resource-aware taxon selection for maximizing phylogenetic diversity. Syst Biol 56:431–444

Possingham HP, Ball IR, Andelman S (2000) Mathematical methods for identifying representative reserve networks. In: Ferson S, Burgman M (eds) Quantitative methods for conservation biology. Springer, New York, pp 291–305

Pressey RL, Possingham HP, Day JR (1997) Effectiveness of alternative heuristic algorithms for identifying indicative minimum requirements for conservation reserves. Biol Conserv 80:207–219

Rodrigues ASL, Gaston KJ (2002) Maximising phylogenetic diversity in the selection of networks of conservation areas. Biol Conserv 105:103–111

Rodrigues ASL, Brooks TM, Gaston KJ (2005) Integrating phylogenetic diversity in the selection of priority areas for conservation: does it make a difference? In: Purvis A, Gittleman JL, Brooks T (eds) Phylogeny and conservation. Cambridge University Press, Cambridge, pp 101–119

Spillner A, Nguyen BT, Moulton V (2008) Computing phylogenetic diversity for split systems.

IEEE/ACM Trans Comput Biol Bioinform 5:235–244

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

Underhill LG (1994) Optimal and suboptimal reserve selection algorithms. Biol Conserv 70:85–87

van der Heide CM, van den Bergh JCJM, van Ierland EC (2005) Extending Weitzman's economic ranking of biodiversity protection: combining ecological and genetic considerations. Ecol Econ 55:218–223

Vane-Wright RI, Humphries CJ, Williams PH (1991) What to protect – systematics and the agony of choice. Biol Conserv 55:235–254

Volkmann L, Martyn I, Moulton V, Spillner A, Mooers AO (2014) Prioritizing populations for conservation using phylogenetic networks. PLoS One 9:e88945

Wang N, Kimball RT, Braun EL, Liang B, Zhang ZW (2013) Assessing phylogenetic relationships among Galliformes: a multigene phylogeny with expanded taxon sampling in Phasianidae. PLoS One 8:e64312

Webb CO, Ackerly DD, Kembel SW (2008) Phylocom: software for the analysis of phylogenetic community structure and trait evolution. Bioinformatics 24:2098–2100

Weitzman ML (1992) On diversity. Q J Econ 107:363–405

Weitzman ML (1998) The Noah's Ark problem. Econometrica 66:1279–1298

Witting L, Loeschcke V (1995) The optimization of biodiversity conservation. Biol Conserv 71:205–207

Witting L, Tomiuk J, Loeschcke V (2000) Modelling the optimal conservation of interacting species. Ecol Model 125:123–143

Wolsey LA (1998) Integer programming. Wiley-Interscience, New York

 
< Prev   CONTENTS   Next >