Esko Ukkonen

TCS Journal 2014 Journal Article

Motif matching using gapped patterns

• Emanuele Giaquinta
• Kimmo Fredriksson
• Szymon Grabowski
• Alexandru I. Tomescu
• Esko Ukkonen

We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length between each two consecutive strings. The problem has applications in the discovery of transcription factor binding sites in DNA sequences when using generalized versions of the Position Weight Matrix model to describe transcription factor specificities. In these models a motif can be matched as a set of gapped patterns with unit-length keywords. The existing algorithms for matching a set of gapped patterns are worst-case efficient but not practical, or vice versa, in this particular case. The novel algorithms that we present are based on dynamic programming and bit-parallelism, and lie in a middle-ground among the existing algorithms. In fact, their time complexity is close to the best existing bound and, yet, they are also practical. We also provide experimental results which show that the presented algorithms are fast in practice, and preferable if all the strings in the patterns have unit-length.

MFCS Conference 2012 Conference Paper

How to Reconstruct a Genome

• Esko Ukkonen

Abstract Since its early formulations (e. g. , [1]), the genome assembly problem has attracted lots of interest from algorithm theoretic as well as from algorithm engineering point of view. In this problem, which is an inversion problem by nature, one is asked to reconstruct the entire DNA sequence from the short, randomly picked sequence fragments that a DNA sequencing instrument is able to read [2]. With the invent of current high-throughput sequencers producing such fragment reads in massive amounts, there is in molecular biology research a pronounced call for an accurate and fast reconstruction procedure. It is customary to structure a reconstruction procedure into the following major steps: (1) Error correction of the fragments; (2) Finding pairwise overlaps between the fragments and representing the overlaps as a graph; (3) Constructing approximate superstrings, called contigs, for the fragments; (4) Constructing a linear order, called a scaffold, of the contigs. All steps are algorithmically challenging. Noisy data and intricate repetition structure of the target genome cause added difficulties. The talk attempts to give an overall picture of the genome assembly process and its algorithmic aspects emphasizing some recent developments in error correction [3], contig assembly, and scaffolding [4]. We also try to convey experiences from a major undertaking of de novo sequencing of a higher organism, Glanville fritillary butterfly Melitea cinxia. (A collaboration with I. Hanski, www. helsinki. fi/science/metapop/index. htm ).

TCS Journal 2009 Journal Article

Efficient construction of maximal and minimal representations of motifs of a string

• François Nicolas
• Veli Mäkinen
• Esko Ukkonen

Two substrings of a given text string are called synchronous (occurrence-equivalent) if their sets of occurrence locations are translates of each other. Linear time algorithms are given for the problems of finding a shortest and a longest substring that is synchronous with a given substring. We also introduce approximate variants of the motif discovery problem and give polynomial time algorithms for finding longest and shortest substrings whose suitably translated occurrence location set contains or, respectively, is contained in a given set of locations. The FFT technique used here also leads to an O ( n log n ) algorithm for finding the maximum-content gapped motif that is synchronous with a given set of locations; the previously known algorithm for this problem is only quadratic.

TCS Journal 2009 Journal Article

Maximal and minimal representations of gapped and non-gapped motifs of a string

• Esko Ukkonen

The problems of finding maximal and minimal equivalent representations for gapped and non-gapped motifs as well as finding motifs that characterize a fixed set of occurrence locations for a given string are studied. We apply two equivalence relations on representations. The first one is the well-known occurrence-equivalence of motifs. The second equivalence is introduced for patterns of occurrence locations, to characterize such patterns by motifs. For both equivalences, quadratic-time algorithms are given for finding a maximal representative of an equivalence class. Finding a minimal representative is shown to be NP-complete in both cases. For non-gapped motifs suffix-tree-based linear-time algorithms are given for finding maximal and minimal representatives. Maximal (minimal) gapped motifs are composed of blocks that are maximal (minimal) non-gapped motifs, maximal and minimal non-gapped motifs thus making up a small basis for all motifs. The implied bound on the number of gapped motifs that have a fixed number of non-gapped blocks is also given.

TCS Journal 2008 Journal Article

Fast profile matching algorithms — A survey

• Cinzia Pizzi
• Esko Ukkonen

Position-specific scoring matrices are a popular choice for modelling signals or motifs in biological sequences, both in DNA and protein contexts. A lot of effort has been dedicated to the definition of suitable scores and thresholds for increasing the specificity of the model and the sensitivity of the search. It is quite surprising that, until very recently, little attention has been paid to the actual process of finding the matches of the matrices in a set of sequences, once the score and the threshold have been fixed. In fact, most profile matching tools still rely on a simple sliding window approach to scan the input sequences. This can be a very time expensive routine when searching for hits of a large set of scoring matrices in a sequence database. In this paper we will give a survey of proposed approaches to speed up profile matching based on statistical significance, multipattern matching, filtering, indexing data structures, matrix partitioning, Fast Fourier Transform and data compression. These approaches improve the expected searching time of profile matching, thus leading to implementation of faster tools in practice.

