Approximate String Matching with Non-Overlapping Adjacent Unbalanced Translocations

Domenico Cantone, Simone Faro () and Arianna Pavone
Additional contact information
Domenico Cantone: Department of Mathematics and Computer Science, University of Catania, Viale A. Doria 6, I-95125 Catania, Italy
Simone Faro: Department of Mathematics and Computer Science, University of Catania, Viale A. Doria 6, I-95125 Catania, Italy
Arianna Pavone: Department of Mathematics and Computer Science, University of Palermo, Via Archirafi 34, I-90123 Palermo, Italy

Mathematics, 2025, vol. 13, issue 13, 1-28

Abstract: In this paper, we investigate the approximate string matching problem when the allowed edit operations are non-overlapping unbalanced translocations of adjacent factors . This kind of edit operation takes place when two adjacent substrings of the text swap, resulting in a modified string. The two involved substrings are allowed to be of different lengths. Such large-scale modifications of strings have various applications, notably in fields such as computational biology and genomics, where structural rearrangements play a key role. However, despite their central role in many fields of text processing, little attention has been devoted to the problem of matching strings allowing for this kind of edit operation. In this paper, we present three algorithms for solving the problem, all of them with an O ( n m 3 ) worst-case and an O ( m 2 ) -space complexity, where m and n are the length of the pattern and of the text, respectively. Specifically, our first algorithm is based on the dynamic programming approach. Our second solution improves the previous one by making use of the Directed Acyclic Word Graph of the pattern. Finally, our third algorithm is based on an alignment procedure. We also show that under the assumptions of equiprobability and independence of characters, our second algorithm has an O ( n log σ 2 m ) average time complexity for an alphabet of size σ ≥ 4 .

Keywords: approximate string matching; unbalanced translocations; non-overlapping adjacent factors; edit operations; text algorithms; chromosomal rearrangements (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/13/2103/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/13/2103/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:13:p:2103-:d:1688477

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().