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 (16)

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

This page was built for publication: Efficient pattern matching in elastic-degenerate strings