Starý web fakulty najdete na adrese https://old.fit.cvut.cz/.

Pražský stringologický klub

V Pražském stringologickém klubu (PSC) se zabýváme zpracováním jednorozměrných řetězců, jejich efektivním ukládáním a vyhledáváním. Hlavní oblast našeho zájmu je stringologie, komprese dat a dalšími příbuzné obory.

Více o nás

Aplikace
Čemu se skupina věnuje

V poslední době se věnujeme komprimovaným datovým strukturám, které umožňují jak efektivně ukládat data, tak v nich efektivně vyhledávat. Dále řešíme různé problémy z oblasti bioinformatiky, jako je třeba vyhledávání v tzv. degenerovaných řetězcích, které reprezentují konečnou množinu velmi podobných řetězců.

Čemu se skupina věnuje?

Projekty

Efektivní vyhledávání řetězců pro Bioinformatiku

Program
Standardní projekty
Období
2019 - 2021
Popis
Index je způsob jak výrazně urychlit vyhledávání v datech, která máme k dispozici dopředu. Vytvořený index umožňuje vyhledávat vzorek v čase závislém na délce vzorku a počtu jeho výskytů. Cílem projektu je vyvinout nové algoritmy a datové struktury pro oblasti zpracovávající velká množství dat (DNA/RNA sekvence) umožňující složitější úlohy typu vyhledávání degenerativního či elastického vzorku. Přes existenci pokročilých technik pro indexu pro řetězce, stále existují výzvy v podobě speciálních typů úloh pro indexování velmi podobných řetězců (např. genomy jedinců stejného druhu), kde klasické indexační metody selhávají. Dále budou vyvinuty i metody pro online vyhledávání elastických vzorků.

Zpracování textových a stromových struktur a jejich aplikace

Program
Standardní projekty
Období
2013 - 2015
Popis
Projekt se zabývá výzkumem čtyř relativně úzce propojených oblastí: arbologií, kompresí přirozených jazyků a vybranými tématy ze stringologie a bioinformatiky. V oblasti arbologie zkoumáme nové indexovací a vyhledávací algoritmy na stromech. V bioinformatice pracujeme na řešení rychlého mapování miliónů krátkých sekvencí na DNA řetězec a indexování DNA řetězců. V oblasti komprese dat se zaměřujeme na výkonné algoritmy pro rychlou kompresi a dekompresi textu přirozeného jazyka a algoritmy pro rychlé vyhledávání v komprimovaném textu. Ve stringologii pracujeme na indexování 2D textu a na algoritmech pro identifikaci opsaných textů a zdrojových kódů, které mohou být navíc komprimované.

Všechny projekty

Analýza a zpracování řetězců a stromů

Program
Standardní projekty
Období
2009 - 2011
Popis
Informační společnost používá výsledky vyhledávání každý den a jejich význam stále roste. Vyhledávání již není omezeno na obyčejné texty. Vyžaduje se vyhledávání ve složitějších strukturách jako jsou stromy (datové struktury pro XML), 2D obrázky nebo komprimovaná data. Navrhovaný projekt si klade za cíl nejen rozšířit naše výsledky v oblasti stringologie, ale také využít naše znalosti v relativně novém oboru vyhledávajícím ve stromech, který jsme nazvali arborologie. Ve stringologii bychom rádi pokračovali v tématech jako vícerozměrné vyhledávání, hledání pravidelností v textu, vyhledávání v zobecněných řetězcích a paralelní vyhledávání. V oblasti komprese dat jsme vyvinuli algoritmy vyhledávající v komprimovaném textu. Chceme zlepšit naše současné výsledky a zaměřit se také na přibližné vyhledávání v komprimovaných datech.

Publikace

SOPanG: online text searching over a pan-genome

Autoři
Holub, J.; Cislak, A.; Grabowski, S.
Rok
2018
Publikováno
Bioinformatics. 2018, 34(24), 4290-4292. ISSN 1367-4803.
Související osoby
Typ
Článek
DOI
10.1093/bioinformatics/bty506
Anotace
Motivation: The many thousands of high-quality genomes available now-a-days imply a shift from single genome to pan-genomic analyses. A basic algorithmic building brick for such a scenario is online search over a collection of similar texts, a problem with surprisingly few solutions presented so far.

Filtering Invalid Off-Targets in CRISPR/Cas9 Design Tools

Autoři
Cvacho, O.; Holub, J.
Rok
2018
Publikováno
Proceedings of Data Compression Conference 2018. New York: IEEE Computer Society Press, 2018. p. 403. ISSN 2375-0359. ISBN 978-1-5386-4883-4.
Typ
Stať ve sborníku
DOI
10.1109/DCC.2018.00056
Anotace
The paper deals with an approximate string matching in CRISPR/Cas9 design tools. The approximate string matching is transformed into sequence of exact string matching tasks processed by fast succinct (compressed) self-index. The number of the tasks is rapidly decreased by filtering technique based on de Bruijn graph.

