Fast string matching for DNA sequences

In this paper we propose the Maximal Average Shift (MAS) algorithm that finds a pattern scan order that maximizes the average shift length. We also present two extensions of MAS: one improves the scan speed of MAS by using the scan result of the previous window, and the other improves the running ti...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-04, Vol.812, p.137-148
Main Authors: Ryu, Cheol, Lecroq, Thierry, Park, Kunsoo
Format: Article
Language:English
Subjects:
Computer Science
Data Structures and Algorithms
Pattern scan order
Scan speed
String matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we propose the Maximal Average Shift (MAS) algorithm that finds a pattern scan order that maximizes the average shift length. We also present two extensions of MAS: one improves the scan speed of MAS by using the scan result of the previous window, and the other improves the running time of MAS by using q-grams. These algorithms show better average performances in scan speed than previous string matching algorithms for DNA sequences.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.09.031