Efficient pattern matching in elastic-degenerate strings

DOI10.1016/j.ic.2020.104616zbMath1497.68603arXiv1610.08111OpenAlexW4210743444MaRDI QIDQ2042726

Ritu Kundu, Solon P. Pissis, Costas S. Iliopoulos

Publication date: 21 July 2021

Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.08111

zbMATH Keywords

indeterminate stringsalgorithms on stringsdegenerate stringselastic-degenerate stringsgapped stringsstring-processing algorithms

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Maximal degenerate palindromes with gaps and mismatches, Algorithms and complexity on indexing founder graphs, Elastic-degenerate string matching with 1 error, A new approach to regular \& indeterminate strings, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Pattern Matching on Elastic-Degenerate Text with Errors, Unnamed Item, Unnamed Item, Special issue: Selected papers of the 11th international conference on language and automata theory and applications, LATA 2017, Efficient pattern matching in elastic-degenerate strings, Approximate pattern matching on elastic-degenerate text, Comparing Degenerate Strings, Unnamed Item, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Faster Online Elastic Degenerate String Matching

Uses Software

• MoTeX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
• Fast pattern-matching on indeterminate strings
• Dynamic dictionary matching
• On-line construction of suffix trees
• Efficient pattern matching in elastic-degenerate strings
• Approximate pattern matching on elastic-degenerate text
• Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding Patterns with Variable Length Gaps or Don’t Cares
• AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• ALGORITHMIC COMBINATORICS ON PARTIAL WORDS
• On-line pattern matching on similar texts
• Faster Online Elastic Degenerate String Matching
• Algorithms on Strings