A graph-theoretic model to solve the approximate string matching problem allowing for translocations

DOI10.1016/J.JDA.2013.08.004MaRDI QIDQ396701zbMATH OpenOpenAlexFDO

Authors Pritom Ahmed, A. S. M. Shohidull Islam, M. Sohel Rahman

Publication date 13 August 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.08.004

zbMATH Keywords

algorithmsgraphspattern matchingapproximate string matchingtranslocations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• A graph theoretic model to solve the approximate string matching problem allowing for translocations
• Text searching allowing for inversions and translocations of factors
• Sequence searching allowing for non-overlapping adjacent unbalanced translocations
• String matching with inversions and translocations in linear average time (most of the time)
• scientific article; zbMATH DE number 1962813

Cites work

• scientific article; zbMATH DE number 5725179 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Efficient string matching
• String matching with inversions and translocations in linear average time (most of the time)

Cited in

(5)

• Sequence searching allowing for non-overlapping adjacent unbalanced translocations
• Text searching allowing for inversions and translocations of factors
• On the complexity of approximately matching a string to a directed graph
• Complexity issues of string to graph approximate matching
• A graph theoretic model to solve the approximate string matching problem allowing for translocations

This page was built for publication: A graph-theoretic model to solve the approximate string matching problem allowing for translocations

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