Cargando…
GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies
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 s...
Autores principales: | , , , , , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2018
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5954284/ https://www.ncbi.nlm.nih.gov/pubmed/29764378 http://dx.doi.org/10.1186/s12864-018-4460-0 |
_version_ | 1783323490579906560 |
---|---|
author | Kim, Jeremie S. Senol Cali, Damla Xin, Hongyi Lee, Donghyuk Ghose, Saugata Alser, Mohammed Hassan, Hasan Ergin, Oguz Alkan, Can Mutlu, Onur |
author_facet | Kim, Jeremie S. Senol Cali, Damla Xin, Hongyi Lee, Donghyuk Ghose, Saugata Alser, Mohammed Hassan, Hasan Ergin, Oguz Alkan, Can Mutlu, Onur |
author_sort | Kim, Jeremie S. |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-5954284 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2018 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-59542842018-05-21 GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies Kim, Jeremie S. Senol Cali, Damla Xin, Hongyi Lee, Donghyuk Ghose, Saugata Alser, Mohammed Hassan, Hasan Ergin, Oguz Alkan, Can Mutlu, Onur BMC Genomics Research 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. BioMed Central 2018-05-09 /pmc/articles/PMC5954284/ /pubmed/29764378 http://dx.doi.org/10.1186/s12864-018-4460-0 Text en © The Author(s) 2018 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated. |
spellingShingle | Research Kim, Jeremie S. Senol Cali, Damla Xin, Hongyi Lee, Donghyuk Ghose, Saugata Alser, Mohammed Hassan, Hasan Ergin, Oguz Alkan, Can Mutlu, Onur GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-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 | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5954284/ https://www.ncbi.nlm.nih.gov/pubmed/29764378 http://dx.doi.org/10.1186/s12864-018-4460-0 |
work_keys_str_mv | AT kimjeremies grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT senolcalidamla grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT xinhongyi grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT leedonghyuk grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT ghosesaugata grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT alsermohammed grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT hassanhasan grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT erginoguz grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT alkancan grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies AT mutluonur grimfilterfastseedlocationfilteringindnareadmappingusingprocessinginmemorytechnologies |