Combinatorial Pattern Matching
23rd Annual Symposium, CPM 2012, Helsinki, Finland, July 3-5, 2012, Proceedings
Published on 13. June 2012
XIII, 454 pages
978-3-642-31265-6 (ISBN)
Description
This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finland, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
More details
Other editions
Additional editions
Juha Kärkkäinen | Jens Stoye
Combinatorial Pattern Matching
23rd Annual Symposium, CPM 2012, Helsinki, Finland, July 3-5, 2012, Proceedings
Book
06/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title Pa ge
- Preface
- Organization
- Table of Contents
- Invited Talks
- Contributed Papers
- The Maximum Number of Squares in a Tree
- Introduction
- Bounds for Combs
- Prelude to Upper Bound Proof
- (p,q)-Representations of Substrings
- General Combs and General Upper Bound
- References
- Faster and Simpler Minimal Conflicting Set Identification
- Introduction
- MCS and Forbidden Induced Subgraphs
- A Global Algorithm
- Conclusion
- References
- Partitioning into Colorful Components by Minimum Edge Deletions
- Introduction
- Computational Hardness
- Algorithms
- Formulation as Weighted Multi-Multiway Cut
- Experiments
- Outlook
- References
- Approximation Algorithmsand Hardness Results for Shortest Path Based Graph Orientations
- Introduction
- Hardness of Approximation
- The Single-Pair Gadget
- Reduction from Independent Set
- Approximation Algorithms
- Exact Shortest Paths
- Approximate Shortest Paths
- References
- Constant-Time Word-Size String Matching
- Introduction
- Basic Concepts
- Word-Size Text Search
- Implementing lmo Operation
- Word-Size Pattern Preprocessing
- Parallel Random Access Machine
- Conclusions
- References
- Pattern Matching in Multiple Streams
- Introduction
- Related Work
- Preliminaries and a New Model for Multiple Streams
- Exact Matching
- LCE Queries in a Stream
- $k$ -Mismatch in Multiple Streams
- $k$ -Difference in Multiple Streams
- Space Lower Bounds
- Open Problems
- References
- An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata
- Introduction
- Definitions and Notations
- Probabilistic Models and Generic Properties
- Probabilistic Models with Low Correlation
- Examples of Probabilistic Models with Low Correlation
- Generic Properties of the Associated Aho-Corasick Automaton
- A Pseudo-minimization Algorithm for Aho-Corasick Automata
- Algorithm
- Complexity
- Experimental Results
- Conclusion
- References
- Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation
- Introduction
- Technical Preliminaries
- Algebraic Parameter Space Characterization
- A Polynomial Time Algorithm
- Conclusions and Future Work
- References
- Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
- Introduction
- Preliminary Results and NP-Completeness of LCS(3, 1)
- NP-Completenessof LCS(2, 2)
- Approximation
- References
- Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
- Introduction
- The Approximate Index
- Warm-Up: A Golden Ratio Approximation in O(n3/2)
- As Close to 1 as Wished
- The Last Piece: A Recursive Argument
- Applying the Index to the Parikh Vector Matching Problem
- Some Final Observations and Open Problems
- References
- The Complexity of String Partitioning
- Introduction
- Preliminaries
- The String Partition Problems
- Equality-Free String Partition Problems
- Equality-Free Multiple String Partition with Unbounded Alphabet
- Equality-Free String Partition with Unbounded Alphabet
- Equality-Free Multiple String Partition with Binary Alphabet
- Equality-Free String Partition with Binary Alphabet
- Factor-, Prefix- and Suffix-Free String Partition Problems
- Conclusion
- References
- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
- Introduction and Related Work
- Preliminaries
- Top-k Using Range Maximum/Minimum Queries
- A Brief Review of Hon et al.'s Index
- Query Answering
- Our Linear-Space Index
- Space-Efficient Encoding of Our Index
- Saving More Space
- References
- Document Listing for Queries with Excluded Pattern
- Introduction and Related Work
- Preliminaries
- Suffix Trees and Suffix Arrays
- Wavelet Tree
- Weight-Balanced Wavelet Tree
- Data Structures for Document Counting
- Data Structures for Document Listing
- Concluding Remarks
- References
- Proof of Lemma 1
- Space of a WBT
- Cross-Document Pattern Matching
- Introduction
- Preliminaries
- Basic Data Structures
- Weighted Level Ancestor Problem
- Cross-Document Pattern Counting and Reporting
- Counting
- Reporting
- Variants of the Problem
- Dynamic Counting and Reporting
- Document Counting and Reporting
- Compact Counting, Reporting and Document Reporting
- References
- Appendix:
- FEMTO: Fast Search of Large Sequence Collections
- Introduction
- Background
- The FEMTO Index
- High Throughput with External Memory
- Bi-directional Locate
- Improving Document Search Time
- Regular Expression Search
- Parallel External Memory Index Construction
- Experimental Methods
- Results
- Approximate Search
- FEMTO Index Space
- Reporting Results
- Conclusion
- References
- Speeding Up q-Gram Mining on Grammar-Based Compressed Texts
- Introduction
- Preliminaries
- Intervals, Strings, and Occurrences
- Straight Line Programs
- O(qn) Algorithm goto11:fastmininslpcomprstrin
- New Algorithm
- q-Gram Neighbor Graph
- Weighted q-Gram Frequencies over a Trie
- Preliminary Experiments
- References
- Simple and Efficient LZW-Compressed Multiple Pattern Matching
- Introduction
- Preliminaries
- Overview of the Algorithm
- Multiple Pattern Matching in a Sequence of Snippets
- Conclusions
- References
- Computing the Burrows-Wheeler Transform of a String and Its Reverse
- Introduction
- Preliminaries
- The Burrows-Wheeler Transform of the Reverse String
- The LCP-Array of the Reversed String
- Parallelization and Experimental Results
- References
- Efficient Algorithm for Circular Burrows-Wheeler Transform
- Introduction
- Preliminaries
- Construction of Circular Burrows-Wheeler Transform
- Constructing ?? for All Short Patterns
- Updating for Long Patterns
- References
- Least Random Suffix/Prefix Matches in Output-Sensitive Time
- Introduction
- Preliminaries
- Finding Exact Overlaps
- Related Work on Approximate String Matching
- Output-Sensitive Algorithms
- Method for Short Strings
- Method for Long Strings
- Sets of Mixed Length Strings
- Least Random Overlaps
- Discussion
- References
- Compressed String Dictionary Look-Up with Edit Distance One
- Introduction
- Related Work
- Background
- A Compressed and Fast Solution
- A More Compressed Solution
- Conclusion
- References
- Time-Space Trade-Offs for Longest Common Extensions
- Introduction
- Our Results
- Techniques
- Applications
- The Deterministic Data Structure
- Difference Covers
- The Data Structure
- The Monte-Carlo Data Structure
- Rabin-Karp fingerprints
- The Data Structure
- The Las-Vegas Data Structure
- The Algorithm
- Longest Common Extensions on Two Strings
- The Data Structure
- References
- Local Exact Pattern Matching for Non-fixed RNA Structures
- Introduction
- Our Results
- Notations and Definitions
- Local Exact Pattern Matching Problem Definition
- A Simple O(n^ 4) Algorithm for Local Exact Pattern Matching
- Finding the Maximal Matching between Two Base Pairs
- Finding the Maximal Score Matching Inside the Base Pairs
- Extending the Match Outside the Base Pairs
- Complete O(n^ 4) Algorithm
- An O(n^3 logn) Algorithm for Local Exact Pattern Matching
- An O(n^ 3) Algorithm for Local Exact Pattern Matching
- Local Exact Pattern Matching for (Nested, Bounded-Unlimited) Inputs
- References
- Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots
- Introduction
- Problem Statement and Free-Energy Models
- NP-Hardness of RNA-PK-Fold(S) in Any Non-degenerate Stacking Energy Model
- Approximability of RNA-PK-Fold(S) in the Stacking Model
- Inapproximability of RNA-PK-Fold(N) in the Nearest-Neighbor Energy Model
- Conclusion/Perspectives
- References
- Finding Longest Common Segments in Protein Structures in Nearly Linear Time
- Introduction
- Preliminary
- Algorithms for ALCSRMSD
- FPTAS for ALCSdist
- Nearly Linear-Time FPTAS for ALCSdist on Protein Structures
- References
- A Linear Kernel for the Complementary Maximal Strip Recovery Problem
- Introduction
- Preliminaries
- ALinearKernel forCMSR
- Bounding the Solution Search Space for CMSR
- Computing the Linear Kernel for CMSR
- Concluding Remarks
- References
- Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees
- Introduction
- Preliminaries
- Algorithm for a General Case
- Algorithm
- Improved Analysis
- Algorithm for a Case of Bounded Degree and Fixed Alphabet
- Algorithm
- Analysis
- Concluding Remarks
- References
- Fixed-Parameter Algorithms for Finding Agreement Supertrees
- Introduction
- Definitions
- The Agreement Supertree Problem
- Chararacterizing Agreement
- Finding Successor Positions and Interesting Vertices
- Testing for an Agreement Supertree
- FPT Algorithms
- An Auxiliary Algorithm
- Solving the AST-EC Problem
- Solving the AST-TR Problem
- Concluding Remarks
- References
- Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles
- Introduction
- New Results
- Preliminaries
- Basic Definitions
- Galled Trees
- Counting Monochromatic and Almost-Monochromatic Triangles
- Computing the Rooted Triplet Distance between Galled Trees
- Counting the Number of Shared Rooted Fan Triplets
- Counting the Number of Shared Rooted Proper Triplets
- Computing the Rooted Triplet Distance
- Concluding Remarks
- References
- Minimum Leaf Removal for Reconciliation: Complexity and Algorithms
- Introduction
- Preliminary Definitions
- Trees
- Reconciliation
- Duplication Nodes and MD-trees
- Hardness of Minimum Leaf Removal
- Fixed-Parameter Algorithms
- MinLeafRem Parameterized by the Number of Leaves Removed
- MinLeafRem Parameterized by the Number of Labels with Multiple Copies
- Conclusion
- References
- On the Closest String via Rank Distance
- Introduction
- Motivation
- Previous Work
- Our Contributions
- Preliminaries
- Pareto Optimality
- Hardness of the Closest String via Rank Distance
- A k-Approximation Algorithm
- A Polynomial Algorithm for Binary Alphabets
- Conclusions
- References
- On Approximating String Selection Problems with Outliers
- Introduction
- Our Contributions
- Brief Description of Parameterized Complexity
- Previous Work
- Approximation Hardness of Close to Most Strings
- Non-existence of an EPTAS for Closest to k Strings
- APX-Hardness of Most Strings with Few Bad Columns
- Conclusions and Open Problems
- References
- The Parameterized Complexity of the Shared Center Problem
- Introduction
- Basic Definitions and Notations
- The SC Problem
- The Hardness of the SC Problem
- An Exact Algorithm for the SC Problem
- Decomposing $gi \in N$
- Decomposing the Strings in $ D$
- Concluding Remarks
- References
- Gene Regulation, Protein Networks and Disease: A Computational Perspective
- Wavelet Trees for All
- Introduction
- Data Structure
- Compression
- Sequences, Reorderings, or Point Grids?
- Applications as Sequences
- Applications as Reorderings
- Applications as Grids
- Conclusions and Further Challenges
- References
- Author Index
