| An approximation algorithm for the Noah's Ark problem with random feature loss. | |
| | |
MedLine Citation:
|
PMID: 20479502 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Glenn Hickey; Mathieu Blanchette; Paz Carmi; Anil Maheshwari; Norbert Zeh |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 8 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2011 Mar-Apr |
Date Detail:
|
Created Date: 2011-02-04 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 551-6 Citation Subset: IM |
Affiliation:
|
School of Computer Science,McGill University, 3480 University Street, McConnell Engineering Building, Room 318, Montreal, QC H3A 2A7, Canada. hickey@mcb.mcgill.ca |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Multistage gene normalization and SVM-based ranking for protein interactor extraction in full-text a...
Next Document: Fast kernel discriminant analysis for classification of liver cancer mass spectra.