So much to do, so little time

Trying to squeeze sense out of chemical data

Applications Invited for CSA Trust Grant for 2016

without comments

The Chemical Structure Association (CSA) Trust is an internationally recognized organization established to promote the critical importance of chemical information to advances in chemical research. In support of its charter, the Trust has created a unique Grant Program and is now inviting the submission of grant applications for 2016.

Purpose of the Grants:

The Grant Program has been created to provide funding for the career development of young researchers who have demonstrated excellence in their education, research or development activities that are related to the systems and methods used to store, process and retrieve information about chemical structures, reactions and compounds. One or more Grants will be awarded annually up to a total combined maximum of ten thousand U.S. dollars ($10,000). Grantees have the option of payments being made in U.S. dollars or in British Pounds equivalent to the U.S. dollar amount. Grants are awarded for specific purposes, and within one year each grantee is required to submit a brief written report detailing how the grant funds were allocated. Grantees are also requested to recognize the support of the Trust in any paper or presentation that is given as a result of that support.

Who is Eligible?

Applicant(s), age 35 or younger, who have demonstrated excellence in their chemical information related research and who are developing careers that have the potential to have a positive impact on the utility of chemical information relevant to chemical structures, reactions and compounds, are invited to submit applications. While the primary focus of the Grant Program is the career development of young researchers, additional bursaries may be made available at the discretion of the Trust. All requests must follow the application procedures noted below and will be weighed against the same criteria.

Which Activities are Eligible?

Grants may be awarded to acquire the experience and education necessary to support research activities; e.g. for travel to collaborate with research groups, to attend a conference relevant to one’s area of research (including the presentation of an already-accepted research paper), to gain access to special computational facilities, or to acquire unique research techniques in support of one’s research.

Application Requirements:

Applications must include the following documentation:

  1. A letter that details the work upon which the Grant application is to be evaluated as well as details on research recently completed by the applicant;
  2. The amount of Grant funds being requested and the details regarding the purpose for which the Grant will be used (e.g. cost of equipment, travel expenses if the request is for financial support of meeting attendance, etc.). The relevance of the above-stated purpose to the Trust’s objectives and the clarity of this statement are essential in the evaluation of the application);
  3. A brief biographical sketch, including a statement of academic qualifications;
  4. Two reference letters in support of the application.  Additional materials may be supplied at the discretion of the applicant only if relevant to the application and if such materials provide information not already included in items 1-4.   A copy of the completed application document must be supplied for distribution to the Grants Committee and can be submitted via regular mail or e-mail to the Committee Chair (see contact information below).

Deadline for Applications:

Application deadline for the 2016 Grant is March 25, 2016. Successful applicants will be notified no later than May 2, 2016.

Address for Submission of Applications:

The application documentation should be forwarded via post or email to: Bonnie Lawlor, CSA Trust Grant Committee Chair, 276 Upper Gulph Road, Radnor, PA 19087, USA. If you wish to enter your application by e-mail, please contact Bonnie Lawlor at chescot@aol.com prior to submission so that she can contact you if the e-mail does not arrive.

Written by Rajarshi Guha

January 26th, 2016 at 7:36 pm

Posted in Uncategorized

Tagged with ,

Cryptography & Chemical Structure Search

without comments

Encryption of chemical information has not been a very common topic in cheminformatics. There was an ACS symposium in 2005 (summary) that had a number of presentations on the topic of “safe exchange” of chemical information – i.e., exchanging information on chemical structures without sharing the structures themselves. The common thread running through many presentations was to identify representations (a.k.a, descriptors) that can be used for useful computation (e.g., regression or classification models or similarity searches) but do not allow one to (easily) regenerate the structure. Examples include the use of PASS descriptors and various topological indices. Non-descriptor based approaches included, surrogate data (that is structures of related molecules with similar properties) and most recently, scaffold networks. Also, Masek et al, JCIM, 2008 described a procedure to assess the risk of revealing structure information given a set of descriptors.

