Parallel strategies for local biological sequence alignment in a cluster of workstations

Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods used are based on heuristics, which are faster but there are no guarantees that the best alignments are produced. On the other hand, the algorithm proposed by Smith-Waterman obtains the best...

Full description

Saved in:
Bibliographic Details
Main Authors: Boukerche, A., de Melo, A.C.M.A., Ayala-Rincon, M.
Format: Conference Proceeding
Language:English
Subjects:
Bioinformatics
Clustering algorithms
Computer science
Concurrent computing
Genomics
Hardware
Laboratories
Mathematics
Sequences
Workstations
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page 8 pp.
container_title
container_volume
creator Boukerche, A.
de Melo, A.C.M.A.
Ayala-Rincon, M.
description Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods used are based on heuristics, which are faster but there are no guarantees that the best alignments are produced. On the other hand, the algorithm proposed by Smith-Waterman obtains the best local alignments at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments with three strategies to run the Smith-Waterman algorithm in a cluster of workstations using a distributed shared memory system. Our results on an eight-machine cluster presented very good speedups and indicate that impressive improvements can be achieved, depending on the strategy used. Also, we present some theoretical remarks on how to reduce the amount of memory used.
doi_str_mv 10.1109/IPDPS.2005.329
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_1420219</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1420219</ieee_id><sourcerecordid>1420219</sourcerecordid><originalsourceid>FETCH-LOGICAL-i90t-49fc6b78947ab3e02a274af15b45cccebffecd69612c425cec497070585ce9833</originalsourceid><addsrcrecordid>eNotzMtKAzEUgOGACtbarRs3eYGpJ7fJZCn1Vig4YBfuSiaeDNF0okmK-PYquvq_1U_IBYMlY2Cu1v1N_7TkAGopuDkiC6M70K1RXDCujsmMKQENB61OyVkprwAchDQz8tzbbGPESEvNtuIYsFCfMo3J2UiHkGIawy8LfhxwckhtDOO0x6nSMFFLXTyUipkmTz9TfivV1pCmck5OvI0FF_-dk-3d7Xb10Gwe79er600TDNRGGu_aQXdGajsIBG65ltYzNUjlnMPBe3QvrWkZd5Irh04aDRpU92PTCTEnl3_bgIi79xz2Nn_tmOTAmRHfLVVSxQ</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Parallel strategies for local biological sequence alignment in a cluster of workstations</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Boukerche, A. ; de Melo, A.C.M.A. ; Ayala-Rincon, M.</creator><creatorcontrib>Boukerche, A. ; de Melo, A.C.M.A. ; Ayala-Rincon, M.</creatorcontrib><description>Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods used are based on heuristics, which are faster but there are no guarantees that the best alignments are produced. On the other hand, the algorithm proposed by Smith-Waterman obtains the best local alignments at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments with three strategies to run the Smith-Waterman algorithm in a cluster of workstations using a distributed shared memory system. Our results on an eight-machine cluster presented very good speedups and indicate that impressive improvements can be achieved, depending on the strategy used. Also, we present some theoretical remarks on how to reduce the amount of memory used.</description><identifier>ISSN: 1530-2075</identifier><identifier>ISBN: 9780769523125</identifier><identifier>ISBN: 0769523129</identifier><identifier>DOI: 10.1109/IPDPS.2005.329</identifier><language>eng</language><publisher>IEEE</publisher><subject>Bioinformatics ; Clustering algorithms ; Computer science ; Concurrent computing ; Genomics ; Hardware ; Laboratories ; Mathematics ; Sequences ; Workstations</subject><ispartof>19th IEEE International Parallel and Distributed Processing Symposium, 2005, p.8 pp.</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/1420219$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,777,781,786,787,2052,4036,4037,27906,54536,54901,54913</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1420219$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Boukerche, A.</creatorcontrib><creatorcontrib>de Melo, A.C.M.A.</creatorcontrib><creatorcontrib>Ayala-Rincon, M.</creatorcontrib><title>Parallel strategies for local biological sequence alignment in a cluster of workstations</title><title>19th IEEE International Parallel and Distributed Processing Symposium</title><addtitle>IPDPS</addtitle><description>Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods used are based on heuristics, which are faster but there are no guarantees that the best alignments are produced. On the other hand, the algorithm proposed by Smith-Waterman obtains the best local alignments at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments with three strategies to run the Smith-Waterman algorithm in a cluster of workstations using a distributed shared memory system. Our results on an eight-machine cluster presented very good speedups and indicate that impressive improvements can be achieved, depending on the strategy used. Also, we present some theoretical remarks on how to reduce the amount of memory used.</description><subject>Bioinformatics</subject><subject>Clustering algorithms</subject><subject>Computer science</subject><subject>Concurrent computing</subject><subject>Genomics</subject><subject>Hardware</subject><subject>Laboratories</subject><subject>Mathematics</subject><subject>Sequences</subject><subject>Workstations</subject><issn>1530-2075</issn><isbn>9780769523125</isbn><isbn>0769523129</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2005</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotzMtKAzEUgOGACtbarRs3eYGpJ7fJZCn1Vig4YBfuSiaeDNF0okmK-PYquvq_1U_IBYMlY2Cu1v1N_7TkAGopuDkiC6M70K1RXDCujsmMKQENB61OyVkprwAchDQz8tzbbGPESEvNtuIYsFCfMo3J2UiHkGIawy8LfhxwckhtDOO0x6nSMFFLXTyUipkmTz9TfivV1pCmck5OvI0FF_-dk-3d7Xb10Gwe79er600TDNRGGu_aQXdGajsIBG65ltYzNUjlnMPBe3QvrWkZd5Irh04aDRpU92PTCTEnl3_bgIi79xz2Nn_tmOTAmRHfLVVSxQ</recordid><startdate>2005</startdate><enddate>2005</enddate><creator>Boukerche, A.</creator><creator>de Melo, A.C.M.A.</creator><creator>Ayala-Rincon, M.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>2005</creationdate><title>Parallel strategies for local biological sequence alignment in a cluster of workstations</title><author>Boukerche, A. ; de Melo, A.C.M.A. ; Ayala-Rincon, M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i90t-49fc6b78947ab3e02a274af15b45cccebffecd69612c425cec497070585ce9833</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Bioinformatics</topic><topic>Clustering algorithms</topic><topic>Computer science</topic><topic>Concurrent computing</topic><topic>Genomics</topic><topic>Hardware</topic><topic>Laboratories</topic><topic>Mathematics</topic><topic>Sequences</topic><topic>Workstations</topic><toplevel>online_resources</toplevel><creatorcontrib>Boukerche, A.</creatorcontrib><creatorcontrib>de Melo, A.C.M.A.</creatorcontrib><creatorcontrib>Ayala-Rincon, M.</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/IET Electronic Library</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>Boukerche, A.</au><au>de Melo, A.C.M.A.</au><au>Ayala-Rincon, M.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Parallel strategies for local biological sequence alignment in a cluster of workstations</atitle><btitle>19th IEEE International Parallel and Distributed Processing Symposium</btitle><stitle>IPDPS</stitle><date>2005</date><risdate>2005</risdate><spage>8 pp.</spage><pages>8 pp.-</pages><issn>1530-2075</issn><isbn>9780769523125</isbn><isbn>0769523129</isbn><abstract>Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods used are based on heuristics, which are faster but there are no guarantees that the best alignments are produced. On the other hand, the algorithm proposed by Smith-Waterman obtains the best local alignments at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments with three strategies to run the Smith-Waterman algorithm in a cluster of workstations using a distributed shared memory system. Our results on an eight-machine cluster presented very good speedups and indicate that impressive improvements can be achieved, depending on the strategy used. Also, we present some theoretical remarks on how to reduce the amount of memory used.</abstract><pub>IEEE</pub><doi>10.1109/IPDPS.2005.329</doi></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1530-2075
ispartof 19th IEEE International Parallel and Distributed Processing Symposium, 2005, p.8 pp.
issn 1530-2075
language eng
recordid cdi_ieee_primary_1420219
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Bioinformatics
Clustering algorithms
Computer science
Concurrent computing
Genomics
Hardware
Laboratories
Mathematics
Sequences
Workstations
title Parallel strategies for local biological sequence alignment in a cluster of workstations
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-19T15%3A12%3A24IST&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=Parallel%20strategies%20for%20local%20biological%20sequence%20alignment%20in%20a%20cluster%20of%20workstations&rft.btitle=19th%20IEEE%20International%20Parallel%20and%20Distributed%20Processing%20Symposium&rft.au=Boukerche,%20A.&rft.date=2005&rft.spage=8%20pp.&rft.pages=8%20pp.-&rft.issn=1530-2075&rft.isbn=9780769523125&rft.isbn_list=0769523129&rft_id=info:doi/10.1109/IPDPS.2005.329&rft_dat=%3Cieee_6IE%3E1420219%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i90t-49fc6b78947ab3e02a274af15b45cccebffecd69612c425cec497070585ce9833%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=1420219&rfr_iscdi=true