Algodan > Combinatorial Pattern Matching

The combinatorial pattern-matching team of professor Esko Ukkonen develops combinatorial algorithms for pattern search and synthesis problems for sequential and higher-dimensional data. The team is interested in the basic research of the theoretical aspects of the area as well as in various applications. In applications, the team works on genome structure, metabolic modelling, gene regulation, music information retrieval, and language technology.


Combinatorial Pattern Matching Algorithms and Applications

The Combinatorial Pattern Matching Algorithms and Applications group develops theoretical concepts, models, and algorithms for sequence-related problems from biological sequence analysis and other areas. The algorithm-theoretic research is complemented by application-oriented work which is done in close collaboration with many groups of biologists who provide up-to-date problems and new data to be analyzed using the new methods developed in the group.

Succinct Data Structures (SuDS)

The study of succinct data structures extends traditional data compression with the functionality preserving property: data structure functions need to be efficiently computable directly from the compressed representation. In addition to providing and analyzing new succinct data structures, the group contributes by engineering open source implementations targeted to applications especially in biological sequence analysis and information retrieval.

Practical Algorithms on Strings

The group develops fast and practical algorithms and data structures for fundamental problems arising in sequence analysis. The research is based on thorough understanding of both the combinatorial properties of the problems and the properties of modern computers. The goal is not only to obtain better algorithms but to understand why they are better.

Computational Geometry

Geometric data analysis, visualization and processing are inherent to numerous domains ranging from motion planning to VLSI to geographic information systems to robotics. We design, analyze, and implement computational-geometry algorithms applicable to current and future tasks in intelligent path design, cartography, shape reconstruction and sensor networks.


The C-BRAHMS (Content-Based Retrieval and Analysis of Harmony and other Music Structures) project aims at designing and developing efficient methods for computational problems arising from music comparison, retrieval, and analysis. The main concentration is on retrieving polyphonic music in large scale music databases containing symbolically encoded music. The project utilizes various algorithmic techniques together with findings in musicology and music psychology to achieve efficient, musically meaningful results.

Document Mining and Linguistic Analysis Group (Domila)

The Domila group works on problems related to analysis of linguistic data. We investigate how language conveys information, how information can be extracted from linguistic data, and how hidden structure can be learned from observed linguistic data. The objectives are to investigate and model linguistic phenomena in the context of real-world applications. The research programme combines empirical, applied and theoretical approaches to the main problems.