Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re^8: Optimization Help

by jmmitc06 (Beadle)
on Aug 02, 2013 at 06:42 UTC ( #1047554=note: print w/replies, xml ) Need Help??

in reply to Re^7: Optimization Help
in thread Optimization Help

Sorry those are separate vectors, each line is a separate I didn't make that very clear...

<-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1> is the first mapping vector, <0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1> is the second and so on.

#IDENTICAL / SIMILAR vectors: -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,- +1 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,-1,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,-1,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,-1,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,-1,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,-1,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,-1,-1 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,-1 #DISSIMILAR VECTORS -1,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,-1,-1,-1,-1,-1,-1,-1,-1,-1 0,-1,-1,-1,-1,-1,-1,-1,-1,-1 1,-1,-1,-1,-1,-1,-1,-1,-1,-1 1,-1,-1,-1,-1,-1,-1,-1,-1,-1 3,-1,-1,-1,-1,-1,-1,-1,-1,-1 3,-1,-1,-1,-1,-1,-1,-1,-1,-1 4,-1,-1,-1,-1,-1,-1,-1,-1,-1 4,-1,-1,-1,-1,-1,-1,-1,-1,-1 6,-1,-1,-1,-1,-1,-1,-1,-1,-1 6,-1,-1,-1,-1,-1,-1,-1,-1,-1 8,-1,-1,-1,-1,-1,-1,-1,-1,-1 8,-1,-1,-1,-1,-1,-1,-1,-1,-1

Yeah, we've struggled with that, the similar case, for a while here in the lab, the way we are doing it now is vastly better than the original algorithm by Ullmann we were using.

Replies are listed 'Best First'.
Re^9: Optimization Help
by BrowserUk (Pope) on Aug 02, 2013 at 16:38 UTC
    the way we are doing it now is vastly better than the original algorithm by Ullmann we were using.

    So, you are searching for subgraph isomorphisms?

    If so, is it possible for you to describe what the graphs are and what you are looking for when comparing them, in terms of the underlying data rather than graph theory?

    I ask because I've never yet encountered a real use for a graph theory algorithm that wasn't more efficiently coded by ignoring graph theory.

    As with all theoretical algorithms; GT algorithms have to deal with, and work for, all possible graphs of the given type regardless of what data and data relationships they actually represent.

    In every real-world case I remember, knowledge of the actual data and required results allowed me to make assumptions and take short cuts that the theorists cannot.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Yes, I am searching for subgraph isomorphisms.

      Sure I will try to explain it. Each graph represents the bonded structure of either a compound from a metabolic database such as the HMDB or it represents the bonded structure of a functional group or other small chemical moeity. I am trying to find all instances of that chemical moeity within the compound of interest and I can do that by searching for all subgraphs which are identical or can be mapped to the chemical moeity.

      Yes, in reference to the GT algorithms ignoring the type of data, I have added some heuristics to the part of the algorithm that creates the "mapping matrix", the actual matrix which is enumerated to remedy this. This matrix has rows equal to the number of atoms in the moeity and columns equal to the number of atoms in the query compound. Potential mappings between atom i in the moeity and j in the compound are designated by setting element i,j equal to one. By setting very strict rules based on chemical properties: don't match a C to a N, don't match atoms of differing total bond order etc, I can reduce the number of ones in the mapping matrix, speeding up the enumeration process greatly.

      A major reason why I adopted the graph theory approach is flexibility. While not as fast as a hard coded method, it allows me to add new moeities I can search for without modifying my code. Additionally, by searching for a database compound within another database compound with the same formula, I can test for stereoisomerism by ignoring stereochemistry on individual atoms and seeing if the graphs are isomorphic. This is a key step in my research and the GT approach allows me to do that as well as search for moeities.

      Hope this answered your questions. Thanks for the help.

Re^9: Optimization Help
by jmmitc06 (Beadle) on Aug 02, 2013 at 06:48 UTC
    Also, I should state that these are not all of the mapping vectors generated during the enumeration process, just some of them at different time points. The latter vectors were generated after the earlier ones in the list. However, the ones I did not print off are essentially the same. Can't print all of them, too many.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1047554]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2018-05-24 10:54 GMT
Find Nodes?
    Voting Booth?