MFCS Conference 2007 Conference Paper

Structural Analysis of Gapped Motifs of a String

• Esko Ukkonen

Abstract We investigate the structure of the set of gapped motifs (repeated patterns with don’t cares) of a given string of symbols. A natural equivalence classification is introduced for the motifs, based on their pattern of occurrences, and another classification for the occurrence patterns, based on the induced motifs. Quadratic–time algorithms are given for finding a maximal representative for an equivalence class while the problems of finding a minimal representative are shown NP–complete. Maximal gapped motifs are shown to be composed of blocks that are maximal non–gapped motifs. These can be found using suffix–tree techniques. This leads to a bound on the number of gapped motifs that have a fixed number of non–gapped blocks.

TCS Journal 2006 Journal Article

On size reduction techniques for multitape automata

• Hellis Tamm
• Matti Nykänen
• Esko Ukkonen

We present a method for size reduction of two-way multitape automata. Our algorithm applies local transformations that change the order in which transitions concerning different tapes occur in the automaton graph, and merge suitable states into a single state. Our work is motivated by implementation of a language for string manipulation in database systems where string predicates are compiled into two-way multitape automata. Additionally, we present a (one-tape) NFA reduction algorithm that is based on a method proposed for DFA minimization by Kameda and Weiner, and apply this algorithm, combined with the multitape automata reduction algorithm, on our multitape automata. Empirical results on the performance of our method when applied on some multitape automata originating from string predicates are reported.

TCS Journal 2005 Journal Article

Sequential and indexed two-dimensional combinatorial template matching allowing rotations

• Kimmo Fredriksson
• Gonzalo Navarro
• Esko Ukkonen

We present new and faster algorithms to search for a two-dimensional pattern in a two-dimensional text allowing any rotation of the pattern. This has applications such as image databases and computational biology. We consider the cases of exact and approximate matching under several matching models, using a combinatorial approach that generalizes string matching techniques. We focus on sequential algorithms, where only the pattern can be preprocessed, as well as on indexed algorithms, where the text is preprocessed and an index built on it. On sequential searching we derive average-case lower bounds and then obtain optimal average-case algorithms for all the matching models. At the same time, these algorithms are worst-case optimal. On indexed searching we obtain search time polylogarithmic on the text size, as well as sublinear time in general for approximate searching.

TCS Journal 2004 Journal Article

Bideterministic automata and minimal representations of regular languages

• Hellis Tamm
• Esko Ukkonen

Bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. It has been known that a bideterministic automaton is the minimal deterministic automaton accepting its language. This paper shows that any bideterministic automaton is the unique minimal automaton among all (including nondeterministic) automata accepting the same language. We also present a more general result that shows that under certain conditions a minimal deterministic automaton accepting some language or the reversal of the minimal deterministic automaton of the reversal language is a minimal automaton representation of the language. These conditions can be checked in polynomial time.

TCS Journal 1997 Journal Article

On the equivalence problem for E-pattern languages

• Enno Ohlebusch
• Esko Ukkonen

On the one hand, the inclusion problem for nonerasing and erasing pattern languages is undecidable (see Jiang et al. , 1995). On the other hand, the language equivalence problem for nonerasing pattern languages is trivially decidable (see Angluin, 1980) but the question of whether the same holds for erasing pattern languages is still open. It has been conjectured by Jiang et al. that the language equivalence problem for erasing pattern languages is also decidable. In this paper, we introduce a new normal form for patterns and show, using the normal form, that the language equivalence problem for erasing pattern languages is decidable in many special cases. We conjecture that our normal form procedure decides the problem in the general case, too. If the conjecture holds true, then the normal form is the shortest pattern generating a given erasing pattern language.

MFCS Conference 1996 Conference Paper

On the Equivalence Problem for E-Pattern Languages

• Enno Ohlebusch
• Esko Ukkonen

Abstract On the one hand, the inclusion problem for nonerasing and erasing pattern languages is undecidable; see [JSSY95]. On the other hand, the language equivalence problem for NE-pattern languages is trivially decidable (see [Ang80a]) but the question of whether the same holds for E-pattern languages is still open. It has been conjectured by Jiang et al. [JSSY95] that the language equivalence problem for E-pattern languages is also decidable. In this paper, we introduce a new normal form for patterns and show, using the normal form, that the language equivalence problem for E-pattern languages is decidable in many special cases. We conjecture that our normal form procedure decides the problem in the general case, too. If the conjecture holds true, then the normal form is the shortest pattern generating a given E-pattern language.

SODA Conference 1994 Conference Paper

Two and Higher Dimensional Pattern Matching in Optimal Expected Time

• Juha Kärkkäinen
• Esko Ukkonen

TCS Journal 1992 Journal Article

Approximate string-matching with q-grams and maximal matches

• Esko Ukkonen

