On the application of the combinatorial theory of solvability to the analysis of chemographs: Part 2. Local completeness of invariants of chemographs in view of the combinatorial theory of solvability

Abstract

This paper presents a novel formalism for the application of the combinatorial theory of solvability to graph-theoretical problems in chemoinformatics. In the second part, it is shown that the binary relations of membership of χ-chains and χ-nodes in chemographs are invariants and the criteria for the completeness of these invariants are obtained. In the framework of the combinatorial theory of solvability, χ-graphs are treated as objects and their invariants (sets of invariants), as feature descriptions. We obtain criteria of the local completeness for the considered sets of invariants with respect to a given set of precedents. It is shown that combinatorial testing of the criteria for the local regularity of the corresponding problem of recognition allows one to make a quantitative assessment of the local completeness of the invariants under study. The formalism developed for the analysis of the local completeness of the invariants of chemographs provides considerable opportunities for substantiated generation and testing of various metrics on the sets of chemographs. Finally, the results of the practical application of the proposed formalism to one of the problems of chemoinformatics, i.e., finding structurally similar chemical compounds, are presented.