{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T21:12:19Z","timestamp":1718485939252},"reference-count":0,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Summary: Suffix tree is one of the most fundamental data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length n from alphabet \u03a3 = {A,\u2009C,\u2009G,\u2009T\u2009} can be stored in n\u2009log\u2009|\u03a3|=\u20092n bits, its suffix tree occupies O(n log n) bits. In practice, the size difference easily reaches factor 50.<\/jats:p>\n               <jats:p>We provide an implementation of the compressed suffix tree very recently proposed by Sadakane (Theory of Computing Systems, in press). The compressed suffix tree occupies space proportional to the text size, i.e. O(n log} | \u03a3 |) bits, and supports all typical suffix tree operations with at most log n factor slowdown. Our experiments show that, e.g. on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of normal suffix tree. Typical operations are slowed down by factor 60.<\/jats:p>\n               <jats:p>Availability: The C++ implementation under GNU license is available at http:\/\/www.cs.helsinki.fi\/group\/suds\/cst\/. An example program implementing a typical pattern discovery task is included. Experimental results in this note correspond to version 0.95.<\/jats:p>\n               <jats:p>Contact: \u00a0vmakinen@cs.helsinki.fi<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl681","type":"journal-article","created":{"date-parts":[[2007,1,20]],"date-time":"2007-01-20T01:12:50Z","timestamp":1169255570000},"page":"629-630","source":"Crossref","is-referenced-by-count":19,"title":["Compressed suffix tree\u2014a basis for genome-scale sequence analysis"],"prefix":"10.1093","volume":"23","author":[{"given":"Niko","family":"V\u00e4lim\u00e4ki","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, P.O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2b), FI-00014 University of Helsinki, Finland, 2Technische Fakult\u00e4t, Universit\u00e4t Bielefeld, Germany and 3Indian Institute of Technology, Kanpur, India"}]},{"given":"Wolfgang","family":"Gerlach","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, P.O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2b), FI-00014 University of Helsinki, Finland, 2Technische Fakult\u00e4t, Universit\u00e4t Bielefeld, Germany and 3Indian Institute of Technology, Kanpur, India"}]},{"given":"Kashyap","family":"Dixit","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, P.O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2b), FI-00014 University of Helsinki, Finland, 2Technische Fakult\u00e4t, Universit\u00e4t Bielefeld, Germany and 3Indian Institute of Technology, Kanpur, India"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, P.O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2b), FI-00014 University of Helsinki, Finland, 2Technische Fakult\u00e4t, Universit\u00e4t Bielefeld, Germany and 3Indian Institute of Technology, Kanpur, India"}]}],"member":"286","published-online":{"date-parts":[[2007,1,19]]},"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/5\/629\/49829845\/bioinformatics_23_5_629.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/5\/629\/49829845\/bioinformatics_23_5_629.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T09:38:09Z","timestamp":1681205889000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/5\/629\/239331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,19]]},"references-count":0,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl681","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,3]]},"published":{"date-parts":[[2007,1,19]]}}}