Logo des Repositoriums
 

PoSSuMsearch: Fast and sensitive matching of position specific scoring matrices using enhanced suffix arrays

Kurzanzeige
dc.contributor.authorBeckstette, Michael
dc.contributor.authorStrothmann, Dirk
dc.contributor.authorHomann, Romann
dc.contributor.authorGiegerich, Robert
dc.contributor.authorKurtz, Stefan
dc.contributor.editorGiegerich, Robert
dc.contributor.editorStoye, Jens
dc.date.accessioned2019-10-11T11:32:41Z
dc.date.available2019-10-11T11:32:41Z
dc.date.issued2004
dc.description.abstractIn biological sequence analysis, position specific scoring matrices (PSSMs) are widely used to represent sequence motifs. In this paper, we present a new nonheuristic algorithm, called ESAsearch, to efficiently find matches of such matrices in large databases. Our approach preprocesses the search space, e.g. a complete genome or a set of protein sequences, and builds an enhanced suffix array which is stored on file. The enhanced suffix array only requires 9 bytes per input symbol, and allows to search a database with a PSSM in sublinear expected time. We also address the problem of non-comparable PSSM-scores by developing a method which allows to efficiently compute a matrix similarity threshold for a PSSM, given an E-value or a p-value. Our method is based on dynamic programming. In contrast to other methods it employs lazy evaluation of the dynamic programming matrix: it only evaluates those matrix entries that are necessary to derive the sought similarity threshold. We tested algorithm ESAsearch with nucleotide PSSMs and with amino acid PSSMs. Compared to the best previous methods, ESAsearch show speedups of a factor between 4 and 50 for nucleotide PSSMs, and speedups up to a factor 1.8 for amino acid PSSMs. Comparisons with the most widely used programs even show speedups by a factor of at least 10. The lazy evaluation method is also much faster than previous methods, with speedups by a factor of at least 10.en
dc.identifier.isbn3-88579-382-2
dc.identifier.pissn1617-5468
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/28676
dc.language.isoen
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofGerman Conference on Bioinformatics 2004, GCB 2004
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-53
dc.titlePoSSuMsearch: Fast and sensitive matching of position specific scoring matrices using enhanced suffix arraysen
dc.typeText/Conference Paper
gi.citation.endPage64
gi.citation.publisherPlaceBonn
gi.citation.startPage53
gi.conference.dateOctober 4-6, 2004
gi.conference.locationBielefeld
gi.conference.sessiontitleRegular Research Papers

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
GI-Proceedings.53-7.pdf
Größe:
338.98 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

P053 - GCB 2004 - German Conference on Bioinformatics