A rate-based prefiltering approach to blast acceleration

DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefilter...

Full description

Saved in:
Bibliographic Details
Main Authors: Afratis, P., Sotiriades, E., Chrysos, G., Fytraki, S., Pnevmatikatos, D.
Format: Conference Proceeding
Language:English
Subjects:
Clocks
Computer architecture
Field programmable gate arrays
Hardware
Radiation detectors
Shift registers
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 634
container_issue
container_start_page 631
container_title
container_volume
creator Afratis, P.
Sotiriades, E.
Chrysos, G.
Fytraki, S.
Pnevmatikatos, D.
description DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefiltering approach offers significant reduction in the size of the database that needs to be fully processed by BLAST, with a corresponding reduction in the run-time of the algorithm. We have implemented our architecture, evaluated its effectiveness for a variety of databases and queries, and compared its accuracy against the original NCBI Blast implementation. We have found that prefiltering offers at least a factor of 5 and up to 3 orders of magnitude reduction in the database space that needs to be fully searched. Due to its prefiltering nature, our approach can be combined with all major reconfigurable acceleration architectures that have been presented up to date.
doi_str_mv 10.1109/FPL.2008.4630026
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_4630026</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4630026</ieee_id><sourcerecordid>4630026</sourcerecordid><originalsourceid>FETCH-LOGICAL-i90t-b049c093f8bef1cf09faab7d2b1051bd3ccad427bc80c3ad740c3c32b85cd26a3</originalsourceid><addsrcrecordid>eNpVkEtLw0AUhcdHwVqzF9zMH0i88-g8lqVYFQK66MJdufPSkdiESTb-ewMWwbP5FufwLQ4htwwaxsDe717bhgOYRioBwNUZqaw2THIpmVVMnZMls1LVTBpz8a8De_nX6bcFuZ412oJVGq5INY6fMEdYqaVZErOhBadYOxxjoEOJKXdTLPn4TnEYSo_-g049dR2OE0XvYxfnfe6PN2SRsBtjdeKK7HcP--1T3b48Pm83bZ0tTLUDaT1YkYyLifkENiE6HbhjsGYuCO8xSK6dN-AFBi1neMGdWfvAFYoVufvV5hjjYSj5C8v34fSJ-AEwC06c</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>A rate-based prefiltering approach to blast acceleration</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Afratis, P. ; Sotiriades, E. ; Chrysos, G. ; Fytraki, S. ; Pnevmatikatos, D.</creator><creatorcontrib>Afratis, P. ; Sotiriades, E. ; Chrysos, G. ; Fytraki, S. ; Pnevmatikatos, D.</creatorcontrib><description>DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefiltering approach offers significant reduction in the size of the database that needs to be fully processed by BLAST, with a corresponding reduction in the run-time of the algorithm. We have implemented our architecture, evaluated its effectiveness for a variety of databases and queries, and compared its accuracy against the original NCBI Blast implementation. We have found that prefiltering offers at least a factor of 5 and up to 3 orders of magnitude reduction in the database space that needs to be fully searched. Due to its prefiltering nature, our approach can be combined with all major reconfigurable acceleration architectures that have been presented up to date.</description><identifier>ISSN: 1946-147X</identifier><identifier>ISBN: 9781424419609</identifier><identifier>ISBN: 1424419603</identifier><identifier>EISSN: 1946-1488</identifier><identifier>EISBN: 9781424419616</identifier><identifier>EISBN: 1424419611</identifier><identifier>DOI: 10.1109/FPL.2008.4630026</identifier><identifier>LCCN: 2007909670</identifier><language>eng</language><publisher>IEEE</publisher><subject>Clocks ; Computer architecture ; Field programmable gate arrays ; Hardware ; Radiation detectors ; Shift registers</subject><ispartof>2008 International Conference on Field Programmable Logic and Applications, 2008, p.631-634</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4630026$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,778,782,787,788,2054,27908,54538,54903,54915</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/4630026$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Afratis, P.</creatorcontrib><creatorcontrib>Sotiriades, E.</creatorcontrib><creatorcontrib>Chrysos, G.</creatorcontrib><creatorcontrib>Fytraki, S.</creatorcontrib><creatorcontrib>Pnevmatikatos, D.</creatorcontrib><title>A rate-based prefiltering approach to blast acceleration</title><title>2008 International Conference on Field Programmable Logic and Applications</title><addtitle>FPL</addtitle><description>DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefiltering approach offers significant reduction in the size of the database that needs to be fully processed by BLAST, with a corresponding reduction in the run-time of the algorithm. We have implemented our architecture, evaluated its effectiveness for a variety of databases and queries, and compared its accuracy against the original NCBI Blast implementation. We have found that prefiltering offers at least a factor of 5 and up to 3 orders of magnitude reduction in the database space that needs to be fully searched. Due to its prefiltering nature, our approach can be combined with all major reconfigurable acceleration architectures that have been presented up to date.</description><subject>Clocks</subject><subject>Computer architecture</subject><subject>Field programmable gate arrays</subject><subject>Hardware</subject><subject>Radiation detectors</subject><subject>Shift registers</subject><issn>1946-147X</issn><issn>1946-1488</issn><isbn>9781424419609</isbn><isbn>1424419603</isbn><isbn>9781424419616</isbn><isbn>1424419611</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2008</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpVkEtLw0AUhcdHwVqzF9zMH0i88-g8lqVYFQK66MJdufPSkdiESTb-ewMWwbP5FufwLQ4htwwaxsDe717bhgOYRioBwNUZqaw2THIpmVVMnZMls1LVTBpz8a8De_nX6bcFuZ412oJVGq5INY6fMEdYqaVZErOhBadYOxxjoEOJKXdTLPn4TnEYSo_-g049dR2OE0XvYxfnfe6PN2SRsBtjdeKK7HcP--1T3b48Pm83bZ0tTLUDaT1YkYyLifkENiE6HbhjsGYuCO8xSK6dN-AFBi1neMGdWfvAFYoVufvV5hjjYSj5C8v34fSJ-AEwC06c</recordid><startdate>200809</startdate><enddate>200809</enddate><creator>Afratis, P.</creator><creator>Sotiriades, E.</creator><creator>Chrysos, G.</creator><creator>Fytraki, S.</creator><creator>Pnevmatikatos, D.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>200809</creationdate><title>A rate-based prefiltering approach to blast acceleration</title><author>Afratis, P. ; Sotiriades, E. ; Chrysos, G. ; Fytraki, S. ; Pnevmatikatos, D.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i90t-b049c093f8bef1cf09faab7d2b1051bd3ccad427bc80c3ad740c3c32b85cd26a3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2008</creationdate><topic>Clocks</topic><topic>Computer architecture</topic><topic>Field programmable gate arrays</topic><topic>Hardware</topic><topic>Radiation detectors</topic><topic>Shift registers</topic><toplevel>online_resources</toplevel><creatorcontrib>Afratis, P.</creatorcontrib><creatorcontrib>Sotiriades, E.</creatorcontrib><creatorcontrib>Chrysos, G.</creatorcontrib><creatorcontrib>Fytraki, S.</creatorcontrib><creatorcontrib>Pnevmatikatos, D.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Afratis, P.</au><au>Sotiriades, E.</au><au>Chrysos, G.</au><au>Fytraki, S.</au><au>Pnevmatikatos, D.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>A rate-based prefiltering approach to blast acceleration</atitle><btitle>2008 International Conference on Field Programmable Logic and Applications</btitle><stitle>FPL</stitle><date>2008-09</date><risdate>2008</risdate><spage>631</spage><epage>634</epage><pages>631-634</pages><issn>1946-147X</issn><eissn>1946-1488</eissn><isbn>9781424419609</isbn><isbn>1424419603</isbn><eisbn>9781424419616</eisbn><eisbn>1424419611</eisbn><abstract>DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefiltering approach offers significant reduction in the size of the database that needs to be fully processed by BLAST, with a corresponding reduction in the run-time of the algorithm. We have implemented our architecture, evaluated its effectiveness for a variety of databases and queries, and compared its accuracy against the original NCBI Blast implementation. We have found that prefiltering offers at least a factor of 5 and up to 3 orders of magnitude reduction in the database space that needs to be fully searched. Due to its prefiltering nature, our approach can be combined with all major reconfigurable acceleration architectures that have been presented up to date.</abstract><pub>IEEE</pub><doi>10.1109/FPL.2008.4630026</doi><tpages>4</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1946-147X
ispartof 2008 International Conference on Field Programmable Logic and Applications, 2008, p.631-634
issn 1946-147X
1946-1488
language eng
recordid cdi_ieee_primary_4630026
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Clocks
Computer architecture
Field programmable gate arrays
Hardware
Radiation detectors
Shift registers
title A rate-based prefiltering approach to blast acceleration
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-17T01%3A18%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=A%20rate-based%20prefiltering%20approach%20to%20blast%20acceleration&rft.btitle=2008%20International%20Conference%20on%20Field%20Programmable%20Logic%20and%20Applications&rft.au=Afratis,%20P.&rft.date=2008-09&rft.spage=631&rft.epage=634&rft.pages=631-634&rft.issn=1946-147X&rft.eissn=1946-1488&rft.isbn=9781424419609&rft.isbn_list=1424419603&rft_id=info:doi/10.1109/FPL.2008.4630026&rft.eisbn=9781424419616&rft.eisbn_list=1424419611&rft_dat=%3Cieee_6IE%3E4630026%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i90t-b049c093f8bef1cf09faab7d2b1051bd3ccad427bc80c3ad740c3c32b85cd26a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=4630026&rfr_iscdi=true