A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.

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 employi...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Drew Mellor, Elena Prieto, Luke Mathieson, Pablo Moscato
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2010
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/2d779693c0f64a8d8317e2ca57508d5e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:2d779693c0f64a8d8317e2ca57508d5e
record_format	dspace
spelling	oai:doaj.org-article:2d779693c0f64a8d8317e2ca57508d5e2021-11-18T07:03:10ZA kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.1932-620310.1371/journal.pone.0013055https://doaj.org/article/2d779693c0f64a8d8317e2ca57508d5e2010-10-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/20976188/?tool=EBIhttps://doaj.org/toc/1932-6203Therapies 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.Drew MellorElena PrietoLuke MathiesonPablo MoscatoPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 5, Iss 10, p e13055 (2010)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Drew Mellor Elena Prieto Luke Mathieson Pablo Moscato A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
description	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.
format	article
author	Drew Mellor Elena Prieto Luke Mathieson Pablo Moscato
author_facet	Drew Mellor Elena Prieto Luke Mathieson Pablo Moscato
author_sort	Drew Mellor
title	A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
title_short	A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
title_full	A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
title_fullStr	A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
title_full_unstemmed	A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.
title_sort	kernelisation approach for multiple d-hitting set and its application in optimal multi-drug therapeutic combinations.
publisher	Public Library of Science (PLoS)
publishDate	2010
url	https://doaj.org/article/2d779693c0f64a8d8317e2ca57508d5e
work_keys_str_mv	AT drewmellor akernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT elenaprieto akernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT lukemathieson akernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT pablomoscato akernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT drewmellor kernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT elenaprieto kernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT lukemathieson kernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations AT pablomoscato kernelisationapproachformultipledhittingsetanditsapplicationinoptimalmultidrugtherapeuticcombinations
_version_	1718423969202176000

A kernelisation approach for multiple d-Hitting Set and its application in optimal multi-drug therapeutic combinations.

Ejemplares similares