Point matching under non-uniform distortions

被引：21

作者：

Akutsu, T

Kanaya, K

Ohyama, A

Fujiyama, A

机构：

[1] Univ Tokyo, Inst Med Sci, Ctr Human Genome, Minato Ku, Tokyo 1088639, Japan

[2] Mitsui Knowledge Ind Co Ltd, Dept Biosci Syst, Nakano Ku, Tokyo 1648555, Japan

[3] Natl Inst Genet, Mishima, Shizuoka 4118540, Japan

来源：

DISCRETE APPLIED MATHEMATICS | 2003年 / 127卷 / 01期

关键词：

point matching; geometric matching; electrophoresis; NP-hard;

D O I：

10.1016/S0166-218X(02)00282-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper discusses the pattern matching problem for points under non-uniform distortions, which arises from the analysis of two-dimensional (2-D) electrophoresis images. First, we provide a formal definition of the problem. Next, we prove that it is NP-hard in two (or more) dimensions. This proof is based on a reduction from planar 3SAT. Then we present a simple polynomial time algorithm for a special and one-dimensional case of the problem, which is based on dynamic programming. We also present a practical heuristic algorithm for identifying a match between two sets of spots in 2-D gel electrophoresis images obtained from genomic DNA. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：5 / 21

页数：17

共 14 条

[1] CONGRUENCE, SIMILARITY, AND SYMMETRIES OF GEOMETRIC OBJECTS [J].