• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    On approximation of optimizing phylogenetic diversity for cluster systems

    Thumbnail
    View/Open
    fallar_semple_steel_ucdms2009-1_report.pdf (780.5Kb)
    Author
    Faller, Beáta
    Semple, Charles
    Steel, M. A.
    Date
    2009
    Permanent Link
    http://hdl.handle.net/10092/12533

    A basic question in conservation biology is how to maximize future biodiversity as species face extinction. One way to approach this question is by measuring the diversity of a set of species in terms of the evolutionary history that those species span in a phylogenetic tree. Maximizing the resulting 'phylogenetic diversity' (PD) is one prominent selection criteria for deciding which species to conserve. The basic PD optimization problem aims to find a k-element subset of a given species set that has maximum PD among all such subsets. In this paper, we consider a generalization of this problem, which arises in situations where we do not know the true tree, or where evolution is not tree-like. We show that a greedy algorithm gives a (1-e⁻¹)-approximation to the general PD optimization problem, and that there is no polynomial-time algorithm that achieves a better approximation ratio unless P=NP.

    Subjects
    Field of Research::01 - Mathematical Sciences::0102 - Applied Mathematics::010202 - Biological Mathematics
    Collections
    • Engineering: Reports [695]
    Rights
    https://canterbury.libguides.com/rights/theses

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us