Scrooge: a fast and memory-frugal genomic sequence aligner for CPUs, GPUs, and ASICs.

MOTIVATION: Pairwise sequence alignment is a very time-consuming step in common bioinformatics pipelines. Speeding up this step requires heuristics, efficient implementations, and/or hardware acceleration. A promising candidate for all of the above is the recently proposed GenASM algorithm. We identify and address three inefficiencies in the GenASM algorithm: it has a high amount of data movement, a large memory footprint, and does some unnecessary work. RESULTS: We propose Scrooge, a fast and memory-frugal genomic sequence aligner. Scrooge includes three novel algorithmic improvements which reduce the data movement, memory footprint, and the number of operations in the GenASM algorithm. We provide efficient open-source implementations of the Scrooge algorithm for CPUs and GPUs, which demonstrate the significant benefits of our algorithmic improvements. For long reads, the CPU version of Scrooge achieves a 20.1×, 1.7×, and 2.1× speedup over KSW2, Edlib, and a CPU implementation of GenASM, respectively. The GPU version of Scrooge achieves a 4.0×, 80.4×, 6.8×, 12.6×, and 5.9× speedup over the CPU version of Scrooge, KSW2, Edlib, Darwin-GPU, and a GPU implementation of GenASM, respectively. We estimate an ASIC implementation of Scrooge to use 3.6× less chip area and 2.1× less power than a GenASM ASIC while maintaining the same throughput. Further, we systematically analyze the throughput and accuracy behavior of GenASM and Scrooge under various configurations. As the best configuration of Scrooge depends on the computing platform, we make several observations that can help guide future implementations of Scrooge. AVAILABILITY AND IMPLEMENTATION: https://github.com/CMU-SAFARI/Scrooge.

A framework for high-throughput sequence alignment using real processing-in-memory systems.

MOTIVATION: Sequence alignment is a memory bound computation whose performance in modern systems is limited by the memory bandwidth bottleneck. Processing-in-memory (PIM) architectures alleviate this bottleneck by providing the memory with computing competencies. We propose Alignment-in-Memory (AIM), a framework for high-throughput sequence alignment using PIM, and evaluate it on UPMEM, the first publicly available general-purpose programmable PIM system. RESULTS: Our evaluation shows that a real PIM system can substantially outperform server-grade multi-threaded CPU systems running at full-scale when performing sequence alignment for a variety of algorithms, read lengths, and edit distance thresholds. We hope that our findings inspire more work on creating and accelerating bioinformatics algorithms for such real PIM systems. AVAILABILITY AND IMPLEMENTATION: Our code is available at https://github.com/safaad/aim.

SneakySnake: a fast and accurate universal genome pre-alignment filter for CPUs, GPUs and FPGAs.

