8:45-9:20 Registration
9:20-9:30 Opening
String compression Chair: Gregory Kucherov
9:30-10:00 Quasi-Distinct Parsing and Optimal Compression Methods
Amihood Amir, Yonatan Aumann, Avivit Levy and Yuri Roshko
10:00-10:30 Generalized Substring Compression
Orgad Keller, Tsvi Kopelowitz, Shir Landau and Moshe Lewenstein
10:30-11:00 Coffee break
Invited Talk Chair: Maxime Crochemore
11:00-12:00 Text Indexing, Suffix Sorting and Data Compression: Common Problems and Techniques
Roberto Grossi
Index structures Chair: Maxime Crochemore
12:00-12:30 Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
Andrzej Ehrenfeucht, Ross McConnell and Sung-Whan Woo
12:30-13:00 Linear Time Suffix Array Construction Using D-Critical Substrings
Ge Nong, Sen Zhang and Wai Hong Chan
13:00-14:30 Lunch
Data compression. Common subsequences and superstrings Chair: Amihood Amir
14:30-15:00 On the Value of Multiple Read/Write Streams for Data Compression
Travis Gagie
15:00-15:30 Reoptimization of the Shortest Common Superstring Problem
Davide Bilò, Hans-Joachim Boeckenhauer, Dennis Komm, Richard Kralovic, Tobias Moemke, Sebastian Seibert and Anna Zych
15:30-16:00 LCS Approximation via Embedding into Local Non-Repetitive Strings
Gad M. Landau, Avivit Levy and Ilan Newman
16:00-16:30 Coffee break
String and image matching Chair: Raphael Clifford
16:30-17:00 An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings
Simone Faro and Thierry Lecroq
17:00-17:30 Fast Searching in Packed Strings
Philip Bille
17:30-18:00 New Complexity Bounds for Image Matching under Rotation and Scaling
Christian Hundt and Maciej Liskiewicz
19:30 Conference dinner - Musée des Beaux-Arts
Approximate string matching Chair: Gad Landau
9:00-9:30 Online Approximate Matching with Non-Local Distances
Benjamin Sach and Raphael Clifford
9:30-10:00 Optimal Edit Distance “1” Dictionary
Djamal Belazzougui
10:00-10:30 Approximate Matching for Run-Length Encoded Strings is 3Sum-Hard
Kuan-Yu Chen, Ping-Hui Hsu and Kun-Mao Chao
10:30-11:00 Coffee break
Invited talk Chair: Ricardo Baeza-Yates
11:00-12:00 Modeling and Algorithmic Challenges in Online Social Networks
Ravi Kumar
String algorithms Chair: Ricardo Baeza-Yates
12:00-12:30 Permuted Longest-Common-Prefix Array
Juha Karkkainen, Giovanni Manzini and Simon Puglisi
12:30-13:00 Periodic String Comparison
Alexander Tiskin
13:00-14:30 Lunch
Parametrized complexity Chair: Moshe Lewenstein
14:30-15:00 Deconstructing Intractability—A Case Study for Interval Constrained Coloring
Christian Komusiewicz, Rolf Niedermeier and Johannes Uhlmann
15:00-15:30 Maximum Motif Problem in Vertex-Colored Graphs
Dondi Riccardo, Fertin Guillaume and Stéphane Vialette
Bioinformatics: RNA and networks Chair: Hélène Touzet
9:00-9:30 Fast RNA Structure Alignment for Crossing Input Structures
Rolf Backofen, Gad M. Landau, Mathias Möhl, Dekel Tsur and Oren Weimann
9:30-10:00 Sparse RNA folding: time and space efficient algorithms
Rolf Backofen, Dekel Tsur, Shay Zakov and Michal Ziv-Ukelson
10:00-10:30 Multiple Alignment of Biological Networks: A Flexible Approach
Yves-Pol Denielou, Frédéric Boyer, Marie-France Sagot and Alain Viari
10:30-11:00 Coffee break
Invited talk Chair: Esko Ukkonen
11:00-12:00 Graph mining: Patterns, Generators and Tools
Christos Faloutsos
Bioinformatics: Phylogenetic networks Chair: Esko Ukkonen
12:00-12:30 Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
Thu-Hien To and Michel Habib
12:30-13:00 The Structure of Level-k Phylogenetic Networks
Philippe Gambette, Vincent Berry and Christophe Paul
13:00-14:30 Lunch
Bioinformatics: Average-case analysis Chair: Rolf Backhofen
14:30-15:00 Finding All Sorting Tandem Duplication Random Loss Operations
Matthias Bernt, Ming-Chiang Chen, Daniel Merkle, Hung-Lung Wang, Kun-Mao Chao and Martin Middendorf
15:00-15:30 Average-case analysis of perfect sorting by reversals (extended abstract)
Mathilde Bouvel, Cedric Chauve, Marni Mishna and Dominique Rossin
15:30-16:00 Statistical properties of factor oracles
Jeremie Bourdon and Irena Rusu
16:00-16:30 Coffee break
Bioinformatics: Haplotype inference Chair: Thierry Lecroq
16:30-17:00 Haplotype Inference Constrained by Plausible Haplotype Data
Michael Fellows, Tzvika Hartman, Danny Hermelin, Gad Landau, Frances A. Rosamond and Liat Rozenberg
17:00-17:30 Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles
Wei-Bung Wang and Tao Jiang