{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:39:08Z","timestamp":1740184748720,"version":"3.37.3"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,5,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Summary<\/jats:title>\n                  <jats:p>Topology determination is one of the most important intermediate steps toward building the atomic structure of proteins from their medium-resolution cryo-electron microscopy (cryo-EM) map. The main goal in the topology determination is to identify correct matches (i.e. assignment and direction) between secondary structure elements (SSEs) (\u03b1-helices and \u03b2-sheets) detected in a protein sequence and cryo-EM density map. Despite many recent advances in molecular biology technologies, the problem remains a challenging issue. To overcome the problem, this article proposes a linear programming-based topology determination (LPTD) method to solve the secondary structure topology problem in three-dimensional geometrical space. Through modeling of the protein\u2019s sequence with the aid of extracting highly reliable features and a distance-based scoring function, the secondary structure matching problem is transformed into a complete weighted bipartite graph matching problem. Subsequently, an algorithm based on linear programming is developed as a decision-making strategy to extract the true topology (native topology) between all possible topologies. The proposed automatic framework is verified using 12 experimental and 15 simulated \u03b1\u2013\u03b2 proteins. Results demonstrate that LPTD is highly efficient and extremely fast in such a way that for 77% of cases in the dataset, the native topology has been detected in the first rank topology in &amp;lt;2\u2009s. Besides, this method is able to successfully handle large complex proteins with as many as 65 SSEs. Such a large number of SSEs have never been solved with current tools\/methods.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The LPTD package (source code and data) is publicly available at https:\/\/github.com\/B-Behkamal\/LPTD. Moreover, two test samples as well as the instruction of utilizing the graphical user interface have been provided in the shared readme file.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac170","type":"journal-article","created":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T20:18:12Z","timestamp":1647634692000},"page":"2734-2741","source":"Crossref","is-referenced-by-count":1,"title":["LPTD: a novel linear programming-based topology determination method for cryo-EM maps"],"prefix":"10.1093","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4630-1178","authenticated-orcid":false,"given":"Bahareh","family":"Behkamal","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Faculty of Engineering, Ferdowsi University of Mashhad , Mashhad 9177948974, Iran"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5550-5565","authenticated-orcid":false,"given":"Mahmoud","family":"Naghibzadeh","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Faculty of Engineering, Ferdowsi University of Mashhad , Mashhad 9177948974, Iran"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6509-0807","authenticated-orcid":false,"given":"Andrea","family":"Pagnani","sequence":"additional","affiliation":[{"name":"Department of Applied Science and Technology (DISAT), Politecnico di Torino , Torino I-10129, Italy"},{"name":"Italian Institute for Genomic Medicine (IIGM), IRCC-Candiolo , Candiolo (TO) I-10060, Italy"},{"name":"INFN Sezione di Torino , Torino I-10125, Italy"}]},{"given":"Mohammad Reza","family":"Saberi","sequence":"additional","affiliation":[{"name":"Medicinal Chemistry Department, School of Pharmacy, Mashhad University of Medical Sciences , Mashhad 9177899191, Iran"},{"name":"Bioinformatics Research Group, Mashhad University of Medical Sciences , Mashhad 9177899191, Iran"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8459-9070","authenticated-orcid":false,"given":"Kamal","family":"Al Nasr","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tennessee State University , Nashville, TN 37209, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,3,21]]},"reference":[{"key":"2023020109053965200_btac170-B1","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1016\/j.cad.2008.01.013","article-title":"Shape modeling and matching in identifying 3D protein structures","volume":"40","author":"Abeysinghe","year":"2008","journal-title":"CAD Comput. Aided Des"},{"first-page":"711","year":"2014","author":"Al Nasr","key":"2023020109053965200_btac170-B2"},{"first-page":"1","year":"2015","author":"Al Nasr","key":"2023020109053965200_btac170-B3"},{"key":"2023020109053965200_btac170-B4","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1017\/S0263574716000242","article-title":"Constrained cyclic coordinate descent for cryo-EM images at medium resolutions: beyond the protein loop closure problem","volume":"34","author":"Al Nasr","year":"2016","journal-title":"Robotica"},{"key":"2023020109053965200_btac170-B5","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1142\/S0219720011005604","article-title":"Ranking valid topologies of the secondary structure elements using a constraint graph","volume":"09","author":"Al Nasr","year":"2011","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023020109053965200_btac170-B6","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1109\/TCBB.2014.2302803","article-title":"Solving the secondary structure matching problem in cryo-EM de novo modeling using a constrained K-shortest path graph algorithm","volume":"11","author":"Al Nasr","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020109053965200_btac170-B7","doi-asserted-by":"crossref","first-page":"28","DOI":"10.3390\/molecules23020028","article-title":"Analytical approaches to improve accuracy in solving the protein topology problem","volume":"23","author":"Al Nasr","year":"2018","journal-title":"Molecules"},{"key":"2023020109053965200_btac170-B8","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.str.2006.11.008","article-title":"Identification of secondary structure elements in intermediate-resolution density maps","volume":"15","author":"Baker","year":"2007","journal-title":"Structure"},{"key":"2023020109053965200_btac170-B9","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.jsb.2011.01.015","article-title":"Modeling protein structure at near atomic resolutions with Gorgon","volume":"174","author":"Baker","year":"2011","journal-title":"J. Struct. Biol"},{"key":"2023020109053965200_btac170-B10","doi-asserted-by":"crossref","first-page":"107815","DOI":"10.1016\/j.jmgm.2020.107815","article-title":"Solving the \u03b1-helix correspondence problem at medium-resolution cryo-EM maps through modeling and 3D matching","volume":"103","author":"Behkamal","year":"2020","journal-title":"J. Mol. Graph. Model"},{"key":"2023020109053965200_btac170-B11","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.3390\/biom11121773","article-title":"Three-dimensional graph matching to identify secondary structure correspondence of medium-resolution cryo-EM density maps","volume":"11","author":"Behkamal","year":"2021","journal-title":"Biomolecules"},{"key":"2023020109053965200_btac170-B12","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1109\/TCBB.2016.2543721","article-title":"An effective computational method incorporating multiple secondary structure predictions in topology determination for Cryo-EM Images","volume":"14","author":"Biswas","year":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020109053965200_btac170-B13","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1038\/nature.2017.22738","article-title":"Cryo-electron microscopy wins chemistry Nobel","volume":"550","author":"Cressey","year":"2017","journal-title":"Nat. News"},{"key":"2023020109053965200_btac170-B14","doi-asserted-by":"crossref","first-page":"1936","DOI":"10.1109\/TCBB.2018.2837753","article-title":"Enhancement of protein \u03b2-sheet topology prediction using maximum weight disjoint path cover","volume":"16","author":"Dehghani","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020109053965200_btac170-B15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1038\/nmeth.3700","article-title":"Single-particle cryo-electron microscopy","volume":"13","author":"Doerr","year":"2016","journal-title":"Nat. Methods"},{"key":"2023020109053965200_btac170-B17","first-page":"5","article-title":"Comparative protein structure modeling using MODELLER","volume":"47","author":"Eswar","year":"2014","journal-title":"Curr. Protoc. Bioinformatics"},{"key":"2023020109053965200_btac170-B18","doi-asserted-by":"crossref","first-page":"bbab156","DOI":"10.1093\/bib\/bbab156","article-title":"EMNUSS: a deep learning framework for secondary structure annotation in cryo-EM maps","volume":"22","author":"He","year":"2021","journal-title":"Brief. Bioinform"},{"key":"2023020109053965200_btac170-B20","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":"2023020109053965200_btac170-B22","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1038\/nprot.2015.053","article-title":"The Phyre2 web portal for protein modeling, prediction and analysis","volume":"10","author":"Kelley","year":"2015","journal-title":"Nat. Protoc"},{"key":"2023020109053965200_btac170-B23","doi-asserted-by":"crossref","first-page":"W526","DOI":"10.1093\/nar\/gkh468","article-title":"Protein structure prediction and analysis using the Robetta server","volume":"32","author":"Kim","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020109053965200_btac170-B25","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/TCBB.2007.1003","article-title":"EMatch\u202f: discovery of high resolution structural homologues of protein domains in intermediate resolution cryo-EM maps","volume":"4","author":"Lasker","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020109053965200_btac170-B26","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.sbi.2009.02.010","article-title":"Hybrid approaches: applying computational methods in cryo-electron microscopy","volume":"19","author":"Lindert","year":"2009","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020109053965200_btac170-B27","doi-asserted-by":"crossref","first-page":"3506","DOI":"10.1093\/bioinformatics\/btv472","article-title":"Protein contact prediction by integrating joint evolutionary coupling analysis and supervised learning","volume":"31","author":"Ma","year":"2015","journal-title":"Bioinformatics"},{"first-page":"49","year":"1936","author":"Mahalanobis","key":"2023020109053965200_btac170-B28"},{"key":"2023020109053965200_btac170-B29","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.sbi.2019.05.024","article-title":"Modelling structures in cryo-EM maps","volume":"58","author":"Malhotra","year":"2019","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020109053965200_btac170-B32","doi-asserted-by":"crossref","first-page":"14898","DOI":"10.1002\/ange.202000421","article-title":"Haruspex: a neural network for the automatic identification of oligonucleotides and protein secondary structure in cryo-electron microscopy maps","volume":"132","author":"Mostosi","year":"2020","journal-title":"Angew. Chem"},{"first-page":"69","year":"2007","author":"M\u00fcller","key":"2023020109053965200_btac170-B33"},{"key":"2023020109053965200_btac170-B34","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1002\/jcc.20084","article-title":"UCSF Chimera\u2014a visualization system for exploratory research and analysis","volume":"25","author":"Pettersen","year":"2004","journal-title":"J. Comput. Chem"},{"key":"2023020109053965200_btac170-B35","doi-asserted-by":"crossref","first-page":"e2017525118","DOI":"10.1073\/pnas.2017525118","article-title":"DeepTracer for fast de novo cryo-EM protein structure modeling and special studies on CoV-related complexes","volume":"118","author":"Pfab","year":"2021","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020109053965200_btac170-B36","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1038\/nprot.2010.5","article-title":"I-TASSER: a unified platform for automated protein structure and function prediction","volume":"5","author":"Roy","year":"2010","journal-title":"Nat. Protoc"},{"first-page":"40","year":"2008","author":"Senin","key":"2023020109053965200_btac170-B37"},{"key":"2023020109053965200_btac170-B38","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1002\/prot.25834","article-title":"Protein structure prediction using multiple deep neural networks in the 13th Critical Assessment of Protein Structure Prediction (CASP13)","volume":"87","author":"Senior","year":"2019","journal-title":"Proteins"},{"key":"2023020109053965200_btac170-B39","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1038\/s41586-019-1923-7","article-title":"Improved protein structure prediction using potentials from deep learning","volume":"577","author":"Senior","year":"2020","journal-title":"Nature"},{"first-page":"764","year":"2013","author":"Si","key":"2023020109053965200_btac170-B40"},{"key":"2023020109053965200_btac170-B41","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1002\/bip.22063","article-title":"A machine learning approach for the identification of protein secondary structure elements from electron cryo-microscopy density maps","volume":"97","author":"Si","year":"2012","journal-title":"Biopolymers"},{"key":"2023020109053965200_btac170-B42","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1201\/b18378","volume-title":"Linear and Integer Optimization: Theory and Practice","author":"Sierksma","year":"2015"},{"key":"2023020109053965200_btac170-B43","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1038\/s41592-019-0500-1","article-title":"Protein secondary structure detection in intermediate-resolution cryo-EM maps using deep learning","volume":"16","author":"Subramaniya","year":"2019","journal-title":"Nat. Methods"},{"key":"2023020109053965200_btac170-B45","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1016\/j.sbi.2005.08.001","article-title":"Combining electron microscopy and comparative protein structure modeling","volume":"15","author":"Topf","year":"2005","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020109053965200_btac170-B48","doi-asserted-by":"crossref","first-page":"W361","DOI":"10.1093\/nar\/gkw307","article-title":"CoinFold: a web server for protein contact prediction and contact-assisted protein folding","volume":"44","author":"Wang","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020109053965200_btac170-B49","doi-asserted-by":"crossref","first-page":"e1005324","DOI":"10.1371\/journal.pcbi.1005324","article-title":"Accurate de novo prediction of protein contact map by ultra-deep learning model","volume":"13","author":"Wang","year":"2017","journal-title":"PLoS Comput. Biol"},{"key":"2023020109053965200_btac170-B53","doi-asserted-by":"crossref","first-page":"W174","DOI":"10.1093\/nar\/gkv342","article-title":"I-TASSER server: new development for protein structure and function predictions","volume":"43","author":"Yang","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023020109053965200_btac170-B54","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1038\/nmeth.3213","article-title":"The I-TASSER Suite: protein structure and function prediction","volume":"12","author":"Yang","year":"2015","journal-title":"Nat. Methods"},{"key":"2023020109053965200_btac170-B55","doi-asserted-by":"crossref","first-page":"1496","DOI":"10.1073\/pnas.1914677117","article-title":"Improved protein structure prediction using predicted interresidue orientations","volume":"117","author":"Yang","year":"2020","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020109053965200_btac170-B56","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1186\/1471-2105-9-40","article-title":"I-TASSER server for protein 3D structure prediction","volume":"9","author":"Zhang","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020109053965200_btac170-B57","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1002\/prot.20264","article-title":"Scoring function for automated assessment of protein structure template quality","volume":"57","author":"Zhang","year":"2004","journal-title":"Proteins"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btac170\/43248825\/btac170.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/10\/2734\/49009566\/btac170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/10\/2734\/49009566\/btac170.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T20:58:47Z","timestamp":1675285127000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/10\/2734\/6551280"}},"subtitle":[],"editor":[{"given":"Lenore","family":"Cowen","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,3,21]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,5,13]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac170","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2022,5,15]]},"published":{"date-parts":[[2022,3,21]]}}}