Approximation algorithms for 3-D common substructure identification in drug and protein molecules

摘要

Identifying the common 3-D substructure between two drug or protein molecules is an important problem in synthetic drug design and molecular biology.this problem can be represented as the following geometric pattern matching problem:given two point sets A adn B in three-dimensions,and a real number #epsilon#>0,find the maximum cardinality subset S is contained in = A for which there is an isometry I,such that each point of I(S) is within #epsilon# distance of a distinct point of B.Since it is difficult to solve this problem exactly,in this paper we have proposed several approximation algorithms with guaranteed approximation ratio.