As indicated by Tetko et al, descriptor based approaches are liable to dictionary based attacks. Theoretically if one fully enumerates all possible molecules and computes the descriptors it would be trivial to obtain the structure of an obfuscated molecule. While this is not currently practical, Masek et al have already shown that an evolutionary algorithm can reconstruct the exact (or closely related) structure from BCUT descriptors in a reasonable time frame and Wong & Burkowski, JCheminf, 2009 described a kernel approach to generating structures from a set of descriptors (though they were considering the inverse QSAR problem rather than chemical privacy). Uptil now I wasn’t aware of approaches that were truly one way – impossible to regenerate the structure from the descriptors, yet also perform useful computations.

Which brings me to an interesting paper by Shimuzu et al which describes a cryptographic approach to chemical structure search, based on homomorphic encryption. A homomorphic encryption scheme allows one to perform computations on the encrypted (usually based on PKI) input leading to an encrypted result, which when decrypted gives the same result as if one had performed the computation on the clear (i.e., unecnrypted) input. Now, a “computation” can involve a variety of operations – addition, multiplication etc. Till recently, most homomorphic schemes were restricted to one or a few operations (and so are termed partially homomorphic). It was only in 2009 that a practical proposal for a fully homomorphic (i.e., supporting arbitrary computations) cryptosystem was described. See this excellent blog post for more details on homomorphic cryptosystems.

The work by Shimuzu et al addresses the specific case of a user trying to identify molecules from a database that are similar to a query structure. They consider a simplified situation where the user is only interested in the count of molecules above a similarity threshold. Two constraints are:

  1. Ensure that the database does not know the actual query structure
  2. The user should not gain information about the database contents (except for number of similar molecules)

Their scheme is based on a additive homomorphic system (i.e., the only operation supported on the encrypted data is addition) and employs binary fingerprints and the Tversky similarity metric (which can be reduced to Tanimoto if required). I note that they used 166-bit MACCS keys. Since it’s small and each bit position is known it seems that some information could leak out of the encrypted fingerprint or be subject to a dictionary attack. I’d have expected that using a larger hashed fingerprint would have helped improve the security. (Though I suspect that the encryption of the query fingerprint alleviates this issue). Another interesting feature, designed to prevent information about the database leaking back to the user is the use of “dummies” – random, encrypted (by the users public key) integers that are mixed with the true (encrypted) query result. Their design allows the user to determine the sign of the query result (which indicates whether the database molecule is similar to the query, above the specified threshold), but does not let them get the actual similarity score. They show that as the number of dummies is increased, the chances of database information leaking out tends towards zero.

Of course, one could argue that the limited usage of proprietary chemical information (in terms of people who have it and people who can make use of it) means that the efforts put in to obfuscation, cryptography etc. could simply be replaced by legal contracts. Certainly, a simple way to address the scenario discussed here (and noted by the authors) is to download the remote database locally. of course this is not feasible if the remote database is meant to stay private (e.g., a competitors structure database).

But nonetheless, methods that rigorously guarantee privacy of chemical information are interesting from an algorithmic standpoint. Even though Shimuzu et al described a very simplistic situation (though the more realistic scenario where the similar database molecules are returned would obviously negate constraint 2 above), it looks like a step forward in terms of applying formal cryptanalysis to chemical problems and supporting truly safe exchange of chemical information.

Written by Rajarshi Guha

January 5th, 2016 at 3:17 am

Elemental Words

without comments

Last night, my colleague Matthew Hall tweeted

With the recent news of the 7th row of the periodic table being filled I figured this would be a good time to follow up on Matthews request and identify such elemental words.

There are a lot of word lists available online. Being an ex-Scrabble addict, the OSPD came to mind. So using the SOWPODS word list of 267,751 words I put together a quick Python program to identify words that can be constructed from 1- and 2-letter element symbols. (The newly confirmed elements – Uut, Uuo, Uup & Uus – don’t occur in any English words). Importantly, 2-letter elements should exist in a contiguous fashion. This means that a word like ABRI (a shelter) is not an elemental word since it contains Boron & Iodine, but the A and R are not contiguous and so wouldn’t correpsond to Argon. (It could also contain Bromine and Iodine but then the remaining A doesn’t match any element).

The code below takes 4.1s 2.0s to process SOWPODS and identifies 19,698 40,989 “elemental words”. Thanks to Noel O’Boyle for suggesting the use of a regex and directly extracting matches (so avoiding looping over individual words) and Rich Lewis for generating output in element-case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from __future__ import print_function
import sys, re

