{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T00:28:45Z","timestamp":1777854525221,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2016,7,10]],"date-time":"2016-07-10T00:00:00Z","timestamp":1468108800000},"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 Information Science"],"published-print":{"date-parts":[[2016,10]]},"abstract":"<jats:p>Pattern matching is a key issue in sequential pattern mining. Many researchers now focus on pattern matching with gap constraints. However, most of these studies involve exact pattern matching problems, a special case of approximate pattern matching and a more challenging task. In this study, we introduce an approximate pattern matching problem with Hamming distance. Its objective is to compute the number of approximate occurrences of pattern P with gap constraints in sequence S under similarity constraint d. We propose an efficient algorithm named Single-rOot Nettree for approximate pattern matchinG with gap constraints (SONG) based on a new non-linear data structure Single-root Nettree to effectively solve the problem. Theoretical analysis and experiments demonstrate an interesting law that the ratio M( P, S, d)\/ N( P, S, m) approximately follows a binomial distribution, where M( P, S, d) and N( P, S, m) are the numbers of the approximate occurrences whose distances to pattern P are d (0\u2264 d\u2264 m) and no more than m (the length of pattern P), respectively. Experimental results for real biological data validate the efficiency and effectiveness of SONG.<\/jats:p>","DOI":"10.1177\/0165551515603286","type":"journal-article","created":{"date-parts":[[2015,9,21]],"date-time":"2015-09-21T22:23:34Z","timestamp":1442874214000},"page":"639-658","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":20,"title":["Approximate pattern matching with gap constraints"],"prefix":"10.1177","volume":"42","author":[{"given":"Youxi","family":"Wu","sequence":"first","affiliation":[{"name":"Hebei University of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiqiang","family":"Tang","sequence":"additional","affiliation":[{"name":"Hebei University of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"He","family":"Jiang","sequence":"additional","affiliation":[{"name":"Dalian University of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xindong","family":"Wu","sequence":"additional","affiliation":[{"name":"Hefei University of Technology, China"},{"name":"University of Vermont, Vermont, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2016,7,10]]},"reference":[{"key":"bibr1-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1177\/0165551506059229"},{"key":"bibr2-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-013-0499-4"},{"key":"bibr3-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.08.063"},{"key":"bibr4-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1177\/0165551510361432"},{"key":"bibr5-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1177\/0165551513519039"},{"key":"bibr6-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1089\/106652703322756140"},{"key":"bibr7-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007374"},{"key":"bibr8-0165551515603286","first-page":"177","volume":"4","author":"Califf M","year":"2003","journal-title":"Journal of Machine Learning Research"},{"key":"bibr9-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20662-7_7"},{"key":"bibr10-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/11809678_17"},{"key":"bibr11-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37064-9_46"},{"key":"bibr12-0165551515603286","doi-asserted-by":"publisher","DOI":"10.3724\/SP.J.1001.2013.04381"},{"key":"bibr13-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1109\/DASC.2009.65"},{"key":"bibr14-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1109\/IRI.2010.5558954"},{"key":"bibr15-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-012-0394-4"},{"key":"bibr16-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1145\/1267066.1267068"},{"key":"bibr17-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0038-2"},{"key":"bibr18-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1145\/2133360.2133362"},{"key":"bibr19-0165551515603286","first-page":"2934","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Zhu X","year":"2007"},{"key":"bibr20-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1109\/BIBM.2007.48"},{"key":"bibr21-0165551515603286","first-page":"113","volume-title":"Proceedings of the 7th SIAM AMS Complexity of Computation","author":"Fischer MJ","year":"1974"},{"key":"bibr22-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90032-D"},{"key":"bibr23-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.029"},{"key":"bibr24-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.104"},{"key":"bibr25-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1007\/11564126_14"},{"key":"bibr26-0165551515603286","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiomed.2013.02.006"},{"key":"bibr27-0165551515603286","first-page":"35","volume":"7","author":"Lam HT","year":"2013","journal-title":"Statistical Analysis and Data Mining"},{"key":"bibr28-0165551515603286","doi-asserted-by":"publisher","DOI":"10.3724\/SP.J.1016.2011.01452"}],"container-title":["Journal of Information Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551515603286","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0165551515603286","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551515603286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T23:09:19Z","timestamp":1777504159000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0165551515603286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,10]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["10.1177\/0165551515603286"],"URL":"https:\/\/doi.org\/10.1177\/0165551515603286","relation":{},"ISSN":["0165-5515","1741-6485"],"issn-type":[{"value":"0165-5515","type":"print"},{"value":"1741-6485","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,10]]}}}