1. Point matching under non-uniform distortions
- Author
-
Akutsu, Tatsuya, Kanaya, Kyotetsu, Ohyama, Akira, and Fujiyama, Asao
- Subjects
- *
ELECTROPHORESIS , *ALGORITHMS - Abstract
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. [Copyright &y& Elsevier]
- Published
- 2003
- Full Text
- View/download PDF