Asymptotic Average Profiles, from Tries to Suffix-trees
Speaker: Pierre Nicodeme , (CNRS)Laboratoire dContact:
Date: May 22 2006
Time: 11:30AM to 1:00PM
Location: TOC Lab 32-G575
Host: P Clote-BC & B Berger- MIT
Kathleen Dickey, 617 253 3037, firstname.lastname@example.orgRelevant URL: http://www-math.mit.edu/compbiosem
We build upon previous work of Julien Fayolle (2004) and Park and
to study asymptotically the average internal profiles of tries and of
suffix-trees. The binary keys and the strings are built from a Bernoulli source $(p,q)$.
We consider the average number of internal nodes at depth $k=O(\log(n))$ of
a trie whose number of input keys (i) is a fixed number $n$
or (ii) follows a Poisson law of parameter $n$.
In both cases we obtain a summation formula with $2^k$ terms; there is
an excellent agreement of the fixed case formula for the trie and
simulations for a suffix-tree with an equivalent number of keys.
When $n$ and $k$ tend to infinity, we get rid of the summation in the
Poisson case by Mellin transform.
The inverse Mellin transform is performed by a saddle-point
integration and depoissonization by a Ramanujan expansion.
This gives, for the trie,
(a) an asymptotic estimate for the average
profile in the Poisson model,
(b) an asymptotic bound of the difference between the fixed case
and the Poisson case.
We end the proof by asymptotically bounding the difference of the profile of
trie in the Poisson model and the suffix-tree.
Department of Mathematics
& The Theory of
See other events that are part of Bioinformatics Seminar Series 2005/2006
See other events happening in May 2006