{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T14:16:37Z","timestamp":1773843397095,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T00:00:00Z","timestamp":1729468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Lenovo-BSC Contract-Framework"},{"name":"Generalitat de Catalunya GenCat-DIUiE"},{"name":"Spanish Ministry"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Recent advances in sequencing technologies have stressed the critical role of sequence analysis algorithms and tools in genomics and healthcare research. In particular, sequence alignment is a fundamental building block in many sequence analysis pipelines and is frequently a performance bottleneck both in terms of execution time and memory usage. Classical sequence alignment algorithms are based on dynamic programming and often require quadratic time and memory with respect to the sequence length. As a result, classical sequence alignment algorithms fail to scale with increasing sequence lengths and quickly become memory-bound due to data-movement penalties.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Processing-In-Memory (PIM) is an emerging architectural paradigm that seeks to accelerate memory-bound algorithms by bringing computation closer to the data to mitigate data-movement penalties. This work presents BIMSA (Bidirectional In-Memory Sequence Alignment), a PIM design and implementation for the state-of-the-art sequence alignment algorithm BiWFA (Bidirectional Wavefront Alignment), incorporating new hardware-aware optimizations for a production-ready PIM architecture (UPMEM). BIMSA supports aligning sequences up to 100K bases, exceeding the limitations of state-of-the-art PIM implementations. First, BIMSA achieves speedups up to 22.24\u00d7 (11.95\u00d7 on average) compared to state-of-the-art PIM-enabled implementations of sequence alignment algorithms. Second, achieves speedups up to 5.84\u00d7 (2.83\u00d7 on average) compared to the highest-performance multicore CPU implementation of BiWFA. Third, BIMSA exhibits linear scalability with the number of compute units in memory, enabling further performance improvements with upcoming PIM architectures equipped with more compute units and achieving speedups up to 9.56\u00d7 (4.7\u00d7 on average).<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Code and documentation are publicly available at https:\/\/github.com\/AlejandroAMarin\/BIMSA.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae631","type":"journal-article","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T07:29:04Z","timestamp":1729150144000},"source":"Crossref","is-referenced-by-count":10,"title":["BIMSA: accelerating long sequence alignment using processing-in-memory"],"prefix":"10.1093","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-4745-7005","authenticated-orcid":false,"given":"Alejandro","family":"Alonso-Mar\u00edn","sequence":"first","affiliation":[{"name":"Department of Computer Sciences , Barcelona Supercomputing Center, Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]},{"name":"Department of Electronic Engineering, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]},{"given":"Ivan","family":"Fernandez","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences , Barcelona Supercomputing Center, Barcelona 08034,","place":["Spain"]},{"name":"Departament d\u2019Arquitectura de Computadors, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4871-3192","authenticated-orcid":false,"given":"Quim","family":"Aguado-Puig","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences , Barcelona Supercomputing Center, Barcelona 08034,","place":["Spain"]},{"name":"Department of Electronic Engineering, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]},{"name":"Departament d\u2019Arquitectura de Computadors i Sistemes Operatius, Universitat Aut\u00f2noma de Barcelona , Barcelona 08193,","place":["Spain"]}]},{"given":"Juan","family":"G\u00f3mez-Luna","sequence":"additional","affiliation":[{"name":"NVIDIA Switzerland, NVIDIA Research , Zurich 8004,","place":["Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7951-3914","authenticated-orcid":false,"given":"Santiago","family":"Marco-Sola","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences , Barcelona Supercomputing Center, Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]},{"given":"Onur","family":"Mutlu","sequence":"additional","affiliation":[{"name":"Department of Information Technology and Electrical Engineering, ETH Zurich , Zurich 8006,","place":["Switzerland"]}]},{"given":"Miquel","family":"Moreto","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences , Barcelona Supercomputing Center, Barcelona 08034,","place":["Spain"]},{"name":"Departament d\u2019Arquitectura de Computadors, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]}],"member":"286","published-online":{"date-parts":[[2024,10,21]]},"reference":[{"key":"2024112005461048700_btae631-B1","doi-asserted-by":"crossref","first-page":"63782","DOI":"10.1109\/ACCESS.2022.3182714","article-title":"Accelerating edit-distance sequence alignment on GPU using the wavefront algorithm","volume":"10","author":"Aguado-Puig","year":"2022","journal-title":"IEEE Access"},{"key":"2024112005461048700_btae631-B2","doi-asserted-by":"crossref","first-page":"btad701","DOI":"10.1093\/bioinformatics\/btad701","article-title":"Wfa-gpu: gap-affine pairwise read-alignment using gpus","volume":"39","author":"Aguado-Puig","year":"2023","journal-title":"Bioinformatics"},{"key":"2024112005461048700_btae631-B3","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1186\/s13059-021-02443-7","article-title":"Technology dictates algorithms: recent developments in read alignment","volume":"22","author":"Alser","year":"2021","journal-title":"Genome Biol"},{"key":"2024112005461048700_btae631-B4","doi-asserted-by":"crossref","first-page":"4579","DOI":"10.1016\/j.csbj.2022.08.019","article-title":"From molecules to genomic variations: accelerating genome analysis via intelligent algorithms and architectures","volume":"20","author":"Alser","year":"2022","journal-title":"Comput Struct Biotechnol J"},{"key":"2024112005461048700_btae631-B5","first-page":"80","author":"Balhaf","year":"2016"},{"key":"2024112005461048700_btae631-B6","doi-asserted-by":"crossref","first-page":"1613","DOI":"10.1161\/CIRCRESAHA.113.300939","article-title":"Overview of high throughput sequencing technologies to elucidate molecular pathways in cardiovascular diseases","volume":"112","author":"Churko","year":"2013","journal-title":"Circ Res"},{"key":"2024112005461048700_btae631-B7","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1186\/s12859-016-0930-z","article-title":"Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments","volume":"17","author":"Daily","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2024112005461048700_btae631-B8","doi-asserted-by":"crossref","first-page":"btad155","DOI":"10.1093\/bioinformatics\/btad155","article-title":"A framework for high-throughput sequence alignment using real processing-in-memory systems","volume":"39","author":"Diab","year":"2023","journal-title":"Bioinformatics"},{"key":"2024112005461048700_btae631-B9","first-page":"150","author":"Gerometta","year":"2023"},{"key":"2024112005461048700_btae631-B10","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1147\/JRD.2019.2934048","article-title":"Processing-in-memory: a workload-driven perspective","volume":"63","author":"Ghose","year":"2019","journal-title":"IBM J Res Dev"},{"key":"2024112005461048700_btae631-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3508041","article-title":"Sparsep: towards efficient sparse matrix vector multiplication on real processing-in-memory architectures","volume":"6","author":"Giannoula","year":"2022","journal-title":"Proc ACM Meas Anal Comput Syst"},{"key":"2024112005461048700_btae631-B12","first-page":"1","author":"G\u00f3mez-Luna","year":"2021"},{"key":"2024112005461048700_btae631-B13","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J Mol Biol"},{"key":"2024112005461048700_btae631-B14","doi-asserted-by":"crossref","first-page":"52565","DOI":"10.1109\/ACCESS.2022.3174101","article-title":"Benchmarking a new paradigm: experimental analysis and characterization of a real processing-in-memory system","volume":"10","author":"G\u00f3mez-Luna","year":"2022","journal-title":"IEEE Access"},{"key":"2024112005461048700_btae631-B15","first-page":"151","author":"Haghi","year":"2021"},{"key":"2024112005461048700_btae631-B16","first-page":"151","author":"Haghi","year":"2021"},{"key":"2024112005461048700_btae631-B17","first-page":"392","author":"Haghi","year":"2023"},{"key":"2024112005461048700_btae631-B18","author":"Hajinazar","year":"2021"},{"key":"2024112005461048700_btae631-B19","author":"Intel","year":"2019"},{"key":"2024112005461048700_btae631-B20","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1109\/T-C.1969.222754","article-title":"Cellular logic-in-memory arrays","volume":"C-18","author":"Kautz","year":"1969","journal-title":"IEEE Trans Comput"},{"key":"2024112005461048700_btae631-B21","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1109\/MM.2021.3097700","article-title":"Near-memory processing in action: accelerating personalized recommendation with axdimm","volume":"42","author":"Ke","year":"2021","journal-title":"IEEE Micro"},{"key":"2024112005461048700_btae631-B22","first-page":"350","author":"Kwon","year":"2021"},{"key":"2024112005461048700_btae631-B23","first-page":"43","author":"Lee","year":"2021"},{"key":"2024112005461048700_btae631-B24","first-page":"1","author":"Lee","year":"2022"},{"key":"2024112005461048700_btae631-B25","author":"Luo","year":"2024"},{"key":"2024112005461048700_btae631-B26","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/bioinformatics\/btaa777","article-title":"Fast gap-affine pairwise alignment using the wavefront algorithm","volume":"37","author":"Marco-Sola","year":"2021","journal-title":"Bioinformatics"},{"key":"2024112005461048700_btae631-B27","doi-asserted-by":"crossref","first-page":"btad074","DOI":"10.1093\/bioinformatics\/btad074","article-title":"Optimal gap-affine alignment in O(s) space","volume":"39","author":"Marco-Sola","year":"2023","journal-title":"Bioinformatics"},{"key":"2024112005461048700_btae631-B28","first-page":"1","author":"Mutlu","year":"2019"},{"key":"2024112005461048700_btae631-B29","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.micpro.2019.01.009","article-title":"Processing data where it makes sense: enabling in-memory computation","volume":"67","author":"Mutlu","year":"2019","journal-title":"Microprocess Microsyst"},{"key":"2024112005461048700_btae631-B30","first-page":"171","volume-title":"Emerging Computing: From Devices to Systems: Looking Beyond Moore and Von Neumann","author":"Mutlu","year":"2022"},{"key":"2024112005461048700_btae631-B31","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J Mol Biol"},{"key":"2024112005461048700_btae631-B32","author":"NIST","year":"2023"},{"key":"2024112005461048700_btae631-B33","author":"Niu","year":"2022"},{"key":"2024112005461048700_btae631-B34","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1016\/j.molcel.2015.05.004","article-title":"High-throughput sequencing technologies","volume":"58","author":"Reuter","year":"2015","journal-title":"Mol Cell"},{"key":"2024112005461048700_btae631-B35","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/j.jmoldx.2017.11.003","article-title":"Standards and guidelines for validating next-generation sequencing bioinformatics pipelines: a joint recommendation of the association for molecular pathology and the college of American pathologists","volume":"20","author":"Roy","year":"2018","journal-title":"J Mol Diagn"},{"key":"2024112005461048700_btae631-B36","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1038\/nbt1008-1113","article-title":"How to get genomes at one ten-thousandth the cost","volume":"26","author":"Schloss","year":"2008","journal-title":"Nat Biotechnol"},{"key":"2024112005461048700_btae631-B37","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TC.1970.5008902","article-title":"A logic-in-memory computer","volume":"C-19","author":"Stone","year":"1970","journal-title":"IEEE Trans Comput"},{"key":"2024112005461048700_btae631-B38","author":"UPMEM","year":"2024"},{"key":"2024112005461048700_btae631-B39","first-page":"314","author":"Vasimuddin","year":"2019"},{"key":"2024112005461048700_btae631-B40","first-page":"91","author":"Walia","year":"2024"},{"key":"2024112005461048700_btae631-B41","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","article-title":"Some biological sequence metrics","volume":"20","author":"Waterman","year":"1976","journal-title":"Adv Math"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae631\/59933646\/btae631.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/11\/btae631\/60752218\/btae631.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/11\/btae631\/60752218\/btae631.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T00:46:37Z","timestamp":1732063597000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae631\/7829141"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024,10,21]]},"references-count":41,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae631","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.05.10.593513","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,11]]},"published":{"date-parts":[[2024,10,21]]},"article-number":"btae631"}}