{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T21:47:17Z","timestamp":1782078437667,"version":"3.54.5"},"reference-count":22,"publisher":"SAGE Publications","license":[{"start":{"date-parts":[[2027,6,19]],"date-time":"2027-06-19T00:00:00Z","timestamp":1813363200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"},{"start":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:00:00Z","timestamp":1781827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["2307571, 2307572, 2307573, 2434487"],"award-info":[{"award-number":["2307571, 2307572, 2307573, 2434487"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"abstract":"<jats:sec>\n                    <jats:title\/>\n                    <jats:p>\n                      In this article, we initiate the study on some problems related to multiple protein scaffold filling, with or without references. The objective is to maximize the sum of Blosum62 scores of the filled sequences when no reference is given, or to maximize the Blosum62 score between the filled sequence and a reference. We present the following results: (1) given\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                      scaffolds generated from the top-down tandem mass spectra, finding\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      scaffolds whose corresponding contents can be used to fill into a target sequence (or a sequence whose Blosum62 score with a reference is maximized) takes\n                      <jats:inline-formula>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo mathvariant=\"bold\" stretchy=\"true\">(<\/mml:mo>\n                            <mml:mrow>\n                              <mml:msup>\n                                <mml:mrow>\n                                  <mml:mi mathvariant=\"bold-italic\">n<\/mml:mi>\n                                <\/mml:mrow>\n                                <mml:mrow>\n                                  <mml:mi mathvariant=\"bold-italic\">k<\/mml:mi>\n                                  <mml:mo>\u2212<\/mml:mo>\n                                  <mml:mi mathvariant=\"bold-italic\">\u03b5<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                            <mml:mo mathvariant=\"bold\" stretchy=\"true\">)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:inline-formula>\n                      time, unless the Strong Exponential Time Hypothesis (SETH) fails. (2) Given two or more protein scaffolds and the corresponding multisets of amino acids to be filled accordingly, the corresponding optimization problem can be solved in polynomial time with dynamic programming. (3) Due to the high (and impractical) running times of these algorithms, we implement several heuristic algorithms for the special cases when three scaffolds are given. The corresponding empirical results are quite promising, from the testing of 12 datasets spanning five different kinds of proteins: antibody, myoglobin, mitochondrial respiratory-chain, calmodulin, and thioredoxin.\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1177\/15578666261457452","type":"journal-article","created":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T12:05:49Z","timestamp":1781870749000},"update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Investigations on Multiple Protein Scaffold Filling"],"prefix":"10.1177","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2923-1994","authenticated-orcid":false,"given":"Ismoiljon","family":"Muzaffarov","sequence":"first","affiliation":[{"name":"Gianforte School of Computing, Montana State University, Bozeman, Montana, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaowen","family":"Liu","sequence":"additional","affiliation":[{"name":"John W. Deming Department of Medicine, Tulane University, New Orleans, Louisiana, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Letu","family":"Qingge","sequence":"additional","affiliation":[{"name":"Department of Computer Science, North Carolina A&amp;T State University, Greensboro, North Carolina, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong."},{"name":"Shenzhen Research Institute, City University of Hong Kong, Shenzhen, China."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3929-4128","authenticated-orcid":false,"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[{"name":"Gianforte School of Computing, Montana State University, Bozeman, Montana, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2026,6,19]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature01511"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-025-4973-3"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-97-5087-0_3"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1074\/mcp.M900144-MCP200"},{"key":"e_1_3_3_7_1","first-page":"475","article-title":"A method for the determination of the amino acid sequence in peptides","volume":"22","author":"Edman P","year":"1949","unstructured":"Edman P. A method for the determination of the amino acid sequence in peptides. Arch. Biochem 1949;22:475\u2013476.","journal-title":"Arch. Biochem"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-97-7798-3_9"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.89.22.10915"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1021\/pr401300m"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2024.0510"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNB.2017.2666780"},{"key":"e_1_3_3_15_1","first-page":"203","volume-title":"Bioinformatics Research and Applications - 21st International Symposium, ISBRA 2025, Helsinki, Finland, August 3\u20135, 2025, Proceedings, Part II, volume 15757 of Lecture Notes in Computer Science","author":"Rizzo N","year":"2025","unstructured":"Rizzo N, , C\u00e1ceres M, , M\u00e4kinen V. Practical colinear chaining on sequences revisited. In: Bioinformatics Research and Applications - 21st International Symposium, ISBRA 2025, Helsinki, Finland, August 3\u20135, 2025, Proceedings, Part II, volume 15757 of Lecture Notes in Computer Science. (Tang J, , Lai X, , Cai Z, , Peng W, , Wei Y, eds). Springer; 2025, pp. 203\u2013216."},{"key":"e_1_3_3_16_1","doi-asserted-by":"crossref","unstructured":"Schaefer TJ. The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing STOC. (Lipton RJ Burkhard WA Savitch WJ Friedman EP Aho AV eds). ACM; 1978 pp. 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_3_17_1","doi-asserted-by":"crossref","unstructured":"Sturtz J Zhu B Liu X et al. Deep learning approaches for the protein scaffold filling problem. In: 2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE; 2022 pp. 1055\u20131061.","DOI":"10.1109\/ICTAI56018.2022.00161"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-7074-2_42"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep31730"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1074\/mcp.M000136-MCP201"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1074\/mcp.O113.037218"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"issue":"9","key":"e_1_3_3_23_1","first-page":"161","article-title":"A graph-based approach for proteoform identification and quantification using top-down homogeneous multiplexed tandem mass spectra","volume":"19","author":"Zhu K","year":"2018","unstructured":"Zhu K, , Liu X. A graph-based approach for proteoform identification and quantification using top-down homogeneous multiplexed tandem mass spectra. BMC Bioinform 2018;19S(9):161\u2013168.","journal-title":"BMC Bioinform"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261457452","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666261457452","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261457452","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261457452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T20:49:48Z","timestamp":1782074988000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15578666261457452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,19]]},"references-count":22,"alternative-id":["10.1177\/15578666261457452"],"URL":"https:\/\/doi.org\/10.1177\/15578666261457452","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,19]]},"article-number":"15578666261457452"}}