Given a sequence A and regular expression R, the approximate regular expression matching problem is to find a sequence matching R whose optimal alignment with A is the highest scoring of all such sequences. This paper develops an algorithm to solve the problem in time O(MN), where M and N are the lengths of A and R. Thus, the time requirement is asymptotically no worse than for the simpler problem of aligning two fixed sequences. Our method is superior to an earlier algorithm by Wagner and Seiferas in several ways. First, it treats real-valued costs, in addition to integer costs, with no loss of asymptotic efficiency. Second, it requires only O(N) space to deliver just the score of the best alignment. Finally, its structure permits implementation techniques that make it extremely fast in practice. We extend the method to accommodate gap penalties, as required for typical applications in molecular biology, and further refine it to search for sub-strings of A that strongly align with a sequence in R, as required for typical data base searches. We also show how to deliver an optimal alignment between A and R in only O(N + log M) space using O(MN log M) time. Finally, an O(MN(M + N) + N2log N) time algorithm is presented for alignment scoring schemes where the cost of a gap is an arbitrary increasing function of its length.

E W Myers

W Miller

Bulletin of mathematical biology

BULLETIN OF MATHEMATICAL BIOLOGY 是数学生物学学会的官方期刊，传播原始研究成果和其他与生物学和数学科学接口相关的信息。贡献应该与这两个领域相关。为了适应广泛的新发展，该期刊接受各种投稿，包括：原创研究文章侧重于借助数学科学工具或新的数学工具和方法获得的新生物学见解，这些工具和方法已证明适用于生物学调查研究数学生物学教育评论评论观点，以及讨论对专业重要的问题的贡献所有贡献都经过同行评审。

The Bulletin of Mathematical Biology is the official journal of the Society for Mathematical Biology, dedicated to disseminating original research findings and information related to the interface between biology and mathematical sciences. Contributions should be relevant to both fields. The journal welcomes a variety of submissions, including original research articles that focus on new biological insights gained through mathematical tools or novel mathematical methods that have proven applicable to biological investigations; reviews on mathematical biology education; and discussions and viewpoints on issues of professional significance. All contributions undergo peer review.

《Bulletin of Mathematical Biology》是数学生物学学会的官方期刊，旨在传播原始研究成果及与生物学和数学科学交叉领域相关的信息。我们欢迎与这两个领域相关的各种投稿，包括：利用数学科学工具或新方法获得的新生物学见解的原创研究文章，这些工具和方法已被证明适用于生物学研究；数学生物学教育的评论；以及对专业重要问题的讨论和观点。所有投稿均经过同行评审。

Bulletin of Mathematical Biology

Bull Math Biol

Approximate matching of regular expressions.

An algorithm to solve the problem in time O(MN), where M and N are the lengths of A and R, and requires only O(N) space to deliver just the score of the best alignment, superior to an earlier algorithm by Wagner and Seiferas.

Category	Quartile
数学	4
数学, 生物学	4
数学, 数学与计算生物学	4

Approximate matching of regular expressions.

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info