| Wednesday, July 5, 2006 |
| 08:30-09:00 |
Registration |
| 09:00-09:50 |
Invited Talk: Asynchronous pattern matching, by Amihood Amir |
| 09:50-10:40 |
Session 1: Data Structures |
| 09:50-10:15 |
Adaptive searching in succinctly encoded binary relations and
tree-structured documents, by Jeremy Barbay, Alexander Golynski, J. Ian
Munro, and S. Srinivasa Rao |
| 10:15-10:40 |
Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE, by Johannes Fischer and Volker Heun |
| 10:40-11:10 |
Coffee Break |
| 11:10-12:50 |
Session 2: Indexing Data Structures |
| 11:10-11:35 |
A linear size index for approximate pattern matching, by Ho-Leung
Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, and Swee-Seong Wong |
| 11:35-12:00 |
On-line linear-time construction of word suffix trees, by Shunsuke Inenaga and Masayuki Takeda |
| 12:00-12:25 |
Obtaining provably good performance from suffix trees in secondary storage, by Pang Ko and Srinivas Aluru |
| 12:25-12:50 |
Geometric suffix tree: A new index structure for protein 3-D structures, by Tetsuo Shibuya |
| 12:50-14:10 |
Lunch |
| 14:10-15:50 |
Session 3: Probabilistic and Algebraic Techniques |
| 14:10-14:35 |
New bounds for motif finding in strong instances, by Brona Brejova, Daniel G. Brown, Ian Matthew Harrower, and Tomas Vinar |
| 14:35-15:00 |
Fingerprint clustering with bounded number of missing values, by
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Giancarlo
Mauri |
| 15:00-15:25 |
Tiling an interval of the discrete line, by Olivier Bodini and Eric Rivals |
| 15:25-15:50 |
Common substrings in random strings, by Eric Blais and Mathieu Blanchette |
| 15:50-16:20 |
Coffee Break |
| 16:20-18:00 |
Session 4: Applications in Molecular Biology I |
| 16:20-16:45 |
On the repeat-annotated phylogenetic tree reconstruction problem, by Firas Swidan, Michal Ziv-Ukelson, and Ron Pinter |
| 16:45-17:10 |
Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms, by Sven Rahmann |
| 17:10-17:35 |
Solving the maximum agreement subtree and the maximum compatible
tree problems on bounded degree trees, by Sylvain Guillemot and
François Nicolas |
| 17:35-18:00 |
An improved algorithm for the macro-evolutionary phylogeny problem, by Behshad Behzadi and Martin Vingron |
| Thursday, July 6, 2006 |
| 08:30-09:00 |
Registration |
| 09:00-09:50 |
Invited Talk: News and blog analysis with Lydia, by Steven Skiena |
| 09:50-10:40 |
Session 5: String Matching I |
| 09:50-10:15 |
Property matching and weighted matching, by Amihood Amir, Eran Chencinski, Costas Iliopoulos, Tsvi Kopelowitz, and Hui Zhang |
| 10:15-10:40 |
Faster two dimensional scaled matching, by Amihood Amir and Eran Chencinski |
| 10:40-11:10 |
Coffee Break |
| 11:10-12:50 |
Session 6: Applications in Molecular Biology II |
| 11:10-11:35 |
Approximation of RNA multiple structural alignment, by Marcin Kubica, Romeo Rizzi, Stephane Vialette, and Tomasz Walen |
| 11:35-12:00 |
Finding common RNA pseudoknot structures in polynomial time, by Patricia Evans |
| 12:00-12:25 |
A compact mathematical programming formulation for DNA motif finding, by Carl Kingsford, Elena Zaslavsky, and Mona Singh |
| 12:25-12:50 |
Local alignment of RNA sequences with arbitrary scoring schemes, by Rolf Backofen, Dan Hermelin, Gad M. Landau, and Oren Weimann |
| 12:50-14:10 |
Lunch |
| Friday, July 7, 2006 |
| 08:30-09:00 |
Registration |
| 09:00-09:50 |
Invited Talk: SNP and haplotype analysis: Algorithms and applications, by Eran Halperin |
| 09:50-10:40 |
Session 7: Applications in Molecular Biology III |
| 09:50-10:15 |
An $O(n^{3/2}\sqrt{\log (n)})$ algorithm for sorting by reciprocal translocations, by Michal Ozery-Flato and Ron Shamir |
| 10:15-10:40 |
Longest common subsequences in permutations and maximum cliques in circle graphs, by Alexander Tiskin |
| 10:40-11:10 |
Coffee Break |
| 11:10-12:50 |
Session 8: Data Compression |
| 11:10-11:35 |
A simpler analysis of Burrows-Wheeler based compression, by Haim Kaplan, Shir Landau, and Elad Verbin Best Paper Award |
| 11:35-12:00 |
Statistical encoding of succinct data structures, by Rodrigo Gonzalez and Gonzalo Navarro |
| 12:00-12:25 |
Dynamic entropy-compressed sequences and full-text indexes, by Veli Mäkinen and Gonzalo Navarro |
| 12:25-12:50 |
Reducing the space requirement of LZ-index, by Diego Arroyuelo, Gonzalo Navarro, and Kunihiko Sadakane |
| 12:50-14:10 |
Lunch |
| 14:10-15:50 |
Session 9: String Matching II |
| 14:10-14:35 |
Faster algorithms for computing longest common increasing
subsequences, by Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel,
and Martin Kutz |
| 14:35-15:00 |
New algorithms for text fingerprinting, by Roman Kolpakov, and Mathieu Raffinot |
| 15:00-15:25 |
Sublinear algorithms for parameterized matching, by Leena Salmela and Jorma Tarhio |
| 15:25-15:50 |
Approximate matching in weighted sequences, by Amihood Amir, Costas Iliopoulos, Oren Kapah, and Ely Porat |
| 15:50-16:20 |
Coffee Break |
| 16:20-17:35 |
Session 10: Dynamic Programming |
| 16:20-16:45 |
Algorithms for finding a most similar subforest, by Zeshan Peng and Jesper Jansson |
| 16:45-17:10 |
Efficient algorithms for regular expression constrained sequence alignment, by Yun-Sheng Chung, Chin Lung Lu, and Chuan Yi Tang |
| 17:10-17:35 |
Large scale matching for position weight matrices, by Aude Liefooghe, Hèléne Touzet, and Jean-Stéphane Varré |