Title:
DEVICE AND METHOD FOR HIGH SPEED GRAPH MATCHING SEARCH TO DETERMINE SIMILARITY BETWEEN MOLECULES
Document Type and Number:
WIPO Patent Application WO/2011/102384
Kind Code:
A1
Abstract:
Disclosed is a high speed molecular graph matching algorithm for use with a method for determining the matching between atoms of two molecules and superimposing the molecules accordingly. Specifically disclosed is a method for determining the optimum atomic matching between a first molecule A and a second molecule B by determining the degree of matching between each atom of the first molecule A and each atom of the second molecule B (represented by the expression m(Ai) = Bk) and superimposing the molecules, said method comprising: a step of calculating S1(Ai, Bk), S2(Ai, Bk), and S3(Ai, Bk) for all sets {i, k}; a step of determining the overall graph matching score M(A, B) by first associating the pair of atoms (Ai, Bk) having the largest calculated value for S3(Ai, Bk) with that having the second largest value for S3(Aj, Bl), then associating the pair of atoms having the second largest value for S3(Aj, Bl) with that having the third largest value, and repeating this procedure until all pairs of atoms have been associated with one another; and a step of, if the determined M(A, B) exceeds a threshold value, outputting superimposition of the molecules A and B.
More Like This:
Inventors:
SHIRAI TSUYOSHI (JP)
Application Number:
PCT/JP2011/053280
Publication Date:
August 25, 2011
Filing Date:
February 16, 2011
Export Citation:
Assignee:
EDUCATIONAL CORP KANSAI BUNRI SOUGOUGAKUEN (JP)
SHIRAI TSUYOSHI (JP)
SHIRAI TSUYOSHI (JP)
International Classes:
C40B30/02; G06F17/30; G06F17/50
Foreign References:
| JP2004118594A | 2004-04-15 |
Other References:
HATTORI, M.: "Heuristics for chemical compound matching, Genome informatics.", INTERNATIONAL CONFERENCE ON GENOME INFORMATICS, vol. 14, 2003, pages 144 - 153
TAKAHASHI, Y.: "Recognition of largest common structural fragment among a variety of chemical structures", ANALYTICAL SCIENCE, vol. 3, 1987, pages 23 - 28
RAYMOND, J.W. ET AL.: "Maximum common subgraph isomorphism algorithms for the matching of chemical structures", JOURNAL OF COMPUTER-AIDED MOLECULAR DESIGN, vol. 16, no. 7, July 2002 (2002-07-01), pages 521 - 533
KOCH, I. ET AL.: "Enumerating all connected maximal common subgraphs in two graphs", THEORETICAL COMPUTER SCIENCE, vol. 250, no. 1-2, January 2001 (2001-01-01), pages 1 - 30
TAKAHASHI, Y.: "Recognition of largest common structural fragment among a variety of chemical structures", ANALYTICAL SCIENCE, vol. 3, 1987, pages 23 - 28
RAYMOND, J.W. ET AL.: "Maximum common subgraph isomorphism algorithms for the matching of chemical structures", JOURNAL OF COMPUTER-AIDED MOLECULAR DESIGN, vol. 16, no. 7, July 2002 (2002-07-01), pages 521 - 533
KOCH, I. ET AL.: "Enumerating all connected maximal common subgraphs in two graphs", THEORETICAL COMPUTER SCIENCE, vol. 250, no. 1-2, January 2001 (2001-01-01), pages 1 - 30
Attorney, Agent or Firm:
TANAKA, Mitsuo et al. (JP)
Mitsuo Tanaka (JP)
Mitsuo Tanaka (JP)
Download PDF:
Claims:
Previous Patent: FINE FIBERS WITH MODIFIED SURFACE
Next Patent: IMAGE RECOGNITION-TYPE CELL COLLECTOR
Next Patent: IMAGE RECOGNITION-TYPE CELL COLLECTOR