Tokyo Tech demos multi-policy-based annealer for solving real-world combinatorial optimization problems

A fully-connected annealer extendable to a multi-chip system and featuring a multi-policy mechanism has been designed by Tokyo Tech researchers to solve a broad class of combinatorial optimization (CO) problems relevant to real-world scenarios quickly and efficiently. Named Amorphica, the annealer has the ability to fine-tune parameters according to a specific target CO problem and has potential applications in logistics, finance, machine learning, and so on.

The modern world has grown accustomed to the efficient delivery of goods right at our doorsteps. But did you know that realizing such efficiency requires solving a mathematical problem, namely what is the best possible route between all the destinations? Known as the “traveling salesman problem,” this belongs to a class of mathematical problems known as “combinatorial optimization” (CO) problems.

As the number of destinations increases, the number of possible routes grows exponentially, and a brute force method based on an exhaustive search for the best route becomes impractical. Instead, an approach called “annealing computation” is adopted to find the best route quickly without an exhaustive search. Yet, a numerical study done by Tokyo Tech researchers has shown that while there exist many annealing computation methods, there is no one method suitable for solving a broad class of CO problems. Therefore, there is a need for an annealing mechanism that features multiple annealing methods (a multi-policy mechanism) to target a variety of such problems.

Fortunately, the same team of researchers, led by Assistant Professor Kazushi Kawamura and Professor Masato Motomura from the Tokyo Institute of Technology (Tokyo Tech), have reported a new annealer that features such a multi-policy approach or “metamorphic annealing.” Their findings are published in the Proceeding of ISSCC2023 and will be presented in the upcoming 2023 International Solid-State Circuits Conference.

“In the annealing computation, a CO problem is represented as an energy function in terms of (pseudo) spin vectors. We start from an initially randomized spin vector configuration and then update it stochastically to find the minimum energy states by reducing its (pseudo) temperature. This closely mirrors the annealing process of metals where hot metals are cooled down in a controlled manner,” explains Dr. Kawamura. “Our annealer named Amorphica features multiple annealing methods, including a new one proposed by our team. This provides it the ability to adopt the annealing method to the specific CO problem at hand.”

The team designed Amorphica to address the limitations of previous annealers, namely that their applicability is limited to only a few CO problems. This is first because these annealers are local-connection ones, meaning they can only deal with spin models having local inter-spin coupling. Another reason is that they do not have flexibility in terms of annealing methods and parameter control. These issues were solved in Amorphica by employing a full-connection spin model and incorporating finely controllable annealing methods and parameters. In addition, the team introduced a new annealing policy called “ratio-controlled parallel annealing” to improve the convergence speed and stability of existing annealing methods.

Additionally, Amorphica can be extended to a multi-chip, full-connection system with reduced inter-chip data transfer. On testing Amorphica against a GPU, the researchers found that it was up to 58 times faster while using only (1/500) power consumption, meaning it achieves around 30k times more energy efficiency.

“With a full-connection annealer like Amorphica, we can now deal with arbitrary topologies and densities of inter-spin couplings, even when they are irregular. This, in turn, would allow us to solve real-world CO problems such as those related to logistics, finance, and machine learning,” concludes Prof. Motomura.

Sea level rise contributions from the Antarctic and Greenland ice sheets, and maps of projected 2150 CE Antarctic ice sheet surface elevation following different greenhouse gas emission scenarios (SSP1-1.9, strong emission cuts; SSP2-4.5, medium emission cuts; SSP5-8.5, weak emission cuts). / Figure credit by Jun-Young Park
Sea level rise contributions from the Antarctic and Greenland ice sheets, and maps of projected 2150 CE Antarctic ice sheet surface elevation following different greenhouse gas emission scenarios (SSP1-1.9, strong emission cuts; SSP2-4.5, medium emission cuts; SSP5-8.5, weak emission cuts). / Figure credit by Jun-Young Park

Prof Lee's supercomputing reveals an acceleration of global sea level rise imminent past 1.8℃ planetary warming

