Recursive Division the Split-search Algorithm

Subsequently Crowing Matchings the Match-search Algorithm 

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. 

An implementation of the above algorithm in this recursive fashion would have an exponential asymptotic runtime behavior. A simple observation shows that such high computing demand is unnecessary. If two trees A and B with nA and nB nodes, respectively, are compared, only 4(nA-l)(nB-l) different calls of 

Match-Search with Caps the Dynamic Match-search Algorithm 

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

---