Back to Search
Start Over
Point matching under non-uniform distortions
- Source :
-
Discrete Applied Mathematics . Apr2003, Vol. 127 Issue 1, p5. 17p. - Publication Year :
- 2003
-
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]
- Subjects :
- *ELECTROPHORESIS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 127
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 9231858
- Full Text :
- https://doi.org/10.1016/S0166-218X(02)00282-2