MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Burkhardt, Stefan
Crauser, Andreas
Ferragina, Paolo
Lenhof, Hans-Peter
Rivals, Eric
Vingron, Martin		dblp
dblp
dblp
dblp
dblp
dblp
Editor(s):
Istrail, Sorin
Pevzner, Pavel
Waterman, Michael		dblp
dblp
dblp
BibTeX cite key*:
Burkhardt1999/1
Title, Booktitle
Title*:
q-gram Based Database Searching Using a Suffix Array (QUASAR)
Booktitle*:
Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Lyon, France
Language:
English
Event Date*
(no longer used):
April 11-14
Organization:
Association of Computing Machinery (ACM)
Event Start Date:
25 September 2023
Event End Date:
25 September 2023
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
April
Pages:
77-83
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
1-58113-069-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 With the increasing amount of DNA sequence information deposited in
our databases searching for similarity to a query sequence
has become a basic operation in molecular biology.
But even todays fast algorithms reach their limits when
applied to all-versus-all comparisons of large databases.
Here we present a new data base searching
algorithm dubbed QUASAR (Q-gram Alignment based on Suffix ARrays)
which was designed to quickly detect sequences with strong
similarity to the query in a context where many searches are
conducted on one database. Our algorithm applies a modification of
$q$-tuple filtering implemented on top of a suffix array. Two
versions were developed, one for a RAM resident suffix array and one
for access to the suffix array on disk. We compared our implementation
with BLAST and found that our approach is an order of magnitude faster.
It is, however, restricted to the search for strongly similar DNA
sequences as is typically required, e.g., in the context of clustering
expressed sequence tags (ESTs).
Keywords:
approximate string matching, suffix array, QUASAR, Computational Biology
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~stburk/research.html
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Burkhardt1999/1,
AUTHOR = {Burkhardt, Stefan and Crauser, Andreas and Ferragina, Paolo and Lenhof, Hans-Peter and Rivals, Eric and Vingron, Martin},
 EDITOR = {Istrail, Sorin and Pevzner, Pavel and Waterman, Michael},
 TITLE = {q-gram Based Database Searching Using a Suffix Array (QUASAR)},
 BOOKTITLE = {Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99)},
 PUBLISHER = {ACM},
 YEAR = {1999},
 ORGANIZATION = {Association of Computing Machinery (ACM)},
 PAGES = {77--83},
 ADDRESS = {Lyon, France},
 MONTH = {April},
 ISBN = {1-58113-069-4},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Stefan Burkhardt		Created
03/30/2000 16:56:18
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Anja Becker
Stefan Burkhardt
Stefan Burkhardt
Edit Dates
04.04.2000 12:04:15
30.03.2000 17:25:31
30/03/2000 17:05:48
30/03/2000 16:56:19