Tyler O'Neal, Staff Editor BIG DATA

Goto's new algorithms quickly deliver highly accurate solutions to complex problems

Breaks the limitations of classical mechanics by introducing a quasi-quantum effect; expected to accelerate complex problem-solving in finance, pharmaceuticals, and logistics

Toshiba Corporation (TOKYO: 6502) and Toshiba Digital Solutions Corporation (collectively Toshiba), industry leaders in solutions for large-scale optimization problems, today announced the Ballistic Simulated Bifurcation Algorithm (bSB) and the Discrete Simulated Bifurcation Algorithm (dSB), new algorithms that far surpass the performance of Toshiba's previous Simulated Bifurcation Algorithm (SB). The new algorithms will be applied to finding solutions to highly complex problems in areas as diverse as portfolio management, drug development and logistics management.

Introduced in April 2019, the previous SB broke new ground as a platform for finding solutions to combinatorial optimization problems, surpassing other approaches by a factor of 10*1. Toshiba has now extended this achievement with two new algorithms that apply innovative approaches, such as a quasi-quantum tunneling effect, to performance improvement, allowing them to acquire optimal solutions (exact solutions) for large-scale combinatorial optimization problems that challenge the capabilities of their predecessor. Implemented on a 16-GPU machine, dSB can find a nearly optimal solution of a one-million-bit problem, the world's largest scale combinatorial problem yet reported in scientific papers, in 30 minutes--a computation that would take 14 months on a typical CPU-based computer. The research results were published in the online academic journal, Science Advances.

The new algorithms have different characteristics. bSB is optimized and named for speed of operation and finds good approximate solutions in a short time. It generates fewer errors than a previously reported Adiabatic Simulated Bifurcation Algorithm (aSB)*3, and so returns faster, more accurate results. Implemented on a field-programmable gate array (FPGA), dubbed the ballistic simulated bifurcation machine (bSBM), it obtains a good solution to a 2,000-bit problem approximately 10 times faster than the previous aSB machine (aSBM) (Figure 1). The bSBM is approximately10x faster than the aSBM in solving a 2000-bit problem*2.{module INSIDE STORY}

dSB is a high-accuracy algorithm. Although implemented in a classical computer, it nonetheless arrives at optimal solutions faster than current quantum machines. Its name is derived from the replacement of continuous variables with discrete variables in equations of motion. This exhibits a quasi-quantum tunneling effect that breaks through the limits of approaches grounded in classical mechanics, reaching the optimal solution of the 2000-bit problem.

Toshiba has implemented dSB on a FPGA and built a discrete simulated bifurcation machine (dSBM) that achieves a higher speed than other machines in terms of computation times required to obtain optimal solutions for various problems (Figure 2). dSBM benchmarked against other machines for computation times to obtain optimal solutions for various problems*2.{module INSIDE STORY}

Implemented on a 16-GPU machine, the dSBM solved a one-million-bit problem, the largest yet reported in scientific papers, and arrived at a nearly optimal solution in 30 minutes--20,000 times faster than a CPU-based simulated annealing machine, which would take 14 months to carry out the computation (Figure 3). Computation times for a one-million-bit problem*2.

In applying the two algorithms to real-world problems, Toshiba proposes bSB for applications that require an immediate response, and dSB for applications that require high accuracy, even if it takes a little longer time.

Toshiba expects the new algorithms to bring higher efficiencies to industry, business and complex decision-making by addressing combinatorial optimization problems in fields including investment portfolios, drug development, and delivery route planning.

Commenting on the algorithms, Hayato Goto, Chief Research Scientist at Toshiba Corporation's Corporate Research & Development Center, said: "We face many real-world problems where we must find the optimal solution among a huge number of choices, and we must also deal with combinatorial explosion, where the number of combination patterns increases exponentially as a problem increases in scale. This is why research into special-purpose computers for combinatorial optimization is being carried out worldwide. Our aim is to develop a software solution--algorithms that can solve large-scale combinatorial optimization problems quickly and accurately, and contribute to the realization of higher efficiencies."

Toshiba will offer the newly developed simulated bifurcation algorithms as a GPU-based cloud service and as an on-premises version implemented on an FPGA within 2021.

BU medicine builds a better lung model

Tyler O'Neal, Staff Editor BIG DATA

May lead to new personalized treatments for lung diseases

In Boston, using a combination of pluripotent stem cells (cells that can potentially produce any cell or tissue type) and machine learning (artificial intelligence that allows supercomputers to learn automatically), researchers have improved how they generate lung cells.

Using this technique, cells can be grown in a laboratory and stored for more than one year without losing their lung identity and used to model lung diseases thereby finding better treatments and cures for lung diseases in the future.

Induced pluripotent stem (iPS) cells are derived from the donated skin or blood cells of adults and, with the reactivation of four genes, are reprogrammed back to an embryonic stem cell-like state. iPS cells can be differentiated toward any cell type in the body and do not require the use of embryos.

