Abstract

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 (Dr.Eng., 1973, Univ. of Naples) is Professor of Computer Engineering at U. of Padova and Professor of Computer Sciences at Purdue University. A Fulbright Scholar in 1974-75 at CMU, held visiting and permanent positions in the U.S. and Europe A Full Prof. in Italy since 87, at DEI since 92, his research interests are in algorithmic analysis and design, with emphasis on pattern matching, on which subject he has co-authored more than 100 papers, and co-authored/edited 7 volumes. He serves on the Editorial Boards of Theor.Comp.Sci., Par.Proc.Let., J.of Comp.Biol., Chaos Th. and Appl.,Springer Lecture Notes in Bioinformatics, Algorithmica (g.e.). Keynote at over 60, PC Member for over 50 international Conferences, he has been a Reviewer for NSF, Canadian SERC, NATO, HSFP, Finland Acad Sci., HongKong and Israel Science Councils.