Alberto Apostolico - Böcker

Issues of matching and searching on elementary discrete structures arise pervasively in computer science and many of its applications, and their relevance is expected to grow as information is amassed and shared at an accelerating pace. Several algorithms were discovered as a result of these needs, which in turn created the subfield of Pattern Matching. This book provides an overview of the current state of Pattern Matching as seen by specialists who have devoted years of study to the field. It covers most of the basic principles and presents material advanced enough to faithfully portray the current frontier of research. Because of these recent advances, this is the right time for a book that brings together information relevant to both graduate students and specialists in need of an in-depth reference.

The papers contained in this volume were presented at the 11th Conference on String Processing and Information Retrieval (SPIRE), held Oct. 5-8, 2004 at the Department of Information Engineering of the University of Padova, Italy. They wereselected from 123 paperssubmitted in responseto the call for papers. In addition, there were invited lectures by C.J. van Rijsbergen (University of Glasgow, UK) and Setsuo Arikawa (Kyushu University, Japan). In view of the large number of good-quality submissions, some were accepted this year also as short abstracts. These also appear in the proceedings. Papers solicited for SPIRE 2004 were meant to constitute original contri- tions to areas such as string pattern searching, matching and discovery; data compression; text and data mining; machine learning; tasks, methods, al- rithms, media, and evaluation in information retrieval; digital libraries; and - plications to and interactions with domains such as genome analysis,speech and naturallanguageprocessing,Web links and communities, and multilingual data. SPIRE has its origins in the South American Workshop on String Proce- ing which was ?rst held in 1993.Starting in 1998, the focus of the symposium was broadened to include the area of information retrieval due to the common emphasisoninformationprocessing.The?rst10meetingswereheldinBeloH- izonte (Brazil, 1993), Valparaiso (Chile, 1995), Recife (Brazil, 1996), Valparaiso (Chile, 1997), Santa Cruz (Bolivia, 1998), Cancun (Mexico, 1999), A Coruna " (Spain, 2000), Laguna San Rafael (Chile, 2001), Lisbon (Portugal, 2002), and Manaus (Brazil, 2003).

The 16th Annual Symposium on Combinatorial Pattern Matching was held on Jeju Island, Korea on June 19-22, 2005. Previous meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway,Warwick,Montreal,Jerusalem,Fukuoka, Morelia,and Istanbul over the years 1990-2004. In response to the call for papers, CPM 2005 received a record number of 129papers.Eachsubmissionwasreviewedbyatleast threeProgramCommittee members with the assistance of external referees. Since there were many hi- quality papers, the Program Committee's task was extremely di?cult. Through an extensive discussion the Program Committee accepted 37 of the submissions tobepresentedattheconference.Theyconstituteoriginalresearchcontributions in combinatorial pattern matching and its applications. Inadditiontotheselectedpapers,CPM2005hadthreeinvitedpresentations, by Esko Ukkonen from the University of Helsinki, Ming Li from the University of Waterloo, and Naftali Tishby from The Hebrew University of Jerusalem.We would like to thank all Program Committee members and external r- erees for their excellent work, especially given the demanding time constraints; they gave the conference its distinctive character. We also thank all who s- mitted papers for consideration; they all contributed to the high quality of the conference. Finally, we thank the Organizing Committee members and the graduates- dents who worked hard to put in place the logistical arrangements of the c- ference. It is their dedicated contribution that made the conference possible and enjoyable.

