Subtree Search Algorithms

Stuff about this module

class glypy.algorithms.subtree_search.MaximumCommonSubtreeResults(score, tree, similarity_matrix)

Bases: object

Results Container for maximum_common_subgraph()

glypy.algorithms.subtree_search._extract_maximum_common_subgraph(node_a, node_b, exact=False)

Given a pair of matched starting nodes from two separate glycan structures, traverse them together, copying the best matching branches into a new Glycan object.

Parameters:

node_a: Monosaccharide

node_b: Monosaccharide

exact: bool

Whether or not to take exact matches, or just take the best pairing. If exact = True and there is no exact match, the branch will terminate.

glypy.algorithms.subtree_search._find_max_of_matrix(solution_matrix)

Given the solution_matrix, find the coordinates of the maximum score

Returns:

float:

The maximum similarity score

int:

The index of the maximum similarity in seq_a

int:

The index of the maximum similarity in seq_b

glypy.algorithms.subtree_search.compare_nodes(node_a, node_b, include_substituents=True, exact=False, visited=None)

Score the pair of node_a and node_b and all pairings of their children.

Returns:

float:

The similarity score between the input nodes

glypy.algorithms.subtree_search.distinct_fragments(self, other, fragmentation_parameters=None)

Compute the set of distinct masses observed between two structures

Parameters:

self: Glycan or list

other : Glycan or list

Glycan objects whose fragments will be compared or lists of Fragment to compare.

fragmentation_parameters : dict, optional

If self and other are Glycan objects, these parameters will be used to call Glycan.fragments().

Returns:

set: The distinct fragment masses of self

set: The distinct fragment masses of other

glypy.algorithms.subtree_search.exact_ordering_inclusion(self, other, substituents=True, tolerance=0, visited=None)

A generalization of exact_ordering_equality() which allows for self to be matched to other, but for other to include more. Consequently, this method is not commutative.

glypy.algorithms.subtree_search.maximum_common_subgraph(seq_a, seq_b, exact=True)

Find the maximum common subgraph between seq_a and seq_b.

Parameters:

seq_a: Glycan

seq_b: Glycan

exact: bool

Whether to use exact equality or fuzzy equality

Returns:

MaximumCommonSubtreeResults

glypy.algorithms.subtree_search.n_saccharide_similarity(self, other, n=2, exact=False)

Calculate n-saccharide similarity between two structures

Parameters:

self: Glycan

other: Glycan

n: int

Size of the fragment saccharide to consider. Defaults to 2

exact: bool

Whether to use Glycan.exact_ordering_equality() or Glycan.topological_equality(). Defaults to exact_ordering_equality

Returns:

score: float

How similar these structures are at the n-saccharide level. Ranges between 0 and 1.0 where 1.0 is exactly the same, while 0.0 means no shared n-saccharides.

glypy.algorithms.subtree_search.subtree_of(subtree, tree, exact=False, tolerance=0)

Test to see if subtree is included in tree anywhere. Returns the node id number of the first occurence of subtree included in tree or None if it is not found.

Parameters:

subtree: Glycan

The structure to search for. The search attempts to match the complete structure of subtree.

tree: Glycan

The sturcture to search in. The search iterates over each residue in tree and calls a comparator function, comparing the subtree to the substructure rooted at that residue.

exact: bool

If True, use exact_ordering_inclusion() to compare nodes. Otherwise use topological_inclusion(). Defaults to False.

Returns:

int or None if no match

glypy.algorithms.subtree_search.topological_inclusion(self, other, substituents=True, tolerance=0, visited=None)

Performs equality testing between two monosaccharides where the exact ordering of child links does not have match between the input Monosaccharide, so long as an a is included in b

Equality testing is done by similarity.monosaccharide_similarity().

Parameters:

self: Glycan

The Glycan to test inclusion of

other: Glycan

The Glycan to test inclusion in

substituents: bool

Consider substituents when comparing Monosaccharide s. Defaults to True

tolerance: int

The amount of error allowed when checking for flat similarity.

Returns:

bool

See also

similarity.monosaccharide_similarity()