Doe Science news source
The DOE Science News Source is a Newswise initiative to promote research news from the Office of Science of the DOE to the public and news media.
  • 2018-03-12 12:30:43
  • Article ID: 690906

A Game Changer: Metagenomic Clustering Powered by HPC

New Berkeley Lab algorithm allows biologists to harness the capabilities of massively parallel supercomputers to make sense of a genomic 'data deluge'

  • Credit: Georgios Pavlopoulos and Nikos Kyrpides, JGI/Berkeley Lab

    Proteins from metagenomes clustered into families according to their taxonomic classification.

  • Credit: Roy Kaltschmidt, Berkeley Lab

    Cori Supercomputer at the National Energy Research Scientific Computing Center (NERSC).

Download HipMCL:

Did you know that the tools used for analyzing relationships between social network users or ranking web pages can also be extremely valuable for making sense of big science data? On a social network like Facebook, each user (person or organization) is represented as a node and the connections (relationships and interactions) between them are called edges. By analyzing these connections, researchers can learn a lot about each user—interests, hobbies, shopping habits, friends, etc.

In biology, similar graph-clustering algorithms can be used to understand the proteins that perform most of life’s functions. It is estimated that the human body alone contains about 100,000 different protein types, and almost all biological tasks—from digestion to immunity—occur when these microorganisms interact with each other. A better understanding of these networks could help researchers determine the effectiveness of a drug or identify potential treatments for a variety of diseases.

Today, advanced high-throughput technologies allow researchers to capture hundreds of millions of proteins, genes and other cellular components at once and in a range of environmental conditions. Clustering algorithms are then applied to these datasets to identify patterns and relationships that may point to structural and functional similarities. Though these techniques have been widely used for more than a decade, they cannot keep up with the torrent of biological data being generated by next-generation sequencers and microarrays. In fact, very few existing algorithms can cluster a biological network containing millions of nodes (proteins) and edges (connections).

That’s why a team of researchers from the Department of Energy’s (DOE’s) Lawrence Berkeley National Laboratory (Berkeley Lab) and Joint Genome Institute (JGI) took one of the most popular clustering approaches in modern biology—the Markov Clustering (MCL) algorithm—and modified it to run quickly, efficiently and at scale on distributed-memory supercomputers. In a test case, their high-performance algorithm—called HipMCL—achieved a previously impossible feat: clustering a large biological network containing about 70 million nodes and 68 billion edges in a couple of hours, using approximately 140,000 processor cores on the National Energy Research Scientific Computing Center’s (NERSC) Cori supercomputer. A paper describing this work was recently published in the journal Nucleic Acids Research.

“The real benefit of HipMCL is its ability to cluster massive biological networks that were impossible to cluster with the existing MCL software, thus allowing us to identify and characterize the novel functional space present in the microbial communities,” says Nikos Kyrpides, who heads JGI’s Microbiome Data Science efforts and the Prokaryote Super Program and is co-author on the paper. “Moreover we can do that without sacrificing any of the sensitivity or accuracy of the original method, which is always the biggest challenge in these sort of scaling efforts.”

“As our data grows, it is becoming even more imperative that we move our tools into high performance computing environments, ” he adds.  “If you were to ask me how big is the protein space? The truth is, we don’t really know because until now we didn’t have the computational tools to effectively cluster all of our genomic data and probe the functional dark matter.” 

In addition to advances in data collection technology, researchers are increasingly opting to share their data in community databases like the Integrated Microbial Genomes & Microbiomes (IMG/M) system, which was developed through a decades-old collaboration between scientists at JGI and Berkeley Lab’s Computational Research Division (CRD). But by allowing users to do comparative analysis and explore the functional capabilities of microbial communities based on their metagenomic sequence, community tools like IMG/M are also contributing to the data explosion in technology.

How Random Walks Lead to Computing Bottlenecks

To get a grip on this torrent of data, researchers rely on cluster analysis, or clustering. This is essentially the task of grouping objects so that items in the same group (cluster) are more similar than those in other clusters. For more than a decade, computational biologists have favored MCL for clustering proteins by similarities and interactions.

