Tree-searching algorithm

Floquet et al. (1985) proposed a tree searching algorithm in order to synthesize chemical processes involving reactor/separator/recycle systems interlinked with recycle streams. The reactor network of this approach is restricted to a single isothermal CSTR or PFR unit, and the separation units are considered to be simple distillation columns. The conversion of reactants into products, the temperature of the reactor, as well as the reflux ratio of the distillation columns were treated as parameters. Once the values of the parameters have been specified, the composition of the outlet stream of the reactor can be estimated and application of the tree searching algorithm on the alternative separation tasks provides the less costly distillation sequence. The problem is solved for several values of the parameters and conclusions are drawn for different regions of operation. 

R. J. Dakin. A tree search algorithm for mixed integer programming problems. Computer J., 8 250,1965. 

P. Floquet, L. Pibouleau, and S. Domenech. Reactor separator sequences synthesis by a tree searching algorithm. Process System Engineering, Symp. Series, 92 415, 1985. 

T. K. Pho and L. Lapidus. Topics in computer-aided design Part II. Synthesis of optimal heat exchanger networks by tree searching algorithms. AlChEJ., 19 1182,1973. 

Pho, T.K. and Lapidus, L., "Topics in Computer-Aided Design Part II. Synthesis of Optimal Heat Exchanger Networks by Tree Search Algorithms," AlChE Journal, Vol. 19, No. 6, pp 1182-1189, November 1973. 

Quartet puzzling is a relatively rapid tree-searching algorithm available for ML tree building (Strinuner and von Haeseler, 1996) and is available in PUZZLE. 

Constraints are typically applied as a penalty function that is added as an extra term in the scoring function, often as some simple function (e.g., harmonic) of the difference between the actual and target values. Other strategies are possible, however, and constraints have also been used systematically in the construction of model structures. This can be applied to distance constraints, where a buildup procedure is used to generate stmctures that satisfy all constraints [64]. Angle constraints can also be used to systematically search the conformational space, both using a branch-and-bound procedure [65] or in a tree-search algorithm in combination with distance constraints [66]. 

In the worst case, the backtracking algorithm will form a search tree of depth n, where n is the number of atoms in the query graph. Also, in this case a separate sub-tree search process for each atom of the target graph will be initiated. That is why the linear multiplier m is apphed to Eq. (7). 

Third, it is easy to find the components and the decomposition tree. An algorithm for this purpose, which uses depth first search (a systematic method of exploring a graph) has been developed (5 D 55,56) It runs in 0(n+m) time on an n vertex, m edge graph. 

The most problematic issue of the split-search algorithm as described above is that unmatched nodes may occur between matched nodes. This gap , also called an inner-NIL match, becomes harder to justify the larger it gets since the two matched parts of the molecule are assumed to interact with the same subpockets of an active site (see also Fig. 4.3). In the following, we will assume that inner-NIL matches are forbidden - which makes the development of an alternative matching algorithm necessary. We will first describe the new algorithm, called match-search, in a recursive fashion which operates on two trees A and B. 

Fig. 4.4 The match search algorithm creates a matrix with one cell for each pair ofdirected tree edges. The cell stores the overall similarity of the two subtrees. The similarity value is calculated with a dynamic programming scheme shown on the right. First, an extension match (blue ellipsoid) is searched. Then the subtrees are cut and matched in all possible combinations. For each combination, a similarity value can be extracted from the matrix (exemplarily shown by the blue arrows). A maximum-weight bipartite matching solves the assignment of the subtrees.

The match-search algorithm described above works well for similar Feature Trees of equal sizes or if one tree is fully contained in the other tree. However, as the algorithm cannot generate inner-NIL matches, variable linker regions between pharmacophoric groups cannot be modeled (see Fig. 4.5). 

In order to build an MTree model from more than two Feature Trees, the dynamic match-search algorithm can be applied in a hierarchical manner. We developed two efficient heuristics for this task ... 

Fig. 4.7 (a) Three of the 10 actives (colored red) used to select the final subset are shown with two unknowns (colored black) found amongst their nearest neighbors. The Feature Tree similarity values (calculated with the dynamic match-search algorithm)... 

Fig. 4.15 Hit list from Feature Tree fragment space searches are grouped by a molecular framework analysis (y-axis) and the Feature Tree similarity score (x-axis). The search algorithm indeed produces compounds from...

Thus ligands are often incrementally built within the active site. The principle of the FlexX algorithm is that, physicochemical properties provide the most useful information for ligand placement. Once a set of favorable placement of the base fragment (the core part of the ligand from where the incremental construction starts) has been computed, the ligand building can be started. The incremental construction is formulated as a tree search (Fig. 14) problem. 

---