| A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations. | |
| | |
MedLine Citation:
|
PMID: 20976188 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
Therapies consisting of a combination of agents are an attractive proposition, especially in the context of diseases such as cancer, which can manifest with a variety of tumor types in a single case. However uncovering usable drug combinations is expensive both financially and temporally. By employing computational methods to identify candidate combinations with a greater likelihood of success we can avoid these problems, even when the amount of data is prohibitively large. Hitting Set is a combinatorial problem that has useful application across many fields, however as it is NP-complete it is traditionally considered hard to solve exactly. We introduce a more general version of the problem (α,β,d)-Hitting Set, which allows more precise control over how and what the hitting set targets. Employing the framework of Parameterized Complexity we show that despite being NP-complete, the (α,β,d)-Hitting Set problem is fixed-parameter tractable with a kernel of size O(αdk(d)) when we parameterize by the size k of the hitting set and the maximum number α of the minimum number of hits, and taking the maximum degree d of the target sets as a constant. We demonstrate the application of this problem to multiple drug selection for cancer therapy, showing the flexibility of the problem in tailoring such drug sets. The fixed-parameter tractability result indicates that for low values of the parameters the problem can be solved quickly using exact methods. We also demonstrate that the problem is indeed practical, with computation times on the order of 5 seconds, as compared to previous Hitting Set applications using the same dataset which exhibited times on the order of 1 day, even with relatively relaxed notions for what constitutes a low value for the parameters. Furthermore the existence of a kernelization for (α,β,d)-Hitting Set indicates that the problem is readily scalable to large datasets. |
| | |
Authors:
|
Drew Mellor; Elena Prieto; Luke Mathieson; Pablo Moscato |
Related Documents
:
|
9810678 - A neural network solution to the transverse patterning problem depends on repetition of... 12513268 - Exact asymptotic results for persistence in the sinai model with arbitrary drift. 18055948 - Computer-aided psychotherapy: revolution or bubble? 2064288 - The diagnosis of acute abdominal pain with computer assistance: worldwide perspective. 21329578 - Alcohol controls and violence in nunavut: a comparison of wet and dry communities. 3094258 - The multiple trauma victim: a nutritional cripple. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't Date: 2010-10-18 |
Journal Detail:
|
Title: PloS one Volume: 5 ISSN: 1932-6203 ISO Abbreviation: PLoS ONE Publication Date: 2010 |
Date Detail:
|
Created Date: 2010-10-26 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101285081 Medline TA: PLoS One Country: United States |
Other Details:
|
Languages: eng Pagination: e13055 Citation Subset: IM |
Affiliation:
|
Centre for Bioinformatics, Biomarker Discovery and Information Based Medicine, The University of Newcastle, Newcastle, Australia. |
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: Uniform silica coated fluorescent nanoparticles: synthetic method, improved light stability and appl...
Next Document: prox1b Activity is essential in zebrafish lymphangiogenesis.