Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

An exact algorithm for finding cancer driver somatic genome alterations: The weighted mutually exclusive maximum set cover problem

Lu, S and Mandava, G and Yan, G and Lu, X (2016) An exact algorithm for finding cancer driver somatic genome alterations: The weighted mutually exclusive maximum set cover problem. Algorithms for Molecular Biology, 11 (1).

[img]
Preview
PDF
Published Version
Available under License : See the attached license file.

Download (2MB)
[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)

Abstract

Background: The mutual exclusivity of somatic genome alterations (SGAs), such as somatic mutations and copy number alterations, is an important observation of tumors and is widely used to search for cancer signaling pathways or SGAs related to tumor development. However, one problem with current methods that use mutual exclusivity is that they are not signal-based; another problem is that they use heuristic algorithms to handle the NP-hard problems, which cannot guarantee to find the optimal solutions of their models. Method: In this study, we propose a novel signal-based method that utilizes the intrinsic relationship between SGAs on signaling pathways and expression changes of downstream genes regulated by pathways to identify cancer signaling pathways using the mutually exclusive property. We also present a relatively efficient exact algorithm that can guarantee to obtain the optimal solution of the new computational model. Results: We have applied our new model and exact algorithm to the breast cancer data. The results reveal that our new approach increases the capability of finding better solutions in the application of cancer research. Our new exact algorithm has a time complexity of O* (1.325m)(Note: Following the recent convention, we use a star * to represent that the polynomial part of the time complexity is neglected), which has solved the NP-hard problem of our model efficiently. Conclusion: Our new method and algorithm can discover the true causes behind the phenotypes, such as what SGA events lead to abnormality of the cell cycle or make the cell metastasis lose control in tumors; thus, it identifies the target candidates for precision (or target) therapeutics.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Lu, Ssongjian@pitt.eduSONGJIAN
Mandava, Ggum13@pitt.eduGUM13
Yan, Ggay7@pitt.eduGAY7
Lu, Xxinghua@pitt.eduXINGHUA
Date: 1 January 2016
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: Algorithms for Molecular Biology
Volume: 11
Number: 1
DOI or Unique Handle: 10.1186/s13015-016-0073-9
Institution: University of Pittsburgh
Schools and Programs: School of Medicine > Biomedical Informatics
Refereed: Yes
Date Deposited: 22 Jul 2016 18:37
Last Modified: 22 Jun 2021 11:55
URI: http://d-scholarship.pitt.edu/id/eprint/28672

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item