Graphics processors accelerate pattern discovery

August 26, 2015
Graphics processors accelerate pattern discovery
Parallel processing using the microprocessors in modern computer graphics adapters can greatly increase the speed of motif discovery at relatively low cost. Credit: tyodwong/iStock/Thinkstock

Repeating patterns in complex biological networks can now be found hundreds of times faster using an algorithm that exploits the parallel computing capacity of modern graphics adapters. The A*STAR-led breakthrough opens the possibility of rapid genome scans for discrete molecular structures.

A network motif is a statistically significant connection of nodes that appears more frequently than chance would allow. In the gene transcription network for the bacteria Escherichia coli, for example, a simple network motif arises in the process by which a transcription factor responds to itself, known as negative auto-regulation. Such a motif occurs repeatedly in the transcriptome.

"This negative auto-regulation process has essential biological functions," explains Wenqing Lin from the A*STAR Institute for Infocomm Research. "Searching for these repeating 'graphs' is of particular importance in the study of network functionality."

These searches, however, are a significant computational drain and increasing the rate of motif discovery is a steep mathematical challenge. "Even state-of-the-art solutions require several days to derive network motifs from networks with only a few thousand vertices," says Lin.

The research team harnessed the capabilities of the modern computer graphics processors to overcome the limitations of existing network motif search algorithms. Graphics processing units often comprise thousands of computing cores, allowing Lin's team to adapt a large number of the computational tasks involved in graph mining. This can significantly reduce computation time.

By developing a parallelized code that utilizes the capabilities of graphical processing units (GPUs), including simultaneous execution of code on multiple GPU cores and efficient memory access patterns, the team was able to expedite the search by up to 100 times—the improved rate was confirmed through extensive experiments on a variety of .

The study demonstrates the feasibility of using GPUs for network motif search tasks. GPUs are also around 20 times cheaper than computer processors for equivalent performance, highlighting the potential for large-scale search projects.

Network motif discovery has many applications beyond biology, including pattern detection in digital circuits and other non-random networks. "Our research results can also be applied to solving the problems of enumerating all subgraphs of a large network, and finding the matches for a given subgraph in a large network," says Lin. "Both of these problems are fundamental aspects of graph mining and graph databases."

Explore further: Many experiments for the price of one: A breakthrough in the study of gene regulation

More information: "Network motif discovery: A GPU approach." IEEE 31st International Conference on Data Engineering (ICDE), 831–842 (2015).

Related Stories

Unraveling biological networks

March 5, 2012

A new approach to disentangling the complexities of biological networks, such as the way in which proteins interact in our body's cells has been developed by researchers in China. The team's algorithm could allow biologists ...

Recommended for you

Making energy-harvesting computers reliable

October 28, 2016

A revolutionary and emerging class of energy-harvesting computer systems require neither a battery nor a power outlet to operate, instead operating by harvesting energy from their environment. While radio waves, solar energy, ...

Microsoft aims at Apple with high-end PCs, 3D software

October 26, 2016

Microsoft launched a new consumer offensive Wednesday, unveiling a high-end computer that challenges the Apple iMac along with an updated Windows operating system that showcases three-dimensional content and "mixed reality."


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.