The research group with almost two-decade tradition started with ordinary pattern matching tasks. However, in accordance with development in other research areas new and more challenging tasks in stringology are being solved.
Current tasks being successfully solved include storage and indexing high volumes of similar data. Such tasks come from bioinformatics and are connected with development of high-throughput sequencing machines.

Prof. Ing. Jan Holub,, +420-22435-9814


  • prof. Ing. Bořivoj Melichar, DrSc.
  • Ing. Miroslav Balík, Ph.D.
  • Ing. Ondřej Guth, Ph.D. (stromové algoritmy, algoritmy na vyhledávání pravidelností v řetězcích)
  • doc. Ing. Jan Janoušek, Ph.D. (stromové algoritmy, překladače)
  • Ing. Luboš Krčál, (komprese dat, deduplikace, similarity search)
  • Ing. Radomír Polách
  • Ing. Petr Procházka, Ph.D., (komprese přirozeného textu, selfindexes)
  • Ing. Jan Trávníček (stromové algoritmy)
  • Ing. Ladislav Vagner, Ph.D.
  • Ing. Jan Žďárek, Ph.D.


  • DNA/RNA and protein sequence processing
  • Exact and approximate string matching
  • Full-text indexing
  • Lossless data compression
  • Natural language text compression and indexing
  • Pattern matching in compressed texts




GA13-03253S (Czech Science Foundation): Text and Tree Structures Processing and Their Applications, main investigator: doc. Ing. Jan Holub, Ph.D., 02/2013 - 12/2015.
GA201/09/0807 (Czech Science Foundation): String and Tree Analysis and Processing, main investigator: doc. Ing. Jan Holub, Ph.D., 01/2009 - 12/2011.

LAHODA, J. and ŽĎÁREK, J.: Simple Tree Pattern Matching for Trees in the Prefix Bar Notation. Discrete Applied Mathematics, 2014, 163(3), 343-351. ISSN 0166-218X.
PROCHÁZKA, P. and HOLUB, J.: Compression of a Set of Files with Natural Language Content. Computer Journal, 2014, ISSN 0010-4620. Published on-line.
PROCHÁZKA, P. and HOLUB, J.: Compressing Similar Biological Sequences using FM-index. In: Proceedings of Data Compression Conference 2014, IEEE, 2014, pp. 312-321. ISSN 1068-0314. ISBN 978-1-4799-3882-7.
NA, J. C., PARK, H., CROCHEMORE, M., HOLUB, J., ILIOPOULOS, C.S.,  MOUCHARD, L., and PARK, K.: Suffix Tree of Alignment: An Efficient Index for Similar Data. In: Proceedings of the 24th Workshop on Combinatorial Algorithms (IWOCA 2013), Springer, 2013, LNCS 8288, pp. 337-348. ISBN 978-3-642-45277-2.
PROCHÁZKA, P. and HOLUB, J.: ODC: Frame for definition of Dense codes. European Journal of Combinatorics, 2013, 34(1), 52-68. ISSN 0195-6698.
HOLUB, J.: The Finite Automata Approaches in Stringology. Kybernetika, 2012, 48(3), 386-401. ISSN 0023-5954.
HOLUB, J.: Finite Automata in Pattern Matching. In: Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, Wiley, 2011, pp. 51-71. ISBN 978-0-470-50519-9.
ŽĎÁREK, J. and MELICHAR, B.: Tree-Based 2D Indexing. International Journal of Foundations of Computer Science, 2011, 22(8), 1893-1907. ISSN 0129-0541.
FLOURI, T., HOLUB, J., ILIOPOULOS, C.S., and PISSIS, S.: An algorithm for mapping short reads to a dynamically changing genomic sequence. In: 2010 IEEE International Conference on Bioinformatics and Biomedicine, IEEE, 2010, pp. 133-136. ISBN 978-1-4244-8305-1.


Last modified: 20.11.2014, 15:53