Approximate string-matching with \(q\)-grams and maximal matches

DOI10.1016/0304-3975(92)90143-4zbMath0747.68026OpenAlexW2043481183MaRDI QIDQ1190465

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

zbMATH Keywords

lower bounddistance functionsedit distance\(q\)-gramsapproximate string-matchingmaximal common substrings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items (32)

Circular Sequence Comparison with q-grams ⋮ New and faster filters for multiple approximate string matching ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS ⋮ On pattern occurrences in a random text ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ DNA physical mapping and alternating Eulerian cycles in colored graphs ⋮ Multiple filtration and approximate pattern matching ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ A new filtration method and a hybrid strategy for approximate string matching ⋮ Fast Approximate Search in Large Dictionaries ⋮ Compact q-gram profiling of compressed strings ⋮ On using q-gram locations in approximate string matching ⋮ Surprises in approximating Levenshtein distances ⋮ Combinatorics of periods in strings. ⋮ Average-case linear-time similar substring searching by the \(q\)-gram distance ⋮ Estimating sequence similarity from read sets for clustering next-generation sequencing data ⋮ On-line approximate string matching with bounded errors ⋮ Hardness of optimal spaced seed design ⋮ Finite automata for testing composition-based reconstructibility of sequences ⋮ Binary matroids and local complementation ⋮ On the string matching with \(k\) mismatches ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS ⋮ Approximate joins for XML at label level ⋮ Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats ⋮ Vector representations for efficient comparison and search for similar strings ⋮ Algorithms for finding a most similar subforest ⋮ The interlace polynomial of a graph ⋮ Shuffling biological sequences ⋮ Investigation of accelerated search for close text sequences with the help of vector representations ⋮ What’s Behind Blast ⋮ String Reconstruction from Substring Compositions ⋮ Euler circuits and DNA sequencing by hybridization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Simple and efficient string matching with k mismatches
• The smallest automaton recognizing the subwords of a text
• A new distance metric on strings computable in linear time
• Data structures and algorithms for approximate string matching
• Fast string matching with k differences
• Sublinear approximate string matching and biological applications
• Transducers and repetitions
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• Efficient randomized pattern-matching algorithms
• The theory and computation of evolutionary distances: Pattern recognition
• A Space-Economical Suffix Tree Construction Algorithm
• Fast parallel and serial approximate string matching
• The String-to-String Correction Problem
• Boyer-Moore approach to approximate string matching

This page was built for publication: Approximate string-matching with \(q\)-grams and maximal matches