Computing Maximal Palindromes in Non-Standard Matching Models
"Explore the intriguing realm of palindromes in text processing and bioinformatics through alternative definitions in various matching models. Learn about efficient algorithms and groundbreaking research on symmetry-based and reversal-based palindromes. Discover the intersection of computational algorithms and combinatorial algorithms, presented at the International Workshop on Combinatorial Algorithms."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Computing maximal palindromes in non-standard matching models Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda International Workshop on Combinatorial Algorithms (pp. 165-179), 1-3 July 2024 Ischia, Italy. Presenter: Wen-Yu Chang Date: Feb. 18, 2025
Abstract (1/2) Palindromes are popular and important objects in textual data processing, bioinformatics, and combinatorics on words. Let ? = ??? be a string, where X and Y are of the same length and a is either a single character or the empty string. Then, there exist two alternative definitions for palindromes: S is said to be a palindrome if S is equal to its reversal ?? (Reversal-based definition); or if its left-arm X is equal to the reversal of its right-arm ?? (Symmetry-based definition). It is clear that if the equality ( ) used in both definitions is exact character matching (=), then the two definitions are the same. 2
Abstract (2/2) However, if we apply other string-equality criteria , including the complementary model for biological sequences, the parameterized model, the order-preserving model, the Cartesian-tree model, and the palindromic-structure model, then are the reversal-based palindromes and the symmetry-based palindromes the same? To the best of our knowledge, no previous work has considered or answered this natural question. In this paper, we first provide answers to this question, and then present efficient algorithms for computing all maximal generalized palindromes that occur in a given string. After confirming that Gusfield s offline suffix-tree based algorithm for computing maximal symmetry-based palindromes can be readily extended to the aforementioned matching models, we show how to extend Manacher s online algorithm for computing maximal reversal-based palindromes in linear time for all the aforementioned matching models. 3
Substring Consistent Symmetric and Two- Transitive Relation (SCSTTR) 4
Complementary Matching f(A) = T, f(T) = A, f(C) = G, f(G) = C Sym-palindromes AATCGGATT Rev-palindromes ACCTGCAGGT TGGACGTCCA 5
Parameterized Matching a b c d a b c d Sym-palindromes f(a) = c, f(b) = b, f(c) = d, f(d) = a abccbbddbc cbddbbddbc Rev-palindromes f(a) = b, f(b) = a, f(c) = d, f(d) = c a b c d a b c d abccbaddab baddabccba 6
Order-Preserving Matching Sym-palindromes accbabcddb 1332112331 Rev-palindromes accbaabcca 1332112331 7
Cartesian-tree Matching (1/3) Sym-palindromes outward: (?[1.. ? /2 ])? ???[ ? /2 .. ? ] R inward: ? 1.. ? /2 ?? ? ? /2 .. ? e.g. aaaaabcd a a a a b a a b a c a c d a a d outward: aaaa abcd inward: aaaa dcba 8
Cartesian-tree Matching (2/3) Sym-palindromes outward: bbdacdbcbd cadbb & dbcbd inward: badbcdbcbd badbc & dbcbd b a b a b d b b b d b c d c c d d c b d outward inward 9
Cartesian-tree Matching (3/3) Rev-palindromes decfadbdc a c b c d f d e d 10
Palindromic-structure Matching Sym-palindromes Rev-palindromes 11
Maximal Theta Reversal-based Palindromes f(A) = T, f(T) = A, f(C) = G, f(G) = C T C C C T A G A G A A G A G A T C C C T 12
Maximal Parameterized Reversal-based Palindromes (1/2) ? ? 0 0 13
Maximal Parameterized Reversal-based Palindromes (2/2) ? ? 14
Maximal Order-preserving Reversal-based Palindromes Manacher s algorithm LPS: Longest Palindromic Substring S = dbcbaabcd C L R - d - b - c - b - a - a - b - c - d - LPS length 0 1 0 1 0 3 0 1 0 1 6 1 0 1 0 1 0 1 0 6 15
Maximal Cartesian-tree Reversal-based Palindromes Update PD?(parent distance) ? ? d e c f a d b d c 0 0 1 0 1 2 1 PD?[?..?] 0 1 0 1 0 1 2 1 2 PD?[? 1..?+1] 16
Maximal Palindromic-structure Reversal- based Palindromes LPal: the length of the longest suffix palindrome of the position i LPal : the length of the longest prefix palindrome of the position i ? ? b b c b a d b a b b LPal[i..j] 1 1 3 1 1 1 1 3 LPal [i..j] 3 1 1 1 1 3 1 1 LPal[i-1..j+1] 1 2 1 3 1 1 1 1 3 2 LPal [i-1..j+1] 2 3 1 1 1 1 3 1 2 1 17
Complexity Time: O(?) Space: O(?) 18