“One of the reasons that MCL has been popular among computational biologists is that it is relatively parameter free; users don’t have to set a ton of parameters to get accurate results and it is remarkably stable to small alterations in the data. This is important because you might have to redefine a similarity between data points or you might have to correct for a slight measurement error in your data. In these cases, you don’t want your modifications to change the analysis from 10 clusters to 1,000 clusters,” says Aydin Buluç, a CRD scientist and one of the paper’s co-authors.

But, he adds, the computational biology community is encountering a computing bottleneck because the tool mostly runs on a single computer node, is computationally expensive to execute and has a big memory footprint—all of which limit the amount of data this algorithm can cluster.

One of the most computationally and memory intensive steps in this analysis is a process called random walk. This technique quantifies the strength of a connection between nodes, which is useful for classifying and predicting links in a network. In the case of an Internet search, this may help you find a cheap hotel room in San Francisco for spring break and even tell you the best time to book it. In biology, such a tool could help you identify proteins that are helping your body fight a flu virus.

Given an arbitrary graph or network, it is difficult to know the most efficient way to visit all of the nodes and links. A random walk gets a sense of the footprint by exploring the entire graph randomly; it starts at a node and moves arbitrarily along an edge to a neighboring node. This process keeps going until all of the nodes on the graph network have been reached. Because there are many different ways of traveling between nodes in a network, this step repeats numerous times. Algorithms like MCL will continue running this random walk process until there is no longer a significant difference between the iterations. 

In any given network, you might have a node that is connected to hundreds of nodes and another node with only one connection. The random walks will capture the highly connected nodes because a different path will be detected each time the process is run. With this information, the algorithm can predict with a level of certainty how a node on the network is connected to another. In between each random walk run, the algorithm marks its prediction for each node on the graph in a column of a Markov matrix—kind of like a ledger—and final clusters are revealed at the end. It sounds simple enough, but for protein networks with millions of nodes and billions of edges, this can become an extremely computationally and memory intensive problem. With HipMCL, Berkeley Lab computer scientists used cutting-edge mathematical tools to overcome these limitations. 

“We have notably kept the MCL backbone intact, making HipMCL a massively parallel implementation of the original MCL algorithm,” says Ariful Azad, a computer scientist in CRD and lead author of the paper. 

Although there have been previous attempts to parallelize the MCL algorithm to run on a single GPU, the tool could still only cluster relatively small networks because of memory limitations on a GPU, Azad notes.

“With HipMCL we essentially rework the MCL algorithms to run efficiently, in parallel on thousands of processors, and set it up to take advantage of the aggregate memory available in all compute nodes,” he adds. “The unprecedented scalability of HipMCL comes from its use of state-of-the-art algorithms for sparse matrix manipulation.”

According to Buluç, performing a random walk simultaneously from many nodes of the graph is best computed using sparse-matrix matrix multiplication, which is one of the most basic operations in the recently released GraphBLAS standard. Buluç and Azad developed some of the most scalable parallel algorithms for GraphBLAS’s sparse-matrix matrix multiplication and modified one of their state-of-the-art algorithms for HipMCL.   

“The crux here was to strike the right balance between parallelism and memory consumption. HipMCL dynamically extracts as much parallelism as possible given the available memory allocated to it,” says Buluç.

HipMCL: Clustering at Scale

In addition to the mathematical innovations, another advantage of HipMCL is its ability to run seamlessly on any system—including laptops, workstations and large supercomputers. The researchers achieved this by developing their tools in C++ and using standard MPI and OpenMP libraries.

“We extensively tested HipMCL on Intel Haswell, Ivy Bridge and Knights Landing processors at NERSC, using a up to 2,000 nodes and half a million threads on all processors, and in all of these runs HipMCL successfully clustered networks comprising thousands to billions of edges,” says Buluç. “We see that there is no barrier in the number of processors that it can use to run and find that it can cluster networks 1,000 times faster than the original MCL algorithm.” 

