{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T20:25:49Z","timestamp":1782246349473,"version":"3.54.5"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01 HG005855"],"award-info":[{"award-number":["R01 HG005855"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"United States\u2013Israel Binational Science Foundation","award":["2017024"],"award-info":[{"award-number":["2017024"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>In the mixed-membership unsupervised clustering analyses commonly used in population genetics, multiple replicate data analyses can differ in their clustering solutions. Combinatorial algorithms assist in aligning clustering outputs from multiple replicates so that clustering solutions can be interpreted and combined across replicates. Although several algorithms have been introduced, challenges exist in achieving optimal alignments and performing alignments in reasonable computation time.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present Clumppling, a method for aligning replicate solutions in mixed-membership unsupervised clustering. The method uses integer linear programming for finding optimal alignments, embedding the cluster alignment problem in standard combinatorial optimization frameworks. In example analyses, we find that it achieves solutions with preferred values of a desired objective function relative to those achieved by Pong and that it proceeds with less computation time than Clumpak. It is also the first method to permit alignments across replicates with multiple arbitrary values of the number of clusters K.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Clumppling is available at https:\/\/github.com\/PopGenClustering\/Clumppling.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad751","type":"journal-article","created":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T22:35:50Z","timestamp":1702593350000},"source":"Crossref","is-referenced-by-count":6,"title":["<i>Clumppling<\/i>: cluster matching and permutation program with integer linear programming"],"prefix":"10.1093","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3955-9026","authenticated-orcid":false,"given":"Xiran","family":"Liu","sequence":"first","affiliation":[{"name":"Institute for Computational and Mathematical Engineering, Stanford University , Stanford, CA 94305, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Naama M","family":"Kopelman","sequence":"additional","affiliation":[{"name":"Faculty of Sciences, Holon Institute of Technology , Holon 58109, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noah A","family":"Rosenberg","sequence":"additional","affiliation":[{"name":"Institute for Computational and Mathematical Engineering, Stanford University , Stanford, CA 94305, United States"},{"name":"Department of Biology, Stanford University , Stanford, CA 94305, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"2024010504113746100_btad751-B1","doi-asserted-by":"crossref","DOI":"10.1201\/b17520","volume-title":"Handbook of Mixed Membership Models and Their Applications","author":"Airoldi","year":"2014"},{"key":"2024010504113746100_btad751-B2","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1101\/gr.094052.109","article-title":"Fast model-based estimation of ancestry in unrelated individuals","volume":"19","author":"Alexander","year":"2009","journal-title":"Genome Res"},{"key":"2024010504113746100_btad751-B3","doi-asserted-by":"crossref","first-page":"2817","DOI":"10.1093\/bioinformatics\/btw327","article-title":"Pong: fast analysis and visualization of latent clusters in population genetic data","volume":"32","author":"Behr","year":"2016","journal-title":"Bioinformatics"},{"key":"2024010504113746100_btad751-B4","doi-asserted-by":"crossref","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","volume":"2008","author":"Blondel","year":"2008","journal-title":"J Stat Mech"},{"key":"2024010504113746100_btad751-B5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"Burkard","year":"2009"},{"key":"2024010504113746100_btad751-B6","doi-asserted-by":"crossref","DOI":"10.1002\/9780470061190","volume-title":"Advances in Fuzzy Clustering and its Applications","author":"De Oliveira","year":"2007"},{"key":"2024010504113746100_btad751-B7","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys Rep"},{"key":"2024010504113746100_btad751-B8","doi-asserted-by":"crossref","first-page":"4261","DOI":"10.1002\/ece3.6195","article-title":"Major inconsistencies of inferred population genetic structure estimated in a large set of domestic horse breeds using microsatellites","volume":"10","author":"Funk","year":"2020","journal-title":"Ecol Evol"},{"key":"2024010504113746100_btad751-B9","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1093\/bioinformatics\/btm233","article-title":"Clumpp: a cluster matching and permutation program for dealing with label switching and multimodality in analysis of population structure","volume":"23","author":"Jakobsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2024010504113746100_btad751-B10","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.jnca.2018.02.011","article-title":"Community detection in networks: a multidisciplinary review","volume":"108","author":"Javed","year":"2018","journal-title":"Journal of Network and Computer Applications"},{"key":"2024010504113746100_btad751-B11","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1111\/1755-0998.12387","article-title":"Clumpak: a program for identifying clustering modes and packaging population structure inferences across K","volume":"15","author":"Kopelman","year":"2015","journal-title":"Mol Ecol Resour"},{"key":"2024010504113746100_btad751-B12","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1080\/10618600.2022.2127739","article-title":"A dirichlet model of alignment cost in mixed-membership unsupervised clustering","volume":"32","author":"Liu","year":"2023","journal-title":"J Comput Graph Stat"},{"key":"2024010504113746100_btad751-B13","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1186\/1471-2105-16-S11-S5","article-title":"XCluSim: a visual analytics tool for interactively comparing multiple clustering results of bioinformatics data","volume":"16","author":"L'Yi","year":"2015","journal-title":"BMC Bioinform"},{"key":"2024010504113746100_btad751-B14","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.jmva.2006.11.013","article-title":"Comparing clusterings\u2014an information based distance","volume":"98","author":"Meil\u0103","year":"2007","journal-title":"J Multivar Anal"},{"key":"2024010504113746100_btad751-B15","first-page":"65","author":"Mitchell","year":"2002"},{"key":"2024010504113746100_btad751-B16","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1093\/genetics\/155.2.945","article-title":"Inference of population structure using multilocus genotype data","volume":"155","author":"Pritchard","year":"2000","journal-title":"Genetics"},{"key":"2024010504113746100_btad751-B17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1046\/j.1471-8286.2003.00566.x","article-title":"Distruct: a program for the graphical display of population structure","volume":"4","author":"Rosenberg","year":"2004","journal-title":"Mol Ecol Notes"},{"key":"2024010504113746100_btad751-B18","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1093\/genetics\/159.2.699","article-title":"Empirical evaluation of genetic clustering methods using multilocus genotypes from 20 chicken breeds","volume":"159","author":"Rosenberg","year":"2001","journal-title":"Genetics"},{"key":"2024010504113746100_btad751-B19","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1998"},{"key":"2024010504113746100_btad751-B20","doi-asserted-by":"crossref","first-page":"e0194079","DOI":"10.1371\/journal.pone.0194079","article-title":"Statistical test for detecting community structure in real-valued edge-weighted graphs","volume":"13","author":"Tokuda","year":"2018","journal-title":"PLoS One"},{"key":"2024010504113746100_btad751-B21","author":"Van Dongen","year":"2000"},{"key":"2024010504113746100_btad751-B22","doi-asserted-by":"crossref","first-page":"2529","DOI":"10.1016\/j.cub.2017.07.002","article-title":"Parallel trajectories of genetic and linguistic admixture in a genetically admixed creole population","volume":"27","author":"Verdu","year":"2017","journal-title":"Curr Biol"},{"key":"2024010504113746100_btad751-B23","doi-asserted-by":"crossref","first-page":"e185","DOI":"10.1371\/journal.pgen.0030185","article-title":"Genetic variation and population structure in native Americans","volume":"3","author":"Wang","year":"2007","journal-title":"PLoS Genet"},{"key":"2024010504113746100_btad751-B24","doi-asserted-by":"crossref","DOI":"10.1002\/9781119606475","volume-title":"Integer Programming","author":"Wolsey","year":"2020"},{"key":"2024010504113746100_btad751-B25","first-page":"157","author":"Zhou","year":"2009"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad751\/54450277\/btad751.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/1\/btad751\/55031101\/btad751.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/1\/btad751\/55031101\/btad751.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T04:12:26Z","timestamp":1704427946000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad751\/7473369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad751","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,1,1]]},"published":{"date-parts":[[2023,12,14]]},"article-number":"btad751"}}