July 10-12, 2013
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 pan-European 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 heap-ordering requirement
is enforced only for one of the two successors of a node.
In 1993, Dutton pioneered that this data structure yields a simple
worst-case 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. Constant-factor optimal
adaptive sorting will be available by extending the weak-heap data
structure to a worst-case efficient priority queue. Various improvements
suggest weak-heaps as an intermediate step for the efficient
construction of binary heap. For graph search and network
optimization a worst-case 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 ki depending on the distance i,
1 ≤ i ≤ p. One seeks the minimum span of such a labelling. The p = 2 case with
k1 = 2 and k2 = 1 has attracted the most attention, particularly the tantalizing
conjecture that for such "L(2, 1)"-labellings, if G has maximum degree Δ
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 ki , 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 rotor-router 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 non-inclusion 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.