TY - GEN

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

AU - Chakraborty, Samarjit

AU - Biswas, Somenath

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - dentifying 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 and B in three-dimensions, and a real number∈ > 0, find the maximum cardinality subset S ⊆ S for which there is an isometry I, such that each point of I(S) is within (ie253-1) 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. Our algorithms can be classifed into two groups. In the first we extend the notion of partial decision algorithms for ∈-congruence of point sets in 2-D in order to approximate the size of S. All the algorithms in this class exactly satisfy the constraint imposed by ∈. In the second class of algorithms this constraint is satisfied only approximately. In the latter case, we improve the known approximation ratio for this class of algorithms, while keeping the time complexity unchanged. For the existing approximation ratio, we propose algorithms with substantially better running times. We also suggest several improvements of our basic algorithms, all of which have a running time of O(n 8.5). These improvements consist of using randomization, and/or an approximate maximum matching scheme for bipartite graphs.

AB - dentifying 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 and B in three-dimensions, and a real number∈ > 0, find the maximum cardinality subset S ⊆ S for which there is an isometry I, such that each point of I(S) is within (ie253-1) 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. Our algorithms can be classifed into two groups. In the first we extend the notion of partial decision algorithms for ∈-congruence of point sets in 2-D in order to approximate the size of S. All the algorithms in this class exactly satisfy the constraint imposed by ∈. In the second class of algorithms this constraint is satisfied only approximately. In the latter case, we improve the known approximation ratio for this class of algorithms, while keeping the time complexity unchanged. For the existing approximation ratio, we propose algorithms with substantially better running times. We also suggest several improvements of our basic algorithms, all of which have a running time of O(n 8.5). These improvements consist of using randomization, and/or an approximate maximum matching scheme for bipartite graphs.

UR - http://www.scopus.com/inward/record.url?scp=34247094868&partnerID=8YFLogxK

U2 - 10.1007/3-540-48447-7_26

DO - 10.1007/3-540-48447-7_26

M3 - Conference contribution

AN - SCOPUS:34247094868

SN - 3540662790

SN - 9783540662792

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 264

BT - Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Gupta, Arvind

A2 - Tamassia, Roberto

PB - Springer Verlag

T2 - 6th International Workshop on Algorithms and Data Structures, WADS 1999

Y2 - 11 August 1999 through 14 August 1999

ER -