{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T02:29:25Z","timestamp":1660271365721},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate k-covers and study them under various commonly used distance measures. We propose the following problem: \"Given a string x of length n, a set U of m strings of length k, and a distance measure, compute the minimum number t such that U is a set of approximate k-covers for x with distance t\". To solve this problem, we present three algorithms with time complexity O(km(n - k)), O(mn<jats:sup>2<\/jats:sup>) and O(mn<jats:sup>2<\/jats:sup>) under Hamming, Levenshtein and edit distance, respectively. A World Wide Web server interface has been established at for automated use of the programs. <\/jats:p>","DOI":"10.1142\/s0129054105003789","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1231-1251","source":"Crossref","is-referenced-by-count":1,"title":["ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS"],"prefix":"10.1142","volume":"16","author":[{"given":"LILI","family":"ZHANG","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences,  University of North Carolina, P. O. Box 26170,  Greensboro, North Carolina 27402\u20136170, United States"}]},{"given":"F.","family":"BLANCHET-SADRI","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences,  University of North Carolina, P.O. Box 26170, Greensboro,  North Carolina 27402\u20136170, United States"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90159-Q"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90056-N"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90111-8"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90060-4"},{"key":"rf6","first-page":"1400","volume":"21","author":"Iliopoulos C. S.","journal-title":"J. Korea Inform. Sci. Soc."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1089\/106652701300099038"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0062-2"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00045-X"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00235-Q"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288489"},{"key":"rf14","volume-title":"Introduction to Computational Molecular Biology","author":"Setubal J.","year":"1997"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00365-0"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:18Z","timestamp":1565191758000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":13,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003789"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003789","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}