학술논문
Approximate regular expression pattern matching with concave gap penalties.
Document Type
Proceedings Paper
Author
Knight, James R. (1-AZ-C) AMS Author Profile; Myers, Eugene W. (1-AZ-C) AMS Author Profile
Source
Subject
68 Computer science -- 68Q Theory of computing
68Q25Analysis of algorithms and problem complexity
68Computer science -- 68R Discrete mathematics in relation to computer science
68R10Graph theory
68R15Combinatorics on words
68Q25
68
68R10
68R15
Language
English
Abstract
Summary: ``Given a sequence $A$ of length $M$ and a regular expression $R$ of length $P$, an approximate regular expression pattern matching algorithm computes the score of the best alignment between $A$ and one of the sequences exactly matched by $R$. There are a variety of schemes of scoring alignments. In a concave gap-penalty scoring scheme, a function $\delta (a,b)$ gives the score of each aligned pair of symbols $a$ and $b$, and a concave function $w(k)$ gives the score of a sequence of unaligned symbols, or gap, of length $k$. A function $w$ is concave if and only if it has the property that for all $k>1$, $w(k+1)-w(k)\leq w(k)-w(k-1)$. In this paper we present an $O(MP(\log M+\log^2 P))$ algorithm for approximate regular expression matching for an arbitrary $\delta$ and any concave $w$.''