{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T04:19:33Z","timestamp":1777522773674,"version":"3.51.4"},"reference-count":21,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2023,1,1]]},"abstract":"\n The simplified partial digest problem (SPDP) models an effective and robust method for the building of a physical map using restriction site analysis. The best known algorithm requires\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2\n \n n<\/jats:italic>\n <\/jats:sup>\n ) time, using\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2\n \n n<\/jats:italic>\n <\/jats:sup>\n ) working space. The high complexities in time and space impede its application to genomes of a large number of sites. This article gives two new algorithms. The first improves the time by a factor of\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) and significantly reduces the space to\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2<\/jats:sup>\n ). The second improves both the time and space to\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 1.5<\/jats:sup>\n 2\n \n n<\/jats:italic>\n \/2\n <\/jats:sup>\n ). Extensive experiments are conducted on real genomes. For instances that can be solved by the best known algorithm, the new algorithms achieve a speedup of up to 4000 times; in addition, due to the reduction in space, the new algorithms can solve many more instances. Experiments also reveal the following advantage of the SPDP method: almost every instance has at most four feasible solutions and for an instance that does not contain any pair of symmetric restriction sites, in all observed examples, the solution is unique.\n <\/jats:p>","DOI":"10.1089\/cmb.2021.0641","type":"journal-article","created":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T11:02:17Z","timestamp":1652698937000},"page":"41-51","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Algorithms for the Simplified Partial Digest Problem"],"prefix":"10.1177","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8109-1914","authenticated-orcid":false,"given":"Biing-feng","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2023,1,5]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-016-1365-2"},{"key":"e_1_3_4_3_1","unstructured":"Abrams Z Chen HL. The simplified partial digest problem: Hardness and a probabilistic analysis. In: Proceedings of the RECOMB Satellite Meeting on DNA Sequencing Technologies and Computation. 2004."},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1060"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.04.017"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.07.027"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.5.398"},{"key":"e_1_3_4_8_1","first-page":"95","article-title":"New algorithm for the simplified partial digest problem","author":"Blazewicz J","year":"2003","unstructured":"Blazewicz J, , Jaroszewski M. New algorithm for the simplified partial digest problem. Lect Notes Bioinform, 2003;2812:95\u2013110; doi: 10.1007\/978-3-540-39763-2_8.","journal-title":"Lect Notes Bioinform"},{"key":"e_1_3_4_9_1","article-title":"On the complexity of the double digest problem","author":"Blazewicz J","year":"2004","unstructured":"Blazewicz J, , Jaroszewski M, , Kasprzak M, et al. On the complexity of the double digest problem. Control Cybern, 2004;33(1):132\u2013140.","journal-title":"Control Cybern"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro:2006007"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.021"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2016.0044"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2016.0046"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_3_4_15_1","article-title":"An algorithm for analyzing probed partial digestion","author":"Karp RM","year":"1995","unstructured":"Karp RM, , Newberg LA. An algorithm for analyzing probed partial digestion. Comput Appl Biosci, 1995;11(3):229\u2013235. doi: 10.1093\/bioinformatics\/11.3.229.","journal-title":"Comput Appl Biosci"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00008-9"},{"key":"e_1_3_4_17_1","doi-asserted-by":"crossref","unstructured":"Pevzner PA. Computational Molecular Biology: An Algorithmic Approach. MIT Press: Cambridge MA USA; 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(91)90028-H"},{"key":"e_1_3_4_19_1","unstructured":"Setubal J Meidanis J. Introduction to Computational Molecular Biology. PWS: Boston MA USA; 1997."},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(05)80259-9"},{"key":"e_1_3_4_21_1","unstructured":"Tas D Kilic K Sezerman OU. A new probabilistic approach for simplified partial digest problem. In: Proceedings of the 12th Annual International Conference on Research in Computational Molecular Biology; 2008; pp. 135\u2013136."},{"key":"e_1_3_4_22_1","unstructured":"Waterman MS. Introduction to Computational Biology: Maps Sequences and Genomes. Chapman and Hall\/CRC: Boca Raton Fl USA; 1995."}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1089\/cmb.2021.0641","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1089\/cmb.2021.0641","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1089\/cmb.2021.0641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:18:37Z","timestamp":1777393117000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1089\/cmb.2021.0641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,1]]}},"alternative-id":["10.1089\/cmb.2021.0641"],"URL":"https:\/\/doi.org\/10.1089\/cmb.2021.0641","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,1]]}}}