Treewidth of molecular graphs

In 2003, Yamaguchi et al. tested the treewidth of 9712 molecules, and found that 19.4% had treewidth one, 75.7% had treewidth two, 4.9% had treewidth three, and only one molecule had treewidth four.  They also tested the local tree-width; you can see those results in Table 2 of their paper here.  Their conclusion: “tree-width of compounds is not only a useful complexity measure, but it is also an appropriate factor to consider in characterizing chemical compounds.”

Unfortunately, it is not clear whether that conclusion is correct.  Rajarshi Guha recently combined an existing treewidth package with the Chemistry Development Kit (CDK), an open-source chemistry suite.  He tested 10,000 molecules at random, and compared treewidth to other molecular descriptors.  His findings were consistent with the findings from 2003: almost all molecules had treewidth 1, 2 or 3; a small fraction had treewidth 4.  However, treewidth appears “degenerate” from a chemistry point of view, as it does not correlate with molecular size or other features of interest.  His conclusion: “I don’t think treewidth is a useful descriptor for modeling purposes.”  Chemist Joerg Kurt Wegner has followed up on  a Friendfeed discussion, suggesting other ways treewidth might be used.  For now, though, it appears to be a tool in search of a job.

Much more explanation, graphs and links can be found in Rajarshi’s blog entry on this subject; the background to his blog entry is in FriendFeed conversations here and here.

Atsuko Yamaguchi, Kiyoko F. Aoki, & Hiroshi Mamitsuka (2003). Graph Complexity of Chemical Compounds
in Biological Pathways Genome Informatics, 14, 376-377


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s