目标化合物析分系统中的重要算法  

Important Algorithms Used in the Target Parsing System

作　　者：王利莎[1] 袁身刚[1] 欧阳政[1] 郑崇直[1] 

机构地区：[1]中国科学院上海有机化学研究所,中国科学院计算机化学开放实验室,上海200032

出　　处：《化学学报》2001年第2期241-246,共6页Acta Chimica Sinica

基　　金：国家科技部"九五"重点攻关项目 ( 96-5 47-0 1-0 2 );国家基础发展规划 (G19980 5 115 );中法先进研究计划 (PRA98M -A0 36);国家自然基金 ( 2 9872 0 48);国家高性能计算基金 ( 995 0 7)资助项

摘　　要：介绍了目标化合物析分系统中所用到的三个重要算法 .它们是 :最短拓扑距离的求解、析分过程结束的判别以及合成树的构建 .分子结构中任意两个原子之间最短拓扑距离的求解是建立在采用队列数据结构的宽度优先搜索算法基础上的 .析分过程结束的判别是由在新Morgan算法基础上产生的化合物的唯一编码和B -树两种算法构成 .前者是为了将前体与原料库中每个化合物是否同构的复杂问题简化为码之间的比较问题 ;后者是一种高效文件组织方式 ,将代表原料库中化合物的唯一编码作为检索键来组织建库 ,从而实现对原料库的快速查询 .合成树采用的是链表存储方式 ,每一个结点由六个域组成 ,且在建树和画树的过程中 ,均用前序遍历 .这些算法是实现析分系统的基础 。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.

关 键 词：拓扑距离 宽度优先搜索 MORGAN算法 B-树算法 目标化合物析分系统 

分 类 号：O641[理学—物理化学]