Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday

Description

Front matter Chapter 1 String Rearrangement Metrics: A Survey Introduction Motivation The String Rearrangement Model Formal Model Definition Independent Individual Moves The $l_1$ Rearrangement Distance The $l_2$ Rearrangement Distance The $l_\infty$ Rearrangement Distance Independent Individual Moves Rearrangements: Summary External Process Rearrangement Systems The Unit Cost Model The Length Cost Model The Element Cost Model External Process Rearrangements: Summary Internal Process Rearrangement Systems The Bit Errors Definition Flipped Bits Errors The Faulty Bits Problem Internal Process Rearrangements: Summary Chapter 2 Maximal Words in Sequence Comparisons Based on Subword Composition Structure, Similarity and Distance The Ubiquitous Maximal Subwords and Related Computations Conclusions Chapter 3 Fast Intersection Algorithms for Sorted Sequences Introduction Related Work A Simple But Good Average Case Algorithm Double Binary Search Best and Worst Case Analysis Average Case Analysis Experimental Analysis Multiple Sequences Hybrid Algorithms Application to Query Processing in Inverted Indexes Context Sequence Lengths with Zipf's Distribution Concluding Remarks Chapter 4 Indexing and Searching a Mass Spectrometry Database Background Problem Definition Lookup Algorithm Analysis of Lookup Algorithm Folding Algorithm Analysis of Folding Algorithm Clustering Algorithm Analysis of Clustering Algorithm Recursive Clustering Extensions Shared Peaks Intensities Mapping Peaks to Integers Tandem Mass Spectrometry Experiments Conclusion Chapter 5 Extended Compact Web Graph Representations Introduction and Related Work Basic Concepts Compact Data Structures for Sequences Re-Pair Compression of Web Graphs Representing the Re-Pair Rules A Simple Representation Based on Binary Relations Combining Re-Pair with Binary Relations Representation Extracting Reverse Neighbors Guaranteeing Reverse Neighbor Retrieval Time Experimental Results Conclusions Chapter 6 A Parallel Algorithm for Fixed-Length Approximate String-Matching with $k$-mismatches Introduction Basic Definitions Problem Definition The Bit-Vector-Mismatches Algorithm The Parallel-Bit-Vector-Mismatches Algorithm Experimental Results Conclusion Chapter 7 Covering Analysis of the Greedy Algorithm for Partial Cover Introduction Minimum Set Cover and the Greedy Algorithm Covering Analysis of the Greedy Algorithm Application of the Analysis to Partial Cover Further Application of the Analysis Related Work Conclusion Chapter 8 From nondeterministic suffix automaton to lazy suffix tree Introduction Preliminaries Basic Algorithm The Real Algorithm Final Touches Average Case Time Lazy Suffix Tree From Suffix Trie to Suffix Tree Sparse Suffix Trees Preliminary Experimental Results Final Remarks Chapter 9 Clustering the Normalized Compression Distance for Influenza Virus Data Introduction Background and Theory Experiments and Results Influenza Viruses – The Data Set Results Conclusions Chapter 10 An Evolutionary Model of DNA Substring Distribution Introduction Methods Evolutionary Model of DNA Regulatory Regions The Equilibrium Distribution Substring Distribution at Equilibrium Experiments Discussion Chapter 11 Indexing a Dictionary for Subset Matching Queries Introduction A Haplotype Trie from a Genotype Dictionary An $O(nm+|\Sigma|^k n\log n)$ Time Construction An $O(nm+|\Sigma|^k n\log m)$ Time Construction An $O(nm+|\Sigma|^k n +|\Sigma|^{k/2} n\log (\min\{n,m\}))$ Time Construction Fractional Cascading Conclusion and Open Problems Chapter 12 Transposition and Time-Scale Invariant Geometric Music Retrieval Introduction Related Work Matching Algorithms S1: Quest for Time Scaled Exact Occurrences S2: Quest for Time Scaled Partial Occurrences Conclusions Chapter 13 Unified View of Backward Backtracking in Short Read Mapping Introduction Background New Pruning Mechanism Dynamic Programming and Backtracking Experiments ChIP-seq RNA-seq Chapter 14 Some Applications of String Algorithms in Human-Computer Interaction Introduction Text Entry and Minimum String Distance Metrics for Evaluating Text Entry Techniques Text Entry by Eye Gaze Scan Paths and Shortest Common Supersequences Personal Reminescenses References Chapter 15 Approximate String Matchingwith Reduced Alphabet Introduction Alphabet Transformations in String Matching Tuned Version of ABM Algorithm with Alphabet Reduction Experimental Results Comparison of Alphabet Reduction Techniques Comparison with Other Algorithms Conclusions Chapter 16 ICT4D: A Computer Science Perspective Introduction Traditional ICT4D: Social Sciences Perspective for Evaluating ICT in Developing Contexts ICT4D Reborn: Computer Science Perspective for Designing Meaningful ICT The Art of Assembling Artifacts Using Contextual Inputs Towards a Functional ICT4D Design Interplay of Computer Science and ICT4D ICT4D as an Agent of Change in Computer Science Education Conclusions Chapter 17 Searching for Linear Dependencies between Heart Magnetic Resonance Images and Lipid Profiles Introduction Methods Study Population Imaging Image Analysis Lipid Profiling Summary of Data Sets Results Correlations between Lipid Data and MRI Parameter Data Regression of Lipid Profiles on MRI Parameters Regression of Lipid Profiles on the Heart Surface Model Discussion Conflict of Interest Chapter 18 The Support Vector Tree Introduction Related Work Contributions of This Paper Problem Definition Tree Based Partitioning of the Input Space Basic Definitions A Simple Exact Algorithm for Balanced Trees An Inexact Greedy Algorithm Algorithm Description Analysis of the Greedy Algorithm Scaling the Columns of XD,S Empirical Evaluation Conclusion Back matter