

E. Birney (European Bioinformatics Institute, UK)
Annotating the human genome
The human genome is the "hard disk" for human biology, encoding the instructions for each protein and RNA and the elements which regulate their expression. I will provide a perspective of the discovery, annotation and utility of these different components over the last two decades, from the annotation of the draft human genome through to the ENCODE project.
The forthcoming decade will see many more molecular tools being used in clinical research and, in some cases, in practicing medicine. There is a wealth of information and experience from existing use of genetic information in medicine as well as new opportunities available to researchers and practitioners. I will discuss some of the experience I have made in translating this information into the clinic setting.
Finally molecular biology is a leading example of a data intensive science, with both pragmatic and theoretical challenges being raised by data volumes and dimensionality of the data. This shift in modality is creating a wealth of new opportunities and has some accompanying challenges. In particular there is a continued need for a robust information infrastructure for molecular biology. I will briefly outline the challenges and the framework for the solution being the panEuropean life sciences information infrastructure, Elixir.

S. Edelkamp (University of Bremen, Germany)
Weak Heaps and Friends  Show me your Bits
Weak heaps are heap variants, for which the heapordering requirement
is enforced only for one of the two successors of a node.
In 1993, Dutton pioneered that this data structure yields a simple
worstcase efficient sequential sorting algorithm.
In this talk I will push the envelope and show various fundamental
applications for weak heaps. This encompasses
the creation of a sorting index and the use as a tournament
tree for faster sequential sorting in practice. Constantfactor optimal
adaptive sorting will be available by extending the weakheap data
structure to a worstcase efficient priority queue. Various improvements
suggest weakheaps as an intermediate step for the efficient
construction of binary heap. For graph search and network
optimization a worstcase efficient priority queue based on
weak heaps will eventually beat Fibonacci heaps.

J. R. Griggs (University of South Carolina, USA)
The Δ^{2} Conjecture for Graph Labellings with Separation Conditions
In 1988 Roberts described a problem posed to him by Lanfear concerning
the efficient assignment of channels to a network of transmitters in the plane.
To understand this problem, Griggs and Yeh introduced the theory of integer
vertex λlabellings of a graph G. To prevent interference, labels for nearby
vertices must be separated by specified amounts k_{i} depending on the distance i,
1 ≤ i ≤ p. One seeks the minimum span of such a labelling. The p = 2 case with
k_{1} = 2 and k_{2} = 1 has attracted the most attention, particularly the tantalizing
conjecture that for such "L(2, 1)"labellings, if G has maximum degree Δ
≥ 2,
then the minimum span is at most Δ^{2} . It has now been proven for all sufficiently
large Δ, but remains open for small Δ, even for Δ = 3. The theory has been
expanded to accommodate real number labellings and separations k_{i} , with a
given separation for each pair of vertices, not necessarily based on distance.
Infinite graphs, such as regular lattices, are considered.

R. Klasing (LaBRI & CNRS, France)
Efficient exploration of anonymous undirected graphs.
In this talk, I will consider the problem of exploring an anonymous
undirected graph using an oblivious robot. The studied exploration
strategies are designed so that the next edge in the robotâ€™s walk is
chosen using only local information. In my presentation, I will discuss
in more detail three approaches: the random walk, the rotorrouter and
the basic walk, reviewing major relevant results, presenting recent
developments, and commenting on directions for further research.

K. Park (Seoul National University, Korea)
New Graph Model for Consistent Superstring Problems
The problems related to string inclusion and noninclusion have been vigorously studied in such diverse fields as data compression, molecular biology, and computer security. Given a finite set P of positive strings and a finite set N of negative strings, a string A is a consistent superstring if every positive string is a substring of A and no negative string is a substring of A. The shortest (resp. longest) consistent superstring problem is finding a string A that is the shortest (resp. longest) among all the consistent superstrings of the given sets P and N.
In this talk I will present a new graph model for consistent superstrings of P and N. The new graph model is more intuitive than the previous one, and it leads to simpler and more efficient algorithms for consistent superstring problems.
