{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T13:56:51Z","timestamp":1769608611208,"version":"3.49.0"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2124,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Recent progress in DNA sequencing technologies calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount of short reads. Searching similar pairs from a string pool is a fundamental process of de novo genome assembly, genome-wide alignment and other important analyses.<\/jats:p>\n               <jats:p>Results: In this study, we designed and implemented an exact algorithm SlideSort that finds all similar pairs from a string pool in terms of edit distance. Using an efficient pattern growth algorithm, SlideSort discovers chains of common k-mers to narrow down the search. Compared to existing methods based on single k-mers, our method is more effective in reducing the number of edit distance calculations. In comparison to backtracking methods such as BWA, our method is much faster in finding remote matches, scaling easily to tens of millions of sequences. Our software has an additional function of single link clustering, which is useful in summarizing short reads for further processing.<\/jats:p>\n               <jats:p>Availability: Executable binary files and C++ libraries are available at http:\/\/www.cbrc.jp\/~shimizu\/slidesort\/ for Linux and Windows.<\/jats:p>\n               <jats:p>Contact: \u00a0slidesort@m.aist.go.jp; shimizu-kana@aist.go.jp<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq677","type":"journal-article","created":{"date-parts":[[2010,12,11]],"date-time":"2010-12-11T01:14:58Z","timestamp":1292030098000},"page":"464-470","source":"Crossref","is-referenced-by-count":21,"title":["SlideSort: all pairs similarity search for short reads"],"prefix":"10.1093","volume":"27","author":[{"given":"Kana","family":"Shimizu","sequence":"first","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) and 2ERATO Minato Project, Japan Science and Technology Agency, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Koji","family":"Tsuda","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) and 2ERATO Minato Project, Japan Science and Technology Agency, Japan"},{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) and 2ERATO Minato Project, Japan Science and Technology Agency, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,12,9]]},"reference":[{"key":"2023012511565727000_B1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discrete Algorithms"},{"key":"2023012511565727000_B2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/3-540-45452-7_19","article-title":"One-gapped q-gram filters for levenshtein distance","volume-title":"Proceedings of the 13th Symposium on Combinatorial Pattern Matching (CPM'f02)","author":"Burkhardt","year":"2002"},{"key":"2023012511565727000_B3","doi-asserted-by":"crossref","first-page":"54","DOI":"10.2307\/2346439","article-title":"Minimum spanning trees and single-linkage cluster analysis","volume":"18","author":"Gower","year":"1969","journal-title":"Appl. Stat."},{"key":"2023012511565727000_B4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1023\/B:DAMI.0000005258.31418.83","article-title":"Mining frequent patterns without candidate generation","volume":"8","author":"Han","year":"2004","journal-title":"Data Min. Knowl. Discov."},{"key":"2023012511565727000_B5","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/bioinformatics\/btn429","article-title":"Seqmap: mapping massive amount of oligonucleotides to the genome","volume":"24","author":"Jiang","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012511565727000_B6","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"2023012511565727000_B7","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short dna sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023012511565727000_B8","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with burrows-wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511565727000_B9","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","article-title":"Soap2: an improved ultrafast tool for short read alignment","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511565727000_B10","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1126\/science.2983426","article-title":"Rapid and sensitive protein similarity searches","volume":"227","author":"Lipman","year":"1985","journal-title":"Science"},{"key":"2023012511565727000_B11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval.","author":"Manning","year":"2008"},{"key":"2023012511565727000_B12","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"26","author":"Prim","year":"1957","journal-title":"Bell Syst. Tech. J."},{"key":"2023012511565727000_B13","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1101\/gr.089151.108","article-title":"Efficient frequency-based de novo short-read clustering for error trimming in next-generation sequencing","volume":"19","author":"Qu","year":"2009","journal-title":"Genome Res."},{"key":"2023012511565727000_B14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10877-005-0677-y","article-title":"High-performance exact algorithms for motif search","volume":"19","author":"Rajasekaran","year":"2005","journal-title":"J. Clin. Monit. Comput."},{"key":"2023012511565727000_B15","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/BFb0054337","article-title":"Spelling approximate repeated or common motifs using a suffix tree","volume-title":"LATIN '98: Theoretical Informatics, Third Latin American Symposium","author":"Sagot","year":"1998"},{"key":"2023012511565727000_B16","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"Abyss: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res."},{"key":"2023012511565727000_B17","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","article-title":"Data Structures and Network Algorithms","volume-title":"Society for Industrial and Applied Mathematics (SIAM)","author":"Tarjan","year":"1983"},{"key":"2023012511565727000_B18","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1093\/bioinformatics\/btp120","article-title":"Tophat: discovering splice junctions with rna-seq","volume":"25","author":"Trapnell","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511565727000_B19","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-3-540-68125-0_31","article-title":"An efficient algorithm for finding similar short substrings from large scale string data","volume-title":"Proceedings of the 12th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD'08)","author":"Uno","year":"2008"},{"key":"2023012511565727000_B20","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btl629","article-title":"Assembling millions of short dna sequences using ssake","volume":"23","author":"Warren","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511565727000_B21","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1101\/gr.088823.108","article-title":"Razers-fast read mapping with sensitivity control","volume":"19","author":"Weese","year":"2009","journal-title":"Genome Res."},{"key":"2023012511565727000_B22","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short read assembly using de bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/464\/48866115\/bioinformatics_27_4_464.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/464\/48866115\/bioinformatics_27_4_464.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:37:50Z","timestamp":1674650270000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/4\/464\/197379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,9]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq677","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,15]]},"published":{"date-parts":[[2010,12,9]]}}}