Combinatorial Pattern Matching
22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011, Proceedings
Published on 27. June 2011
XV, 480 pages
978-3-642-21458-5 (ISBN)
Description
This book constitutes the refereed proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching, CPM 2011, held in Palermi, Italy, in June 2011.
The 36 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 70 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 36 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 70 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
Raffaele Giancarlo | Giovanni Manzini
Combinatorial Pattern Matching
22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011, Proceedings
Book
06/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Invited Talks
- Algorithms on Grammar-Compressed Strings
- Automatic Discovery of Patterns in Media Content
- Introduction
- Data Acquisition and Management
- Experiments: Patterns in Content
- News Coverage in the EU
- Gender, Style and Topic
- Event Discovery in Textual Streams
- Conclusions
- References
- Computational Regulatory Genomics
- Contributed Papers
- Lempel-Ziv Factorization Revisited
- Introduction
- LZ-Factorization by Peak Elimination
- Ultra-Fast Lempel-Ziv Factorization
- LZ-Factorization with Succinct Data Structures
- Experimental Results
- References
- Succincter Text Indexing withWildcards
- Introduction
- Preliminaries
- A Succinct Full-Text Dictionary
- A Compressed Suffix Array Representation of Text Segments
- Storing Text Segment Lengths
- The Text Segment Interval Tree
- Finding the Smallest Enclosing Text Segment Interval
- The Overall Dictionary and Its Full-Text Capabilities
- Matching Wildcards in Succinct Texts
- Overall Design of the Index
- Type 2 Matching
- Type 3 Matching
- Conclusions
- References
- Self-indexing Based on LZ77
- Introduction and Related Work
- Direct Access to LZ-Compressed Texts
- Pattern Searches
- Primary Occurrences
- Secondary Occurrences
- Experimental Evaluation
- Conclusions
- References
- Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
- Introduction
- Preliminaries
- Hardness of SF-MNSA
- Approximation Algorithms for SF-MNSA
- A 2-Approximation Algorithm for SF-MNSA
- A 1.33-Approximation Algorithm for One-Sided SF-MNSA
- Exact Algorithms for Some Variants of One-Sided SF-MNSA
- FPT Algorithm for One-Sided d-SF-MNSA
- FPT Algorithm for One-Sided SF-MNSAc
- Concluding Remarks
- References
- String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
- Introduction
- String Comparison
- Lyndon-Like Factorization
- References
- A $d$-Step Approach for Distinct Squares in Strings
- Introduction
- Some Basic Properties of the ($d,n-d$) Table
- Main Results
- Structure of Relatively Short Square-Maximal Strings
- Conclusions
- References
- Tractability Results for the Consecutive-Ones Property with Multiplicity
- Introduction
- Preliminaries
- A Tractable Case of the mC1P Decision Problem
- The Case of a Single Multicolumn
- Completing the Proof of Theorem 3
- Building a PQ-Tree Which Describes All Sequences That Satisfy the Consecutivity Requirement
- Conclusion
- References
- Forest Alignment with Affine Gaps and Anchors
- Introduction and Motivation
- State of the Art
- Forest Alignment Algorithm
- Forest Alignment with Affine Gap Costs
- Speed-Up by Anchoring
- Computational Complexity and Performance
- Towards a Generalized Model of Forest Alignment
- References
- Phylogenetic Footprinting and Consistent Sets of Local Aligments
- Introduction
- Theory
- Heuristic Algorithm
- References
- Unique Perfect Phylogeny Is $N P$-Hard
- Introduction
- Preliminaries
- Construction
- Formal Description
- Proof of Theorem 8
- Conclusion
- References
- Fast Error-Tolerant Quartet Phylogeny Algorithms
- Introduction
- Related Work
- Definitions
- Search Tree
- An Algorithm for Error-Free Data
- The Height of the Search Tree
- Accounting for Errors
- Random Walk in the Search Tree
- Finding Quartets to Ask
- Shrinking the Error Probability to $o$(1)
- Maximum Quartet Consistency Is Consistent
- Experiments
- Accuracy on Simulated Alignments
- Conclusion
- References
- Real-Time Streaming String-Matching
- Introduction
- Fingerprints and Periods
- The $O(n logm)$ Time Algorithm
- The Real-Time Algorithm
- The Pattern Preprocessing
- References
- Simple Real-Time Constant-Space String Matching
- Introduction
- Basic Real-Time Algorithm
- Real-Time Variation
- Pattern Preprocessing
- Concluding Remarks
- References
- Space Lower Bounds for Online Pattern Matching
- Introduction
- Preliminaries and Related Work
- Communication Complexity Problems
- Addition
- Conjunction
- Other Boolean Operators
- The L8 Distance
- Non-binary Alphabets
- Non-local Pattern Matching
- Open Problems
- References
- Counting Colours in Compressed Strings
- Introduction
- Simple Blocking
- Multi-size Blocking
- Time Independent of $n$
- Improving Time
- Partial Dynamism
- References
- On Wavelet Tree Construction
- Introduction
- Stable Sorting of Bit Key Sequences
- Generating Wavelet Trees
- Definitions
- Wavelet Tree Construction Algorithms
- Conclusion
- References
- Lightweight BWT Construction for Very Large String Collections
- Introduction
- Preliminaries
- Lightweight BWT Construction for a Collection of Strings
- Computational Experiments
- Discussion
- References
- Palindrome Pattern Matching
- Introduction
- Preliminaries
- Linear-Time Palindrome Pattern Matching Algorithm
- Palindrome Suffix Trees
- Constructing Palindrome Suffix Trees
- Conclusions and Future Work
- References
- Sparse and Truncated Suffix Trees on Variable-Length Codes
- Introduction
- Preliminaries
- A Linear-Time Online Algorithm for Code Suffix Trees
- Code Automata and Code Suffix Links
- Main Algorithm
- Time Complexity
- Application to Truncated Code Suffix Trees
- Experimental Results
- Conclusion
- References
- On the Weak Prefix-Search Problem
- Introduction
- Background
- A 2-Level Indexing Scheme for RAM
- I/O-Packing of the Patricia Tries
- References
- Quick Greedy Computation for MinimumCommon String Partitions
- Introduction
- Sorting by Reversals and MCSP
- Edit Distance with Moves and MCSP
- Restricted Versions of MCSP
- MCSP and the GREEDY Algorithm
- Our Results
- Problem Definitions and Preliminaries
- Preliminary Definitions and Notations
- Algorithm Outline
- Transforming the Suffix Tree in Round Change
- Maintaining Data Structures to Quickly Find the Current Round LCS
- Maintaining LP() Dynamically
- Detailed Data Structure Maintenance
- Finding a Matching T-Suffix
- Putting It All Together
- References
- LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
- Introduction
- Previous Work and Concepts
- Left-to-Right-Minima Trees
- Range Minimum Queries
- Adaptive Sorting and Compression of Permutations
- Compressed Succinct Indexes for Range Minima
- Sorting Permutations
- Compressing Permutations
- References
- Substring Range Reporting
- Introduction
- Substring Range Reporting
- Applications
- Basic Concepts
- Strings and Suffix Trees
- Range Reporting
- Substring Range Reporting
- The Data Structure
- Substring Range Queries
- Applications
- Position-Restricted Substring Searching
- Indexing Substrings with Intervals
- Indexing Substrings with Gaps
- References
- Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts
- Introduction
- Preliminaries
- Strings
- Straight Line Programs
- Subsequence Matching Problems on Compressed Texts
- Subsequence Recognition
- Subsequence Matching
- Don't-Care Pattern Matching Problems on Compressed Texts
- FLDC Pattern Matching on Compressed Texts
- VLDC Pattern Matching on Compressed Texts
- Conclusion
- References
- A Combinatorial Model of PhyllotaxisPerturbations in $Arabidopsis thaliana$
- Introduction
- Model Formulation
- Detecting $n$-Admissibility in Noisy Sequences
- Problems
- Algorithms
- Results
- Assignment of Measured Angles to Theoretical Angles
- Interpretation on Our Dataset
- References
- Tractability and Approximability of Maximal Strip Recovery
- Introduction
- An FPT Algorithm for d-gap-MSR-d
- An FPT Algorithm for CMSR-d and d-gap-CMSR-d
- An Approximation Algorithm for CMSR-d and d-gap-CMSR-d
- References
- Efficient Seeds Computation Revisited
- Introduction
- Computing Left-Seed Arrays
- Computing Seeds of Given Length and Seed Array
- Alternative Algorithm for Shortest Seeds
- Long Seeds
- References
- Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions
- Introduction
- Basic Notions and Properties
- A General Dynamic Programming Approach
- The Algorithm InversionSampling
- Correctness Issues
- Worst-Case Time Analysis
- Conclusions and Future Work
- References
- A Coarse-to-Fine Approach to Computing the $k$-Best Viterbi Paths
- Introduction
- Methods
- The Viterbi Algorithm
- Coarse-to-Fine
- $k$-Best
- Coarse-to-Fine $k$-Best
- Building $T$
- Results
- Conclusion
- References
- Finding Approximate and Constrained Motifs in Graphs
- Introduction
- Preliminaries
- NP-Hardness of Min-Substitute and Min-Add
- Parameterized Complexity of Min-Substitute
- Parameterized Complexity of CGM
- An FPT Algorithm for Graphs of Bounded Treewidth
- Hardness of Parameterization
- References
- Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees
- Introduction
- Edit Distance and Mapping
- MAX SNP-Hard Results
- The Problem of UTED(2, *, ?µ)
- The Problem of UTED(*, 2, ?µ)
- The Problem of UTED(3, *, µ)
- The Problem of UTED(*, 2, µ)
- Conclusion
- References
- Approximation Algorithms for Orienting Mixed Graphs
- Introduction
- Preliminaries
- Logarithmic Approximations for Tree-Like Instances
- Orienting Mixed Trees
- Crossings through a Junction Component
- Orientations for Small Feedback Vertex Sets or Treewidth
- Sub-linear Approximations for General Instances
- The Algorithm
- Analysis
- An Improved Approximation for Bounded-Distance Pairs
- Conclusions
- References
- Frequent Submap Discovery
- Introduction
- Recalls on Combinatorial Maps
- Frequent Submap Discovery
- Generalization to $nD$ Combinatorial Maps
- Experimental Evaluation on Synthetic Databases
- Application to Image Classification
- Conclusion
- References
- Edit Distance with Duplications and Contractions Revisited
- Introduction
- Our Contribution and Roadmap
- Edit Distance with Duplications and Contractions
- Problem Definition
- The Basic Recursion
- Context-Free Grammar Representation
- A Basic Dynamic Programming Algorithm for EDDC
- Accelerating the Algorithm Using Fast Square Matrix Multiplication
- Matrix Multiplication Preliminaries
- The General Case Algorithm
- Fast Square Matrix Multiplication on Top of Run Length Encoding
- Sparsifying the Computation Using Run Length Encoding
- The Algorithm
- A Faster, Online Algorithm Using Fast Matrix-Vector Multiplication
- A High-Level Overview of the Algorithm
- Fast $D$-discrete Matrix-Vector Multiplication
- References
- Polynomial-Time Approximation Algorithms for Weighted LCS Problem
- Introduction
- Preliminaries
- Integer LCWS2 over a Bounded Alphabet Is NP-Hard
- Approximating LCWS2
- (1/2)-Approximation Algorithm for LCWS2
- Polynomial-Time Approximation Scheme for LCWS2
- References
- Restricted Common Superstring and Restricted Common Supersequence
- Introduction
- Motivation
- Previous Work
- Our Contributions
- $RCSstr$
- Hardness of the $RCSstr$
- Approximating $RCSstr$
- $RCSseq$
- Hardness of the $RCSseq$ problem
- Approximating $RCSseq$
- References
- Author Index