A study by an international team of scientists shows that an irreversible loss of the West Antarctic and Greenland ice sheets, and a corresponding rapid acceleration of sea level rise, may be imminent if global temperature change cannot be stabilized below 1.8°C, relative to the preindustrial levels.

Coastal populations worldwide are already bracing for rising seas. However, planning for counter-measures to prevent inundation and other damages has been extremely difficult since the latest climate model projections presented in the 6th assessment report of the Intergovernmental Panel on Climate Change (IPCC) do not agree on how quickly the major ice sheets will respond to global warming.

Melting ice sheets are potentially the most significant contributor to sea level change, and historically the hardest to predict because the physics governing their behavior is notoriously complex. “Moreover, computer models that simulate the dynamics of the ice sheets in Greenland and Antarctica often do not account for the fact that ice sheet melting will affect ocean processes, which, in turn, can feed back onto the ice sheet and the atmosphere,” says Jun Young Park, a Ph.D. student at the IBS Center for Climate Physics and Pusan National University, Busan, South Korea and first author of the study.

Using a new supercomputer model, which captures the coupling between ice sheets, icebergs, ocean, and atmosphere for the first time, climate researchers found that an ice sheet/sea level run-away effect can be prevented only if the world reaches net zero carbon emissions before 2060.

“If we miss this emission goal, the ice sheets will disintegrate and melt at an accelerated pace, according to our calculations. If we don’t take any action, retreating ice sheets will continue to increase sea level by at least 100 cm within the next 130 years. This would be on top of other contributions, such as the thermal expansion of ocean water” says Prof. Axel Timmermann, co-author of the study and Director of the IBS Center for Climate Physics.

Ice sheets respond to atmospheric and oceanic warming in delayed and often unpredictable ways. Previously, scientists have highlighted the importance of subsurface ocean melting as a critical process, which can trigger runaway effects in the major marine-based ice sheets in Antarctica. “However, according to our supercomputer simulations, the effectiveness of these processes may have been overestimated in recent studies,” says Prof. June Yi Lee from the IBS Center for Climate Physics and Pusan National University and co-author of the study. “We see that sea ice and atmospheric circulation changes around Antarctica also play a crucial role in controlling the amount of ice sheet melting with repercussions for global sea level projections,” she adds.

The study highlights the need to develop more complex earth system models, which capture the different climate components and their interactions. Furthermore, new observational programs are needed to constrain the representation of physical processes in earth system models, particularly from highly active regions, such as Pine Island glaciers in Antarctica.

“One of the key challenges in simulating ice sheets is that even small-scale processes can play a crucial role in the large-scale response of an ice sheet and for the corresponding sea-level projections. Not only do we have to include the coupling of all components, as we did in our current study, but we also need to simulate the dynamics at the highest possible spatial resolution using some of the fastest supercomputers,” summarizes Axel Timmermann.

 

AI model sheds light on cognition, brain disorders

Researchers from the National Institutes of Health (NIH) used computational modeling to uncover mutations in the human genome that likely influenced the evolution of human cognition. This groundbreaking research in human genomics could lead to a better understanding of human health and the discovery of novel treatments for complex brain disorders. The study was published in Science Advances.

Human cognition is a defining feature of human evolution, setting us apart from other primates. Despite over 100 million mutations since the human-chimp split, only a small fraction is significant. To navigate this vast landscape of genomic changes, researchers from the National Library of Medicine (NLM) and the National Cancer Institute (NCI) created an artificial intelligence (AI) model of gene regulation in the human brain. The model identified thousands of mutations likely impacting neocortical development and facilitating the acquisition of mathematical abilities through altered brain gene regulation mechanisms.

When the human genome was sequenced in 2001, researchers learned that only 2% of the sequence of our genome is used for coding genes that, in turn, translate into proteins. This is the sequence information that is being used by every single cell. The function of the other 98% of our DNA—often referred to as “noncoding DNA"— remains relatively unknown. It is believed that 95% of disease associations hide within these noncoding parts of our genome.

