SEECS Colloquium

The problem of characterizing and detecting recurrent sequence patterns such as substrings or motifs and related associations or rules is variously pursued in order to compress data, unveil structure, infer succinct descriptions, extract and classify features, etc. In Molecular Biology, such regularities have been implicated in various facets of biological function and structure. The discovery, particularly on a massive scale, of significant patterns and correlations thereof poses interesting methodological and algorithmic problems, and often exposes scenarios in which tables and descriptors grow faster and bigger than the phenomena they are meant to encapsulate. This talk reviews some results at the crossroads of statistics, pattern matching and combinatorics on words that enable us to control such paradoxes, and presents related constructions, implementations and empirical results.

Alberto Apostolico earned his Dr. Eng. degree (cum laude) in Electronics Engineering from the University of Naples in 1973, and the Diploma of Specialisation in Computer Science (cum laude) from the University of Salerno in 1976.

A Fulbright Scholar in 1974-75 at Carnegie-Mellon University, he has visited extensively and held positions at institutions in the U.S. (University of Illinois at Urbana-Champaign, Rensselaer Polytechnic Institute, Purdue University, IBM T.J. Watson Center) and Europe (IASI-CNR in Rome, University of Paris, University of London, King's College London).

Prior to joining Purdue CS in 1983 as an Associate and then Full Professor, he was an Associate Professor with the Department of Computer Science of the University of Salerno, Italy. In 1987, he became a Professor of Computer Science in the Italian University System. He joined the Dept. of Electronics and Informatics at U. of Padova, Italy, in 1992, and he holds there the Chair of Theoretical Computer Science in the School of Engineering.

His main research interests are in the area of analysis and design of algorithms. His recent work focuses on pattern matching and discovery algorithms and applications, notably, to computational molecular biology. On this and more in general on string algorithmics he has published extensively and co-edited with Z. Galil the books ``Combinatorial Algorithms on Words'' (Springer, 1985) and ``Pattern Matching Algorithms'' (Oxford U.Press, 1996).

He serves on the editorial boards of Theoretical Computer Science, Parallel Processing Letters, Journal of Computational Biology, Chaos Theory and Applications, and was a guest editor of a special issue of Algorithmica devoted to String Algorithmics and its Applications. He has been Keynote Speaker or Lecturer at over 40 International Conferences and Advanced Schools, and on the Program Committee of about as many International Conferences and workshops.

He was a co-founder (with F.P. Preparata, H.Wang Professor of CS-Brown) of the Fibonacci Institute for Theoretical Computer Science (Trento, Italy; 1987-1994) and (with R. De Millo, former CTO - HP) of a joint SE Program between U.of Padova and Purdue-Serc (1993-1999). With M. Crochemore (Paris), Z. Galil (Columbia) and U. Manber (Yahoo), he established the series of International Colloquia on ``Combinatorial Pattern Matching (CPM)'' , now in its 13th edition under the Founder's Steering Committee. The recipient or co-recipient of U.S., French, British, Italian, and International (Fulbright, NATO, ESPRIT) research grants, Dr. Apostolico also served as Referee/Reviewer for most TCS Journals and major conferences, NSF, Canadian SERC, NATO, Israel Science Council, Eurandom, the HongKong and the Finnish Sci. Acad., among others.