if len(sys.argv) != 2:
    print('Usage: code.py WORD_LIST_FILE_NAME')
    sys.exit(0)
   
wordlist = sys.argv[1]
words = open(wordlist, 'r').read()
print('Dictionary has %d words' % (len(re.findall('\n', words))))
with open('elements.txt', 'r') as eles:
    elems = {e.lower(): e for e in eles.read().split() if e != ''}
valid_w = re.findall('(^(?:'+'|'.join(elems.keys())+')+?$)', words, re.I|re.M)
print('Found %d elemental words' % (len(valid_w)))
pattern = re.compile('|'.join(elems.keys()))
elementify = lambda s: pattern.sub(lambda x: elems[x.group()], s)
with open('elemental-%s' % (wordlist), 'w') as o:
    for w in valid_w:
        o.write(elementify(w)+"\n")

Just for fun I also extracted all the titles from Wiktionary, irrespective of language. That gives me a list of 2,726,436 words to examine. After 35s 20s I got 148,211 370,724 “elemental words”.

You can find the code along with the element symbol list and input files in this repository

Update: Thanks to Noels’ suggestion of a regex, I realized my initial implementation had a bug and did not identify all elemental words in a dictionary. The updated code now does, and does it 50% faster

Update:Thanks to Rich Lewis for providing a patch to output matching words in element-case (e.g., AcOUSTiCAl)

Written by Rajarshi Guha

January 3rd, 2016 at 3:07 pm

Maximally Bridging Rings (or, Doing What the Authors Should’ve Done)

with one comment

Recently I came across a paper from Marth et al that described a method based on network analysis to support retrosynthetic planning, particularly for complex natural products. I’m no synthetic chemist so I can’t comment on the relevance or importance of the targets or the significance of the proposed approach to planning a synthetic route. What caught my eye was the claim that

This work validates the utility of network analysis as a starting point for identifying strategies for the syntheses of architecturally complex secondary metabolites.

I was a little disappointed (hey, a Nature publication sets certain expectations!) that the network analysis was fundamentally walking the molecular graph to identify a certain type of ring, termed the maximally bridging ring. The algorithm is described in the SI and the authors make it availableCopaene
as an online tool. Unfortunately they didn’t provide any source code for their algorithm, which was a bit irritating, given that the algorithm is a key component of the paper.

I put together an implementation using the CDK (1.5.12), available in a Github repo. It’s a quick hack, using the parameters specified in the paper, and hasn’t been extensively tested. However it seems to give the correct result for the first few test cases in the SI.

The tool will print out the hash code of the rings recognized as maximally bridging and also generate an SVG depiction with the first such ring highlighted in red, such as shown alongside. You can build a self-contained version of the tool as

1
2
3
git clone git@github.com:rajarshi/maxbridgerings.git
cd maxbridgerings
mvn clean package

The tool can then be run (with the depiction output to Copaene.svg)

1
2
java -jar target/MaximallyBridgingRings-1.0-jar-with-dependencies.jar \
  "CC(C)C1CCC2(C3C1C2CC=C3C)C" Copaene

Written by Rajarshi Guha

December 24th, 2015 at 4:10 am

Cleaning up a WAR in a SBT Build

without comments

Recently some of our software projects have beging using SBT to build them using Build.scala (rather than build.sbt). One of the challenges (apart from learning Scala to build a Java project!) was removing some unneeded JAR files from a WAR build. I use xsbt-web-plugin to provide support for WAR packaging. It turns out that the plugin provides a hook, webappPostProcess to manipulate the web application before generating the WAR. Using this and an example we can write some Scala to list files matching a regex and then delete the matching files

1
2
3
4
5
6
7
8
9
    webappPostProcess := {
      webappDir: File =>
        def recursiveListFiles(f: File, r: Regex): Array[File] = {
          val these = f.listFiles
          val good = these.filter(f => r.findFirstIn(f.getName).isDefined)
          good ++ these.filter(_.isDirectory).flatMap(recursiveListFiles(_,r))
        }
        recursiveListFiles(webappDir / "WEB-INF/lib/", """javax.*""".r).map( x => IO.delete(x))
    }

You could place this in your web app settings Seq to make it available to all WAR builds

Written by Rajarshi Guha

December 22nd, 2015 at 6:00 pm

Posted in software

Tagged with , , , ,