Detecting Single Nucleotide Polymorphisms (SNPs) in genome analysis is a fundamental procedure. SNPs act as biological markers and are used by geneticists to identify genes associated with a particular disease. However, with up to five million SNPs in a single person’s genome, detecting and cataloging them is a prodigious task.
The most common tool for SNP detection, SOAPsnp, would require upward of a week to perform an analysis on a single typical human genome. This severely affects any downstream analyses, which reduces efficiency.
Recently, IEEE posted a paper entitled mSNP: A Massively Parallel Algorithm for Large-Scale SNP Detection. It introduces mSNP as an improved version of SOAPsnp that is able to handle large-scale SNP detection using Intel Xeon Phi coprocessors.
Redesign of the Essential Data Structures
Developing mSNP began with the redesign of SOAPsnp’s essential data structures. The development of a space-efficient data structure increases computing efficiency. Unnecessary access to memory is reduced, which significantly reduces the overall memory footprint. This improvement is especially important when you consider that memory would be accessed almost 420 trillion times during a whole human genome scan using SOAPsnp.
Want More Tech News? Subscribe to ComputingEdge Newsletter Today!
Leveraging a Parallel Framework
The inefficiencies of SOAPsnp were countered by a coordinated parallel framework to optimize the use of hardware. Normally, the CPU would need to wait for Xeon Phi to return results on each job, meaning it would lay idle, wasting computing power. However, by making data transfer asynchronous, the CPU can continue with the next job without waiting for results. This asynchronous configuration is possible because rather than utilizing Xeon Phi’s native mode, offload mode was adopted by mSNP. Additionally, Xeon Phi has a 512-bit wide VPU, so mSNP’s tailored operations and data structures can make optimal use of the wide VPU to improve data throughput. This is something SOAPsnp could not do without optimization.
Using a Window Division Strategy
In order to address load imbalance and achieve higher performance, mSNP uses a strategy of read-based window division. This improves throughput since different processes are able to load reads from various lines of input simultaneously. Better load balance and increased efficiency are achieved because the number of reads per process is more or less equal, and all processes can communicate at the same time.
mSNP has the boasting rights of being the first SNP detection tool empowered by Intel’s Xeon Phi. During testing, a 38x single thread speedup on CPU was achieved. Given the speed benefits researchers can reap from this advancement, this improvement is significant enough on its own. However, this was also done without experiencing any loss in precision. Thus the team was able to achieve an often elusive “twofer”: more speed without sacrificing quality. Additionally, mSNP was able to successfully scale to 4,096 nodes on Tianhe-2. These results demonstrate the efficiency and scalability mSNP offers for large-scale human genome SNP detection.
The whole article, mSNP: A Massively Parallel Algorithm for Large-Scale SNP Detection, can be downloaded and read from IEEE’s digital library.
