Class TreeMatcher
- java.lang.Object
-
- com.actelion.research.chem.descriptor.pharmacophoretree.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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
TreeMatcher.FeatureMatch
TODO: don't add null-matches!static class
TreeMatcher.TreeMatching
-
Field Summary
Fields Modifier and Type Field Description static double
ALPHA
static int
EXTENSION_MATCH_NODE_NR_LIMIT
static int
EXTENSION_MATCHES
static int
INITIAL_SPLITS
static double
MATCH_BALANCE
static int
MATCH_NODE_NR_LIMIT
static double
MATCH_SIZE_LIMIT
static double
NULL_MATCH_SCALING
static double
SIMILARITY_SCALING_SPLIT_SCORE
static double
SIZE_RATIO
-
Constructor Summary
Constructors Constructor Description TreeMatcher(PharmacophoreTree queryTree, PharmacophoreTree baseTree)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int[][]
findInitialSplits()
TreeMatcher.TreeMatching
matchSearch()
finds a set of balanced, high-scoring initial splits that are then used as an input for the extension match algorithm
-
-
-
Field Detail
-
EXTENSION_MATCHES
public static final int EXTENSION_MATCHES
- See Also:
- Constant Field Values
-
ALPHA
public static final double ALPHA
- See Also:
- Constant Field Values
-
NULL_MATCH_SCALING
public static final double NULL_MATCH_SCALING
- See Also:
- Constant Field Values
-
SIMILARITY_SCALING_SPLIT_SCORE
public static final double SIMILARITY_SCALING_SPLIT_SCORE
- See Also:
- Constant Field Values
-
MATCH_BALANCE
public static final double MATCH_BALANCE
- See Also:
- Constant Field Values
-
MATCH_SIZE_LIMIT
public static final double MATCH_SIZE_LIMIT
- See Also:
- Constant Field Values
-
MATCH_NODE_NR_LIMIT
public static final int MATCH_NODE_NR_LIMIT
- See Also:
- Constant Field Values
-
EXTENSION_MATCH_NODE_NR_LIMIT
public static final int EXTENSION_MATCH_NODE_NR_LIMIT
- See Also:
- Constant Field Values
-
INITIAL_SPLITS
public static final int INITIAL_SPLITS
- See Also:
- Constant Field Values
-
SIZE_RATIO
public static final double SIZE_RATIO
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
TreeMatcher
public TreeMatcher(PharmacophoreTree queryTree, PharmacophoreTree baseTree)
-
-
Method Detail
-
matchSearch
public TreeMatcher.TreeMatching matchSearch()
finds a set of balanced, high-scoring initial splits that are then used as an input for the extension match algorithm- Returns:
-
findInitialSplits
public int[][] findInitialSplits()
-
-