Algorithms and Applications

1. Front Matter

   PDF

2. String Rearrangement Metrics: A Survey

   • Amihood Amir, Avivit Levy

   Pages 1-33

3. Maximal Words in Sequence Comparisons Based on Subword Composition

   • Alberto Apostolico

   Pages 34-44

4. Fast Intersection Algorithms for Sorted Sequences

   • Ricardo Baeza-Yates, Alejandro Salinger

   Pages 45-61

5. Indexing and Searching a Mass Spectrometry Database

   • Søren Besenbacher, Benno Schwikowski, Jens Stoye

   Pages 62-76

6. Extended Compact Web Graph Representations

   • Francisco Claude, Gonzalo Navarro

   Pages 77-91

7. A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches

   • Maxime Crochemore, Costas S. Iliopoulos, Solon P. Pissis

   Pages 92-101

8. Covering Analysis of the Greedy Algorithm for Partial Cover

   • Tapio Elomaa, Jussi Kujala

   Pages 102-113

9. From Nondeterministic Suffix Automaton to Lazy Suffix Tree

   • Kimmo Fredriksson

   Pages 114-129

10. Clustering the Normalized Compression Distance for Influenza Virus Data

    • Kimihito Ito, Thomas Zeugmann, Yu Zhu

    Pages 130-146

11. An Evolutionary Model of DNA Substring Distribution

    • Meelis Kull, Konstantin Tretyakov, Jaak Vilo

    Pages 147-157

12. Indexing a Dictionary for Subset Matching Queries

    • Gad M. Landau, Dekel Tsur, Oren Weimann

    Pages 158-169

13. Transposition and Time-Scale Invariant Geometric Music Retrieval

    • Kjell Lemström

    Pages 170-181

14. Unified View of Backward Backtracking in Short Read Mapping

    • Veli Mäkinen, Niko Välimäki, Antti Laaksonen, Riku Katainen

    Pages 182-195

15. Some Applications of String Algorithms in Human-Computer Interaction

    • Kari-Jouko Räihä

    Pages 196-209

16. Approximate String Matching with Reduced Alphabet

    • Leena Salmela, Jorma Tarhio

    Pages 210-220

17. ICT4D: A Computer Science Perspective

    • Erkki Sutinen, Matti Tedre

    Pages 221-231

18. Searching for Linear Dependencies between Heart Magnetic Resonance Images and Lipid Profiles

    • Marko Sysi-Aho, Juha Koikkalainen, Jyrki Lötjönen, Tuulikki Seppänen-Laakso, Hans Söderlund, Tiina Heliö et al.

    Pages 232-243

19. The Support Vector Tree

    • Antti Ukkonen

    Pages 244-259

20. Back Matter

    PDF

For many years Esko Ukkonen has played a major role in the advancement of computer science in Finland. He was the key person in the development of the school of algorithmic research and has contributed considerably to post-graduate education in his country. Esko Ukkonen has over the years worked within many areas of computer science, including numerical methods, complexity theory, theoretical aspects of compiler construction, and logic programming. However, the main focus of his research has been on algorithms and their applications. This Festschrift volume, published to honor Esko Ukkonen on his 60th birthday, includes 18 refereed contributions by his former PhD students and colleagues, with whom he has cooperated closely during the course of his career. The Festschrift was presented to Esko during a festive symposium organized at the University of Helsinki to celebrate his birthday. The essays primarily present research on computational pattern matching and string algorithms, two areas that have benefited significantly from the work of Esko Ukonen.

• Pattern Matching
• algorithms
• applications
• approximate string-matching
• clustering
• complexity
• complexity theory
• compressed data structures
• cost models
• evolution
• human-computer interaction (HCI)
• logic programming
• algorithm analysis and problem complexity

• Department of Software Systems, Tampere University of Technology, Tampere, Finland

  Tapio Elomaa

• Department of Information and Computer Science, Aalto University School of Science and Technology, Aalto, Finland

  Heikki Mannila, Pekka Orponen

Policies and ethics