Home

Awesome

odgi-layout-gpu

Computational Pangenoemics is an emerging field that studies genetic variation using a graph structure encom- passing multiple genomes. Visualizing pangenome graphs is vital for understanding genome diversity. Yet, handling large graphs can be challenging due to the high computational demands of the graph layout process.

Evaluated on 24 human whole-chromosome pangenomes, our GPU-based solution achieves a 57.3x speedup over the state-of-the-art multithreaded CPU baseline odgi-layout without layout quality loss, reducing execution time from hours to minutes.

We build upon the widely-used pangenome tools ODGI. This codebase includes our GPU kernel implementation of odgi-layout.

Installation

For CPU-only build, you can follow the installation guide in ODGI.

Our requirements are the same:

odgi requires a C++ version of 9.3 or higher.

odgi pulls in a host of source repositories as dependencies. It may be necessary to install several system-level libraries to build odgi. On Ubuntu 20.04, these can be installed using apt:

sudo apt install build-essential cmake python3-distutils python3-dev libjemalloc-dev

To build with GPU, we provide a flag USE_GPU when cmake.

git clone --recursive git@github.com:tonyjie/odgi.git
cd odgi
mkdir build
cmake .. -DCMAKE_BUILD_TYPE=Generic -DUSE_GPU=ON
make -j

The runnable odgi binary should be at odgi/bin/odgi

Usage

To compute odgi layout with GPU is very simple: you only need an extra --gpu. The other arguments follows the description here.

An example is as follows:

odgi/bin/odgi layout -i ${INPUT_OG} -o ${OUTPUT_LAY} --threads ${NUM_THREAD} --gpu

Performance

Datasets: HPRC, its Github

Machines:

Run time and speedup — the run time format is in h:mm:ss.

ChromosomeCPUA6000Speedup (A6000)A100Speedup (A100)
Chr.12:32:380:04:5930.6x0:02:4256.5x
Chr.21:17:030:03:3321.7x0:01:0175.8x
Chr.31:28:410:03:2725.7x0:01:3158.5x
Chr.41:47:320:03:4029.3x0:02:0651.2x
Chr.51:41:090:03:1930.5x0:01:0790.6x
Chr.61:13:550:02:4926.3x0:01:2751.0x
Chr.71:16:460:03:0025.6x0:01:3449.0x
Chr.81:17:270:02:5726.3x0:01:4146.0x
Chr.91:16:490:02:5326.6x0:00:5583.8x
Chr.100:48:340:02:2220.6x0:00:4466.2x
Chr.110:56:250:02:0726.7x0:00:3791.5x
Chr.120:44:050:02:0720.9x0:00:4954.0x
Chr.131:03:320:02:2226.8x0:00:5371.9x
Chr.140:51:210:02:0424.9x0:00:4667.0x
Chr.151:11:330:02:5225.0x0:01:1656.5x
Chr.162:19:470:04:5628.3x0:12:5810.8x
Chr.171:03:450:02:0131.7x0:01:0757.1x
Chr.180:50:290:01:5027.6x0:01:0844.6x
Chr.190:40:230:01:2927.3x0:00:2789.8x
Chr.200:51:340:01:3034.3x0:01:0150.7x
Chr.210:44:180:01:2630.9x0:00:3869.9x
Chr.220:39:590:01:3724.8x0:00:3080.0x
Chr.X1:04:060:01:4935.4x0:00:4978.4x
Chr.Y0:01:550:00:0336.9x0:00:0428.7x
Geometric Mean27.7x57.3x

Upstream PR & Artifact

Ready to be merged into the ODGI with this PR.

To reproduce the experiments in the paper, the easiet way is to follow our provided artifact repo.

Paper

Rapid GPU-Based Pangenome Graph Layout: https://arxiv.org/abs/2409.00876

To be presented at SC'24.