{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:44:30Z","timestamp":1753875870183,"version":"3.41.2"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ontario Research Fund","award":["34876"],"award-info":[{"award-number":["34876"]}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Many real-world problems can be modeled as annotated graphs. Scalable graph algorithms that extract actionable information from such data are in demand since these graphs are large, varying in topology, and have diverse node\/edge annotations. When these graphs change over time they create dynamic graphs, and open the possibility to find patterns across different time points. In this article, we introduce a scalable algorithm that finds unique dense regions across time points in dynamic graphs. Such algorithms have applications in many different areas, including the biological, financial, and social domains.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>There are three important contributions to this manuscript. First, we designed a scalable algorithm, USNAP, to effectively identify dense subgraphs that are unique to a time stamp given a dynamic graph. Importantly, USNAP provides a lower bound of the density measure in each step of the greedy algorithm. Second, insights and understanding obtained from validating USNAP on real data show its effectiveness. While USNAP is domain independent, we applied it to four non-small cell lung cancer gene expression datasets. Stages in non-small cell lung cancer were modeled as dynamic graphs, and input to USNAP. Pathway enrichment analyses and comprehensive interpretations from literature show that USNAP identified biologically relevant mechanisms for different stages of cancer progression. Third, USNAP is scalable, and has a time complexity of O(m+mc\u2009log\u2009nc+nc\u2009log\u2009nc), where m is the number of edges, and n is the number of vertices in the dynamic graph; mc is the number of edges, and nc is the number of vertices in the collapsed graph.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The code of USNAP is available at https:\/\/www.cs.utoronto.ca\/\u223cjuris\/data\/USNAP22.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad477","type":"journal-article","created":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T16:23:35Z","timestamp":1690907015000},"source":"Crossref","is-referenced-by-count":0,"title":["<i>USNAP<\/i>: fast unique dense region detection and its application to lung cancer"],"prefix":"10.1093","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8294-4846","authenticated-orcid":false,"given":"Serene W H","family":"Wong","sequence":"first","affiliation":[{"name":"Osteoarthritis Research Program, Division of Orthopedic Surgery, Schroeder Arthritis Institute, and Data Science Discovery Centre for Chronic Diseases, Krembil Research Institute, University Health Network, 60 Leonard Avenue , Toronto, ON M5T 0S8, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1934-7472","authenticated-orcid":false,"given":"Chiara","family":"Pastrello","sequence":"additional","affiliation":[{"name":"Osteoarthritis Research Program, Division of Orthopedic Surgery, Schroeder Arthritis Institute, and Data Science Discovery Centre for Chronic Diseases, Krembil Research Institute, University Health Network, 60 Leonard Avenue , Toronto, ON M5T 0S8, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1111-8667","authenticated-orcid":false,"given":"Max","family":"Kotlyar","sequence":"additional","affiliation":[{"name":"Osteoarthritis Research Program, Division of Orthopedic Surgery, Schroeder Arthritis Institute, and Data Science Discovery Centre for Chronic Diseases, Krembil Research Institute, University Health Network, 60 Leonard Avenue , Toronto, ON M5T 0S8, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Carnegie Mellon University , 5000 Forbes Avenue, Pittsburgh, PA 15213, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Jurisica","sequence":"additional","affiliation":[{"name":"Osteoarthritis Research Program, Division of Orthopedic Surgery, Schroeder Arthritis Institute, and Data Science Discovery Centre for Chronic Diseases, Krembil Research Institute, University Health Network, 60 Leonard Avenue , Toronto, ON M5T 0S8, Canada"},{"name":"Department of Computer Science, University of Toronto , 40 St. George Street, Room 4283, Toronto, ON, M5S 2E4, Canada"},{"name":"Department of Medical Biophysics, University of Toronto, Princess Margaret Cancer Research Tower, MaRS Centre , 101 College Street, Room 15-701, Toronto, ON, M5G 1L7, Canada"},{"name":"Institute of Neuroimmunology, Slovak Academy of Sciences , vvi, Dubravsk\u00e1 cesta 9, 845 10 Bratislava 45, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,8,1]]},"reference":[{"key":"2024052216112739000_btad477-B1","first-page":"417","article-title":"Condensing temporal networks using propagation","author":"Adhikari","year":"2017"},{"key":"2024052216112739000_btad477-B2","doi-asserted-by":"crossref","first-page":"e1002955","DOI":"10.1371\/journal.pcbi.1002955","article-title":"Dissection of regulatory networks that are altered in disease via differential co-expression","volume":"9","author":"Amar","year":"2013","journal-title":"PLoS Comput Biol"},{"key":"2024052216112739000_btad477-B3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1165\/rcmb.2006-0151OC","article-title":"Serotoninergic receptors on human airway epithelial cells","volume":"36","author":"Bayer","year":"2007","journal-title":"Am J Respir Cell Mol Biol"},{"key":"2024052216112739000_btad477-B4","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1109\/TKDE.2014.2349918","article-title":"HOCTracker: tracking the evolution of hierarchical and overlapping communities in dynamic social networks","volume":"27","author":"Bhat","year":"2015","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"2024052216112739000_btad477-B5","first-page":"57","article-title":"Ion channels in lung cancer","volume-title":"Reviews of Physiology, Biochemistry and Pharmacology","author":"Bulk","year":"2021"},{"key":"2024052216112739000_btad477-B6","doi-asserted-by":"crossref","first-page":"3095","DOI":"10.1038\/s41467-019-11058-3","article-title":"The nasal methylome as a biomarker of asthma and airway inflammation in children","volume":"10","author":"Cardenas","year":"2019","journal-title":"Nat Commun"},{"key":"2024052216112739000_btad477-B7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s10115-007-0117-z","article-title":"Discovering correlated spatio-temporal changes in evolving graphs","volume":"16","author":"Chan","year":"2008","journal-title":"Knowl Inf Syst"},{"first-page":"84","year":"2000","author":"Charikar","key":"2024052216112739000_btad477-B8"},{"key":"2024052216112739000_btad477-B9","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1002\/em.22087","article-title":"Mechanisms of DNA damage, repair, and mutagenesis","volume":"58","author":"Chatterjee","year":"2017","journal-title":"Environ Mol Mutagen"},{"key":"2024052216112739000_btad477-B10","doi-asserted-by":"crossref","first-page":"2477","DOI":"10.1016\/j.bbamem.2014.12.008","article-title":"Involvement of potassium channels in the progression of cancer to a more malignant phenotype","volume":"1848","author":"Comes","year":"2015","journal-title":"Biochim Biophys Acta"},{"key":"2024052216112739000_btad477-B11","first-page":"847","article-title":"Local community detection in dynamic networks","author":"DiTursi","year":"2017"},{"first-page":"300","year":"2015","author":"Epasto","key":"2024052216112739000_btad477-B12"},{"first-page":"1378","year":"2018","author":"Eswaran","key":"2024052216112739000_btad477-B13"},{"key":"2024052216112739000_btad477-B14","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.pharmthera.2018.10.002","article-title":"Acetylcholine signaling system in progression of lung cancers","volume":"194","author":"Friedman","year":"2019","journal-title":"Pharmacol Ther"},{"key":"2024052216112739000_btad477-B15","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1515\/hsz-2020-0157","article-title":"The role of mitochondrial ATP synthase in cancer","volume":"401","author":"Galber","year":"2020","journal-title":"Biol Chem"},{"first-page":"107","year":"2018","author":"Galimberti","key":"2024052216112739000_btad477-B16"},{"key":"2024052216112739000_btad477-B17","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.3389\/fphys.2019.01267","article-title":"Bitter taste receptors (TAS2Rs) in human lung macrophages: receptor expression and inhibitory effects of TAS2R agonists","volume":"10","author":"Grassin-Delyle","year":"2019","journal-title":"Front Physiol"},{"key":"2024052216112739000_btad477-B19","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1165\/ajrcmb.15.2.8703471","article-title":"Hox genes in the lung","volume":"15","author":"Kappen","year":"1996","journal-title":"Am J Respir Cell Mol Biol"},{"key":"2024052216112739000_btad477-B20","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1038\/jhg.2010.34","article-title":"A new association between polymorphisms of the SLC6A7 gene in the chromosome 5q31\u201332 region and asthma","volume":"55","author":"Kim","year":"2010","journal-title":"J Hum Genet"},{"key":"2024052216112739000_btad477-B21","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1186\/1471-2350-14-39","article-title":"Genome-wide methylation profiling of the bronchial mucosa of asthmatics: relationship to atopy","volume":"14","author":"Kim","year":"2013","journal-title":"BMC Med Genet"},{"key":"2024052216112739000_btad477-B22","doi-asserted-by":"crossref","first-page":"e594","DOI":"10.1016\/S2589-7500(20)30225-9","article-title":"A prognostic model for overall survival of patients with early-stage non-small cell lung cancer: a multicentre, retrospective study","volume":"2","author":"Lu","year":"2020","journal-title":"Lancet Digit Health"},{"key":"2024052216112739000_btad477-B23","doi-asserted-by":"crossref","first-page":"1290","DOI":"10.1093\/bioinformatics\/btr136","article-title":"COSINE: COndition-SpecIfic sub-NEtwork identification using a global optimization method","volume":"27","author":"Ma","year":"2011","journal-title":"Bioinformatics"},{"key":"2024052216112739000_btad477-B24","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TKDE.2019.2891604","article-title":"An efficient approach to finding dense temporal subgraphs","volume":"32","author":"Ma","year":"2019","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"2024052216112739000_btad477-B25","first-page":"5","article-title":"DNA repair in lung cancer: potential not yet reached","volume-title":"Lung Cancer Manag","author":"Mamdani","year":"2016"},{"key":"2024052216112739000_btad477-B26","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1038\/nature05670","article-title":"Quantifying social group evolution","volume":"446","author":"Palla","year":"2007","journal-title":"Nature"},{"key":"2024052216112739000_btad477-B27","doi-asserted-by":"crossref","first-page":"e0217037","DOI":"10.1371\/journal.pone.0217037","article-title":"Loss of parkin reduces lung tumor development by blocking p21 degradation","volume":"14","author":"Park","year":"2019","journal-title":"PLoS One"},{"first-page":"1130","year":"2019","author":"Qin","key":"2024052216112739000_btad477-B28"},{"key":"2024052216112739000_btad477-B29","first-page":"D479","article-title":"PathDIP 4: an extended pathway annotations and enrichment analysis resource for human, model organisms and domesticated species","volume":"48","author":"Rahmati","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2024052216112739000_btad477-B30","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1093\/carcin\/bgr307","article-title":"Asthma and lung cancer risk: a systematic investigation by the international lung cancer consortium","volume":"33","author":"Rosenberger","year":"2012","journal-title":"Carcinogenesis"},{"key":"2024052216112739000_btad477-B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3172867","article-title":"Community discovery in dynamic networks: a survey","volume":"51","author":"Rossetti","year":"2018","journal-title":"ACM Comput Surv"},{"key":"2024052216112739000_btad477-B32","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1080\/15384101.2018.1557487","article-title":"HIV-1 Nef promotes cell proliferation and microRNA dysregulation in lung cells","volume":"18","author":"Santerre","year":"2019","journal-title":"Cell Cycle"},{"key":"2024052216112739000_btad477-B33","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1007\/s10618-018-0602-x","article-title":"Finding lasting dense subgraphs","volume":"33","author":"Semertzidis","year":"2019","journal-title":"Data Min Knowl Disc"},{"first-page":"1055","year":"2015","author":"Shah","key":"2024052216112739000_btad477-B34"},{"first-page":"264","year":"2016","author":"Shin","key":"2024052216112739000_btad477-B35"},{"key":"2024052216112739000_btad477-B18","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1108\/eb026526","article-title":"A statistical interpretation of term specificity and its application in retrieval","volume":"28","author":"Sp\u00e4rck Jones","year":"1972","journal-title":"J Doc"},{"first-page":"687","year":"2007","author":"Sun","key":"2024052216112739000_btad477-B36"},{"key":"2024052216112739000_btad477-B37","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1186\/1471-2105-11-497","article-title":"DiffcoEx: a simple and sensitive method to find differentially coexpressed gene modules","volume":"11","author":"Tesson","year":"2010","journal-title":"BMC Bioinformatics"},{"first-page":"867","year":"2018","author":"Wong","key":"2024052216112739000_btad477-B38"},{"first-page":"2309","year":"2020","author":"Zhang","key":"2024052216112739000_btad477-B39"},{"key":"2024052216112739000_btad477-B40","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1186\/1479-5876-11-102","article-title":"Expression of gamma-aminobutyric acid receptors on neoplastic growth and prediction of prognosis in non-small cell lung cancer","volume":"11","author":"Zhang","year":"2013","journal-title":"J Transl Med"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad477\/51016582\/btad477.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/8\/btad477\/57828545\/btad477.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/8\/btad477\/57828545\/btad477.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T16:41:30Z","timestamp":1716396090000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad477\/7234611"}},"subtitle":[],"editor":[{"given":"Janet","family":"Kelso","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,8,1]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad477","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2023,8,1]]},"published":{"date-parts":[[2023,8,1]]},"article-number":"btad477"}}