{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T21:40:02Z","timestamp":1747518002255,"version":"3.40.5"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,1,28]],"date-time":"2015-01-28T00:00:00Z","timestamp":1422403200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s12859-014-0438-3","type":"journal-article","created":{"date-parts":[[2015,1,27]],"date-time":"2015-01-27T10:54:52Z","timestamp":1422356092000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast inexact mapping using advanced tree exploration on backward search methods"],"prefix":"10.1186","volume":"16","author":[{"given":"Jos\u00e9","family":"Salavert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9s","family":"Tom\u00e1s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joaqu\u00edn","family":"T\u00e1rraga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignacio","family":"Medina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joaqu\u00edn","family":"Dopazo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignacio","family":"Blanquer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,28]]},"reference":[{"issue":"5","key":"438_CR1","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1093\/bib\/bbq015","volume":"11","author":"H Li","year":"2010","unstructured":"Li H, Homer N. A survey of sequence alignment algorithms for next-generation sequencing. Brief Biol. 2010; 11(5):473\u201383.","journal-title":"Brief Biol."},{"key":"438_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981; 147:195\u20137.","journal-title":"J Mol Biol."},{"key":"438_CR3","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O. An improved algorithm for matching biological sequences. J Mol Biol. 1982; 162:705\u20138.","journal-title":"J Mol Biol."},{"key":"438_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis: probabilistic models of proteins and nucleic acids","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy SR, Krogh A, Mitchison G. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press: Cambridge; 1998. [http:\/\/books.google.es\/books?id=R5P2GlJvigQC]"},{"issue":"4","key":"438_CR5","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina P, Manzini G. Indexing compressed text. J ACM. 2005; 52(4):552\u201381. doi:10.1145\/10820361082039","journal-title":"J ACM."},{"key":"438_CR6","unstructured":"Burrows M, Wheeler DJ. A block-sorting lossless data compression algorithm. Technical Report 124. (SRC Digital, DEC Palo Alto); May 1994"},{"key":"438_CR7","volume-title":"Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"G Manzini","year":"1999","unstructured":"Manzini G. An analysis of the burrows-wheeler transform. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. NY: ACM-SIAM: 1999. p. 669\u201377."},{"key":"438_CR8","doi-asserted-by":"crossref","unstructured":"Ferragina P, Manzini G. Opportunistic data structures with applications. In: FOCS: 2000. p. 390\u2013398.","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"14","key":"438_CR9","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Durbin R. Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics. 2009; 25(14):1754\u20131760.","journal-title":"Bioinformatics"},{"issue":"15","key":"438_CR10","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R Li","year":"2009","unstructured":"Li R, Yu C, Li Y, Lam T-W, Yiu S-M, Kristiansen K, et al. Soap2: an improved ultrafast tool for short read alignment. Bioinformatics. 2009; 25(15):1966\u20131967. doi:10.1093\/bioinformatics\/btp336.","journal-title":"Bioinformatics"},{"key":"438_CR11","doi-asserted-by":"publisher","first-page":"(R25)","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg SL. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 2009; 10:(R25).","journal-title":"Genome Biol"},{"issue":"5","key":"438_CR12","doi-asserted-by":"publisher","first-page":"65632","DOI":"10.1371\/journal.pone.0065632","volume":"8","author":"R Luo","year":"2013","unstructured":"Luo R, Wong T, Zhu J, Liu C-M, Zhu X, Wu E, et al. Soap3-dp: Fast, accurate and sensitive gpu-based short read aligner. PLoS ONE. 2013; 8(5):65632. doi:10.1371\/journal.pone.0065632","journal-title":"PLoS ONE"},{"issue":"18","key":"438_CR13","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1093\/bioinformatics\/bts414","volume":"28","author":"Y Liu","year":"2012","unstructured":"Liu Y, Schmidt B. Long read alignment based on maximal exact match seeds. Bioinformatics. 2012; 28(18):318\u2013324. doi:10.1093\/bioinformatics\/bts414","journal-title":"Bioinformatics."},{"issue":"1","key":"438_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1186\/1756-0500-5-27","volume":"5","author":"P Klus","year":"2012","unstructured":"Klus P, Lam S, Lyberg D, Cheung M, Pullan G, McFarlane I, et al. Barracuda - a fast short read sequence aligner using graphics processing units. BMC Res Notes. 2012; 5(1):27. doi:10.1186\/1756-0500-5-27","journal-title":"BMC Res Notes."},{"issue":"4","key":"438_CR15","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1109\/TCBB.2012.49","volume":"9","author":"J Salavert","year":"2012","unstructured":"Salavert J, Blanquer I, Andr\u00e9s T, Vicente H, Ignacio M, Joaqu\u00edn T, et al. Using gpus for the exact alignment of short-read genetic sequences by means of the burrows-wheeler transform. IEEE\/ACM Trans Comput Biol Bioinf. 2012; 9(4):1245\u201356. doi:10.1109\/TCBB.2012.49","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf."},{"issue":"8","key":"438_CR16","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.mejo.2013.05.004","volume":"44","author":"Y Xin","year":"2013","unstructured":"Xin Y, Liu B, Min B, Li WXY, Cheung RCC, Fong AS, et al. Parallel architecture for {DNA} sequence inexact matching with burrows-wheeler transform. Microelectron J. 2013; 44(8):670\u201382. doi:10.1016\/j.mejo.2013.05.004","journal-title":"Microelectron J."},{"key":"438_CR17","volume-title":"Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201990","author":"U Manber","year":"1990","unstructured":"Manber U, Myers G. Suffix arrays: A new method for on-line string searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201990Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 1990. p. 319\u2013327. http:\/\/dl.acm.org\/citation.cfm?id=320176.320218"},{"key":"438_CR18","volume-title":"Proc. Workshop on Algorithms in Bioinformatics, in Lecture Notes in Computer Science,","author":"MI Abouelhoda","year":"2002","unstructured":"Abouelhoda MI, Kurtz S, Ohlebusch E. The enhanced suffix array and its applications to genome analysis. In: Proc. Workshop on Algorithms in Bioinformatics, in Lecture Notes in Computer Science,Heidelberger, Berlin: Springer: 2002. p. 449\u201363."},{"issue":"6","key":"438_CR19","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1093\/bioinformatics\/btt042","volume":"29","author":"M Vyverman","year":"2013","unstructured":"Vyverman M, De Baets B, Fack V, Dawyndt P. essamem: finding maximal exact matches using enhanced sparse suffix arrays. Bioinformatics. 2013; 29(6):802\u20134. doi:10.1093\/bioinformatics\/btt042","journal-title":"Bioinformatics."},{"issue":"Suppl 2","key":"438_CR20","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1186\/1471-2164-12-S2-S7","volume":"12","author":"M Oguzhan Kulekci","year":"2011","unstructured":"Oguzhan Kulekci M, Hon W-K, Shah R, Scott Vitter J, Xu B. Psi-ra: a parallel sparse index for genomic read alignment. BMC Genomics. 2011; 12(Suppl 2):7. doi:10.1186\/1471-2164-12-S2-S7","journal-title":"BMC Genomics."},{"issue":"2","key":"438_CR21","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K Sadakane","year":"2003","unstructured":"Sadakane K. New text indexing functionalities of the compressed suffix arrays. J Algorithms. 2003; 48(2):294\u2013313. doi:10.1016\/S0196-6774(03)00087-7","journal-title":"J Algorithms."},{"issue":"6","key":"438_CR22","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1093\/bioinformatics\/bts061","volume":"28","author":"C-M Liu","year":"2012","unstructured":"Liu C-M, Wong T, Wu E, Luo R, Yiu S-M, Li Y, et al. Soap3: ultra-fast gpu-based parallel alignment tool for short reads. Bioinformatics. 2012; 28(6):878\u20139. doi:10.1093\/bioinformatics\/bts061. http:\/\/bioinformatics.oxfordjournals.org\/content\/28\/6\/878.full.pdf+html","journal-title":"Bioinformatics."},{"key":"438_CR23","volume-title":"IEEE International Conference On Bioinformatics and Biomedicine, 2009. BIBM \u201909.,","author":"TW Lam","year":"2009","unstructured":"Lam TW, Li R, Tam A, Wong S, Wu E, Yiu SM. High throughput short read alignment via bi-directional bwt. In: IEEE International Conference On Bioinformatics and Biomedicine, 2009. BIBM \u201909.,Washington, D.C., USA: IEEE Computer Society Press: 2009. p. 31\u20136. doi:10.1109\/BIBM.2009.42"},{"issue":"5","key":"438_CR24","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li H, Durbin R. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics. 2010; 26(5):589\u201395. doi:10.1093\/bioinformatics\/btp698","journal-title":"Bioinformatics."},{"issue":"4","key":"438_CR25","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nat Meth. 2012; 9(4):357\u20139. doi:10.1038\/nmeth.1923","journal-title":"Nat Meth."},{"issue":"18","key":"438_CR26","doi-asserted-by":"publisher","first-page":"2366","DOI":"10.1093\/bioinformatics\/bts450","volume":"28","author":"JC Mu","year":"2012","unstructured":"Mu JC, Jiang H, Kiani A, Mohiyuddin M, Asadi NB, Wong WH. Fast and accurate read alignment for resequencing. Bioinformatics. 2012; 28(18):2366\u201373. doi:10.1093\/bioinformatics\/bts450","journal-title":"Bioinformatics."},{"issue":"10","key":"438_CR27","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1101\/gr.194201","volume":"11","author":"Z Ning","year":"2001","unstructured":"Ning Z, Cox AJ, Mullikin JC. Ssaha: A fast search method for large dna databases. Genome Res. 2001; 11(10):1725\u20139. doi:10.1101\/gr.194201","journal-title":"Genome Res."},{"issue":"12","key":"438_CR28","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1038\/nmeth.2221","volume":"9","author":"S Marco-Sola","year":"2012","unstructured":"Marco-Sola S, Sammeth M, Guigo R, Ribeca P. The GEM mapper: fast, accurate and versatile alignment by filtration. Nat Meth. 2012; 9(12):1185\u20138. doi:10.1038\/nmeth.2221","journal-title":"Nat Meth."},{"key":"438_CR29","unstructured":"Sadakane K. A library for compressed full-text indexes. https:\/\/code.google.com\/p\/csalib\/ (2010)"},{"key":"438_CR30","volume-title":"Proceedings of the 15th International Conference on Algorithms and Computation. ISAAC\u201904,","author":"V M\u00e4kinen","year":"2004","unstructured":"M\u00e4kinen V, Navarro G, Sadakane K. Advantages of backward searching; efficient secondary memory and distributed implementation of compressed suffix arrays. In: Proceedings of the 15th International Conference on Algorithms and Computation. ISAAC\u201904,Berlin, Heidelberg: Springer: 2004. p. 681\u201392. doi:10.1007\/978-3-540-30551-4_59. http:\/\/dx.doi.org\/10.1007\/978-3-540-30551-4_59"},{"key":"438_CR31","doi-asserted-by":"crossref","unstructured":"Puglisi SJ, Smyth WF, Turpin AH. A taxonomy of suffix array construction algorithms. ACM Comput Surv. 2007; 39(2). doi:10.1145\/1242471.1242472","DOI":"10.1145\/1242471.1242472"},{"key":"438_CR32","volume-title":"String Processing and Information Retrieval. Lecture Notes in Computer Science, vol. 5721","author":"D Okanohara","year":"2009","unstructured":"Okanohara D, Sadakane K. A linear-time burrows-wheeler transform using induced sorting. In: Karlgren J, Tarhio J, Hyyr\u00f6 H, editors. String Processing and Information Retrieval. Lecture Notes in Computer Science, vol. 5721. Heidelberg, Berlin: Springer: 2009. p. 90\u2013101."},{"issue":"2","key":"438_CR33","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi R, Vitter J. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SICOMP: SIAM J Comput. 2005; 35(2):378\u2013407.","journal-title":"SICOMP: SIAM J Comput."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-014-0438-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-014-0438-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-014-0438-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-014-0438-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T20:58:32Z","timestamp":1747515512000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-014-0438-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,28]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["438"],"URL":"https:\/\/doi.org\/10.1186\/s12859-014-0438-3","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2015,1,28]]},"assertion":[{"value":"24 January 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}