Sublinear approximate string matching and biological applications

DOI10.1007/BF01185431zbMath0942.68575OpenAlexW2055417893MaRDI QIDQ1336963

W. I. Chang, Eugene L. Lawler

Publication date: 26 February 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185431

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Protein sequences, DNA sequences (92D20)

Related Items (25)

New and faster filters for multiple approximate string matching ⋮ Computing suffix links for suffix trees and arrays ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Replacing suffix trees with enhanced suffix arrays ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ On updating suffix tree labels ⋮ Analysis of two-dimensional approximate pattern matching algorithms ⋮ A new filtration method and a hybrid strategy for approximate string matching ⋮ Multiple approximate string matching ⋮ Block edit models for approximate string matching ⋮ On using q-gram locations in approximate string matching ⋮ Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads ⋮ Bidirectional search in a string with wavelet trees and bidirectional matching statistics ⋮ Average-case linear-time similar substring searching by the \(q\)-gram distance ⋮ On-line approximate string matching with bounded errors ⋮ Text indexing with errors ⋮ Hardness of optimal spaced seed design ⋮ Approximate string-matching with \(q\)-grams and maximal matches ⋮ Quantum pattern matching fast on average ⋮ On average sequence complexity ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ THE VIRTUAL SUFFIX TREE ⋮ Distributed suffix trees ⋮ Longest common substrings with \(k\) mismatches ⋮ Space-efficient representation of truncated suffix trees, with applications to Markov order estimation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate string matching with suffix automata
• Data structures and algorithms for approximate string matching
• Fast string matching with k differences
• An Improved Algorithm For Approximate String Matching
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Finding approximate patterns in strings
• Efficient randomized pattern-matching algorithms
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• The Complexity of Pattern Matching for a Random String
• The theory and computation of evolutionary distances: Pattern recognition
• Linear Algorithm for Data Compression via String Matching
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• Inferring Evolutionary History From DNA Sequences

This page was built for publication: Sublinear approximate string matching and biological applications