June 6 – 11 , 2010, Dagstuhl Seminar 10231

Structure Discovery in Biology: Motifs, Networks & Phylogenies


Alberto Apostolico (Georgia Institute of Technology – Atlanta, US)
Andreas Dress (Shanghai Institutes for Biological Sciences, CN)
Laxmi Parida (IBM TJ Watson Research Center – Yorktown Heights, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


This seminar was intended to focus on combinatorial and algorithmic techniques of structure discovery from biological data that is at the core of understanding a coherent body of data, small or large. In biological systems, similarly to the tenet of modern architecture, ``form and function are solidly intertwined''. Thus, to gain complete understanding in various contexts, the curation and study of forms turns out to be a mandatory first phase.

Biology is in the era of the Ome's: Genome, Proteome, Transcriptome, Metabolome, Interactome, ORFeome, Recombinome and so on. Thus it is no surprise that biological data is accumulating at a much faster rate than it can be understood. While on one hand, the sheer size of data can be daunting, this provides on the other hand a golden opportunity for testing (bioinformatic) structure-discovery primitives and methods. In spite of the difficulties of structure discovery, there are reasons to believe that evolution based on reproduction, variation, and selection endowed biological systems with some underlying principles of organization (involving redundancy, similarity, and so on) that appear to be present across the board. Correspondingly, it should be possible to identify a number of primitive characteristics of the various embodiments of form and structure (using for instance notions of ``maximality'', ``irreducibility'', etc.) and build similarly unified discovery tools around them. At a core level in these efforts, there is the need for novel techniques enabling the automated discovery of structures, whether syntactic, such as patterns or motifs, or semantic, such as phylogenies. It is therefore a worthwhile effort to try and identify these primitives.

The workshop gathered a roster of highly qualified senior participants and several talented young researchers who convened to discuss issues of modeling, formalization, and algorithmic design as they emerge in the discovery of biological structure. The schedule unraveled in form of a busy sequence of sessions, intermixed with small group-work sessions and guest lectures. The opening consisted of an extended round-robin aimed at letting participants give detailed accounts of their background and interests. Following opening remarks by Andreas Dress and completed by concluding comments by Alberto Apostolico, three broad-spectred lectures were delivered by Benny Chor, Laxmi Parida, and Raffaele Giancarlo in the afternoon of the first day. A special lecture on epigenetics offered on Tuesday morning in the concurrent Workshop on ``The Semantic of Information'' provided the opportunity to nicely complement the presentations already scheduled. The morning session resumed with three lectures centered on networks, offered in turn by Axel Mosig, Ina Koch, and David Gilbert. The afternoon session was devoted to phylogenies, with featured presentations by Stefan Gruenewald, David Bryant, Peter F. Stadler, and Andeas Spillner. After dinner, a guest lecture by Michael Clausen exposed, not without entertaining notes, the analogies between motifs in biosequences and music and methods for searching for them. The morning session of Wednesday revolved on regulation, with presentations by Rahul Siddharthan, Esko Ukkonen, Matteo Comin, and Ion Mandoiu. Thursday was entirely dedicated to motif discovery in various contexts. Presentations were given in the morning by Jens Stoye, Peter Erdos, Asif Javed, and Nadia Pisanti, followed in the afternoon by Cinzia Pizzi, Fabio Cunial, Matthias Gallé and Benjarath Pupacdi. After dinner, a thorough introduction to toponomics by Andreas Dress was followed by a lecture and software demonstration by Peter Serocka. The participants re-convened in the lecture hall on Friday morning for a general discussion, an assessment of the experience and recommendation for (enthusiastically endorsed) possible encores in the future.

Related Dagstuhl Seminar


  • Mathematical biology
  • Computational biology
  • Algorithmic bioinformatics
  • Pattern discovery
  • Phylogenetics
  • Networks


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.