“HipMCL is going to be really transformational for computational biology of big data, just as the IMG and IMG/M systems have been for microbiome genomics,” says Kyrpides. “This accomplishment is a testament to the benefits of interdisciplinary collaboration at Berkeley Lab. As biologists we understand the science, but it’s been so invaluable to be able to collaborate with computer scientists that can help us tackle our limitations and propel us forward.”    

Their next step is to continue to rework HipMCL and other computational biology tools for future exascale systems, which will be able to compute quintillion calculations per second. This will be essential as genomics data continues to grow at a mindboggling rate—doubling about every five to six months.  This will be done as part of DOE Exascale Computing Project’s Exagraph co-design center.

Development of HipMCL was primarily supported by the U.S. Department of Energy’s Office of Science via the  Exascale Solutions for Microbiome Analysis (ExaBiome) project, which is developing exascale algorithms and software to address current limitations in metagenomics research. The development of the fundamental ideas behind this research was also supported by the Office of Advanced Scientific Computing Research’s Applied Math Early Career program. NERSC is an DOE Office of Science User Facility.

HipMCL is based on MPI and OpenMP and is freely available under a modified BSD license at: Installation instructions and large datasets can be found in the relevant Wiki tab.

  • Filters

  • × Clear Filters

Out of Thin Air

Argonne researchers conducted basic science computational studies as part of a collaboration with researchers at the University of Illinois at Chicago to design a "beyond-lithium-ion" battery cell that operates by running on air over many charge and discharge cycles. The design offers energy storage capacity about three times that of a lithium-ion battery, with significant potential for further improvements.

COSMIC Impact: Next-Gen X-ray Microscopy Platform Now Operational

COSMIC, a next-generation X-ray beamline now operating at Berkeley Lab, brings together a unique set of capabilities to measure the properties of materials at the nanoscale. It allows scientists to probe working batteries and other active chemical reactions, and to reveal new details about magnetism and correlated electronic materials.

Turning Up the Heat on Remote Research Plots Without Electricity

Flexible, tunable technique warms plants without need for electricity, aiding ecosystem research in remote locales.

Weird Superconductor Leads Double Life

Understanding strontium titanate's odd behavior will aid efforts to develop materials that conduct electricity with 100 percent efficiency at higher temperatures.

Engineering Yeast Tolerance to a Promising Biomass Deconstruction Solvent

Chemical genomic-guided engineering of gamma-valerolactone-tolerant yeast.

Beyond the WIMP: Unique Crystals Could Expand the Search for Dark Matter

A new particle detector design proposed at the U.S. Department of Energy's Berkeley Lab could greatly broaden the search for dark matter - which makes up 85 percent of the total mass of the universe yet we don't know what it's made of - into an unexplored realm.

20 Percent of Americans Responsible for Almost Half of US Food-Related Greenhouse Gas Emissions

On any given day, 20 percent of Americans account for nearly half of U.S. diet-related greenhouse gas emissions, and high levels of beef consumption are largely responsible, according to a new study from researchers at the University of Michigan and Tulane University.

Saplings Survive Droughts via Storage

Certain species of trees retain stored water, limit root growth to survive three months without water.

Study Reveals New Insights into How Hybrid Perovskite Solar Cells Work

Scientists have gained new insights into a fundamental mystery about hybrid perovskites, low-cost materials that could enhance or even replace conventional solar cells made of silicon.

Want to Clean Up the Environment? Make Credit Easier to Get.

Research by Berkeley Haas Prof. Ross Levine, the Willis H. Booth Chair in Banking and Finance, is the first to show that when lending conditions ease, businesses invest more in projects to cut pollution.

  • Filters

  • × Clear Filters

Rensselaer Polytechnic Institute Professor Jian Shi Receives Air Force Young Investigator Research Program Award

