# CSAIL Event Calendar: Previous Series

 Asymptotic Average Profiles, from Tries to Suffix-treesSpeaker: Pierre Nicodeme , (CNRS)Laboratoire dDate: May 22 2006 Time: 11:30AM to 1:00PM Location: TOC Lab 32-G575Host: P Clote-BC & B Berger- MITContact: Kathleen Dickey, 617 253 3037, kvdickey@mit.eduRelevant URL: http://www-math.mit.edu/compbiosemWe build upon previous work of Julien Fayolle (2004) and Park and Szpankowski (2005) 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. MIT Department of Mathematics & The Theory of Computation Group at CSAILSee other events that are part of Bioinformatics Seminar Series 2005/2006See other events happening in May 2006