{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:01:09Z","timestamp":1774368069838,"version":"3.50.1"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Similarity-measure-based clustering is a crucial problem appearing throughout scientific data analysis. Recently, a powerful new algorithm called Affinity Propagation (AP) based on message-passing techniques was proposed by Frey and Dueck (2007a). In AP, each cluster is identified by a common exemplar all other data points of the same cluster refer to, and exemplars have to refer to themselves. Albeit its proved power, AP in its present form suffers from a number of drawbacks. The hard constraint of having exactly one exemplar per cluster restricts AP to classes of regularly shaped clusters, and leads to suboptimal performance, e.g. in analyzing gene expression data.<\/jats:p><jats:p>Results: This limitation can be overcome by relaxing the AP hard constraints. A new parameter controls the importance of the constraints compared to the aim of maximizing the overall similarity, and allows to interpolate between the simple case where each data point selects its closest neighbor as an exemplar and the original AP. The resulting soft-constraint affinity propagation (SCAP) becomes more informative, accurate and leads to more stable clustering. Even though a new a priori free parameter is introduced, the overall dependence of the algorithm on external tuning is reduced, as robustness is increased and an optimal strategy for parameter selection emerges more naturally. SCAP is tested on biological benchmark data, including in particular microarray data related to various cancer types. We show that the algorithm efficiently unveils the hierarchical cluster structure present in the data sets. Further on, it allows to extract sparse gene expression signatures for each cluster.<\/jats:p><jats:p>Contact: \u00a0leone@isi.it, sumedha@isi.it and weigt@isi.it<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm414","type":"journal-article","created":{"date-parts":[[2007,9,26]],"date-time":"2007-09-26T02:14:39Z","timestamp":1190772879000},"page":"2708-2715","source":"Crossref","is-referenced-by-count":100,"title":["Clustering by soft-constraint affinity propagation: applications to gene-expression data"],"prefix":"10.1093","volume":"23","author":[{"given":"Michele","family":"Leone","sequence":"first","affiliation":[{"name":"Institute for Scientific Interchange, Viale Settimio Severo 65, Villa Gualino, I-10133 Torino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Sumedha","sequence":"additional","affiliation":[{"name":"Institute for Scientific Interchange, Viale Settimio Severo 65, Villa Gualino, I-10133 Torino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Weigt","sequence":"additional","affiliation":[{"name":"Institute for Scientific Interchange, Viale Settimio Severo 65, Villa Gualino, I-10133 Torino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,9,25]]},"reference":[{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1038\/35000501","article-title":"Distinct types of diffuse large B-cell-lymphoma identified by gene expression profiling","volume":"403","author":"Alizadeh","year":"2000","journal-title":"Nature"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"3251","DOI":"10.1103\/PhysRevLett.76.3251","article-title":"Super-paramagnetic clustering of data","volume":"76","author":"Blatt","year":"1996","journal-title":"Phys. Rev. Lett"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"030201","DOI":"10.1103\/PhysRevLett.96.030201","article-title":"Learning by message passing in networks of discrete synapses","volume":"96","author":"Braunstein","year":"2006","journal-title":"Phys. Rev. Lett"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"3583","DOI":"10.1093\/bioinformatics\/bth447","article-title":"BagBoosting for tumor classification with gene expression data","volume":"20","author":"Dettling","year":"2004","journal-title":"Bioinformatics"},{"key":"2023041105592693600_","volume-title":"Pattern Classification and Scene Analysis","author":"Duda","year":"1973"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1126\/science.1136800","article-title":"Clustering by passing messages between data points","volume":"315","author":"Frey","year":"2007","journal-title":"Science"},{"key":"2023041105592693600_","article-title":"Mixture modeling by affinity propagation","author":"Frey","year":"2007"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1126\/science.286.5439.531","article-title":"Molecular classification of cancer: class discovery and class prediction by gene expression monitoring","volume":"286","author":"Golub","year":"1999","journal-title":"Science"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","DOI":"10.1002\/3527606734","volume-title":"Phase Transitions in Combinatorial Optimization Problems","author":"Hartmann","year":"2005"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","article-title":"Data clustering: a review","volume":"31","author":"Jain","year":"1999","journal-title":"ACM Comput. Surv"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"11111","DOI":"10.1088\/0305-4470\/36\/43\/030","article-title":"A CDMA multiuser detection algorithm on the basis of belief propagation","volume":"36","author":"Kabashima","year":"2003","journal-title":"J. Phys. A"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1038\/89044","article-title":"Classification and diagnostic prediction of cancer using gene expression profiling and artificial neural networks","volume":"6","author":"Khan","year":"2001","journal-title":"Nat. Med"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/18.910572","article-title":"Factor graphs and the sum-product algorithm","volume":"47","author":"Kschischang","year":"2001","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023041105592693600_","first-page":"281","article-title":"Some Methods for Classification and Analysis of Multivariate Observations","author":"MacQueen","year":"1967"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","article-title":"Analytic and algorithmic solution of random satisfiability problems","volume":"297","author":"M\u00e9zard","year":"2002","journal-title":"Science"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1038\/415436a","article-title":"Prediction of central nervous system embryonal tumor outcome based on gene expression","volume":"415","author":"Pomeroy","year":"2002","journal-title":"Nature"},{"key":"2023041105592693600_","article-title":"Pairwise clustering and graphical models","author":"Shental","year":"2003"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"2023041105592693600_","doi-asserted-by":"crossref","first-page":"2282","DOI":"10.1109\/TIT.2005.850085","article-title":"Belief propagation and generalizations","volume":"51","author":"Yedidia","year":"2005","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/20\/2708\/49818691\/bioinformatics_23_20_2708.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/20\/2708\/49818691\/bioinformatics_23_20_2708.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T07:04:10Z","timestamp":1684047850000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/20\/2708\/230273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,25]]},"references-count":19,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2007,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm414","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,10,15]]},"published":{"date-parts":[[2007,9,25]]}}}