CPM 2006 Accepted Papers

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