Thumbnail
Access Restriction
Subscribed

Author Barsky, Marina ♦ Stege, Ulrike ♦ Thomo, Alex ♦ Upton, Chris
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword String matching ♦ Bioinformatics ♦ Complexity
Abstract We present a novel graph model and an efficient algorithm for solving the “threshold all against all” problem, which involves searching two strings (with length $\textit{M}$ and $\textit{N},$ respectively) for all maximal approximate substring matches of length at least $\textit{S},$ with up to $\textit{K}$ differences. Our algorithm solves the problem in time $O(MNK_{3}),$ which is a considerable improvement over the previous known bound for this problem. We also provide experimental evidence that, in practice, our algorithm exhibits a better performance than its worst-case running time.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-06-12
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 26
Starting Page 1
Ending Page 26


Open content in new tab

   Open content in new tab
Source: ACM Digital Library