Jian Shi, assistant professor of materials science and engineering at Rensselaer Polytechnic Institute, has won a Young Investigator Research Program (YIP) award from the Air Force Office of Scientific Research (AFOSR). Shi will use the three-year, $450,000 grant to pursue fundamental research on nanoscale complex materials that could lead to the development of next-generation resilient and high-performance energy conversion and sensing technologies.

Kerstin Kleese van Dam Receives 32nd Town of Brookhaven Annual Women's Recognition Award for Science

The award recognizes the contributions Kleese van Dam--director of Brookhaven Lab's Computational Science Initiative since 2015--has made to scientific computing and data management over the past three decades.

Jefferson Lab Announces New Accelerator Science Leader

The Department of Energy's Thomas Jefferson National Accelerator Facility has announced that Andrei Seryi will become its new associate director for accelerator operations, research and development in June.

First Plasma for New Machine to Study Puzzling Process That Occurs Throughout the Universe

Announcement describes completion of construction of FLARE, a powerful new machine to study magnetic reconnection.

Rensselaer Polytechnic Institute Professor Jian Sun Receives Power Electronics Achievement Award

Jian Sun, professor of electrical, computer, and systems engineering and director the New York State Center for Future Energy Systems at Rensselaer Polytechnic Institute, received the 2017 R. David Middlebrook Outstanding Achievement Award from the IEEE Power Electronics Society (PELS). He was recognized for "contributions to modeling and control of power electronic converters and systems."

FGC Plasma Solutions Wins Top NASA Innovation Award

Argonne Chain Reaction Innovator Felipe Gomez del Campo has received the 2018 NASA iTech award for X-Factor Innovation.

Sandia Researcher Jacqueline Chen Elected to National Academy of Engineering

LIVERMORE, Calif. -- Jacqueline Chen, a distinguished member of the technical staff at Sandia National Laboratories, has been elected to the National Academy of Engineering. Chen is among the 99 new members from around the globe in the 2018 class.Election to the National Academy of Engineering is the highest professional distinction for an engineer in the United States.

PNNL Helps Form International Energy Storage Organization

News Release DALIAN, China -- Energy storage allows power operators across the nation to balance electricity supply and demand instantaneously, affording ratepayers a more resilient power supply.Now the focus on energy storage is global. In January, energy storage experts at the Department of Energy's Pacific Northwest National Laboratory joined forces with their counterparts around the world to forge the International Coalition for Energy Storage and Innovation, or ICESI.

University Partnership to Help Nevada Scientists Commercialize Discovery

UNLV's Office of Technology Transfer and the Desert Research are partnering to help faculty and students leverage each other's talent and resources to transform inventionsĀ into new products and services.

DOE Seeks Industry Partners for HPC Research on Materials in Applied Energy Technologies

The Department of Energy (DOE) today announced a funding opportunity totaling $3 million to support projects between U.S. industry and DOE national laboratories related to improving materials in severe or complex environments through the new High Performance Computing for Materials in Applied Energy Technologies (HPC4Mtls) Program.

  • Filters

  • × Clear Filters

Turning Up the Heat on Remote Research Plots Without Electricity

Flexible, tunable technique warms plants without need for electricity, aiding ecosystem research in remote locales.

Engineering Yeast Tolerance to a Promising Biomass Deconstruction Solvent

Chemical genomic-guided engineering of gamma-valerolactone-tolerant yeast.

Saplings Survive Droughts via Storage

Certain species of trees retain stored water, limit root growth to survive three months without water.

Unlocking On-Package Memory's Effects on High-Performance Computing's Scientific Kernels

Intuitive visual analytical model better explains complex architectural scenarios and offers general design principles.

Data Dive: How Microbes Handle Poor Nutrition in Tropical Soil

High-performance computing reveals the relationship between DNA and phosphorous uptake.

The Secret Lives of Cells

Supercomputer simulations predict how E. coli adapts to environmental stresses.

It's Not Part of the Problem, but Part of the Solution

Americium(III) is selectively and efficiently separated from europium(III) by an extractant in an ionic liquid.

Buckyball Marries Graphene

Electronic and structure richness arise from the merger of semiconducting molecules of carbon buckyballs and 2-D graphene.

Atomic Movies Explain Why Perovskite Solar Cells Are More Efficient

Tracking atoms is crucial to improving the efficiency of next-generation perovskite solar cells.

Catalysts: High Performance Lies on the Edge

Iron may be more valuable than platinum. Sometimes.


Wednesday March 14, 2018, 02:05 PM

Q&A: Al Ashley Reflects on His Efforts to Diversify SLAC and Beyond

SLAC National Accelerator Laboratory

Thursday February 15, 2018, 12:05 PM

Insights on Innovation in Energy, Humanitarian Aid Highlight UVA Darden's Net Impact Week

University of Virginia Darden School of Business

Friday February 09, 2018, 11:05 AM

Ivy League Graduate, Writer and Activist with Dyslexia Visits CSUCI to Reframe the Concept of Learning Disabilities

California State University, Channel Islands

Wednesday January 17, 2018, 12:05 PM

Photographer Adam Nadel Selected as Fermilab's New Artist-in-Residence for 2018

Fermi National Accelerator Laboratory (Fermilab)

Wednesday January 17, 2018, 12:05 PM

Fermilab Computing Partners with Argonne, Local Schools for Hour of Code

Fermi National Accelerator Laboratory (Fermilab)

Wednesday December 20, 2017, 01:05 PM

Q&A: Sam Webb Teaches X-Ray Science from a Remote Classroom

SLAC National Accelerator Laboratory

Monday December 18, 2017, 01:05 PM

The Future of Today's Electric Power Systems

Rensselaer Polytechnic Institute (RPI)

Monday December 18, 2017, 12:05 PM

Supporting the Development of Offshore Wind Power Plants

Rensselaer Polytechnic Institute (RPI)

Tuesday October 03, 2017, 01:05 PM

Stairway to Science

Argonne National Laboratory

Thursday September 28, 2017, 12:05 PM

After-School Energy Rush

Argonne National Laboratory

Thursday September 28, 2017, 10:05 AM

Bringing Diversity Into Computational Science Through Student Outreach

Brookhaven National Laboratory

Thursday September 21, 2017, 03:05 PM

From Science to Finance: SLAC Summer Interns Forge New Paths in STEM

SLAC National Accelerator Laboratory

Thursday September 07, 2017, 02:05 PM

Students Discuss 'Cosmic Opportunities' at 45th Annual SLAC Summer Institute

SLAC National Accelerator Laboratory

Thursday August 31, 2017, 05:05 PM

Binghamton University Opens $70 Million Smart Energy Building

Binghamton University, State University of New York

Wednesday August 23, 2017, 05:05 PM

Widening Horizons for High Schoolers with Code

Argonne National Laboratory

Saturday May 20, 2017, 12:05 PM

Rensselaer Polytechnic Institute Graduates Urged to Embrace Change at 211th Commencement

Rensselaer Polytechnic Institute (RPI)

Monday May 15, 2017, 01:05 PM

ORNL, University of Tennessee Launch New Doctoral Program in Data Science

Oak Ridge National Laboratory

Friday April 07, 2017, 11:05 AM

Champions in Science: Profile of Jonathan Kirzner

Department of Energy, Office of Science

Wednesday April 05, 2017, 12:05 PM

High-Schooler Solves College-Level Security Puzzle From Argonne, Sparks Interest in Career

Argonne National Laboratory

Tuesday March 28, 2017, 12:05 PM

Champions in Science: Profile of Jenica Jacobi

Department of Energy, Office of Science

Friday March 24, 2017, 10:40 AM

Great Neck South High School Wins Regional Science Bowl at Brookhaven Lab

Brookhaven National Laboratory

Wednesday February 15, 2017, 04:05 PM

Middle Schoolers Test Their Knowledge at Science Bowl Competition

Argonne National Laboratory

Friday January 27, 2017, 04:00 PM