The research group of Ivan Ovcharenko, Ph.D., senior investigator in the Computational Biology Branch of NLM’s Intramural Research Program teamed up with the research group of Sridhar Hannenhalli, Ph.D., senior investigator in NCI’s Center for Cancer Research to create an AI model that measures the effect of noncoding genome mutations on human brain function and development. This led to the identification of a group of noncoding mutations disrupting brain regulatory pathways and potentially causing various complex brain disorders, including autism.

“There are treasure islands within the sea of noncoding DNA in the human genome that are critically important for regulating human genes,” said Dr. Ovcharenko. “Mutations in these regions are largely benign, but there is a class of mutations which detrimentally impact the function of regulatory regions in the brain and affect cellular activity there. By being able to address the impact of individual mutations, we are advancing towards understanding the mechanism of complex diseases and disorders and paving the way for the development of novel therapeutic approaches.”

According to the study authors, this fundamental work in human genomics is likely to have a long-ranging impact on human health and advance the research on the complex nature of the human brain.

A perovskite crystalline stone isolated on white background. Perovskites, like the one shown here, show great potential as light-absorbing material for solar harvesting. (Getty Images photo)
A perovskite crystalline stone isolated on white background. Perovskites, like the one shown here, show great potential as light-absorbing material for solar harvesting. (Getty Images photo)

Optics professor Guo demos how to harness the power of metals to enhance the efficiency of perovskites

Silicon, the standard semiconducting material used in a host of applications—computer central processing units (CPUs), semiconductor chips, detectors, and solar cells—is an abundant, naturally occurring material. However, it is expensive to mine and purify.

Perovskites—a family of materials nicknamed for their crystalline structure—have shown extraordinary promise in recent years as a far less expensive, equally efficient replacement for silicon in solar cells and detectors. Now, a study led by Chunlei Guo, a professor of optics at the University of Rochester, suggests perovskites may become far more efficient. This illustration from the Guo Lab shows the interaction between a perovskite material (cyan) and a substrate of metal-dielectric material. The red and blue pairings are electron-hole pairs. Mirror images reflected from the substrate reduce the ability of excited electrons in the perovskite to recombine with their atomic cores, increasing the efficiency of the perovskite to harvest solar light. (Illustration by Chloe Zhang)

Researchers typically synthesize perovskites in a wet lab, and then apply the material as a film on a glass substrate and explore various applications

Guo instead proposes a novel, physics-based approach. By using a substrate of either a layer of metal or alternating layers of metal and dielectric material—rather than glass—he and his coauthors found they could increase the perovskite’s light conversion efficiency by 250 percent.

“No one else has come to this observation in perovskites,” Guo says. “All of a sudden, we can put a metal platform under a perovskite, utterly changing the interaction of the electrons within the perovskite. Thus, we use a physical method to engineer that interaction.”

The novel perovskite-metal combination creates a lot of surprising physics

Metals are probably the simplest materials in nature, but they can be made to acquire complex functions. The Guo Lab has extensive experience in this direction. The lab has pioneered a range of technologies transforming simple metals to pitch black, super hydrophilic (water-attracting), or superhydrophobic (water-repellent). The enhanced metals have been used for solar energy absorption and water purification in their recent studies.

In this new paper, instead of presenting a way to enhance the metal itself, the Guo Lab demonstrates how to use the metal to enhance the efficiency of perovskites.

“A piece of metal can do just as much work as complex chemical engineering in a wet lab,” says Guo, adding that the new research may be particularly useful for future solar energy harvesting.”

In a solar cell, photons from sunlight need to interact with and excite electrons, causing the electrons to leave their atomic cores and generate an electrical current, Guo explains. Ideally, the solar cell would use materials that are weak to pull the excited electrons back to the atomic cores and stop the electrical current.

Guo’s lab demonstrated that such recombination could be substantially prevented by combining a perovskite material with either a layer of metal or a metamaterial substrate consisting of alternating layers of silver, a noble metal, and aluminum oxide, a dielectric.

