Approximate string-matching with q-grams and maximal matches
From MaRDI portal
Publication:1190465
DOI10.1016/0304-3975(92)90143-4zbMATH Open0747.68026OpenAlexW2043481183MaRDI QIDQ1190465FDOQ1190465
Authors: Esko Ukkonen 
Publication date: 26 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90143-4
Recommendations
lower bounddistance functionsedit distance\(q\)-gramsapproximate string-matchingmaximal common substrings
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)
Cites Work
- A Mathematical Theory of Communication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient randomized pattern-matching algorithms
- The String-to-String Correction Problem
- A Space-Economical Suffix Tree Construction Algorithm
- The smallest automaton recognizing the subwords of a text
- The theory and computation of evolutionary distances: Pattern recognition
- Fast parallel and serial approximate string matching
- Transducers and repetitions
- Algorithms for approximate string matching
- Sublinear approximate string matching and biological applications
- Finding approximate patterns in strings
- Title not available (Why is that?)
- Simple and efficient string matching with k mismatches
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast string matching with k differences
- Data structures and algorithms for approximate string matching
- Boyer-Moore approach to approximate string matching
- A new distance metric on strings computable in linear time
Cited In (37)
- Compact q-gram profiling of compressed strings
- Estimating sequence similarity from read sets for clustering next-generation sequencing data
- Algorithms for finding a most similar subforest
- Combinatorics of periods in strings.
- On-line approximate string matching with bounded errors
- Finite automata for testing composition-based reconstructibility of sequences
- The interlace polynomial of a graph
- Hardness of optimal spaced seed design
- On using q-gram locations in approximate string matching
- Multiple filtration and approximate pattern matching
- Title not available (Why is that?)
- Title not available (Why is that?)
- Circular sequence comparison with \(q\)-grams
- Euler circuits and DNA sequencing by hybridization
- A subquadratic algorithm for approximate limited expression matching
- Average complexity of backward \(q\)-gram string matching algorithms
- Vector representations for efficient comparison and search for similar strings
- Investigation of accelerated search for close text sequences with the help of vector representations
- A bracket polynomial for graphs. IV: Undirected Euler circuits, graph-links and multiply marked graphs
- Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences
- On pattern occurrences in a random text
- On-Line Approximate String Searching Algorithms: Survey and Experimental Results
- Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats
- Fast approximate search in large dictionaries
- Binary matroids and local complementation
- What's behind blast
- String reconstruction from substring compositions
- An approximate string-matching algorithm
- Average-case linear-time similar substring searching by the \(q\)-gram distance
- Shuffling biological sequences
- DNA physical mapping and alternating Eulerian cycles in colored graphs
- New and faster filters for multiple approximate string matching
- Approximate joins for XML at label level
- Surprises in approximating Levenshtein distances
- On the string matching with \(k\) mismatches
- A new filtration method and a hybrid strategy for approximate string matching
- A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS
This page was built for publication: Approximate string-matching with \(q\)-grams and maximal matches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190465)
