Acta Chimica Sinica ›› 2001, Vol. 59 ›› Issue (2): 241-246. Previous Articles     Next Articles

Original Articles



  1. 中国科学院上海有机化学研究所.上海(200032);中国科学院计算机化学开放实 验室.上海(200032)
  • 发布日期:2001-02-15

Important algorithms used in the target parsing system

Wang Lisha;Yuan Shengang;Ou Yangzheng;Zheng Chongzhi   

  1. Shanghai Inst Organ Chem., CAS.Shanghai(200032);Lab of Comp Chem, CAS.Shanghai(200032)
  • Published:2001-02-15

This article presents the three most important algorithms used in the Target Parsing System. They are the shortest topological distance between two atoms, the determination of the termination of the parsing process and the construction of the synthesis tree. The shortest topological distance between two atoms in a structure was designed according to the widely used breadth first search algorithm which uses a data structure called Queue. The determination of the termination of the parsing process consists of the canonicalisation algorithm based on the new Morgan algorithm and the B - tree algorithm, The former is used to convert the complicated isomorphic problem into the comparison between two unique codes. The latter is one of efficient file organizations, in which the unique code is used to represent the compound in the material data base. All these codes are organized in a B - tree. Thus, for a given compound it is very fast to know if it is contained in the data base by searching in the B - tree. The construction of the synthesis tree adopts data structure of list. Each node of the list consists of six fields. Both the generation and drawing of the synthesis tree use the preorder technique. Since these algorithms constitute the core of the Target Parsing System, their proper design and implementation is extremely important.


CLC Number: