Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


Event Address*:

Lyon, France

Language:

English

Event Date*
(no longer used):

April 11-14

Organization:

Association of Computing Machinery (ACM)

Event Start Date:

19 October 2019

Event End Date:

19 October 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 04:56:18 PM
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