This volume contains the papers presented at the 10th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2006), which was held in Venice, Italy, on April 2-5, 2006. The RECOMB conference serieswasstartedin1997bySorinIstrail,PavelPevznerandMichaelWaterman. The table on p. VIII summarizes the history of the meetings. RECOMB 2006 was hosted by the University of Padova at the Cinema Palace of the Venice Convention Center, Venice Lido, Italy. It was organized by a committee chaired by Concettina Guerra. A special 10th Anniversary Program Committee was formed, by including the members of the Steering Committee and inviting all Chairs of past editions. The Program Committee consisted of the 38 members whose names are listed on a separate page. From212submissionsofhighquality,40paperswereselectedforpresentation atthemeeting,andtheyappearintheseproceedings.Theselectionwasbasedon reviewsandevaluationsproducedbytheProgramCommitteemembersaswellas byexternalreviewers,andonasubsequentWeb-basedPCopenforum.Following thedecisionmadein2005bytheSteeringCommittee,RECOMBProceedingsare published as a volume of Lecture Notes in Bioinformatics (LNBI), which is - editedbythefoundersofRECOMB.Traditionally,theJournalofComputational Biology devotes a special issue to the publication of archival versions of selected conference papers. RECOMB 2006 featured seven keynote addresses by as many invited spe- ers: Anne-Claude Gavin (EMBL, Heidelberg, Germany), David Haussler (U- versity of California, Santa Cruz, USA), Ajay K. Royyuru (IBM T.J. Watson ResearchCenter, USA), David Sanko? (University of Ottawa,Canada), Michael S. Waterman (University of Southern California, USA), Carl Zimmer (Science Writer, USA), Roman A. Zubarev (Uppsala University, Sweden). The Stanislaw Ulam Memorial Computational BiologyLecture was given by Michael S. Wat- man. A special feature presentation was devoted to the 10th anniversary and is included in this volume.

This book constitutes the refereed proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002, held in Fukuoka, Japan, in July 2002. The 21 revised full papers presented together with two invited contributions were carefully reviewed and selected from 37 submissions. The papers are devoted to current theoretical and computational aspects of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. Among the application fields are the World Wide Web, computational biology, computer vision, multimedia, information retrieval, data compression, and pattern recognition.

This volume contains the 22 papers accepted for presentationat the Third Annual Symposium on Combinatorial PatternMatching held April 29 to May 1, 1992, in Tucson, Arizona;it constitutes the first conference proceedings entirelydevoted to combinatorial pattern matching (CPM).CPM deals withissues of searching and matching of stringsand other more complicated patterns such as trees, regularexpressions, extended expressions, etc. in order to derivecombinatorial properties for such structures. As aninterdisciplinary field of growing interest, CPM is relatedto research in information retrieval, pattern recognition,compilers, data compression, and program analysis as well asto results, problems and methods from combinatorialmathematics and molecular biology.

The papers contained in this volume were presented at the 4th Annual Symposium on Combinatorial Pattern Matching, held in Padova, Italy, in June 1993. Combinatorial pattern matching addresses issues of searching and matching of strings and more complicated patterns such as trees, regular expressions and extended expressions. The goal is to derive non-trivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. The area is expected to grow further due to the increasing demand for speed and efficiency that comes especially from molecular biology and the Genome Project, but also from such diverse areas as information retrieval, pattern recognition, compilers, data compression and program analysis.

This book constitutes the refereed proceedings of the Eighth Annual Symposium on Combinatorial Pattern Matching, CPM 97, held in Aarhus, Denmark, in June/July 1997.The volume presents 20 revised full papers carefully selected from 32 submissions received; also included are abstracts of two invited contributions. The volume is devoted to the issue of searching and matching strings and more complicated patterns, such as trees, regular expressions, graphs, point sets and arrays. The results presented are particularly relevant to molecular biology, but also to information retrieval, pattern recognition, compiling, data compression and program analysis.

Combinatorial Algorithms on Words refers to the collection of manipulations of strings of symbols (words) - not necessarily from a finite alphabet - that exploit the combinatorial properties of the logical/physical input arrangement to achieve efficient computational performances. The model of computation may be any of the established serial paradigms (e.g. RAM's, Turing Machines), or one of the emerging parallel models (e.g. PRAM ,WRAM, Systolic Arrays, CCC). This book focuses on some of the accomplishments of recent years in such disparate areas as pattern matching, data compression, free groups, coding theory, parallel and VLSI computation, and symbolic dynamics; these share a common flavor, yet ltave not been examined together in the past. In addition to being theoretically interest­ ing, these studies have had significant applications. It happens that these works have all too frequently been carried out in isolation, with contributions addressing similar issues scattered throughout a rather diverse body of literature. We felt that it would be advantageous to both current and future researchers to collect this work in a sin­ gle reference. It should be clear that the book's emphasis is on aspects of combinatorics and com­ plexity rather than logic, foundations, and decidability. In view of the large body of research and the degree of unity already achieved by studies in the theory of auto­ mata and formal languages, we have allocated very little space to them.