{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:36Z","timestamp":1772138076831,"version":"3.50.1"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2315,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Motivation: Single-particle cryo electron microscopy (cryoEM) typically produces density maps of macromolecular assemblies at intermediate to low resolution (\u223c5\u201330 \u00c5). By fitting high-resolution structures of assembly components into these maps, pseudo-atomic models can be obtained. Optimizing the quality-of-fit of all components simultaneously is challenging due to the large search space that makes the exhaustive search over all possible component configurations computationally unfeasible.<\/jats:p>\n                  <jats:p>Results: We developed an efficient mathematical programming algorithm that simultaneously fits all component structures into an assembly density map. The fitting is formulated as a point set matching problem involving several point sets that represent component and assembly densities at a reduced complexity level. In contrast to other point matching algorithms, our algorithm is able to match multiple point sets simultaneously and not only based on their geometrical equivalence, but also based on the similarity of the density in the immediate point neighborhood. In addition, we present an efficient refinement method based on the Iterative Closest Point registration algorithm. The integer quadratic programming method generates an assembly configuration in a few seconds. This efficiency allows the generation of an ensemble of candidate solutions that can be assessed by an independent scoring function. We benchmarked the method using simulated density maps of 11 protein assemblies at 20 \u00c5, and an experimental cryoEM map at 23.5 \u00c5 resolution. Our method was able to generate assembly structures with root-mean-square errors &amp;lt;6.5 \u00c5, which have been further reduced to &amp;lt;1.8 \u00c5 by the local refinement procedure.<\/jats:p>\n                  <jats:p>Availability: The program is available upon request as a Matlab code package.<\/jats:p>\n                  <jats:p>Contact: \u00a0alber@usc.edu and m.topf@cryst.bbk.ac.uk<\/jats:p>\n                  <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics Online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq201","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T03:28:13Z","timestamp":1275881293000},"page":"i261-i268","source":"Crossref","is-referenced-by-count":23,"title":["A fast mathematical programming procedure for simultaneous fitting of assembly components into cryoEM density maps"],"prefix":"10.1093","volume":"26","author":[{"given":"Shihua","family":"Zhang","sequence":"first","affiliation":[{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"},{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"}]},{"given":"Daven","family":"Vasishtan","sequence":"additional","affiliation":[{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"}]},{"given":"Min","family":"Xu","sequence":"additional","affiliation":[{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"}]},{"given":"Maya","family":"Topf","sequence":"additional","affiliation":[{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"}]},{"given":"Frank","family":"Alber","sequence":"additional","affiliation":[{"name":"1 Program in Molecular and Computational Biology, University of Southern California, Los Angeles, CA, USA, 2 Academy of Mathematics and Systems Science, CAS, Beijing 100190, China and 3 Institute of Structural and Molecular Biology, Crystallography, Department of Biological Sciences, Birkbeck College, University of London, London, UK"}]}],"member":"286","published-online":{"date-parts":[[2010,6,1]]},"reference":[{"key":"2023012508061551800_B1","first-page":"186","article-title":"Fast correspondence search for 3D surface matching","volume":"XXXVI","author":"Akca","year":"2005","journal-title":"ISPRS Workshop Laser scanning, Enschede, the Netherlands, International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences"},{"key":"2023012508061551800_B2","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1146\/annurev.biochem.77.060407.135530","article-title":"Integrating diverse data for structure determination of macromolecular assemblies","volume":"77","author":"Alber","year":"2008","journal-title":"Ann. Rev. Biochem."},{"key":"2023012508061551800_B3","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1016\/S0968-0004(00)01720-5","article-title":"Macromolecular electron microscopy in the era of structural genomics","volume":"25","author":"Baumeister","year":"2000","journal-title":"Trends Biochem. Sci."},{"key":"2023012508061551800_B4","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/S0022-2836(77)80200-3","article-title":"The Protein Data Bank: a computer-based archival file for macromolecular structures","volume":"112","author":"Bernstein","year":"1977","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/34.121791","article-title":"A method for registration of 3-D shapes","volume":"14","author":"Besl","year":"1992","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2023012508061551800_B6","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.jsb.2006.08.008","article-title":"Multi-resolution anchor-point registration of biomolecular assemblies and their components","volume":"157","author":"Birmanns","year":"2007","journal-title":"J. Struct. Biol."},{"key":"2023012508061551800_B7","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1093\/protein\/11.9.739","article-title":"Protein structure alignment by incremental combinatorial extension of optimal path","volume":"11","author":"Bourne","year":"1998","journal-title":"Protein Eng."},{"key":"2023012508061551800_B8","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/106652704773416876","article-title":"1001 Optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap","volume":"11","author":"Caprara","year":"2004","journal-title":"J. Comp. Bio."},{"key":"2023012508061551800_B9","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1016\/j.jmb.2004.02.066","article-title":"Fast fitting of atomic structures to lowresolution electron density maps by surface overlap maximization","volume":"338","author":"Ceulemans","year":"2004","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B10","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1006\/jmbi.2002.5438","article-title":"Multi-resolution contour-based fitting of macromolecular structures","volume":"317","author":"Chac\u00f3n","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B11","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1107\/S0907444906041059","article-title":"EMatch: an efficient method for aligning atomic resolution subunits into intermediate-resolution cryo-EM maps of large","volume":"63","author":"Dror","year":"2007","journal-title":"Acta Crystallogr. D. Biol. Crystallogr."},{"key":"2023012508061551800_B12","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/j.str.2005.01.007","article-title":"Fitting of high-resolution structures into electron microscopy reconstruction images","volume":"13","author":"Fabiola","year":"2005","journal-title":"Structure"},{"key":"2023012508061551800_B13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1093\/bioinformatics\/btl625","article-title":"ADP_EM: fast exhaustive multi-resolution docking for high-throughput coverage","volume":"23","author":"Garzon","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012508061551800_B14","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","article-title":"Protein structure comparison by alignment of distance matrices","volume":"233","author":"Holm","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B15","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/978-3-540-71233-6_32","article-title":"Joining soft assign and dynamic programming for the contact map overlap problem","volume-title":"the 1st International Confernce on Bioinformatics Research and Development (BIRD07)","author":"Jain","year":"2007"},{"key":"2023012508061551800_B16","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1006\/jmbi.2001.4633","article-title":"Bridging the information gap: computational tools for intermediate resolution structure interpretation","volume":"308","author":"Jiang","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B17","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1038\/nature06665","article-title":"Backbone structure of the infectious e15 virus capsid revealed by electron cryomicroscopy","volume":"451","author":"Jiang","year":"2008","journal-title":"Nature"},{"key":"2023012508061551800_B18","doi-asserted-by":"crossref","first-page":"4643","DOI":"10.1529\/biophysj.108.137125","article-title":"Multiple subunit fitting into a low-resolution density map of a macromolecular complex using a gaussian mixture model","volume":"95","author":"Kawabata","year":"2008","journal-title":"Biophys. J."},{"key":"2023012508061551800_B19","doi-asserted-by":"crossref","first-page":"1371","DOI":"10.1107\/S0907444903011247","article-title":"Fast rotational matching of rigid bodies by fast Fourier transform acceleration of five degrees of freedom","volume":"59","author":"Kovacs","year":"2003","journal-title":"Acta Crystallogr. D. Biol. Crystallogr."},{"key":"2023012508061551800_B20","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.jmb.2009.02.031","article-title":"Inferential optimization for simultaneous fitting of multiple components into a cryoEM map of their assembly","volume":"388","author":"Lasker","year":"2009","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B21","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1093\/bioinformatics\/btm156","article-title":"Alignment of molecular networks by integer quadratic programming","volume":"23","author":"Li","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012508061551800_B22","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.sbi.2009.02.010","article-title":"Hybrid approaches: applying computational methodsin cryo-electronmicroscopy","volume":"19","author":"Lindert","year":"2009","journal-title":"Curr. Opin. Struc. Biol."},{"key":"2023012508061551800_B23","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1109\/72.238311","article-title":"\u2018Neural-gas\u2019 network for vector quantization and its application to time-series prediction","volume":"4","author":"Martinetz","year":"1993","journal-title":"IEEE Trans. Neural Netw."},{"key":"2023012508061551800_B24","doi-asserted-by":"crossref","first-page":"1820","DOI":"10.1107\/S0907444902013707","article-title":"On the fitting of model electron densities into EM reconstructions: a reciprocal-space formulation","volume":"58","author":"Navaza","year":"2002","journal-title":"Acta Crystallogr. D. Biol. Crystallogr."},{"key":"2023012508061551800_B25","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1016\/S0092-8674(01)00617-1","article-title":"ATP-bound states of GroEL captured by cryo-electron microscopy","volume":"107","author":"Ranson","year":"2001","journal-title":"Cell"},{"key":"2023012508061551800_B26","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jsb.2003.09.029","article-title":"Fast 3D motif search of EM density maps using a locally normalized cross-correlation function","volume":"144","author":"Rath","year":"2003","journal-title":"J. Struct. Biol."},{"key":"2023012508061551800_B27","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1038\/nature06523","article-title":"The molecular sociology of the cell","volume":"450","author":"Robinson","year":"2007","journal-title":"Nature"},{"key":"2023012508061551800_B28","doi-asserted-by":"crossref","first-page":"1332","DOI":"10.1107\/S0907444900010908","article-title":"Docking structures of domains into maps from cryo-electron microscopy using local correlation","volume":"56","author":"Roseman","year":"2000","journal-title":"Acta Crystallogr. D."},{"key":"2023012508061551800_B29","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1107\/S0907444900009562","article-title":"Fitting atomic models into electron-microscopy maps","volume":"56","author":"Rossmann","year":"2000","journal-title":"Acta Crystallogr. D."},{"key":"2023012508061551800_B30","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1006\/jsbi.2002.4435","article-title":"Combining electron microscopic with X-ray crystallographic structures","volume":"136","author":"Rossmann","year":"2001","journal-title":"J. Struct. Biol."},{"key":"2023012508061551800_B31","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/IM.2001.924423","article-title":"Efficient variants of the ICP algorithm","volume-title":"Internal Conference on 3-D Digital Imaging and Modeling","author":"Rusinkiewicz","year":"2001"},{"key":"2023012508061551800_B32","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.jsb.2004.11.004","article-title":"Structural characterization of components of protein assemblies by comparative modeling and electron cryo-microscopy","volume":"149","author":"Topf","year":"2005","journal-title":"J. Struct. Biol."},{"key":"2023012508061551800_B33","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.str.2007.11.016","article-title":"Fitting and refinement of atomic structures guided by cryoEM density structure","volume":"16","author":"Topf","year":"2008","journal-title":"Structure"},{"key":"2023012508061551800_B34","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1016\/j.str.2006.05.013","article-title":"Flexible fitting in 3D-EM guided by the structural variability of protein superfamilies","volume":"14","author":"Velazquez-Muriel","year":"2006","journal-title":"Structure"},{"key":"2023012508061551800_B35","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/S0076-6879(03)74010-5","article-title":"Docking of atomic models into reconstructions from electron microscopy","volume":"374","author":"Volkmann","year":"2003","journal-title":"Meth. Enzymol."},{"key":"2023012508061551800_B36","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1006\/jmbi.1998.2232","article-title":"Selforganizing neural networks bridge the biomolecular resolution gap","volume":"284","author":"Wriggers","year":"1998","journal-title":"J. Mol. Biol."},{"key":"2023012508061551800_B37","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1016\/S0969-2126(01)00648-7","article-title":"Modeling tricks and fitting techniques for multiresolution structures","volume":"9","author":"Wriggers","year":"2001","journal-title":"Structure"},{"key":"2023012508061551800_B38","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1006\/jsbi.1998.4080","article-title":"Situs: a package for docking crystal structures into low-resolution maps from electron microscopy","volume":"125","author":"Wriggers","year":"1999","journal-title":"J. Struct. Biol."},{"key":"2023012508061551800_B39","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF01580903","article-title":"On affine-scaling algorithm for nonconvex quadratic programming","volume":"56","author":"Ye","year":"1992","journal-title":"Math. Program."},{"key":"2023012508061551800_B40","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1038\/nature06893","article-title":"3.88 \u00c5 structure of cytoplasmic polyhedrosis virus by cryo-electron microscopy","volume":"453","author":"Yu","year":"2008","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i261\/48859033\/bioinformatics_26_12_i261.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i261\/48859033\/bioinformatics_26_12_i261.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T03:10:02Z","timestamp":1674616202000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/i261\/284341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":40,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq201","relation":{"has-review":[{"id-type":"doi","id":"10.3410\/f.3524956.3227064","asserted-by":"object"}]},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,6,1]]}}}