On the string matching with \(k\) mismatches

DOI10.1016/j.tcs.2018.02.001zbMath1464.68444OpenAlexW2790857551MaRDI QIDQ1743717

Yangjun Chen, Yujia Wu

Publication date: 16 April 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.02.001

zbMATH Keywords

DNA sequencesstring matchingtriesBurrows-Wheeler transformation

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Data structures (68P05) Algorithms on strings (68W32)

Uses Software

• Soap
• CloudBurst
• ZOOM
• BWA

Cites Work

• An algorithm for string matching with a sequence of don't cares
• A space and time efficient algorithm for constructing compressed suffix arrays
• Efficient string matching with k mismatches
• A new distance metric on strings computable in linear time
• A variation on the Boyer-Moore algorithm
• Approximate string-matching with \(q\)-grams and maximal matches
• Fast practical multi-pattern matching
• On improving the worst case running time of the Boyer-Moore string matching algorithm
• A fast string searching algorithm
• Multipattern string matching with q -grams
• Dictionary matching and indexing with errors and don't cares
• The Boyer–Moore–Galil String Searching Strategies Revisited
• Efficient randomized pattern-matching algorithms
• Approximate Boyer–Moore String Matching
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Faster algorithms for string matching with k mismatches
• Boyer-Moore approach to approximate string matching
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the string matching with \(k\) mismatches