학술논문
Approximate regular expression pattern matching with concave gap penalties.
Document Type
Journal
Author
Knight, J. R. (1-AZ-C) AMS Author Profile; Myers, E. W. (1-AZ-C) AMS Author Profile
Source
Subject
68 Computer science -- 68Q Theory of computing
68Q25Analysis of algorithms and problem complexity
68Q25
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 optimal alignment between $A$ and one of the sequences $B$ exactly matched by $R$. An alignment between sequences $A=a_1a_2\cdots a_M$ and $B=b_1b_2\cdots b_N$ is a list of ordered pairs $\langle (i_1,j_1), (i_2,j_2),\cdots , (i_t,j_t)\rangle$ such that $i_k1$, $w(k+1)-w(k)\le w(k)-w(k-1)$. We present an $O(MP(\log M+\log^2P))$ algorithm for approximate regular expression matching for an arbitrary $\delta$ and any concave $w$.''