Differentially mutated subnetworks discovery
Abstract Problem We study the problem of identifying differentially mutated subnetworks of a large gene–gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem an...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-03-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13015-019-0146-7 |
| _version_ | 1818281678878015488 |
|---|---|
| author | Morteza Chalabi Hajkarim Eli Upfal Fabio Vandin |
| author_facet | Morteza Chalabi Hajkarim Eli Upfal Fabio Vandin |
| author_sort | Morteza Chalabi Hajkarim |
| collection | DOAJ |
| description | Abstract Problem We study the problem of identifying differentially mutated subnetworks of a large gene–gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem and show that the problem is NP-hard. Algorithm We propose a novel and efficient algorithm, called DAMOKLE, to identify differentially mutated subnetworks given genome-wide mutation data for two sets of cancer samples. We prove that DAMOKLE identifies subnetworks with statistically significant difference in mutation frequency when the data comes from a reasonable generative model, provided enough samples are available. Experimental results We test DAMOKLE on simulated and real data, showing that DAMOKLE does indeed find subnetworks with significant differences in mutation frequency and that it provides novel insights into the molecular mechanisms of the disease not revealed by standard methods. |
| first_indexed | 2024-12-13T00:08:57Z |
| format | Article |
| id | doaj.art-821d957a84d6460388d72201b1d53d8a |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-12-13T00:08:57Z |
| publishDate | 2019-03-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-821d957a84d6460388d72201b1d53d8a2022-12-22T00:06:06ZengBMCAlgorithms for Molecular Biology1748-71882019-03-0114111110.1186/s13015-019-0146-7Differentially mutated subnetworks discoveryMorteza Chalabi Hajkarim0Eli Upfal1Fabio Vandin2Biotech Research and Innovation Centre, University of CopenhagenDepartment of Computer Science, Brown UniversityDepartment of Information Engineering, University of PadovaAbstract Problem We study the problem of identifying differentially mutated subnetworks of a large gene–gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem and show that the problem is NP-hard. Algorithm We propose a novel and efficient algorithm, called DAMOKLE, to identify differentially mutated subnetworks given genome-wide mutation data for two sets of cancer samples. We prove that DAMOKLE identifies subnetworks with statistically significant difference in mutation frequency when the data comes from a reasonable generative model, provided enough samples are available. Experimental results We test DAMOKLE on simulated and real data, showing that DAMOKLE does indeed find subnetworks with significant differences in mutation frequency and that it provides novel insights into the molecular mechanisms of the disease not revealed by standard methods.http://link.springer.com/article/10.1186/s13015-019-0146-7Network analysisSomatic mutationsDifferential analysis |
| spellingShingle | Morteza Chalabi Hajkarim Eli Upfal Fabio Vandin Differentially mutated subnetworks discovery Algorithms for Molecular Biology Network analysis Somatic mutations Differential analysis |
| title | Differentially mutated subnetworks discovery |
| title_full | Differentially mutated subnetworks discovery |
| title_fullStr | Differentially mutated subnetworks discovery |
| title_full_unstemmed | Differentially mutated subnetworks discovery |
| title_short | Differentially mutated subnetworks discovery |
| title_sort | differentially mutated subnetworks discovery |
| topic | Network analysis Somatic mutations Differential analysis |
| url | http://link.springer.com/article/10.1186/s13015-019-0146-7 |
| work_keys_str_mv | AT mortezachalabihajkarim differentiallymutatedsubnetworksdiscovery AT eliupfal differentiallymutatedsubnetworksdiscovery AT fabiovandin differentiallymutatedsubnetworksdiscovery |