GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies
Abstract Background Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locatio...
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-05-01
|
| Series: | BMC Genomics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12864-018-4460-0 |
| _version_ | 1830486286704574464 |
|---|---|
| author | Jeremie S. Kim Damla Senol Cali Hongyi Xin Donghyuk Lee Saugata Ghose Mohammed Alser Hasan Hassan Oguz Ergin Can Alkan Onur Mutlu |
| author_facet | Jeremie S. Kim Damla Senol Cali Hongyi Xin Donghyuk Lee Saugata Ghose Mohammed Alser Hasan Hassan Oguz Ergin Can Alkan Onur Mutlu |
| author_sort | Jeremie S. Kim |
| collection | DOAJ |
| description | Abstract Background Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locations for seeds (i.e., smaller segments) within each read, 2) extract reference sequences at each of the mapping locations, and 3) check similarity between each read and its associated reference sequences with a computationally-expensive algorithm (i.e., sequence alignment) to determine the origin of the read. A seed location filter comes into play before alignment, discarding seed locations that alignment would deem a poor match. The ideal seed location filter would discard all poor match locations prior to alignment such that there is no wasted computation on unnecessary alignments. Results We propose a novel seed location filtering algorithm, GRIM-Filter, optimized to exploit 3D-stacked memory systems that integrate computation within a logic layer stacked under memory layers, to perform processing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1) introducing a new representation of coarse-grained segments of the reference genome, and 2) using massively-parallel in-memory operations to identify read presence within each coarse-grained segment. Our evaluations show that for a sequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the false negative rate of filtering by 5.59x–6.41x, and 2) provides an end-to-end read mapper speedup of 1.81x–3.65x, compared to a state-of-the-art read mapper employing the best previous seed location filtering algorithm. Conclusion GRIM-Filter exploits 3D-stacked memory, which enables the efficient use of processing-in-memory, to overcome the memory bandwidth bottleneck in seed location filtering. We show that GRIM-Filter significantly improves the performance of a state-of-the-art read mapper. GRIM-Filter is a universal seed location filter that can be applied to any read mapper. We hope that our results provide inspiration for new works to design other bioinformatics algorithms that take advantage of emerging technologies and new processing paradigms, such as processing-in-memory using 3D-stacked memory devices. |
| first_indexed | 2024-12-21T18:40:26Z |
| format | Article |
| id | doaj.art-0c114fee79d948bbbce02af311133723 |
| institution | Directory Open Access Journal |
| issn | 1471-2164 |
| language | English |
| last_indexed | 2024-12-21T18:40:26Z |
| publishDate | 2018-05-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Genomics |
| spelling | doaj.art-0c114fee79d948bbbce02af3111337232022-12-21T18:54:01ZengBMCBMC Genomics1471-21642018-05-0119S2234010.1186/s12864-018-4460-0GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologiesJeremie S. Kim0Damla Senol Cali1Hongyi Xin2Donghyuk Lee3Saugata Ghose4Mohammed Alser5Hasan Hassan6Oguz Ergin7Can Alkan8Onur Mutlu9Department of Electrical and Computer Engineering, Carnegie Mellon UniversityDepartment of Electrical and Computer Engineering, Carnegie Mellon UniversityDepartment of Computer Science, Carnegie Mellon UniversityNVIDIA ResearchDepartment of Electrical and Computer Engineering, Carnegie Mellon UniversityDepartment of Computer Engineering, Bilkent UniversityDepartment of Computer Science, ETH ZürichDepartment of Computer Engineering, TOBB University of Economics and TechnologyDepartment of Computer Engineering, Bilkent UniversityDepartment of Electrical and Computer Engineering, Carnegie Mellon UniversityAbstract Background Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locations for seeds (i.e., smaller segments) within each read, 2) extract reference sequences at each of the mapping locations, and 3) check similarity between each read and its associated reference sequences with a computationally-expensive algorithm (i.e., sequence alignment) to determine the origin of the read. A seed location filter comes into play before alignment, discarding seed locations that alignment would deem a poor match. The ideal seed location filter would discard all poor match locations prior to alignment such that there is no wasted computation on unnecessary alignments. Results We propose a novel seed location filtering algorithm, GRIM-Filter, optimized to exploit 3D-stacked memory systems that integrate computation within a logic layer stacked under memory layers, to perform processing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1) introducing a new representation of coarse-grained segments of the reference genome, and 2) using massively-parallel in-memory operations to identify read presence within each coarse-grained segment. Our evaluations show that for a sequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the false negative rate of filtering by 5.59x–6.41x, and 2) provides an end-to-end read mapper speedup of 1.81x–3.65x, compared to a state-of-the-art read mapper employing the best previous seed location filtering algorithm. Conclusion GRIM-Filter exploits 3D-stacked memory, which enables the efficient use of processing-in-memory, to overcome the memory bandwidth bottleneck in seed location filtering. We show that GRIM-Filter significantly improves the performance of a state-of-the-art read mapper. GRIM-Filter is a universal seed location filter that can be applied to any read mapper. We hope that our results provide inspiration for new works to design other bioinformatics algorithms that take advantage of emerging technologies and new processing paradigms, such as processing-in-memory using 3D-stacked memory devices.http://link.springer.com/article/10.1186/s12864-018-4460-0High throughput sequencingGenome sequencingSeed location filtering3D-stacked DRAMProcessing-in-memoryEmerging memory technologies |
| spellingShingle | Jeremie S. Kim Damla Senol Cali Hongyi Xin Donghyuk Lee Saugata Ghose Mohammed Alser Hasan Hassan Oguz Ergin Can Alkan Onur Mutlu GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies BMC Genomics High throughput sequencing Genome sequencing Seed location filtering 3D-stacked DRAM Processing-in-memory Emerging memory technologies |
| title | GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies |
| title_full | GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies |
| title_fullStr | GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies |
| title_full_unstemmed | GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies |
| title_short | GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies |
| title_sort | grim filter fast seed location filtering in dna read mapping using processing in memory technologies |
| topic | High throughput sequencing Genome sequencing Seed location filtering 3D-stacked DRAM Processing-in-memory Emerging memory technologies |
| url | http://link.springer.com/article/10.1186/s12864-018-4460-0 |
| work_keys_str_mv | AT jeremieskim grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT damlasenolcali grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT hongyixin grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT donghyuklee grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT saugataghose grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT mohammedalser grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT hasanhassan grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT oguzergin grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT canalkan grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT onurmutlu grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies |