Graph Complexity of Chemical Compounds in Biological Pathways
Atsuko Yamaguchi, Kiyoko Flora Aoki-Kinoshita, Hiroshi Mamitsuka · 2003
Introduction Graph theory for chemical compounds is often studied for the fact that labeled graphs are suited to express the connectivity of chemical compounds [4]. However, in the field of chemoinformatics, methods using graph algorithms have not entered the mainstream because graph problems comparing two graphs are often intractable. For example, the problem of finding the maximum common subgraph of two graphs is known to be NP-hard [1], even for two graphs of bounded degree [3]. Therefore, we focus on chemical compounds in biological pathways and analyze the characteristics of the chemical compounds to reduce the problem space to allow for tractable comparisons of graphs. In analyzing these characteristics, we can focus on consistent measures for estimating the similarity of chemical compounds. Such measures are essential for gaining an understanding of the structural aspects of chemical compounds. They also assist in useful tasks such as querying chemical databases. As an example