#### (équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 04 décembre 2013 à 10h30 en B107, Uno Takeaki nous parlera de : **A New Approach to String Pattern Mining with Approximate Match***Résumé :* Frequent string mining is the problem of finding frequently appearing
strings in a given string database or large text.
It has many applications to string data analysis on strings such as texts,
word sequences, and genome sequences.
The problem becomes difficult if the string patterns are allowed to match
approximately, i.e., a fixed number of errors leads to an explosion
in the number of small solutions, and a fixed ratio of errors violates
the monotonicity that disables hill climbing algorithms, and thus
makes searching difficult.
There would be also a difficulty on the modeling of the problem;
simple mathematical definitions would result explosion of the solutions.
To solve this difficulty, we go back to the motivations to find frequent
strings, and propose a new method for generating string patterns
that appear in the input string many times.
In the method, we first compute the similarity between the strings
in the database, and enumerate clusters generated by similarity.
We then compute representative strings for each cluster, and the
representatives are our frequent strings.
Further, by taking majority votes, we extend the obtained representatives
to obtain long frequent strings.
The computational experiments we performed show the efficiency of both
our model and algorithm; we were able to find many string
patterns appearing many times in the data, and that were long but
not particularly numerous.
The computation time of our method is practically short, such as
20 minutes even for a genomic sequence of 100 millions of letters.