English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  q-gram Based Database Searching Using a Suffix Array (QUASAR)

Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H.-P., Rivals, E., & Vingron, M. (1999). q-gram Based Database Searching Using a Suffix Array (QUASAR). In S. Istrail, P. Pevzner, & M. Waterman (Eds.), Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99) (pp. 77-83). New York, USA: ACM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3606-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3607-5
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Burkhardt, Stefan1, Author           
Crauser, Andreas1, Author           
Ferragina, Paolo1, Author           
Lenhof, Hans-Peter1, Author           
Rivals, Eric1, Author           
Vingron, Martin, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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).

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021999
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518074
Other: Local-ID: C1256428004B93B8-5611988C44151F5CC12568B200520F68-Burkhardt1999/1
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Lyon, France
Start-/End Date: 1999

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB-99)
Source Genre: Proceedings
 Creator(s):
Istrail, Sorin, Editor
Pevzner, Pavel, Editor
Waterman, Michael, Editor
Affiliations:
-
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 77 - 83 Identifier: ISBN: 1-58113-069-4