{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:23:06Z","timestamp":1772500986269,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,2,24]],"date-time":"2016-02-24T00:00:00Z","timestamp":1456272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002809","name":"Generalitat de Catalunya","doi-asserted-by":"publisher","award":["SGR1051"],"award-info":[{"award-number":["SGR1051"]}],"id":[{"id":"10.13039\/501100002809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["313931\/2013-5,305208\/2014-4,446297\/2014-3"],"award-info":[{"award-number":["313931\/2013-5,305208\/2014-4,446297\/2014-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006280","name":"Ministerio de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["TIN2012-34557"],"award-info":[{"award-number":["TIN2012-34557"]}],"id":[{"id":"10.13039\/501100006280","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Severo Ochoa Program","award":["SEV-2011-00067"],"award-info":[{"award-number":["SEV-2011-00067"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,3,15]]},"abstract":"<jats:p>Biological sequence alignment is a very popular application in Bioinformatics, used routinely worldwide. Many implementations of biological sequence alignment algorithms have been proposed for multicores, GPUs, FPGAs and CellBEs. These implementations are platform-specific; porting them to other systems requires considerable programming effort. This article proposes and evaluates MASA, a flexible and customizable software architecture that enables the execution of biological sequence alignment applications with three variants (local, global, and semiglobal) in multiple hardware\/software platforms with block pruning, which is able to reduce significantly the amount of data processed. To attain our flexibility goals, we also propose a generic version of block pruning and developed multiple parallelization strategies as building blocks, including a new asynchronous dataflow-based parallelization, which may be combined to implement efficient aligners in different platforms. We provide four MASA aligner implementations for multicores (OmpSs and OpenMP), GPU (CUDA), and Intel Phi (OpenMP), showing that MASA is very flexible. The evaluation of our generic block pruning strategy shows that it significantly outperforms the previously proposed block pruning, being able to prune up to 66.5% of the cells when using the new dataflow-based parallelization strategy.<\/jats:p>","DOI":"10.1145\/2858656","type":"journal-article","created":{"date-parts":[[2016,2,26]],"date-time":"2016-02-26T14:29:03Z","timestamp":1456496943000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["MASA"],"prefix":"10.1145","volume":"2","author":[{"given":"Edans F.","family":"De O. Sandes","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Brasilia, Brazil, CEP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillermo","family":"Miranda","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xavier","family":"Martorell","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center and Universitat Politecnica de Catalunya, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduard","family":"Ayguade","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center and Universitat Politecnica de Catalunya, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Teodoro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Brasilia, Brazil, CEP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alba C. M. A.","family":"De Melo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Brasilia, Brazil, CEP"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2010.93"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(03)00010-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/752910"},{"key":"e_1_2_1_5_1","volume-title":"IEEE Cluster Computing Conference, 38--45","author":"Chen C.","unstructured":"C. Chen and B. Schmidt . 2003. Computing large-scale alignments on a multi-cluster . IEEE Cluster Computing Conference, 38--45 . C. Chen and B. Schmidt. 2003. Computing large-scale alignments on a multi-cluster. IEEE Cluster Computing Conference, 38--45."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1217-y"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626411000151"},{"key":"e_1_2_1_8_1","unstructured":"R. Durbin S. Eddy A. Krogh and G. Mitchison. 2002. Biological Sequence Analysis. Cambridge University Press New York NY.  R. Durbin S. Eddy A. Krogh and G. Mitchison. 2002. Biological Sequence Analysis. Cambridge University Press New York NY."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl582"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(82)90398-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863482.1863494"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-012-0209-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt410"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature13200"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3371"},{"key":"e_1_2_1_17_1","volume-title":"25th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201914)","author":"Liu Y.","unstructured":"Y. Liu and B. Schmidt . 2014b. SWAPHI: Smith-Waterman protein database search on Xeon Phi coprocessors . In 25th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201914) . 184--185. Y. Liu and B. Schmidt. 2014b. SWAPHI: Smith-Waterman protein database search on Xeon Phi coprocessors. In 25th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201914). 184--185."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2009.14"},{"key":"e_1_2_1_19_1","volume-title":"IEEE International Conference on Cluster Computing\u2014CLUSTER. 257--265","author":"Liu Y.","unstructured":"Y. Liu , T. Tam , F. Lauenroth , and B. Schmidt . 2014. SWAPHI-LS: Smith-Waterman algorithm on Xeon Phi coprocessors for long DNA sequences . In IEEE International Conference on Cluster Computing\u2014CLUSTER. 257--265 . Y. Liu, T. Tam, F. Lauenroth, and B. Schmidt. 2014. SWAPHI-LS: Smith-Waterman algorithm on Xeon Phi coprocessors for long DNA sequences. In IEEE International Conference on Cluster Computing\u2014CLUSTER. 257--265."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-117"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555264"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-9-S2-S10","article-title":"CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment","volume":"9","author":"Manavski S.","year":"2008","unstructured":"S. Manavski and G. Valle . 2008 . CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment . BMC Bioinformatics 9, Suppl 2 . S. Manavski and G. Valle. 2008. CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics 9, Suppl 2.","journal-title":"BMC Bioinformatics"},{"key":"e_1_2_1_23_1","volume-title":"Bioinformatics: Sequence and Genome Analysis","author":"Mount D. W.","year":"2004","unstructured":"D. W. Mount . 2004 . Bioinformatics: Sequence and Genome Analysis . CSHL Press , Long Island, NY . D. W. Mount. 2004. Bioinformatics: Sequence and Genome Analysis. CSHL Press, Long Island, NY."},{"key":"e_1_2_1_24_1","first-page":"11","article-title":"Optimal alignments in linear space","volume":"4","author":"Myers E. W.","year":"1988","unstructured":"E. W. Myers and W. Miller . 1988 . Optimal alignments in linear space . Computer Applications in the Biosciences 4 , 1, 11 -- 17 . E. W. Myers and W. Miller. 1988. Optimal alignments in linear space. Computer Applications in the Biosciences 4, 1, 11--17.","journal-title":"Computer Applications in the Biosciences"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_26_1","unstructured":"Gregory F. Pfister. 1995. In search of Clusters: the Coming Battle in Lowly Parallel Computing. Prentice-Hall Inc. Upper Saddle NJ.   Gregory F. Pfister. 1995. In search of Clusters: the Coming Battle in Lowly Parallel Computing. Prentice-Hall Inc. Upper Saddle NJ."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.86"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-221"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"F. Sanchez F. Cabarcas A. Ramirez and M. Valero. 2010. Long DNA sequence comparison on multicore architectures. In Euro-Par 2010\u2014Parallel Processing. 247--259.   F. Sanchez F. Cabarcas A. Ramirez and M. Valero. 2010. Long DNA sequence comparison on multicore architectures. In Euro-Par 2010\u2014Parallel Processing. 247--259.","DOI":"10.1007\/978-3-642-15291-7_24"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555280"},{"key":"e_1_2_1_31_1","volume-title":"IEEE\/ACM Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201914)","author":"Sandes E. F.","unstructured":"E. F. de O. Sandes , G. Miranda , A. C. M. A. Melo , X. Martorell , and E. Ayguade . 2014b. CUDAlign 3.0: Parallel biological sequence comparison in large GPU clusters . In IEEE\/ACM Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201914) . 160--169. E. F. de O. Sandes, G. Miranda, A. C. M. A. Melo, X. Martorell, and E. Ayguade. 2014b. CUDAlign 3.0: Parallel biological sequence comparison in large GPU clusters. In IEEE\/ACM Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201914). 160--169."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.114"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.194"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.194"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.254"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.133"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"M. Scarpato R. Esposito D. Evangelista M. Aprile M. R. Ambrosio A. Ciccodicola C. Angelini and V. Costa. 2014. Analysis of expression on human chromosome 21 ALE-HSA21: A pilot integrated web resource. Database\u2014Journal of Biological Databases and Curation 2014 Article ID bau009.  M. Scarpato R. Esposito D. Evangelista M. Aprile M. R. Ambrosio A. Ciccodicola C. Angelini and V. Costa. 2014. Analysis of expression on human chromosome 21 ALE-HSA21: A pilot integrated web resource. Database\u2014Journal of Biological Databases and Curation 2014 Article ID bau009.","DOI":"10.1093\/database\/bau009"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1046192.1046222"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.245"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1128\/JB.05819-11"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1155\/2009\/615038"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2009.110"},{"key":"e_1_2_1_44_1","volume-title":"International Conference on Applied Reconfigurable Computing (ARC\u201911)","author":"Yamagutchi Y.","unstructured":"Y. Yamagutchi , H. K. Tsoi , and W. Luk . 2011. FPGA-Based Smith-Waterman algorithm: Analysis and novel design . In International Conference on Applied Reconfigurable Computing (ARC\u201911) . 181--192. Y. Yamagutchi, H. K. Tsoi, and W. Luk. 2011. FPGA-Based Smith-Waterman algorithm: Analysis and novel design. In International Conference on Applied Reconfigurable Computing (ARC\u201911). 181--192."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1038\/cr.2010.87"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2858656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:43Z","timestamp":1750225723000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858656"}},"subtitle":["A Multiplatform Architecture for Sequence Aligners with Block Pruning"],"short-title":[],"issued":{"date-parts":[[2016,2,24]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,3,15]]}},"alternative-id":["10.1145\/2858656"],"URL":"https:\/\/doi.org\/10.1145\/2858656","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,24]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}