IWOCA 2013
July 10-12, 2013
Rouen, France

Normandie Université

Université de Rouen



Région Haute-Normandie



Conseil Général de Seine-Maritime

  • 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 Δ ≥ 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 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.

contacts | crédits | mentions légales

Valid XHTML 1.0 Strict