Fujitsu Technology to Solve Combinatorial Optimization Problems for Medium-Sized Drug Discovery

Fujitsu Laboratories Ltd. today announced that it has developed a large-scale problem segmentation technology, produced together with Fujitsu Advanced Technologies Limited, that utilizes the Digital Annealer, Fujitsu's computational architecture that can solve combinatorial optimization problems at breathtaking speed.

Previously, the Digital Annealer could only handle problems up to a size that could be input into standalone hardware. This new development now makes it possible to extract essential portions of a problem based on its characteristics, and after processing with the Digital Annealer, are repeatedly cycled through to return to an overall state. During this stage, the method to elicit the most optimized response is adopted, which makes it possible to apply to large-scale problems.

By applying this technology to the second generation Digital Annealer, which will be capable of handling 8 Kbits-scale (8,192 bits) problems, Fujitsu Laboratories anticipates that it will be possible to apply it to problems on a 100 Kbit scale. In this trial, Fujitsu Laboratories confirmed through simulations that it would be possible to solve the 30 Kbit stable molecular configuration search problems expected to be used in medium-sized drug discovery. This technology can cut simulation time to just a few days from the half a year taken by conventional computers. Fujitsu Laboratories will begin a joint research with ProteinQure Inc.⁽¹⁾ in order to accelerate the discovery of mid-size protein therapeutics.

Fujitsu Laboratories is contributing to the creation of new business by using the new technology and applying the Digital Annealer to combinatorial optimization problems in a variety of fields.

Development Background

Combinatorial optimization problems exist across a range of fields in everyday society, necessitating the combinations that will produce the most efficient and effective results. With combinatorial optimization problems, as the number of combinations increases explosively when all of the factors that need to be considered to find solutions are factored in, there is a limit to the scale of a problem that can be solved in a practical length of time with existing computing technology. In light of this, Fujitsu Laboratories developed the Digital Annealer, a dedicated architecture for combinatorial optimization problems. Services for 1 Kbit (1,024 bits) scale problems are already available, and research is ongoing to provide support of up to 8 Kbits, within fiscal 2018.

There is demand, however, to go further and provide support for massive problems of a scale greater that those that can be input into hardware so as to solve combinatorial optimization problems of evermore complexity. For example, with computations of around 30 Kbits, it becomes possible to quickly solve stable configuration search problems for molecules of up to 50 amino acids in the field of medium-sized drug discovery. This can accelerate the development of medium-sized drugs. Beyond that, this technology can also be applied to a variety of other fields, including factories and manufacturing as well as transportation.

Issues

Simply segmenting large-scale problems into portions that are small enough to be input into the hardware, then optimizing those individual portions would not optimize the problem as a whole. In other words, while it is possible to optimize individual portions by extracting parts of a problem, if the appropriate portion is not extracted, a sufficient level of effectiveness cannot be achieved.

About the Newly Developed Technology

Fujitsu Laboratories has now developed a technology to handle problems of a larger scale than can be input into standalone hardware. When this technology is applied to the second generation Digital Annealer, it is expected to be capable of handling problems up to 100 Kbits in size. The features of the newly developed technology are as follows.

1. Executes a solution search cycle in order to find the optimal solution

After conducting a quick overall search of the entire problem, this technology extracts a portion of the problem of a size that can be input into the hardware, and uses the Digital Annealer to search for an optimal solution for the extracted portion. That result is fed back into the problem as a whole, and the cycle is repeated multiple times, changing the extracted portion, and finding an even more optimal solution for the larger-scale problem.

2. Multiple segmentation methods based on the characteristics of the problem

To increase the efficiency of optimizing the problem as a whole, it is important to determine the portion to extract, depending on the characteristics of the question. Fujitsu Laboratories focused on the relationship of the problem, developing multiple segmentation methods, including a method that primarily extracts the portions of the problem as a whole that change the most easily, and a method that segments the portions that have the least amount of coupling between elements. By selecting the appropriate segmentation method for each problem, this technology can efficiently find solutions for large-scale problems.

Effects

Fujitsu Laboratories, together with ProteinQure Inc., a company developing a software platform for protein drug discovery, confirmed the possibility of using the Digital Annealer on simulations that find stable configurations of protein drug candidates.

In protein drug discovery, drug candidates, in which anywhere from a handful to about 50 amino acids are connected in a chain, have an effect as drugs by binding strongly with targeted proteins. The Digital Annealer is used to search for the most stable configurations when each amino acid is modeled and placed on a point in a 3D grid, using factors such as the binding relationship between amino acids. Then the strength of the binding between the configuration discovered with this method and the target protein is investigated using a docking computation. By repeating this cycle about 1,000 times, for example, this technology can find a highly effective medium-sized drug candidate.

By applying this technology to the second generation Digital Annealer, Fujitsu Laboratories was able to shorten the simulation time required for a computation involving a medium-sized drug candidate consisting of 48 amino acids (about 30 Kbits) from several hours using conventional computers to several minutes, using the same method of modeling amino acids. This means that by repeating this flow, a search for therapeutic molecules that would have taken half a year could be done in a few days. Applying this newly developed technology, the Digital Annealer is expected to accelerate the development of protein therapeutics, which are attracting attention as next-generation drugs.

Future Plans

By using the Digital Annealer and the application of this technology, in the future Fujitsu Laboratories expects to be able to handle massive combinatorial optimization problems of up to 100,000 bits, contributing to customers in a wide range of businesses, including drug discovery, chemistry, manufacturing, transportation, finance, and logistics.

Accordingly, Fujitsu Laboratories will begin a joint research with ProteinQure Inc. in order to accelerate the commercialization of this technology for protein drug discovery.