Skip to main content

2017 | OriginalPaper | Buchkapitel

2. Full-Text Indexes for High-Throughput Sequencing

verfasst von : David Weese, Enrico Siragusa

Erschienen in: Algorithms for Next-Generation Sequencing Data

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Recent advances in High-Throughput Sequencing demand for novel algorithms working on efficient data structures specifically designed for the analysis of large volumes of sequence data. This chapter describes such data structures, called full-text indexes, to represent all substrings (or substrings up to a certain length) contained in a given text (or text collection).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Abouelhoda, M., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2, 53–86 (2004)MathSciNetCrossRefMATH Abouelhoda, M., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2, 53–86 (2004)MathSciNetCrossRefMATH
2.
Zurück zum Zitat Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer Science & Business Media, Berlin (2008)CrossRef Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer Science & Business Media, Berlin (2008)CrossRef
3.
Zurück zum Zitat Arlazarov, V., Dinic, E., Kronrod, M., Faradzev, I.: On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk 11, 194 (1970) Arlazarov, V., Dinic, E., Kronrod, M., Faradzev, I.: On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk 11, 194 (1970)
4.
Zurück zum Zitat Bauer, M.J., Cox, A.J., Rosone, G., Sciortino, M.: Lightweight LCP construction for next-generation sequencing datasets. In: Algorithms in Bioinformatics, pp. 326–337. Springer, Berlin (2012) Bauer, M.J., Cox, A.J., Rosone, G., Sciortino, M.: Lightweight LCP construction for next-generation sequencing datasets. In: Algorithms in Bioinformatics, pp. 326–337. Springer, Berlin (2012)
5.
Zurück zum Zitat Bauer, M.J., Cox, A.J., Rosone, G.: Lightweight algorithms for constructing and inverting the bwt of string collections. Theor. Comput. Sci. 483, 134–148 (2013)MathSciNetCrossRefMATH Bauer, M.J., Cox, A.J., Rosone, G.: Lightweight algorithms for constructing and inverting the bwt of string collections. Theor. Comput. Sci. 483, 134–148 (2013)MathSciNetCrossRefMATH
6.
Zurück zum Zitat Burkhardt, S., Kärkkäinen, J.: Better filtering with gapped q-grams. Fund. Inform. 56(1,2), 51–70 (2003) Burkhardt, S., Kärkkäinen, J.: Better filtering with gapped q-grams. Fund. Inform. 56(1,2), 51–70 (2003)
7.
Zurück zum Zitat Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H.P., Rivals, E., Vingron, M.: q-gram based database searching using suffix arrays. In: Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99), pp. 77–83 (1999) Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H.P., Rivals, E., Vingron, M.: q-gram based database searching using suffix arrays. In: Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99), pp. 77–83 (1999)
8.
Zurück zum Zitat Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital SRC Research Report (1994) Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital SRC Research Report (1994)
9.
Zurück zum Zitat Cazaux, B., Lecroq, T., Rivals, E.: From indexing data structures to de Bruijn graphs. In: Combinatorial Pattern Matching, pp. 89–99. Springer, Berlin (2014) Cazaux, B., Lecroq, T., Rivals, E.: From indexing data structures to de Bruijn graphs. In: Combinatorial Pattern Matching, pp. 89–99. Springer, Berlin (2014)
10.
Zurück zum Zitat Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT, Cambridge, MA (2001)MATH Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT, Cambridge, MA (2001)MATH
11.
Zurück zum Zitat Crochemore, M., Grossi, R., Kärkkäinen, J., Landau, G.M.: A constant-space comparison-based algorithm for computing the Burrows–Wheeler transform. In: Combinatorial Pattern Matching, pp. 74–82. Springer, Berlin (2013) Crochemore, M., Grossi, R., Kärkkäinen, J., Landau, G.M.: A constant-space comparison-based algorithm for computing the Burrows–Wheeler transform. In: Combinatorial Pattern Matching, pp. 74–82. Springer, Berlin (2013)
12.
Zurück zum Zitat Döring, A., Weese, D., Rausch, T., Reinert, K.: SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinf. 9, 11 (2008)CrossRef Döring, A., Weese, D., Rausch, T., Reinert, K.: SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinf. 9, 11 (2008)CrossRef
13.
Zurück zum Zitat Emde, A.K., Grunert, M., Weese, D., Reinert, K., Sperling, S.R.: MicroRazerS: rapid alignment of small RNA reads. Bioinformatics 26(1), 123–124 (2010)CrossRef Emde, A.K., Grunert, M., Weese, D., Reinert, K., Sperling, S.R.: MicroRazerS: rapid alignment of small RNA reads. Bioinformatics 26(1), 123–124 (2010)CrossRef
14.
Zurück zum Zitat Emde, A.K., Schulz, M.H., Weese, D., Sun, R., Vingron, M., Kalscheuer, V.M., Haas, S.A., Reinert, K.: Detecting genomic indel variants with exact breakpoints in single- and paired-end sequencing data using splazers. Bioinformatics 28(5), 619–627 (2012)CrossRef Emde, A.K., Schulz, M.H., Weese, D., Sun, R., Vingron, M., Kalscheuer, V.M., Haas, S.A., Reinert, K.: Detecting genomic indel variants with exact breakpoints in single- and paired-end sequencing data using splazers. Bioinformatics 28(5), 619–627 (2012)CrossRef
15.
Zurück zum Zitat Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987–1011 (2000)MathSciNetCrossRefMATH Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987–1011 (2000)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Faro, S., Lecroq, T.: The exact online string matching problem: a review of the most recent results. ACM Comput. Surv. 45(2), 13 (2013)CrossRefMATH Faro, S., Lecroq, T.: The exact online string matching problem: a review of the most recent results. ACM Comput. Surv. 45(2), 13 (2013)CrossRefMATH
18.
Zurück zum Zitat Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica 63(3), 707–730 (2012)MathSciNetCrossRefMATH Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica 63(3), 707–730 (2012)MathSciNetCrossRefMATH
19.
20.
Zurück zum Zitat Giegerich, R., Kurtz, S.: A comparison of imperative and purely functional suffix tree constructions. Sci. Comput. Program. 25, 187–218 (1995)MathSciNetCrossRefMATH Giegerich, R., Kurtz, S.: A comparison of imperative and purely functional suffix tree constructions. Sci. Comput. Program. 25, 187–218 (1995)MathSciNetCrossRefMATH
21.
Zurück zum Zitat Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. Softw. Pract. Exp. 33(11), 1035–1049 (2003)CrossRef Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. Softw. Pract. Exp. 33(11), 1035–1049 (2003)CrossRef
22.
Zurück zum Zitat Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Experimental Algorithms, pp. 326–337. Springer, Berlin (2014) Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Experimental Algorithms, pp. 326–337. Springer, Berlin (2014)
23.
Zurück zum Zitat Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378–407 (2005)MathSciNetCrossRefMATH Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378–407 (2005)MathSciNetCrossRefMATH
24.
Zurück zum Zitat Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, pp. 841–850. Society for Industrial and Applied Mathematics, Philadelphia, PA (2003) Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, pp. 841–850. Society for Industrial and Applied Mathematics, Philadelphia, PA (2003)
25.
Zurück zum Zitat Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)CrossRefMATH Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)CrossRefMATH
27.
Zurück zum Zitat Hon, W.K., Lam, T.W., Sadakane, K., Sung, W.K., Yiu, S.M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica 48(1), 23–36 (2007)MathSciNetCrossRefMATH Hon, W.K., Lam, T.W., Sadakane, K., Sung, W.K., Yiu, S.M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica 48(1), 23–36 (2007)MathSciNetCrossRefMATH
28.
Zurück zum Zitat Intel: Intel®; 64 and IA-32 Architectures Optimization Reference Manual. Intel Corporation, Santa Clara, CA (2011) Intel: Intel®; 64 and IA-32 Architectures Optimization Reference Manual. Intel Corporation, Santa Clara, CA (2011)
29.
Zurück zum Zitat Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 549–554. IEEE, New York (1989) Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 549–554. IEEE, New York (1989)
30.
Zurück zum Zitat Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, CPM ’01, pp. 181–192. Springer, Berlin (2001) Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, CPM ’01, pp. 181–192. Springer, Berlin (2001)
31.
Zurück zum Zitat Kehr, B., Weese, D., Reinert, K.: Stellar: fast and exact local alignments. BMC Bioinf. 12(Suppl. 9), S15 (2011)CrossRef Kehr, B., Weese, D., Reinert, K.: Stellar: fast and exact local alignments. BMC Bioinf. 12(Suppl. 9), S15 (2011)CrossRef
32.
Zurück zum Zitat Langmead, B., Trapnell, C., Pop, M., Salzberg, S.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 10(3), R25 (2009)CrossRef Langmead, B., Trapnell, C., Pop, M., Salzberg, S.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 10(3), R25 (2009)CrossRef
33.
Zurück zum Zitat Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics 25(14), 1754–1760 (2009)CrossRef Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics 25(14), 1754–1760 (2009)CrossRef
34.
Zurück zum Zitat Li, H., Handsaker, B., Wysoker, A., Fennell, T., Ruan, J., Homer, N., Marth, G., Abecasis, G., Durbin, R., 1000 Genome Project Data Processing Subgroup: The sequence alignment/map format and SAMtools. Bioinformatics 25(16), 2078–2079 (2009)CrossRef Li, H., Handsaker, B., Wysoker, A., Fennell, T., Ruan, J., Homer, N., Marth, G., Abecasis, G., Durbin, R., 1000 Genome Project Data Processing Subgroup: The sequence alignment/map format and SAMtools. Bioinformatics 25(16), 2078–2079 (2009)CrossRef
35.
Zurück zum Zitat Louza, F.A., Telles, G.P., Ciferri, C.D.D.A.: External memory generalized suffix and LCP arrays construction. In: Combinatorial Pattern Matching, pp. 201–210. Springer, Berlin (2013) Louza, F.A., Telles, G.P., Ciferri, C.D.D.A.: External memory generalized suffix and LCP arrays construction. In: Combinatorial Pattern Matching, pp. 201–210. Springer, Berlin (2013)
36.
Zurück zum Zitat Manber, U., Myers, E.: Suffix arrays: a new method for on-line string searches. In: SODA ’90, pp. 319–327. SIAM, Philadelphia (1990) Manber, U., Myers, E.: Suffix arrays: a new method for on-line string searches. In: SODA ’90, pp. 319–327. SIAM, Philadelphia (1990)
37.
38.
Zurück zum Zitat Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows–Wheeler transform. Theor. Comput. Sci. 387(3), 298–312 (2007)MathSciNetCrossRefMATH Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows–Wheeler transform. Theor. Comput. Sci. 387(3), 298–312 (2007)MathSciNetCrossRefMATH
41.
Zurück zum Zitat Morrison, D.R.: Patricia – practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514–534 (1968)CrossRef Morrison, D.R.: Patricia – practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514–534 (1968)CrossRef
42.
Zurück zum Zitat Navarro, G., Mäkinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), 2:1–2:61 (2007) Navarro, G., Mäkinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), 2:1–2:61 (2007)
43.
Zurück zum Zitat Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch, Bremen (2013)MATH Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch, Bremen (2013)MATH
44.
Zurück zum Zitat Puglisi, S., Smyth, W., Turpin, A.: A taxonomy of suffix array construction algorithms. In: Holub, J. (ed.) Proceedings of Prague Stringology Conference ’05, Prague, pp. 1–30 (2005) Puglisi, S., Smyth, W., Turpin, A.: A taxonomy of suffix array construction algorithms. In: Holub, J. (ed.) Proceedings of Prague Stringology Conference ’05, Prague, pp. 1–30 (2005)
45.
Zurück zum Zitat Rausch, T., Emde, A.K., Weese, D., Döring, A., Notredame, C., Reinert, K.: Segment-based multiple sequence alignment. Bioinformatics 24(16), i187–192 (2008)CrossRef Rausch, T., Emde, A.K., Weese, D., Döring, A., Notredame, C., Reinert, K.: Segment-based multiple sequence alignment. Bioinformatics 24(16), i187–192 (2008)CrossRef
46.
Zurück zum Zitat Rausch, T., Koren, S., Denisov, G., Weese, D., Emde, A.K., Döring, A., Reinert, K.: A consistency-based consensus algorithm for de novo and reference-guided sequence assembly of short reads. Bioinformatics 25(9), 1118–1124 (2009)CrossRef Rausch, T., Koren, S., Denisov, G., Weese, D., Emde, A.K., Döring, A., Reinert, K.: A consistency-based consensus algorithm for de novo and reference-guided sequence assembly of short reads. Bioinformatics 25(9), 1118–1124 (2009)CrossRef
47.
Zurück zum Zitat Schulz, M.H., Weese, D., Rausch, T., Döring, A., Reinert, K., Vingron, M.: Fast and adaptive variable order Markov chain construction. In: Crandall, K., Lagergren, J. (eds.) Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 5251, pp. 306–317. Springer, Berlin (2008)CrossRef Schulz, M.H., Weese, D., Rausch, T., Döring, A., Reinert, K., Vingron, M.: Fast and adaptive variable order Markov chain construction. In: Crandall, K., Lagergren, J. (eds.) Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 5251, pp. 306–317. Springer, Berlin (2008)CrossRef
48.
Zurück zum Zitat Schulz, M.H., Weese, D., Holtgrewe, M., Dimitrova, V., Niu, S., Reinert, K., Richard, H.: Fiona: a parallel and automatic strategy for read error correction. Bioinformatics 30(17), i356–i363 (2014)CrossRef Schulz, M.H., Weese, D., Holtgrewe, M., Dimitrova, V., Niu, S., Reinert, K., Richard, H.: Fiona: a parallel and automatic strategy for read error correction. Bioinformatics 30(17), i356–i363 (2014)CrossRef
49.
Zurück zum Zitat Shi, F.: Suffix arrays for multiple strings: a method for on-line multiple string searches. In: Jaffar, J., Yap, R. (eds.) Concurrency and Parallelism, Programming, Networking, and Security. Lecture Notes in Computer Science, vol. 1179, pp. 11–22. Springer, Berlin (1996). DOI 10.1007/BFb0027775. http://dx.doi.org/10.1007/BFb0027775 CrossRef Shi, F.: Suffix arrays for multiple strings: a method for on-line multiple string searches. In: Jaffar, J., Yap, R. (eds.) Concurrency and Parallelism, Programming, Networking, and Security. Lecture Notes in Computer Science, vol. 1179, pp. 11–22. Springer, Berlin (1996). DOI 10.1007/BFb0027775. http://​dx.​doi.​org/​10.​1007/​BFb0027775 CrossRef
50.
Zurück zum Zitat Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22(3), 549–556 (2012)CrossRef Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22(3), 549–556 (2012)CrossRef
51.
Zurück zum Zitat Siragusa, E.: Approximate string matching for high-throughput sequencing. Ph.D. thesis, Freie Universität Berlin (2015) Siragusa, E.: Approximate string matching for high-throughput sequencing. Ph.D. thesis, Freie Universität Berlin (2015)
52.
Zurück zum Zitat Siragusa, E., Weese, D., Reinert, K.: Fast and accurate read mapping with approximate seeds and multiple backtracking. Nucleic Acids Res. 41(7), e78 (2013)CrossRef Siragusa, E., Weese, D., Reinert, K.: Fast and accurate read mapping with approximate seeds and multiple backtracking. Nucleic Acids Res. 41(7), e78 (2013)CrossRef
53.
Zurück zum Zitat Siragusa, E., Weese, D., Reinert, K.: Scalable string similarity search/join with approximate seeds and multiple backtracking. In: Proceedings of the Joint EDBT/ICDT 2013 Workshops, pp. 370–374. ACM, New York (2013) Siragusa, E., Weese, D., Reinert, K.: Scalable string similarity search/join with approximate seeds and multiple backtracking. In: Proceedings of the Joint EDBT/ICDT 2013 Workshops, pp. 370–374. ACM, New York (2013)
54.
Zurück zum Zitat Ukkonen, E.: Approximate string-matching over suffix trees. In: Combinatorial Pattern Matching, pp. 228–242. Springer, Berlin (1993) Ukkonen, E.: Approximate string-matching over suffix trees. In: Combinatorial Pattern Matching, pp. 228–242. Springer, Berlin (1993)
56.
Zurück zum Zitat Weese, D.: Indices and applications in high-throughput sequencing. Ph.D. thesis, Freie Universität Berlin (2013) Weese, D.: Indices and applications in high-throughput sequencing. Ph.D. thesis, Freie Universität Berlin (2013)
57.
Zurück zum Zitat Weese, D., Schulz, M.H.: Efficient string mining under constraints via the deferred frequency index. In: Proceedings of the 8th Industrial Conference on Data Mining (ICDM ’08). LNAI, vol. 5077, pp. 374–388. Springer, Berlin (2008) Weese, D., Schulz, M.H.: Efficient string mining under constraints via the deferred frequency index. In: Proceedings of the 8th Industrial Conference on Data Mining (ICDM ’08). LNAI, vol. 5077, pp. 374–388. Springer, Berlin (2008)
58.
Zurück zum Zitat Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Symposium on Switching and Automata Theory, SWAT ’73, pp. 1–11. IEEE Computer Society, Washington (1973) Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Symposium on Switching and Automata Theory, SWAT ’73, pp. 1–11. IEEE Computer Society, Washington (1973)
Metadaten
Titel
Full-Text Indexes for High-Throughput Sequencing
verfasst von
David Weese
Enrico Siragusa
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-59826-0_2