Degenerate string comparison and applications

DOI10.4230/LIPICS.WABI.2018.21MaRDI QIDQ5090361zbMATH OpenFDO

Authors Mai Alzamel, Lorraine A. K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S. Iliopoulos, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.WABI.2018.21

zbMATH Keywords

degenerate stringselastic-degenerate stringsgeneralised degenerate stringspalindromesstring comparison

Mathematics Subject Classification ID

Computational methods for problems pertaining to biology (92-08) Protein sequences, DNA sequences (92D20)

Recommendations

• Comparing Degenerate Strings
• Faster Online Elastic Degenerate String Matching
• Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform
• Pattern matching on elastic-degenerate text with errors

Cites work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A subquadratic algorithm for minimum palindromic factorization
• Algorithms on Strings, Trees and Sequences
• Generalized String Matching
• On the complexity of k-SAT
• On-line pattern matching on similar texts
• Palindromic decompositions with gaps and errors
• Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
• Which problems have strongly exponential complexity?

Cited in

(15)

• Approximate pattern matching on elastic-degenerate text
• Longest property-preserved common factor: a new string-processing framework
• Indeterminate string factorizations and degenerate text transformations
• Comparing Degenerate Strings
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Maximal degenerate palindromes with gaps and mismatches
• On the Complexity of String Matching for Graphs
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Elastic-degenerate string matching with 1 error
• Linear time construction of indexable founder block graphs
• Elastic-degenerate string matching with 1 error or mismatch
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• Reconstructing general matching graphs
• Elastic-degenerate string comparison
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

This page was built for publication: Degenerate string comparison and applications

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