Maximal degenerate palindromes with gaps and mismatches

DOI10.1016/J.TCS.2023.114182MaRDI QIDQ6073887zbMATH OpenFDO

Authors Mai Alzamel, Christopher Hampson, Costas S. Iliopoulos, Zara Lim, Solon P. Pissis, Dimitrios Vlachakis, Steven Watts

Publication date 12 October 2023

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/J.TCS.2023.114182

zbMATH Keywords

degenerate palindromeinverted repeatmismatchstring factorisation

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Review text

The exact computation of maximal degenerate palindromes with gaps and mismatches is examined through the construction of an optimization algorithm. The algorithm identifies inverted repeats with permitted gaps and mismatches. An interesting case study is the application of the algorithm on a set of SARS-COV-2 genomes revealing unexpected significance of the patterns of its genomic signature. As a future work the authors consider the prediction of secondary structures from genomic strings through the same procedure.

Recommendations

• Palindromic decompositions with gaps and errors
• Palindromic decompositions with gaps and errors
• Searching for Gapped Palindromes
• Searching for gapped palindromes
• Degenerate string comparison and applications

Cites work

• \(\mathrm{Pal}^{k}\) is linear recognizable online
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• 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
• Computing palindromic factorizations and palindromic covers on-line
• Efficient string matching with k mismatches
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Finding gapped palindromes online
• Generalized String Matching
• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• On-line pattern matching on similar texts
• Palindromes in SARS and other coronaviruses
• Palindromic decompositions with gaps and errors
• Parallel detection of all palindromes in a string
• Pattern matching on elastic-degenerate text with errors
• Searching for gapped palindromes
• Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.

Cited in

(2)

• 2-dimensional palindromes with k mismatches
• Reconstructing general matching graphs

This page was built for publication: Maximal degenerate palindromes with gaps and mismatches

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