Semen Trygubenko, Ph.D.
Research Director and Functional Programmer based in Oxford, UK
> Graph Transformation Method
This website hosts information about a few academic and technical community projects I work(ed) on.
Graph Transformation is an exact approach for calculating transition probabilities and waiting times in finite-state discrete-time Markov processes. It outperforms kinetic Monte Carlo, master equation and matrix multiplication methods for extraction of kinetic information from networks of rearrangement pathways.
This work was described in detail in: S. A. Trygubenko and D. J. Wales, 'Graph Transformation Method for Calculating Waiting Times in Markov Chains', J. Chem. Phys., 124, 234110 (2006) [JCP Online] [arXiv]
Fortran 95 implementations of the sparse- and dense-optimised graph transformation algorithms discussed in this article are distributed free of charge under the GPL. Source code for gt program is available for download.
The main problems with finding transition states and pathways using the nudged elastic band (NEB) method are associated with accuracy and efficiency. We have developed a framework for finding transition states that is based on the variable tradeoff between the two, and showed that in most cases the new approach is more than an order of magnitude faster. A short summary of the doubly nudged elastic band approach (DNEB) follows:
We use DNEB method with a revised connection algorithm that is an efficient way of constructing connections between distant minima using multiple DNEB transition state searches. It automatically optimizes transition state candidates from each DNEB run, constructs steepest-descent pathways and analyses the database of minima and transition states to choose which connections need to be established to produce a connected rearrangement pathway. The main features of our revised connection algorithm are as follows:
This work was described in detail in:
S. A. Trygubenko and D. J. Wales, 'A Doubly Nudged Elastic Band Method for Finding Transition States' [JCP Online] [arXiv]
J. M. Carr, S. A. Trygubenko and D. J. Wales, 'Finding pathways between distant local minima' [JCP Online] [arXiv]
As of 2020, benchmarks of DNEB, its predecessors and successors are available in a more structured form, thanks to the efforts of the group of Graeme Henkelman, creator of NEB.
While doing PhD under the supervision of Professor David J. Wales I contributed to the development of OPTIM.
OPTIM is a Fortran program that provides a wide variety of geometry optimisation tools for locating stationary points on potential energy surfaces and calculating reaction pathways.
The optimisation algorithms include eigenvector-following, steepest-descent (Page-McIver second order; Bulirsch-Stoer, Runga-Kutta, or Barzilai-Borwein-Raydan for first order), conjugate gradient and hybrids thereof. Pathways can be calculated in several ways, and it is also possible to use a 'fictitious kinetic' metric, usually referred to as 'mass-weighted' coordinates. There is provision to treat rigid body systems; the TIP family of rigid molecule, effective pair potentials for H2O are known to the program and employ centre-of-mass and Euler angle coordinates.
The OPTIM program has analytic first and second energy derivatives coded for dozens of empirical potentials and can also read derivatives from disc so that it can be run iteratively in tandem with ab initio or other packages.
You can read about OPTIM and download it and related programs from Wales Group website.
I worked on translation of Learn You a Haskell for Great Good! into Ukrainian during lunchtimes for a few years. A surprising number of lunchtimes went into it; as my music teacher used to say, "it is not the water that carves the stone but the frequency of falling" (paraphrasing Ovid, perhaps), and so some progress has been made by now.
Many find Haskell a difficult language to learn, but the barriers to understanding are sometimes artificial. Othertimes they are heightened by factors such as lack of study materials available in the native language of the learner. I have found that exactly, and few attempts to rectify the situation citing a variety of other difficulties that have little to do with the domain of functional programming.
While translating the book we have found that many concepts do not have words to describe them in Ukrainian efficiently, and so, verbal prowess and command of computer science were necessary but insufficient prerequisites to doing a good job of it. Many people helped out with the translation, latest version is available on https://haskell.trygub.com, and is licensed under a creative commons license.
I did a PhD under the supervision of Professor David Wales. The work that was carried out is summarised in the PhD thesis "Pathways and Energy Landscapes". It's a trilogy in three parts, and a summary of each of the main chapters follows:
The main focus of the first one is on double-ended methods for finding transition states. A detailed review of one of the leading methods from that class is followed by the discussion of our modifications and improvements that allowed us to extend its applicability. Results for a model two-dimensional surface and Lennard-Jones clusters of several sizes are presented. The chapter culminates with an application to finding folding paths for a family of small peptides known as tryptophan zippers.
The second part is devoted to discussion of two exciting properties of rearrangement pathways — cooperativity and localisation. A new measure of cooperativity suitable for applications to atomic rearrangements is introduced and subsequently used to establish the links between cooperativity of a single-step rearrangement, the energy barrier height and the difficulty of locating the corresponding transition state with both single-ended and double-ended methods.
In the third chapter we deal with compact representations of large pathway ensembles borrowing ideas from graph theory and the theory of random processes. The main theme is the development of faster methods for calculation of mean escape times for graphs of increasing complexity. We devise a number of approaches for extracting this kinetic information and compare them to well-established techniques such as kinetic Monte Carlo and discrete path sampling.
Slovnenya is a dictionary authoring system that aims to amplify the power of lexicographers, allowing to produce a higher quality dictionary with fewer editors and resources, which benefits minority language communities.
The dictionary is written in Haskell and uses elements of machine learning, some moderate computational linguistics wizardry and functional programming type-foo to help itself grow over time.
Presently the system has high error rate most of which was directly inherited from the sources Slovnenya reasoning engine was seeded with. These are (slowly) being weeded out with use, and adverts are paying for infrastructure and hosting.
While studying cooperativity and localization properties of rearrangement pathways we sampled and analysed a large number of them for LJ75—a 75-atom cluster bound by Lennard-Jones intermolecular pair potential.
The potential energy surface for LJ75 is rich in stationary points, and using cooperativity measure as a guide we saw why some pathways are easy to find with aggressive, approximate optimisers while others are excruciatingly hard.
Here we present two rearrangements of LJ75—the most cooperative and the most uncooperative ones we have found at the time of study. They illustrate the issues one will face when coming up with sampling and optimisation techniques that are both unbiased in terms of construction of initial guesses and robust so that they can work well with numerical optimisers.
Cooperativity and localization are properties of the rearrangement pathways.
Rearrangement is called 'localized' if a small fraction of the atoms participates in it, and 'delocalized' in the opposite limit. Rearrangement is called 'cooperative' if most of the atoms that participate move simultaneously, and 'uncooperative' if atoms move sequentially.
Any pathway can be broken down into elementary (or single-step) rearrangement paths that feature no intermediate minima. Among single-step rearrangements, delocalized uncooperative ones are the most difficult to find. It turns out that cooperativity and barrier height are related: cooperative rearrangements have the smallest barriers.