MOTIVATION: We introduce SneakySnake, a highly parallel and highly accurate pre-alignment filter that remarkably reduces the need for computationally costly sequence alignment. The key idea of SneakySnake is to reduce the approximate string matching (ASM) problem to the single net routing (SNR) problem in VLSI chip layout. In the SNR problem, we are interested in finding the optimal path that connects two terminals with the least routing cost on a special grid layout that contains obstacles. The SneakySnake algorithm quickly solves the SNR problem and uses the found optimal path to decide whether or not performing sequence alignment is necessary. Reducing the ASM problem into SNR also makes SneakySnake efficient to implement on CPUs, GPUs and FPGAs. RESULTS: SneakySnake significantly improves the accuracy of pre-alignment filtering by up to four orders of magnitude compared to the state-of-the-art pre-alignment filters, Shouji, GateKeeper and SHD. For short sequences, SneakySnake accelerates Edlib (state-of-the-art implementation of Myers's bit-vector algorithm) and Parasail (state-of-the-art sequence aligner with a configurable scoring function), by up to 37.7× and 43.9× (>12× on average), respectively, with its CPU implementation, and by up to 413× and 689× (>400× on average), respectively, with FPGA and GPU acceleration. For long sequences, the CPU implementation of SneakySnake accelerates Parasail and KSW2 (sequence aligner of minimap2) by up to 979× (276.9× on average) and 91.7× (31.7× on average), respectively. As SneakySnake does not replace sequence alignment, users can still obtain all capabilities (e.g. configurable scoring functions) of the aligner of their choice, unlike existing acceleration efforts that sacrifice some aligner capabilities. AVAILABILITYAND IMPLEMENTATION: https://github.com/CMU-SAFARI/SneakySnake. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

From molecules to genomic variations: Accelerating genome analysis via intelligent algorithms and architectures.

We now need more than ever to make genome analysis more intelligent. We need to read, analyze, and interpret our genomes not only quickly, but also accurately and efficiently enough to scale the analysis to population level. There currently exist major computational bottlenecks and inefficiencies throughout the entire genome analysis pipeline, because state-of-the-art genome sequencing technologies are still not able to read a genome in its entirety. We describe the ongoing journey in significantly improving the performance, accuracy, and efficiency of genome analysis using intelligent algorithms and hardware architectures. We explain state-of-the-art algorithmic methods and hardware-based acceleration approaches for each step of the genome analysis pipeline and provide experimental evaluations. Algorithmic approaches exploit the structure of the genome as well as the structure of the underlying hardware. Hardware-based acceleration approaches exploit specialized microarchitectures or various execution paradigms (e.g., processing inside or near memory) along with algorithmic changes, leading to new hardware/software co-designed systems. We conclude with a foreshadowing of future challenges, benefits, and research directions triggered by the development of both very low cost yet highly error prone new sequencing technologies and specialized hardware chips for genomics. We hope that these efforts and the challenges we discuss provide a foundation for future work in making genome analysis more intelligent.

Accelerating Chan-Vese model with cross-modality guided contrast enhancement for liver segmentation.

Accurate and fast liver segmentation remains a challenging and important task for clinicians. Segmentation algorithms are slow and inaccurate due to noise and low quality images in computed tomography (CT) abdominal scans. Chan-Vese is an active contour based powerful and flexible method for image segmentation due to superior noise robustness. However, it is quite slow due to time-consuming partial differential equations, especially for large medical datasets. This can pose a problem for a real-time implementation of liver segmentation and hence, an efficient parallel implementation is highly desirable. Another important aspect is the contrast of CT liver images. Liver slices are sometimes very low in contrast which reduces the overall quality of liver segmentation. Hence, we implement cross-modality guided liver contrast enhancement as a pre-processing step to liver segmentation. GPU implementation of Chan-Vese improves average speedup by 99.811 (± 7.65) times and 14.647 (± 1.155) times with and without enhancement respectively in comparison with the CPU. Average dice, sensitivity and accuracy of liver segmentation are 0.656, 0.816 and 0.822 respectively on the original liver images and 0.877, 0.964 and 0.956 respectively on the enhanced liver images improving the overall quality of liver segmentation.

Accelerating B-spline interpolation on GPUs: Application to medical image registration.

BACKGROUND AND OBJECTIVE: B-spline interpolation (BSI) is a popular technique in the context of medical imaging due to its adaptability and robustness in 3D object modeling. A field that utilizes BSI is Image Guided Surgery (IGS). IGS provides navigation using medical images, which can be segmented and reconstructed into 3D models, often through BSI. Image registration tasks also use BSI to transform medical imaging data collected before the surgery and intra-operative data collected during the surgery into a common coordinate space. However, such IGS tasks are computationally demanding, especially when applied to 3D medical images, due to the complexity and amount of data involved. Therefore, optimization of IGS algorithms is greatly desirable, for example, to perform image registration tasks intra-operatively and to enable real-time applications. A traditional CPU does not have sufficient computing power to achieve these goals and, thus, it is preferable to rely on GPUs. In this paper, we introduce a novel GPU implementation of BSI to accelerate the calculation of the deformation field in non-rigid image registration algorithms. METHODS: Our BSI implementation on GPUs minimizes the data that needs to be moved between memory and processing cores during loading of the input grid, and leverages the large on-chip GPU register file for reuse of input values. Moreover, we re-formulate our method as trilinear interpolations to reduce computational complexity and increase accuracy. To provide pre-clinical validation of our method and demonstrate its benefits in medical applications, we integrate our improved BSI into a registration workflow for compensation of liver deformation (caused by pneumoperitoneum, i.e., inflation of the abdomen) and evaluate its performance. RESULTS: Our approach improves the performance of BSI by an average of 6.5×  and interpolation accuracy by 2×  compared to three state-of-the-art GPU implementations. Through pre-clinical validation, we demonstrate that our optimized interpolation accelerates a non-rigid image registration algorithm, which is based on the Free Form Deformation (FFD) method, by up to 34%. CONCLUSION: Our study shows that we can achieve significant performance and accuracy gains with our novel parallelization scheme that makes effective use of the GPU resources. We show that our method improves the performance of real medical imaging registration applications used in practice today.

Fast parallel vessel segmentation.

BACKGROUND AND OBJECTIVE: Accurate and fast vessel segmentation from liver slices remain challenging and important tasks for clinicians. The algorithms from the literature are slow and less accurate. We propose fast parallel gradient based seeded region growing for vessel segmentation. Seeded region growing is tedious when the inter connectivity between the elements is unavoidable. Parallelizing region growing algorithms are essential towards achieving real time performance for the overall process of accurate vessel segmentation. METHODS: The parallel implementation of seeded region growing for vessel segmentation is iterative and hence time consuming process. Seeded region growing is implemented as kernel termination and relaunch on GPU due to its iterative mechanism. The iterative or recursive process in region growing is time consuming due to intermediate memory transfers between CPU and GPU. We propose persistent and grid-stride loop based parallel approach for region growing on GPU. We analyze static region of interest of tiles on GPU for the acceleration of seeded region growing. RESULTS: We aim fast parallel gradient based seeded region growing for vessel segmentation from CT liver slices. The proposed parallel approach is 1.9x faster compared to the state-of-the-art. CONCLUSION: We discuss gradient based seeded region growing and its parallel implementation on GPU. The proposed parallel seeded region growing is fast compared to kernel termination and relaunch and accurate in comparison to Chan-Vese and Snake model for vessel segmentation.

GPU acceleration of liver enhancement for tumor segmentation.

BACKGROUND AND OBJECTIVE: Medical image segmentation plays a vital role in medical image analysis. There are many algorithms developed for medical image segmentation which are based on edge or region characteristics. These are dependent on the quality of the image. The contrast of a CT or MRI image plays an important role in identifying region of interest i.e. lesion(s). In order to enhance the contrast of image, clinicians generally use manual histogram adjustment technique which is based on 1D histogram specification. This is time consuming and results in poor distribution of pixels over the image. Cross modality based contrast enhancement is 2D histogram specification technique. This is robust and provides a more uniform distribution of pixels over CT image by exploiting the inner structure information from MRI image. This helps in increasing the sensitivity and accuracy of lesion segmentation from enhanced CT image. The sequential implementation of cross modality based contrast enhancement is slow. Hence we propose GPU acceleration of cross modality based contrast enhancement for tumor segmentation. METHODS: The aim of this study is fast parallel cross modality based contrast enhancement for CT liver images. This includes pairwise 2D histogram, histogram equalization and histogram matching. The sequential implementation of the cross modality based contrast enhancement is computationally expensive and hence time consuming. We propose persistence and grid-stride loop based fast parallel contrast enhancement for CT liver images. We use enhanced CT liver image for the lesion or tumor segmentation. We implement the fast parallel gradient based dynamic seeded region growing for lesion segmentation. RESULTS: The proposed parallel approach is 104.416 ( ±  5.166) times faster compared to the sequential implementation and increases the sensitivity and specificity of tumor segmentation. CONCLUSION: The cross modality approach is inspired by 2D histogram specification which incorporates spatial information existing in both guidance and input images for remapping the input image intensity values. The cross modality based liver contrast enhancement improves the quality of tumor segmentation.

Genotoxicity studies of organically grown broccoli (Brassica oleracea var. italica) and its interactions with urethane, methyl methanesulfonate and 4-nitroquinoline-1-oxide genotoxicity in the wing spot test of Drosophila melanogaster.

Broccoli (Brassica oleracea var. italica) has been defined as a cancer preventive food. Nevertheless, broccoli contains potentially genotoxic compounds as well. We performed the wing spot test of Drosophila melanogaster in treatments with organically grown broccoli (OGB) and co-treatments with the promutagen urethane (URE), the direct alkylating agent methyl methanesulfonate (MMS) and the carcinogen 4-nitroquinoline-1-oxide (4-NQO) in the standard (ST) and high bioactivation (HB) crosses with inducible and high levels of cytochrome P450s (CYPs), respectively. Larvae of both crosses were chronically fed with OGB or fresh market broccoli (FMB) as a non-organically grown control, added with solvents or mutagens solutions. In both crosses, the OGB added with Tween-ethanol yielded the expected reduction in the genotoxicity spontaneous rate. OGB co-treatments did not affect the URE effect, MMS showed synergy and 4-NQO damage was modulated in both crosses. In contrast, FMB controls produced damage increase; co-treatments modulated URE genotoxicity, diminished MMS damage, and did not change the 4-NQO damage. The high dietary consumption of both types of broccoli and its protective effects in D. melanogaster are discussed.