Wyszukiwanie dokładne i przybliżone ciągów tekstowych z wykorzystaniem transformaty Burrowsa Wheelera

• Autorzy: Kajzer, A. , Pokrzywa, R.

Warianty tytułu

EN

The exact and approximate string matching with Burrows-Wheeler transform

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł przedstawia sposoby rozwiązywania problemu wyszukiwania dokładnego i przybliżonego ciągów tekstowych z wykorzystaniem transformaty Burrowsa-Wheelera. Omówione zostało także działanie skompresowanych indeksów pełnotekstowych, dzięki którym algorytmy wyszukiwania tekstu moŹgą działać w ograniczonej przestrzeni. Głównymi strukturami danych, które zostały opisane w tekście, są Wavelet Tree oraz Bi-directional Burrows-Wheeler Transform.

EN

This paper describes how the problem of exact and approximate string matching can be resolved using Burrows-Wheeler Transform. The paper considers how compressed full-text indexes work and allow string matching algorithms to operate in a limited space. Two main data structures presented in the text are Wavelet Tree and Bi-directional Burrows Wheeler Transform.

Słowa kluczowe

PL

transformata Burrowsa-Wheelera; wyszukiwanie ciągów tekstowych

EN

Burrows-Wheeler transform; string matching

• Czasopismo: Studia Informatica
• Rocznik: 2012
• Tom: Vol. 33, nr 1
• Strony: 77-89
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Kajzer, A.

autor

Pokrzywa, R.

• Politechnika Śląska, Instytut Informatyki, Gliwice, Akademicka 16, pokój 412,

Bibliografia

• 1. Manber U., Myers G.: Suffix arrays: a new method for on-line string searches. Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, 1991, p. 319-327.
• 2. Boyer R. S., Moore J. S.: A fast string searching algorithm. Commun. ACM, Vol. 20, No. 10, 1977, p. 762-772.
• 3. Hall P., Dowling G. R.: Approximate String Matching. ACM Comput. Surv., Vol. 12, No. 4, 1980, p. 381-402.
• 4. Levenshtein V.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, Vol. 10, 1966, p. 707.
• 5. Russo L., Navarro G., Oliveira A., Morales P.: Approximate String Matching with Compressed Indexes. Algorithms, Vol. 2, No. 3, 2009, p. 1105-1136.
• 6. Karkkainen J.: Fast BWT in Small Space by Blockwise Suffix Sorting. Theoretical Computer Science, Vol. 386, Issue 3, 2007, p. 249-257.
• 7. Burrow M., Wheeler D.J.: A Block-sorting lossless data compression algorithm. Technical Report 124, Digital SRC Research Report, 1994.
• 8. Ferragina P., Manzini G.: An experimental study of a compressed index. Information Sciences: special issue on "Dictionary Based Compression", 135, 2001, p. 13-28.
• 9. Langmead B.: Bowtie: A Highly Scalable Tool for Post-Genomic Datasets. National Center for Biotechnology Information Seminar, November 10, 2008.
• 10. Simpson J., Durbin R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics, Vol. 26, No. 12, 2010, p. i367-i373.
• 11. Schnattinger T, Ohlebusch E., Gog S.: Bidirectional Search in a String with Wavelet Trees. Combinatorial Pattern Matching, Vol. 6129, 2010, p. 40-50.
• 12. Navarro G.: A guided tour to approximate string matching. ACM Comput. Surv., Vol. 33, No. 1,2001, p. 31-88.
• 13. Li H., Durbin R.: Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics (Oxford, England), Vol. 25, No. 14., 2009, p. 1754-1760.
• 14. Lam T., Li R., Tarn A., Wong S., Wu E., Yiu S.: High Throughput Short Read Alignment via Bi-directional BWT. IEEE International Conference on Bioinformatics and Biomedicine, 2009, p. 31-36.
• 15. Wu S., U. Manber U.: Fast text searching allowing errors. Commun. ACM, Vol. 35, No. 10, 1992,p.83-91.
• 16. Langmead B.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology, Vol. 10, No. 3, 10:R25, 2009.
• 17. Navarro G.: Indexing methods for Approximate String Matching. IEEE Data Engineering Bulletin, Vol. 24, No. 4, 2001, p. 19-24.
• 18. Pokrzywa R., Polahski A.: Exact string matching with Burrows-Wheeler transform. Krajowa Konferencja Zastosowaii Matematyki w Biologii i Medycynie, Koninki, 26-29 September 2006.
• 19. Pokrzywa R., Polahski A.: BWtrs: A tool for searching for tandem repeats in DNA sequences based on the Burrows-Wheeler transform. Genomics, vol. 96(5), 2010, p. 316-321.
• 20. Sellers, Peter H.: The Theory and Computation of Evolutionary Distances: Pattern Recognition. Journal of Algorithms 1 (4), 1980, p. 359-373.