The Prize-collecting Steiner Forest (PCSF) problem is NP-hard, requiring extreme computational effort to find exact solutions for large inputs. We introduce a new heuristic algorithm for PCSF which preserves the quality of solutions obtained by previous heuristic approaches while reducing the runtime by a factor of 10 for larger graphs. By decreasing the draw on computational resources, this algorithm affords systems biologists the opportunity to analyze larger biological networks faster and narrow their analyses to individual patients.
A fast prize-collecting steiner forest algorithm for functional analyses in biological networks / Akhmedov, Murodzhon; Lenail, Alexander; Bertoni, Francesco; Kwee, Ivo; Fraenkel, Ernest; Montemanni, Roberto. - (2017), pp. 263-276. (Intervento presentato al convegno CPAIOR 2017: Integration of AI and OR Techniques in Constraint Programming tenutosi a Padova nel June 2017) [10.1007/978-3-319-59776-8_22].
A fast prize-collecting steiner forest algorithm for functional analyses in biological networks
Montemanni Roberto
2017
Abstract
The Prize-collecting Steiner Forest (PCSF) problem is NP-hard, requiring extreme computational effort to find exact solutions for large inputs. We introduce a new heuristic algorithm for PCSF which preserves the quality of solutions obtained by previous heuristic approaches while reducing the runtime by a factor of 10 for larger graphs. By decreasing the draw on computational resources, this algorithm affords systems biologists the opportunity to analyze larger biological networks faster and narrow their analyses to individual patients.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