Haslam Visits ORNL to Highlight State's Role in Discovering Tennessine

Oak Ridge National Laboratory

Tuesday November 08, 2016, 12:05 PM

Internship Program Helps Foster Development of Future Nuclear Scientists

Oak Ridge National Laboratory

Friday May 13, 2016, 04:05 PM

More Than 12,000 Explore Jefferson Lab During April 30 Open House

Thomas Jefferson National Accelerator Facility

Monday April 25, 2016, 05:05 PM

Giving Back to National Science Bowl

Ames Laboratory

Friday March 25, 2016, 12:05 PM

NMSU Undergrad Tackles 3D Particle Scattering Animations After Receiving JSA Research Assistantship

Thomas Jefferson National Accelerator Facility

Tuesday February 02, 2016, 10:05 AM

Shannon Greco: A Self-Described "STEM Education Zealot"

Princeton Plasma Physics Laboratory

Monday November 16, 2015, 04:05 PM

Rare Earths for Life: An 85th Birthday Visit with Mr. Rare Earth

Ames Laboratory

Tuesday October 20, 2015, 01:05 PM

Meet Robert Palomino: 'Give Everything a Shot!'

Brookhaven National Laboratory

Tuesday April 22, 2014, 11:30 AM

University of Utah Makes Solar Accessible

University of Utah

Wednesday March 06, 2013, 03:40 PM

Student Innovator at Rensselaer Polytechnic Institute Seeks Brighter, Smarter, and More Efficient LEDs

Rensselaer Polytechnic Institute (RPI)

Friday November 16, 2012, 10:00 AM

Texas Tech Energy Commerce Students, Community Light up Tent City

Texas Tech University

Wednesday November 23, 2011, 10:45 AM

Don't Get 'Frosted' Over Heating Your Home This Winter

Temple University

Wednesday July 06, 2011, 06:00 PM

New Research Center To Tackle Critical Challenges Related to Aircraft Design, Wind Energy, Smart Buildings

Rensselaer Polytechnic Institute (RPI)

Friday April 22, 2011, 09:00 AM

First Polymer Solar-Thermal Device Heats Home, Saves Money

Wake Forest University

Friday April 15, 2011, 12:25 PM

Like Superman, American University Will Get Its Energy from the Sun

American University

Thursday February 10, 2011, 05:00 PM

ARRA Grant to Help Fund Seminary Building Green Roof

University of Chicago

Tuesday December 07, 2010, 05:00 PM

UC San Diego Installing 2.8 Megawatt Fuel Cell to Anchor Energy Innovation Park

University of California San Diego

Monday November 01, 2010, 12:50 PM

Rensselaer Smart Lighting Engineering Research Center Announces First Deployment of New Technology on Campus

Rensselaer Polytechnic Institute (RPI)

Friday September 10, 2010, 12:40 PM

Ithaca College Will Host Regional Clean Energy Summit

Ithaca College

Tuesday July 27, 2010, 10:30 AM

Texas Governor Announces $8.4 Million Award to Create Renewable Energy Institute

Texas Tech University

Friday May 07, 2010, 04:20 PM

Creighton University to Offer New Alternative Energy Program

Creighton University

Wednesday May 05, 2010, 09:30 AM

National Engineering Program Seeks Subject Matter Experts in Energy

JETS Junior Engineering Technical Society

Wednesday April 21, 2010, 12:30 PM

Students Using Solar Power To Create Sustainable Solutions for Haiti, Peru

Rensselaer Polytechnic Institute (RPI)

Wednesday March 03, 2010, 07:00 PM

Helping Hydrogen: Student Inventor Tackles Challenge of Hydrogen Storage

Rensselaer Polytechnic Institute (RPI)

Thursday February 04, 2010, 02:00 PM

Turning Exercise into Electricity

Furman University

Thursday November 12, 2009, 12:45 PM

Campus Leaders Showing the Way to a Sustainable, Clean Energy Future

National Wildlife Federation (NWF)

Showing results

0-4 Of 2215