Class TreeMatcher


  • public class TreeMatcher
    extends java.lang.Object
    Finds the optimal matching of nodes between two PharmacophoreTrees employing a dynamic programing scheme termed as "match-search" algorithm in the original publication (DOI:10.1023/a:1008068904628). Given a set of initial splits (a split is created by cutting an edge each in both trees), both pair of subtrees resulting from the split are used as an input for the recursive extensionMatch method. Starting from the head nodes of the subtrees, extension matches up to a certain size containing the head node and connecting nodes are enumerated. The best-scoring extension match are further considered. The resulting cut subtrees from the extension cuts form possible matches and are also used as an input for recursive calls of the match-search routine. The highest-scoring assignments of the subtrees are determined using a Hungarian Algorithm. If a match between two subtrees fulfills size and balance criteria, the recursion is stopped. The assignments of the nodes in the matching and the score of a subtree match are stored in TreeMatching objects. These objects are stored in a dynamic programming matrix to facilitate memoization of the results.
    Author:
    joel