We study approximate string-matching in connection with two string distance functions that are computable in linear time. The first function is based on the so-called q-grams. An algorithm is given for the associated string-matching problem that finds the locally best approximate occurrences of pattern P, ∣P∣ = m, in text T, ∣T∣ = n, in time O(n log (m–q)). The occurrences with distance ⩽k can be found in time O(n log k). The other distance function is based on finding maximal common substrings and allows a form of approximate string-matching in time O(n). Both distances give a lower bound for the edit distance (in the unit cost model), which leads to fast hybrid algorithms for the edit distance based string-matching.

MFCS Conference 1991 Conference Paper

Two Algorithms for Approximate String Matching in Static Texts

• Petteri Jokinen
• Esko Ukkonen

Abstract The problem of finding all approximate occurrences P′ of a pattern string P in a text string T such that the edit distance between P and P′ is ≤ k is considered. We concentrate on a scheme in which T is first preprocessed to make the subsequent searches with different P fast. Two preprocessing methods and the corresponding search algorithms are described. The first is based suffix automata and is applicable for edit distances with general edit operation costs. The second is a special design for unit cost edit distance and is based on q -gram lists. The preprocessing needs in both cases time and space O (| T |). The search algorithms run in the worst case in time O (| P || T |) or O ( k | T |), and in the best case in time O (| P |).

TCS Journal 1988 Journal Article

A greedy approximation algorithm for constructing shortest common superstrings

• Jorma Tarhio
• Esko Ukkonen

An approximation algorithm for the shortest common superstring problem is developed, based on the Knuth-Morris-Pratt string-matching procedure and on the greedy heuristics for finding longest Hamiltonian paths in weighted graphs. Given a set R of strings, the algorithm constructs a common superstring for R in O(mn) steps where m is the number of strings in R and n is the total length of these strings. The performance of the algorithm is analysed in terms of the compression in the common superstrings constructed, that is, in terms of n−k where k is the length of the obtained superstring. We show that (n−k)⩾ 1 2 (n−kmin) where k min is the length of a shortest common superstring. Hence the compression achieved by the algorithm is at least half of the maximum compression. It also seems that the lengths always satisfy k⩽2·k min but proving this remains open.

MFCS Conference 1986 Conference Paper

A Greedy Algorithm for Constructing Shortest Common Superstrings

• Jorma Tarhio
• Esko Ukkonen

Abstract An algorithm for constructing shortest common superstrings for a given set R of strings is developed, based on Knuth-Morris-Pratt string matching procedure and on the greedy heuristics for finding longest Hamiltonian paths in weighted graphs. The algorithm runs in O ( mn + m 2 log m ) steps where m is the number of strings in R and n is the total length of these strings. The compression in the common superstring constructed by the algorithm is shown to be at least half of the compression in a shortest superstring.

TCS Journal 1982 Journal Article

Structure preserving elimination of null productions from context-free grammars

• Esko Ukkonen

A method is presented for the elimination of null productions from a context-free grammar in such a way that the resulting grammar covers the original one, that is, the languages generated are the same and parses in the original grammar are homomorphic images of equivalent parses in the covering grammar. We show that in a natural subclass of covers, called the class of compatible covers, the method is best possible in the sense that a compatible cover with no null productions can be produced by the method if and only if such a cover exists. The use of the method in transformations for obtaining a cover in Greibach normal form is finally analyzed.

STOC Conference 1981 Conference Paper

LALR(k) Testing is PSPACE-Complete

• Esko Ukkonen
• Eljas Soisalon-Soininen

TCS Journal 1981 Journal Article

The shortest common supersequence problem over binary alphabet is NP-complete

• Kari-Jouko Räihä
• Esko Ukkonen

We consider the complexity of the Shortest Common Supersequence (SCS) problem, i. e. the problem of finding for finite strings S 1, S 2, …, S u a shortest string S such that every Si can be obtained by deleting zero or more elements from S. The SCS problem is shown to be NP-complete for strings over an alphabet of size ⩾ 2.

STOC Conference 1980 Conference Paper

A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata

• Esko Ukkonen

A generalization of the alternate stacking procedure of Valiant for deciding the equivalence of some deterministic pushdown automata (dpda) is introduced. To analyze the power of the generalized procedure we define a subclass of dpda's, called the proper dpda's. This class properly contains the non-singular dpda's and the real time strict dpda's, and the corresponding class of languages properly contains the real time strict deterministic languages. The equivalence problem for proper automata is reducible to the problem of deciding whether or not an automaton is proper. The main result of the paper is that the generalized procedure yields an equivalence test for proper dpda's, at least one of which is also a finite-turn machine.

MFCS Conference 1978 Conference Paper

Tranformations to Produce Certain Covering Grammars

• Esko Ukkonen

Abstract Two grammatical transformations are presented for producing a context-free grammar which left-to-right covers the original grammar. The first transformation can be used to transform grammars in an extensive subclass of the non-right-recursive grammars into covering grammars which are in Greibach normal form. The second transformation converts a subclass of LR(0) grammars into covering grammars which are strict deterministic. This transformation is further extended to produce a covering strict deterministic grammar for all LR(0) grammars.