Všechny publikace

Reconstructing a String from its Lyndon Arrays

Autoři
Daykin, J.W.; Franek, F; Holub, J.; Smyth, W.F.; Sohidull Islam, A.S.M.
Rok
2018
Publikováno
Theoretical Computer Science. 2018, 710 44-51. ISSN 0304-3975.
Související osoby
Typ
Článek
DOI
10.1016/j.tcs.2017.04.008
Anotace
Given a string x = x[1.. n] on an ordered alphabet of size σ , the Lyndon array λ = λx [1..n] of x is an array of positive integers such that λ[i], 1 ≤ i ≤ n, is the length of the maximal Lyndon word over the ordering of that begins at position i in x. The Lyndon array has recently attracted considerable attention due to its pivotal role in establishing the long-standing conjecture that ρ (n ) < n, where ρ ( n) is the maximum number of maximal periodicities (runs) in any string of length n. Here we first describe two linear-time algorithms that, given a valid Lyndon array λ, compute a corresponding string — one for an alphabet of size n, the other for a smaller alphabet. We go on to describe another linear-time algorithm that determines whether or not a given integer array is a Lyndon array of some string. Finally we show how σ Lyndon arrays λ = {λ1 = λ, λ2 , . . . , λσ } corresponding to σ “rotations” of the alphabet can be used to determine uniquely the string x on such that λx = λ.

Towards Efficient Positional Inverted Index

Autoři
Holub, J.; Procházka, P.
Rok
2017
Publikováno
Algorithms. 2017, 10(1), ISSN 1999-4893.
Typ
Článek
DOI
10.3390/a10010030
Anotace
We address the problem of positional indexing in the natural language domain. The positional inverted index contains the information of the word positions. Thus, it is able to recover the original text file, which implies that it is not necessary to store the original file. Our Positional Inverted Self-Index (PISI) stores the word position gaps encoded by variable byte code. Inverted lists of single terms are combined into one inverted list that represents the backbone of the text file since it stores the sequence of the indexed words of the original file. The inverted list is synchronized with a presentation layer that stores separators, stop words, as well as variants of the indexed words. The Huffman coding is used to encode the presentation layer. The space complexity of the PISI inverted list is O((N−n)⌈log2bN⌉+(⌊N−nα⌋+n)×(⌈log2bn⌉+1)) where N is a number of stems, n is a number of unique stems, α is a step/period of the back pointers in the inverted list and b is the size of the word of computer memory given in bits. The space complexity of the presentation layer is O(−∑Ni=1⌈log2pn(i)i⌉−∑N′j=1⌈log2p′j⌉+N) with respect to pn(i)i as a probability of a stem variant at position i, p′j as the probability of separator or stop word at position j and N′ as the number of separators and stop words

Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Autoři
Holub, J.; Procházka, P.
Rok
2017
Publikováno
Proceedings of 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Saarbrücken: Dagstuhl Publishing,, 2017. p. 20:1-20:13. ISSN 1868-8969. ISBN 978-3-95977-050-7.
Typ
Stať ve sborníku
DOI
10.4230/LIPIcs.WABI.2017.20
Anotace
In this article, we propose a novel pattern matching algorithm, called BAPM, that performs searching in the encoded genomic sequences. The algorithm works at the level of single bytes and it achieves sublinear performance on average. The preprocessing phase of the algorithm is linear with respect to the size of the searched pattern $m$. A simple $\mathcal{O}(m)$-space data structure is used to store all factors (with a defined length) of the searched pattern. These factors are later searched during the searching phase which ensures sublinear time on average. Our algorithm significantly overcomes the state-of-the-art pattern matching algorithms in the locate time on middle and long patterns. Furthermore, it is able to cooperate very easily with the block $q$-gram inverted index. The block $q$-gram inverted index together with our pattern matching algorithm achieve superior results in terms of locate time to the current index data structures for less frequent patterns. We present experimental results using real genomic data. These results prove efficiency of our algorithm.

Technology Beats Algorithms (in Exact String Matching)

Autoři
Giaquinta, E; Holub, J.; Tarhio, J
Rok
2017
Publikováno
Software - Practice and Experience. 2017, 47(12), 1877-1885. ISSN 0038-0644.
Související osoby
Typ
Článek
DOI
10.1002/spe.2511
Anotace
More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the \naive{} algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols and the increasing order of their probabilities in the text was the best.

Kde nás najdete?

Pražský stringologický klub
Katedra teoretické informatiky
Fakulta informačních technologií
České vysoké učení technické v Praze

Místnost TH:A-1235 (Budova A, 12. patro)
Thákurova 7
Praha 6 – Dejvice
160 00

Kontaktní osoba

prof. Ing. Jan Holub, Ph.D.

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.