{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773726,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            We present a novel graph model and an efficient algorithm for solving the \u201cthreshold all against all\u201d problem, which involves searching two strings (with length\n            <jats:italic>M<\/jats:italic>\n            and\n            <jats:italic>N<\/jats:italic>\n            , respectively) for all maximal approximate substring matches of length at least\n            <jats:italic>S<\/jats:italic>\n            , with up to\n            <jats:italic>K<\/jats:italic>\n            differences. Our algorithm solves the problem in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>MNK<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            ), which is a considerable improvement over the previous known bound for this problem. We also provide experimental evidence that, in practice, our algorithm exhibits a better performance than its worst-case running time.\n          <\/jats:p>","DOI":"10.1145\/1227161.1370601","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["A graph approach to the threshold all-against-all substring matching problem"],"prefix":"10.1145","volume":"12","author":[{"given":"Marina","family":"Barsky","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}]},{"given":"Chris","family":"Upton","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.4.327"},{"key":"e_1_2_1_3_1","unstructured":"Baeza-Yates R. A. and Gonnet G. H. 1990. All-against-all sequence matching. Tech. rep. Department of Computer Science Universidad de Chile.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Baeza-Yates R. A. and Gonnet G. H. 1999. A fast algorithm on average for all-against-all sequence matching. In SPIRE\/CRIWG. IEEE Los Alamitos CA. 16--23.]]","DOI":"10.5555\/519452.830786"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993379"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11880561_31"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/299432.299460"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146650"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146656"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/262228"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647813.757210"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.8211139"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11415770_15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/267521.267845"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/647819.736204"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt1098-939"},{"key":"e_1_2_1_18_1","unstructured":"Sankoff D. and Kruskal J. 1983. Time Warps String Edits and Macromolecules: the Theory and Practice of Sequence Comparisons. Addison-Wesley Reading MA.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370601","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1370601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":19,"alternative-id":["10.1145\/1227161.1370601"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1370601","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}