{module INSIDE STORY} Building on previous work from the Center for Regenerative Medicine (CReM) of Boston University and Boston Medical Center, researchers in the CReM, working together with investigators from Carnegie Mellon University (CMU), reprogrammed blood from adults into iPS cells. They then treated these stem cells with growth factors over a period of one month until they became cells that were very similar to adult lung cells.

According to the researchers, often when this type of experiment is performed the resulting cells are not a pure collection of the cell that they aimed to create (target cell) and they do not keep the characteristics of the target cell for prolonged periods of time.

"Therefore, we developed a combination of techniques that examines the gene expression of thousands of single cells combined with DNA barcoding of each individual cell and machine learning to build up a dynamic picture of what factors favor cells that go on to be lung cells in our system. Using this knowledge we were able to improve our methods for generating lung cells so that we can now create more relevant cells that keep their cell identity in a dish for more than one year," explained Killian Hurley, MD, PhD, researcher at the Royal College of Surgeons in Ireland, who co-authored the study with Jun Ding, PhD, a post-doctoral fellow at CMU.

The researchers believe this study will improve their ability to model lung disease and treatments in the laboratory for diseases including idiopathic pulmonary fibrosis, chronic obstructive pulmonary disease (COPD), alpha-1 antitrypsin deficiency and neonatal respiratory distress or early-onset interstitial lung disease.

Millions of people in the United States and around the world have severe lung diseases, often without good treatments or cure. Some of these diseases may even require lung transplantation which is a complex and high-risk surgery with the need for donor organs always exceeding the supply.

"The machine learning methods we developed for this study can also be applied to studies of other tissues and organs," said Ding. "We hope that our newly developed techniques for generating a pure, unlimited supply of cells using patients-derived stem cells can make possible new treatments or cures for diseases. These developments would prolong lives and improve the quality of those lives."

"The key hurdle to understanding what goes wrong with an individual patient's lung cells has been our inability to access those cells or to grow them in the laboratory. This approach allows us to now engineer from any individual patient those very finicky cells and to introduce bar codes into those cells that allow us to track and understand each cell and all their progeny over time in the laboratory dish. The result is an inexhaustible source of new lung cells that can be prepared from any patient of any age," added co-corresponding author Darrell Kotton, MD, David C. Seldin Professor of Medicine and Director, CReM, who led the work together with Ziv Bar-Joseph, PhD, the FORE Systems Professor of Computer Science at CMU.

Russian biophysicists find 'extra' component in molecular motor

Tyler O'Neal, Staff Editor BIG DATA

Researchers from the Moscow Institute of Physics and Technology have discovered an additional component in ATP synthase, a molecular machine that produces the energy-conserving compound in all cellular organisms. 

In order to store energy, living cells rely on a molecule called ATP. It is produced by ATP synthase, a molecular-scale motor comprised of a rotor and a stator. Such machines are nested in the inner membranes of mitochondria and chloroplasts in most organisms, including animals, plants, and bacteria. The rotor component resembles a barrel embedded into a biological membrane. This "barrel," or C-ring, is made of between eight and 17 so-called protomers. Their exact number depends on the organism.

MIPT researchers and their colleagues from Grenoble, France, have obtained a first-ever high-resolution structure of the C ring from spinach chloroplasts. As the supercomputer model of the C ring was taking shape, the biophysicists spotted something peculiar. The new unique features of the ATP synthase structure are described in detail in a paper in an educational journal. Overall view of the additional elements inside the C ring: side view (A), C ring cross section (B), from above (C), additional element details (D). The protein subunits C are shown as colored spirals.{module INSIDE STORY}

"We noticed additional circle-shaped elements inside the C ring," said MIPT doctoral student Alexey Vlasov from the Institute's Research Center for Molecular Mechanisms of Aging and Age-Related Diseases. "At first we thought that was an artifact. But when we looked through the C ring structures obtained by other scientists for various organisms, the circles turned up again, time after time."

It came as a surprise for the researchers that previous studies did not pay attention to the circles inside C rings. Up until now, their nature remained unexplained.

"This study speaks to the fact that no minor detail is negligible in science. Even a subtle feature, spotted in due course, might lead to a breakthrough discovery," noted Valentin Gordeliy, who heads research groups at the Institute of Structural Biology in Grenoble (France) and Jülich Research Center (Germany) and is the scientific coordinator of the MIPT Research Center for Molecular Mechanisms of Aging and Age-Related Diseases.

The biophysicists from MIPT set out to solve the C ring puzzle. Supercomputer modeling and biochemical experiments indicated that the ring contained quinone molecules. They act as electron carriers in biological systems. Some of the examples are plastoquinone, found in chloroplasts, and the coenzyme Q in mitochondria.

Biologists have long known that the C ring of ATP synthase does not have a "hole" in it. So while some molecules were expected to exist on the inside, no one was sure which exactly. The finding proved unexpected: quinones.

While the discovery is interesting in and of itself, researchers have yet to determine why the C ring hosts quinones and how they get there. One theory suggests C rings can function as pores in mitochondrial membranes. Such a pore might open when the cell death process is initiated. Can the quinones in a C ring kill a cell? This is a question for the MIPT biologists to address in their further research.