EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, kΔ, α)-MATCHING

DOI10.1142/S0129054108005607MaRDI QIDQ3532148zbMATH OpenOpenAlexFDO

Authors Kimmo Fredriksson, Szymon Grabowski

Publication date 3 November 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054108005607

zbMATH Keywords

computational biologybounded gapssparse dynamic programmingapproximate string matchingmusic information retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computing methodologies for text processing; mathematical typography (68U15)

Recommendations

• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• Combinatorial Pattern Matching
• Algorithms on Extended (δ, γ)-Matching
• scientific article; zbMATH DE number 2087053
• Faster algorithms for string matching with k mismatches

Cites work

• A priority queue in which initialization and queue operations takeO(loglogD) time
• Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata
• Transposition invariant string matching
• Universal codeword sets and representations of the integers

Cited in

(6)

• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• Order-preserving matching
• Simple algorithm for pattern-matching with bounded gaps in genomic sequences
• Combinatorial Pattern Matching
• Algorithms on Extended (δ, γ)-Matching
• On approximate pattern matching with thresholds

This page was built for publication: EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532148)