Match search algorithm

Subsequently Crowing Matchings the Match-search Algorithm... 

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). 

Therefore, a further improvement of the match-search algorithm was developed the dynamic match-search algorithm. The new algorithm extends the dy-... 

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.12 A chemistry space can be searched for the compound most similar to a query with the following dynamic programming procedure. For every directed edge and every link type, a list of the most similar fragments is calculated with the match-search algorithm. When a second link is found in the fragment, the dynamic programming matrix can be used in order to find the highest possible similarity value (red arrow, the part of the query which has to be matched to the link blue arrows, the compatible link types green arrows, previously calculated similarity values for these edge-link-type combinations).

Technically valid calibrations transfer is not the trivial process that some would propose. In fact, due to advancing calibration mathematics such as PCR, PLS, and spectral matching/search algorithms, it becomes even more critical that transfer technologies be scientifically scrutinized. To date, the most successful approach for transferring calibrations for use with all multivariate mathematical modeling techniques is found in a three-pronged approach ... 

FIGURE 21.14 Flow-chart of the Mix-Match search algorithm. 

---