The result was a significant reduction of electron recombination through “a lot of surprising physics,” Guo says. In effect, the metal layer serves as a mirror, which creates reversed images of electron-hole pairs, weakening the ability of the electrons to recombine with the holes.

The lab was able to use a simple detector to observe the resulting 250 percent increase in the efficiency of light conversion.

Several challenges must be resolved before perovskites become practical for applications, especially their tendency to degrade relatively quickly. Currently, researchers are racing to find new, more stable perovskite materials.

“As new perovskites emerge, we can then use our physics-based method to further enhance their performance,” Guo says.

Coauthors include Kwang Jin Lee, Ran Wei, Jihua Zhang, and Mohamed Elkabbash, all current and former members of the Guo Lab, and Ye Wang, Wenchi Kong, Sandeep Kumar Chamoli, Tao Huang, and Weili Yu, all of the Changchun Institute of Optics, Fine Mechanics, and Physics in China.

The Bill and Melinda Gates Foundation, the Army Research Office, and the National Science Foundation supported this research.

 

National Institutes of Health researchers have developed and released an innovative software tool to assemble truly complete (i.e., gapless) genome sequences from a variety of species.Ernesto del Aguila, NHGRI
National Institutes of Health researchers have developed and released an innovative software tool to assemble truly complete (i.e., gapless) genome sequences from a variety of species.Ernesto del Aguila, NHGRI

Verkko software assembles complete genome sequences more affordable

National Institutes of Health researchers have developed and released an innovative software tool to assemble truly complete (i.e., gapless) genome sequences from a variety of species. This software, called Verkko, which means “network” in Finnish, makes the process of assembling complete genome sequences more affordable and accessible.

Verkko grew from assembling the first gapless human genome sequence, which was finished last year by the Telomere-to-Telomere (T2T) consortium, a collaborative project funded by the National Human Genome Research Institute (NHGRI), part of NIH.

“We took everything we learned in the T2T project and automated the process,” said NHGRI associate investigator Sergey Koren, Ph.D., who led the creation of Verkko and is the senior author of the paper. “Now with Verkko, we can essentially push a button and automatically get a complete genome sequence.”

The T2T consortium used new DNA sequencing technologies and analytical methods to generate and assemble the remaining 8-10% of the human genome sequence. However, the researchers assembled those fragments manually — a process that took this massive and highly skilled team several years to complete. Verkko can finish the same task in a couple of days.

Assembling a genome sequence is like putting together a jigsaw puzzle, and different DNA sequencing technologies generate different types of genomic puzzle pieces. Some are small and highly detailed, while others are much bigger though the image is blurry. Verkko compares and assembles both types of pieces to generate a complete and accurate picture.

Verkko starts by putting together the small, detailed pieces, creating many partially assembled but disconnected segments of sequence. Then, Verkko compares the assembled regions with the larger, less precise pieces. These larger pieces serve as a framework to order the more detailed regions. The final product is an accurate and complete genome sequence.

The researchers tested Verkko with human and non-human genome sequencing data. The software quickly and precisely assembled the sequences of whole chromosomes, which was once a painstaking feat.

As Verkko leads to more complete human genome sequences, researchers can better assess human genomic diversity. With only one gapless human genome sequence, scientists currently lack knowledge about the diversity of many portions of the genome, such as regions of highly repetitive DNA, across the human population.

Verkko will also accelerate efforts to generate gapless genome sequences of species commonly used in research, such as mice, fruit flies, and zebrafish, improving their usefulness to scientists. Additionally, generating gapless genome sequences from a variety of plants, animals and other organisms will aid in comparative genomics, the study of the differences and similarities among the genomes of diverse species.

“Verkko can democratize generating gapless genome sequences,” said Adam Phillippy, Ph.D., an NHGRI senior investigator who worked on the T2T project and the development of Verkko. “This new software will make assembling complete genome sequences as affordable and routine as possible.”