The exact multiple pattern matching problem solved by a reference tree approach

DOI10.1016/J.TCS.2021.06.003MaRDI QIDQ2044955zbMATH OpenOpenAlexFDO

Authors Yi-Kung Shieh, Shyong Jian Shyu, Chin Lung Lu, R. C. T. Lee

Publication date 11 August 2021

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

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

zbMATH Keywords

DNA sequenceexact multiple pattern matchingreference stringreference treesuffix arraysuffix tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• String Processing and Information Retrieval
• The exact online string matching problem: a review of the most recent results
• Tuning string matching for huge pattern sets
• Multipattern string matching with q -grams
• Multi-pattern matching algorithm with wildcards based on bit-parallelism

Cites work

• Algorithms on Strings
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees with full functionality
• Encyclopedia of algorithms. In 3 volumes
• Error detecting and error correcting codes
• Fast and Lightweight LCP-Array Construction Algorithms
• Fully compressed suffix trees
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• New text indexing functionalities of the compressed suffix arrays
• On-line construction of suffix trees
• Parallel computation for the all-pairs suffix-prefix problem
• Replacing suffix trees with enhanced suffix arrays
• String processing and information retrieval. 22nd international symposium, SPIRE 2015, London, UK, September 1--4, 2015. Proceedings
• Suffix Arrays: A New Method for On-Line String Searches
• Trickier XBWT tricks

Cited in

(3)

• TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING
• Filtering multi-set tree: data structure for flexible matching using multi-track data
• Exact pattern matching. Current achievements and research

Describes a project that uses

Uses Software

• SPAdes
• Mauve
• Velvet
• SOAPdenovo

This page was built for publication: The exact multiple pattern matching problem solved by a reference tree approach

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