{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T07:05:36Z","timestamp":1648537536632},"reference-count":8,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n<jats:sup>3<\/jats:sup>), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n<jats:sup>2<\/jats:sup>log n log |\u03a3|) and O(|\u03a3|n<jats:sup>2<\/jats:sup>log<jats:sup>2<\/jats:sup>n log log n), with \u03a3 denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences.<\/jats:p><jats:p>The present paper describes an off-line algorithm for binary strings that takes O(n<jats:sup>2<\/jats:sup>) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite \u03a3.<\/jats:p>","DOI":"10.1142\/s0129054110007714","type":"journal-article","created":{"date-parts":[[2010,11,24]],"date-time":"2010-11-24T08:39:03Z","timestamp":1290587943000},"page":"1035-1047","source":"Crossref","is-referenced-by-count":2,"title":["OPTIMAL EXTRACTION OF IRREDUNDANT MOTIF BASES"],"prefix":"10.1142","volume":"21","author":[{"given":"ALBERTO","family":"APOSTOLICO","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria dell' Informazione, Universit\u00e0 di Padova, Italy"},{"name":"College of Computing, Georgia Institute of Technology, USA"}]},{"given":"CLAUDIA","family":"TAGLIACOLLO","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria dell' Informazione, Universit\u00e0 di Padova, Italy"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195119404.001.0001","volume-title":"Pattern Discovery in Biomolecular Data: Tools, Techniques and Applications","author":"Wang Jason T. L.","year":"1999"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1089\/106652704773416867"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2005.5"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.010"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.002"},{"key":"rf9","first-page":"111","author":"Apostolico Alberto","journal-title":"Artificial Intelligence and Heuristic Methods for Bioinformatics"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63220-4"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054110007714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,14]],"date-time":"2021-11-14T01:53:38Z","timestamp":1636854818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054110007714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S0129054110007714"],"URL":"https:\/\/doi.org\/10.1142\/s0129054110007714","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}