<< 2012-3 >>
Department of
Computer Science

# Algorithms on Extended (delta, gamma)-Matching

Inbok Lee, Raphaël Clifford, Sung-Kyul Kim, Algorithms on Extended (delta, gamma)-Matching. International Conference on Computational Science and its Applications (ICCSA 2006). ISSN 0302-9743, pp. 1137–1142. May 2006. No electronic version available.

## Abstract

Approximate pattern matching plays an important role in various applications, such as bioinformatics, computer-aided music analysis and computer vision. We focus on $(\delta, \gamma)$-matching. Given a text $T$ of length $n$, a pattern $P$ of length $m$,and two parameters $\delta$ and $\gamma$, the aim is to find all the substring $T[i, i+m-1]$ such that (a) $\forall 1 \le j \le m$, $|T[i+j-1] - P[j]| \le \delta$ ($\delta$-matching) , and (b) $\sum_{1 \le j \le m} |T[i+j-1] - P[j]| \le \gamma$ ($\gamma$-matching). In this paper we consider three variations of $(\delta, \gamma)$-matching: {\em amplified matching}, {\em transposition-invariant matching}, and {\em amplified transposition-invariant matching}. For each problem we propose a simple and efficient algorithm which is easy to implement.