Wyniki wyszukiwania - BazTech

1

On Fixed Points of the Burrows-Wheeler Transform

Mantaci S., Restivo A., Rosone G., Russo F., Sciortino M.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

277--288

EN

The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of “clustering” together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet {a, b} having at most four b’s and those having at most four a’s.

2

Wyszukiwanie przybliżone sekwencji DNA z użyciem indeksu FM

Kawulok J.

Studia Informatica

|

2012

|

Vol. 33, nr 2A

493-506

PL

Artykuł opisuje nowy algorytm wyszukiwania przybliżonego zadanych fragmentów DNA w długich sekwencjach. Zgodnie z zaproponowanym podejściem poszukiwany fragment jest dzielony na nakładające się słowa, których pozycje w badanej sekwencji są wyznaczane przez użycie indeksu FM. Wykorzystując tak otrzymaną listę pozycji słów w sekwencji, poszukuje się połączeń spełniających założenie o dopuszczalnej maksymalnej liczbie różnic. Stworzony algorytm został poddany walidacji eksperymentalnej, której wyniki przedstawiono w artykule.

EN

This paper presents an algorithm for searching fragments of sequences in previously prepared DNA bases. The pattern is divided into words which overlap themselves. Their positions are found using FM-index, and they are used to search connections with each other under the assumption about a permissible maximum number of distinction.

3

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

Kajzer A., Pokrzywa R.

Studia Informatica

|

2012

|

Vol. 33, nr 1

77-89

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.

4

Searching for unique DNA sequences with the Burrows-Wheeler Transform

Pokrzywa R.

Biocybernetics and Biomedical Engineering

|

2008

|

Vol. 28, no. 1

95-104

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.