{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:27:56Z","timestamp":1773275276201,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1201,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: As an increasing number of genome-wide association studies reveal the limitations of the attempt to explain phenotypic heritability by single genetic loci, there is a recent focus on associating complex phenotypes with sets of genetic loci. Although several methods for multi-locus mapping have been proposed, it is often unclear how to relate the detected loci to the growing knowledge about gene pathways and networks. The few methods that take biological pathways or networks into account are either restricted to investigating a limited number of predetermined sets of loci or do not scale to genome-wide settings.<\/jats:p><jats:p>Results: We present SConES, a new efficient method to discover sets of genetic loci that are maximally associated with a phenotype while being connected in an underlying network. Our approach is based on a minimum cut reformulation of the problem of selecting features under sparsity and connectivity constraints, which can be solved exactly and rapidly.<\/jats:p><jats:p>SConES outperforms state-of-the-art competitors in terms of runtime, scales to hundreds of thousands of genetic loci and exhibits higher power in detecting causal SNPs in simulation studies than other methods. On flowering time phenotypes and genotypes from Arabidopsis thaliana, SConES detects loci that enable accurate phenotype prediction and that are supported by the literature.<\/jats:p><jats:p>Availability: Code is available at http:\/\/webdav.tuebingen.mpg.de\/u\/karsten\/Forschung\/scones\/.<\/jats:p><jats:p>Contact: \u00a0chloe-agathe.azencott@tuebingen.mpg.de<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt238","type":"journal-article","created":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T05:33:26Z","timestamp":1372311206000},"page":"i171-i179","source":"Crossref","is-referenced-by-count":48,"title":["Efficient network-guided multi-locus association mapping with graph cuts"],"prefix":"10.1093","volume":"29","author":[{"given":"Chlo\u00e9-Agathe","family":"Azencott","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Grimm","sequence":"additional","affiliation":[]},{"given":"Mahito","family":"Sugiyama","sequence":"additional","affiliation":[]},{"given":"Yoshinobu","family":"Kawahara","sequence":"additional","affiliation":[]},{"given":"Karsten M.","family":"Borgwardt","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"key":"2023062614293365900_btt238-B1","first-page":"726","volume-title":"Two-Locus Association Mapping In Subquadratic Time. KDD \u201911","author":"Achlioptas","year":"2011"},{"key":"2023062614293365900_btt238-B2","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/7503.003.0009","article-title":"Learning on graph with Laplacian regularization","volume-title":"Advances in Neural Information Processing Systems 19","author":"Ando","year":"2007"},{"key":"2023062614293365900_btt238-B3","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1038\/nature08800","article-title":"Genome-wide association study of 107 phenotypes in Arabidopsis thaliana inbred lines","volume":"465","author":"Atwell","year":"2010","journal-title":"Nature"},{"key":"2023062614293365900_btt238-B4","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision","volume":"26","author":"Boykov","year":"2004","journal-title":"IEEE T. Pattern Anal."},{"key":"2023062614293365900_btt238-B5","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.ajhg.2009.11.017","article-title":"Prioritizing GWAS results: a review of statistical methods and recommendations for their application","volume":"86","author":"Cantor","year":"2010","journal-title":"Am. J. Hum. Genet."},{"key":"2023062614293365900_btt238-B6","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1111\/j.1469-1809.2010.00597.x","article-title":"Joint identification of multiple genetic variants via elastic-net variable selection in a genome-wide association analysis","volume":"74","author":"Cho","year":"2010","journal-title":"Ann. Hum. Genet."},{"key":"2023062614293365900_btt238-B7","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1038\/msb4100180","article-title":"Network-based classification of breast cancer metastasis","volume":"3","author":"Chuang","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023062614293365900_btt238-B8","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1038\/ejhg.2011.57","article-title":"Gene set analysis of SNP data: benefits, challenges, and future directions","volume":"19","author":"Fridley","year":"2011","journal-title":"Eur. J. Hum. Genet."},{"key":"2023062614293365900_btt238-B9","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach to the maximum-flow problem","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. ACM"},{"key":"2023062614293365900_btt238-B10","first-page":"63","article-title":"Measuring statistical dependence with Hilbert-Schmidt norms","volume-title":"Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 8-11, 2005, Proceedings. Lecture Notes in Computer Science 3734 Springer 2005. ALT","author":"Gretton","year":"2005"},{"key":"2023062614293365900_btt238-B11","doi-asserted-by":"crossref","first-page":"423","DOI":"10.2307\/2529430","article-title":"Best linear unbiased estimation and prediction under a selection model","volume":"31","author":"Henderson","year":"1975","journal-title":"Biometrics"},{"key":"2023062614293365900_btt238-B12","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1038\/ng.1042","article-title":"Genome-wide patterns of genetic variation in worldwide Arabidopsis thaliana accessions from the RegMap panel","volume":"44","author":"Horton","year":"2012","journal-title":"Nat. Genet."},{"key":"2023062614293365900_btt238-B13","first-page":"417","article-title":"Learning with Structured Sparsity","volume-title":"Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009","author":"Huang","year":"2009"},{"key":"2023062614293365900_btt238-B14","first-page":"433","article-title":"Group Lasso with Overlap and Graph Lasso","volume-title":"Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009","author":"Jacob","year":"2009"},{"key":"2023062614293365900_btt238-B15","first-page":"175","article-title":"Structural feature selection for connectivity network-based MCI diagnosis","volume-title":"Multimodal Brain Image Analysis, Volume 7509 of Lecture Notes in Computer Science","author":"Jie","year":"2012"},{"key":"2023062614293365900_btt238-B16","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1159\/000341885","article-title":"GLIDE: GPU-based linear regression for detection of epistasis","volume":"73","author":"Kam-Thong","year":"2012","journal-title":"Hum. Hered."},{"key":"2023062614293365900_btt238-B17","author":"Kuncheva","year":"2007"},{"key":"2023062614293365900_btt238-B18","first-page":"147","article-title":"Feature selection for graph-based image classifiers","volume-title":"Pattern Recognition and Image Analysis, Volume 3523 of Lecture Notes in Computer Science","author":"Le Saux","year":"2005"},{"key":"2023062614293365900_btt238-B19","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/(SICI)1520-6750(199610)43:7<985::AID-NAV4>3.0.CO;2-9","article-title":"Algorithms for the constrained maximum-weight connected graph problem","volume":"43","author":"Lee","year":"1996","journal-title":"Nav. Res. Logist."},{"key":"2023062614293365900_btt238-B20","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1093\/bioinformatics\/btn081","article-title":"Network-constrained regularization and variable selection for analysis of genomic data","volume":"24","author":"Li","year":"2008","journal-title":"Bioinformatics"},{"key":"2023062614293365900_btt238-B21","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1038\/nmeth.1681","article-title":"FaST linear mixed models for genome-wide association studies","volume":"8","author":"Lippert","year":"2011","journal-title":"Nat. Meth."},{"key":"2023062614293365900_btt238-B22","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1093\/biostatistics\/kxs034","article-title":"Incorporating group correlations in genome-wide association studies using smoothed group lasso","volume":"14","author":"Liu","year":"2012","journal-title":"Biostatistics"},{"key":"2023062614293365900_btt238-B23","author":"Mairal","year":"2011"},{"key":"2023062614293365900_btt238-B24","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1038\/nature08494","article-title":"Finding the missing heritability of complex diseases","volume":"461","author":"Manolio","year":"2009","journal-title":"Nature"},{"key":"2023062614293365900_btt238-B25","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1038\/ng1537","article-title":"Genome-wide strategies for detecting multiple loci that influence complex diseases","volume":"37","author":"Marchini","year":"2005","journal-title":"Nat. Genet."},{"key":"2023062614293365900_btt238-B26","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1198\/jasa.2009.tm08647","article-title":"P-values for high-dimensional regression","volume":"104","author":"Meinshausen","year":"2009","journal-title":"J. Am. Stat. Assoc."},{"key":"2023062614293365900_btt238-B27","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1093\/bioinformatics\/btm019","article-title":"Gene expression network analysis and applications to immunology","volume":"23","author":"Nacu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062614293365900_btt238-B28","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"2023062614293365900_btt238-B29","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1038\/ng1847","article-title":"Principal components analysis corrects for stratification in genome-wide association studies","volume":"38","author":"Price","year":"2006","journal-title":"Nat. Genet."},{"key":"2023062614293365900_btt238-B30","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1093\/bioinformatics\/bts669","article-title":"A lasso multi-marker mixed model for association mapping with population structure correction","volume":"29","author":"Rakitsch","year":"2012","journal-title":"Bioinformatics."},{"key":"2023062614293365900_btt238-B31","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1038\/ng.2314","article-title":"An efficient multi-locus mixed-model approach for genome-wide association studies in structured populations","volume":"44","author":"Segura","year":"2012","journal-title":"Nat. Genet."},{"key":"2023062614293365900_btt238-B32","first-page":"144","article-title":"Kernels and regularization on graphs","volume-title":"Learning Theory and Kernel Machines, Volume 2777 of Lecture Notes in Computer Science","author":"Smola","year":"2003"},{"key":"2023062614293365900_btt238-B33","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the lasso","volume":"58","author":"Tibshirani","year":"1994","journal-title":"J. R. Stat. Soc. Series B"},{"key":"2023062614293365900_btt238-B34","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-642-16345-6_16","article-title":"Graph classification methods in chemoinformatics","volume-title":"Handbook of Statistical Bioinformatics, Springer Handbooks of Computational Statistics","author":"Tsuda","year":"2011"},{"key":"2023062614293365900_btt238-B35","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/s13253-010-0046-2","article-title":"Identifying QTLs and epistasis in structured plant populations using adaptive mixed lasso","volume":"16","author":"Wang","year":"2011","journal-title":"J. Agric. Biol. Environ. Stat."},{"key":"2023062614293365900_btt238-B36","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.ajhg.2011.05.029","article-title":"Rare-variant association testing for sequencing data with the sequence kernel association test","volume":"89","author":"Wu","year":"2011","journal-title":"Am. J. Hum. Genet."},{"key":"2023062614293365900_btt238-B37","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1073\/pnas.1119675109","article-title":"The mystery of missing heritability: Genetic interactions create phantom heritability","volume":"109","author":"Zuk","year":"2012","journal-title":"Proc. Natl Acad. Sci. USA"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i171\/50703450\/bioinformatics_29_13_i171.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i171\/50703450\/bioinformatics_29_13_i171.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T02:35:34Z","timestamp":1715567734000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/13\/i171\/198210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,19]]},"references-count":37,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt238","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2013,7]]},"published":{"date-parts":[[2013,6,19]]}}}