Searching for unique DNA sequences with the Burrows-Wheeler Transform

• Autorzy: Pokrzywa R.
• Języki publikacji: EN

Abstrakty

EN

The objective of this study was to present an efficient algorithm that effectively aids the problem of searching for unique DNA sequences in the set of genes. The presented algorithm is based on the Burrows-Wheeler Transform (BWT), a very fast and effective data compression algorithm. The developed algorithm exploits all the advantages offered by the BWT algorithm and the suffix array data structure. It allows obtaining a structure that is ideal for solving many problems related to the pattern-matching problem. This algorithm is applicable to the identification of yeast species as well as to many other computational molecular biology problems like searching for repetitive structures in genomic sequences, designing of DNA hybridization probes and many more.

Słowa kluczowe

EN

Burrows-Wheeler transform; yeasts species; suffix array; longest common prefix

PL

transformata Burrowsa-Wheelera; tablica sufiksowa; prefiks wspólny

• Wydawca: Nałęcz Institute of Biocybernetics and Biomedical Engineering of the Polish Academy of Sciences ; Elsevier
• Czasopismo: Biocybernetics and Biomedical Engineering
• Rocznik: 2008
• Tom: Vol. 28, no. 1
• Strony: 95--104
• Opis fizyczny: Bibliogr. 9 poz., rys., tab., wykr.

Twórcy

autor

Pokrzywa R.

• Department of Computer Science, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland,

Bibliografia

• 1. Wesselink J.-J. at el.: Determining a unique defining DNA sequence for yeast species using hashingm techniques, Bioinformatics, 2002, 18, 1004-1010.
• 2. Schuler G. D.: Sequence Mapping by Electronic PCR, Genome Research, 1997, 7, 541-550.
• 3. Sugita T., Nishikawa A.: Fungal Identification Method Based on DNA Sequence Analysis: Reassessment of the Methods of the Pharmaceutical Society of Japan and the Japan Pharmacopoeia, Journal of Health Science, 2003, 531-533.
• 4. Kurtzman C. P., Robnett C. J.: Identification and phylogeny of ascomycetous yeasts from analysis of nuclear large subunit (26S) ribosomal DBA partial sequence, Antonie Van Leeuwenhoek, 1998, 331-371.
• 5. Lachance M.A. at el.: The D1/D2 domain of the large-subunit rDNA of the yeast species Clavispora lusitaniae is unusually polymorphic, FEMS Yeast Research, 2003, 253-258.
• 6. Burrows M., Wheeler D.J.: A Block-sorting Lossless Data Compression Algorithm, Technical Report 124, Digital Equipment Corporation, 1994.
• 7. Deorowicz S.: Universal lossless data compression algorithms, Doctor of Philosophy Dissertation, Silesian University of Technology, 2003, 31-45.
• 8. Powell M.: Compressed-Domain Pattern Matching with the Burrows-Wheeler Transform, Honours Project Report, 2001, 7-14, 19-22.
• 9. Gusfield D.: Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, 151-154.