{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:59:01Z","timestamp":1766066341889},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Maximal exact matches, or just MEMs, are a powerful tool in the context of multiple sequence alignment and approximate string matching. The most efficient algorithms to collect them are based on compressed indexes that rely on longest common prefix array-centered data structures. However, their space-efficient representations make use of encoding techniques that are expensive from a computational point of view. With the deluge of data generated by high-throughput sequencing, new approaches need to be developed to deal with larger genomic sequences.<\/jats:p>\n               <jats:p>Results: In this work, we have developed a new longest common prefix array-sampled representation, optimized to work with the backward search method inherently used by the FM-Index. Unlike previous implementations that sacrifice running time to have smaller space, ours lead to both a fast and a space-efficient approach. This implementation was used by the new software slaMEM, developed to efficiently retrieve MEMs. The results show that the new algorithm is competitive against existing state-of-the-art approaches.<\/jats:p>\n               <jats:p>Availability and implementation: The software is implemented in C and is operating system independent. The source code is freely available for download at http:\/\/github.com\/fjdf\/slaMEM\/ under the GPLv3 license.<\/jats:p>\n               <jats:p>Contact: \u00a0atf@inesc-id.pt<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt706","type":"journal-article","created":{"date-parts":[[2013,12,13]],"date-time":"2013-12-13T02:10:14Z","timestamp":1386900614000},"page":"464-471","source":"Crossref","is-referenced-by-count":15,"title":["slaMEM: efficient retrieval of maximal exact matches using a sampled LCP array"],"prefix":"10.1093","volume":"30","author":[{"given":"Francisco","family":"Fernandes","sequence":"first","affiliation":[{"name":"1 Knowledge Discovery and Bioinformatics Group (KDBIO), Instituto de Engenharia de Sistemas e Computadores Investiga\u00e7\u00e3o e Desenvolvimento (INESC-ID), Rua Alves Redol, 9, 1000-029 Lisbon and 2Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico (IST) \u2013 Universidade de Lisboa, Avenida Rovisco Pais, 1, 1049-001 Lisbon, Portugal"}]},{"given":"Ana T.","family":"Freitas","sequence":"additional","affiliation":[{"name":"1 Knowledge Discovery and Bioinformatics Group (KDBIO), Instituto de Engenharia de Sistemas e Computadores Investiga\u00e7\u00e3o e Desenvolvimento (INESC-ID), Rua Alves Redol, 9, 1000-029 Lisbon and 2Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico (IST) \u2013 Universidade de Lisboa, Avenida Rovisco Pais, 1, 1049-001 Lisbon, Portugal"},{"name":"1 Knowledge Discovery and Bioinformatics Group (KDBIO), Instituto de Engenharia de Sistemas e Computadores Investiga\u00e7\u00e3o e Desenvolvimento (INESC-ID), Rua Alves Redol, 9, 1000-029 Lisbon and 2Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico (IST) \u2013 Universidade de Lisboa, Avenida Rovisco Pais, 1, 1049-001 Lisbon, Portugal"}]}],"member":"286","published-online":{"date-parts":[[2013,12,11]]},"reference":[{"key":"2023012710420893400_btt706-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":"2023012710420893400_btt706-B2","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1186\/1471-2105-9-476","article-title":"CoCoNUT: an efficient system for the comparison and analysis of genomes","volume":"9","author":"Abouelhoda","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012710420893400_btt706-B3","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023012710420893400_btt706-B4","volume-title":"A Block-Sorting Lossless Data Compression Algorithm","author":"Burrows","year":"1994"},{"key":"2023012710420893400_btt706-B5","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01185431","article-title":"Sublinear approximate string matching and biological applications","volume":"12","author":"Chang","year":"1994","journal-title":"Algorithmica"},{"key":"2023012710420893400_btt706-B6","doi-asserted-by":"crossref","first-page":"e1001091","DOI":"10.1371\/journal.pbio.1001091","article-title":"Modernizing reference genome assemblies","volume":"9","author":"Church","year":"2011","journal-title":"PLoS Biol."},{"key":"2023012710420893400_btt706-B7","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","article-title":"Alignment of whole genomes","volume":"27","author":"Delcher","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012710420893400_btt706-B8","doi-asserted-by":"crossref","first-page":"2478","DOI":"10.1093\/nar\/30.11.2478","article-title":"Fast algorithms for large-scale genome alignment and comparison","volume":"30","author":"Delcher","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012710420893400_btt706-B9","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1109\/SFCS.2000.892127","article-title":"Opportunistic data structures with applications","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000","author":"Ferragina","year":"2000"},{"key":"2023012710420893400_btt706-B10","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023012710420893400_btt706-B11","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","article-title":"Faster entropy-bounded compressed suffix trees","volume":"410","author":"Fischer","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"2023012710420893400_btt706-B12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","article-title":"A new succinct representation of RMQ-information and improvements in the enhanced suffix array","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"Fischer","year":"2007"},{"key":"2023012710420893400_btt706-B13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","article-title":"A simple optimal representation for balanced parentheses","volume":"368","author":"Geary","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2023012710420893400_btt706-B14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023012710420893400_btt706-B15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-642-02441-2_17","article-title":"Permuted longest-common-prefix array","volume-title":"Combinatorial Pattern Matching","author":"K\u00e4rkk\u00e4inen","year":"2009"},{"key":"2023012710420893400_btt706-B16","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","article-title":"Simple linear work suffix array construction","volume-title":"Automata, Languages and Programming","author":"K\u00e4rkk\u00e4inen","year":"2003"},{"key":"2023012710420893400_btt706-B17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","article-title":"Linear-time longest-common-prefix computation in suffix arrays and its applications","volume-title":"Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching","author":"Kasai","year":"2001"},{"key":"2023012710420893400_btt706-B18","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1093\/bioinformatics\/btp275","article-title":"A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays","volume":"25","author":"Khan","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012710420893400_btt706-B19","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/3-540-44888-8_14","article-title":"Linear-time construction of suffix arrays","volume-title":"Combinatorial Pattern Matching","author":"Kim","year":"2003"},{"key":"2023012710420893400_btt706-B20","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-44888-8_15","article-title":"Space efficient linear time construction of suffix arrays","volume-title":"Combinatorial Pattern Matching","author":"Ko","year":"2003"},{"key":"2023012710420893400_btt706-B21","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1109\/TCBB.2011.127","article-title":"Efficient maximal repeat finding using the Burrows-Wheeler transform and wavelet tree","volume":"9","author":"Kulekci","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012710420893400_btt706-B22","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","article-title":"Reducing the space requirement of suffix trees","volume":"29","author":"Kurtz","year":"1999","journal-title":"Softw. Pract. Exp."},{"key":"2023012710420893400_btt706-B23","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012710420893400_btt706-B24","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"2023012710420893400_btt706-B25","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","article-title":"Compressed full-text indexes","volume":"39","author":"Navarro","year":"2007","journal-title":"ACM Comput. Surv."},{"key":"2023012710420893400_btt706-B26","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/DCC.2009.42","article-title":"Linear suffix array construction by almost pure induced-sorting","volume-title":"Data Compression Conference, 2009. DCC\u201909","author":"Nong","year":"2009"},{"key":"2023012710420893400_btt706-B27","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-642-16321-0_36","article-title":"Computing matching statistics and maximal exact matches on compressed full-text indexes","volume-title":"String Processing and Information Retrieval","author":"Ohlebusch","year":"2010"},{"key":"2023012710420893400_btt706-B28","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-642-03784-9_9","article-title":"A linear-time burrows-wheeler transform using induced sorting","volume-title":"String Processing and Information Retrieval","author":"Okanohara","year":"2009"},{"key":"2023012710420893400_btt706-B29","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed suffix trees with full functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"2023012710420893400_btt706-B30","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-3-642-13509-5_21","article-title":"Sampled longest common prefix array","volume-title":"Combinatorial Pattern Matching","author":"Sir\u00e9n","year":"2010"},{"key":"2023012710420893400_btt706-B31","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"2023012710420893400_btt706-B32","doi-asserted-by":"crossref","first-page":"6993","DOI":"10.1093\/nar\/gks408","article-title":"Prospects and limitations of full-text index structures in genome analysis","volume":"40","author":"Vyverman","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012710420893400_btt706-B33","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1093\/bioinformatics\/btt042","article-title":"essaMEM: finding Maximal Exact Matches using enhanced sparse suffix arrays","volume":"29","author":"Vyverman","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012710420893400_btt706-B34","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1038\/nature01262","article-title":"Initial sequencing and comparative analysis of the mouse genome","volume":"420","author":"Waterston","year":"2002","journal-title":"Nature"},{"key":"2023012710420893400_btt706-B35","first-page":"1","article-title":"Linear pattern matching algorithms","volume-title":"IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory, 1973. SWAT\u201908","author":"Weiner","year":"1973"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/464\/48915383\/bioinformatics_30_4_464.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/464\/48915383\/bioinformatics_30_4_464.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T10:57:29Z","timestamp":1674817049000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/4\/464\/203195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,11]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt706","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,2,15]]},"published":{"date-parts":[[2013,12,11]]}}}