http://dl.gi.de/handle/20.500.12116/28649 2026-07-21T13:37:50Z 2026-07-21T13:37:50Z Beckstette, Michael Strothmann, Dirk Homann, Romann Giegerich, Robert Kurtz, Stefan http://dl.gi.de/handle/20.500.12116/28676 2019-10-11T11:32:41Z 2004-01-01T00:00:00Z

PoSSuMsearch: Fast and sensitive matching of position specific scoring matrices using enhanced suffix arrays Beckstette, Michael; Strothmann, Dirk; Homann, Romann; Giegerich, Robert; Kurtz, Stefan Giegerich, Robert; Stoye, Jens In 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.

2004-01-01T00:00:00Z Täubig, Hanjo Buchner, Arno Griebsch, Jan http://dl.gi.de/handle/20.500.12116/28677 2019-10-11T11:32:41Z 2004-01-01T00:00:00Z

A method for fast approximate searching of polypeptide structures in the PDB Täubig, Hanjo; Buchner, Arno; Griebsch, Jan Giegerich, Robert; Stoye, Jens The main contribution of this paper is a novel approach for fast searching in huge structural databases like the PDB. The data structure is based on an adaption of the generalized suffix tree and relies on an translationand rotation-invariant representation of the protein backbone. The method was evaluated by applying structural queries to the PDB and comparing the results to the established tool SPASM. Our experiments show that the new method reduces the query time by orders of magnitude while producing comparable results.

2004-01-01T00:00:00Z Isermann, Nicole Weitzel, Michael Wiechert, Wolfgang http://dl.gi.de/handle/20.500.12116/28678 2019-10-11T11:32:41Z 2004-01-01T00:00:00Z

Kleene's theorem and the solution of metabolic carbon labeling systems Isermann, Nicole; Weitzel, Michael; Wiechert, Wolfgang Giegerich, Robert; Stoye, Jens Carbon Labeling Systems (CLS) are large equation systems that describe the dynamics of labeled carbon atoms in a metabolic network. The rapid solution of these systems is the algorithmic backbone of 13C Metabolic Flux Analysis (MFA) which has become one of the most widely used tools in Metabolic Engineering. A new algorithm is presented for the solution of CLS which is not based on iteration schemes or numerical linear algebra methods but on path tracing of labeled particles. It is shown that the set of all paths from the system input to the internal network nodes directly gives the clue to an explicit solution of CLS. The promising potential of this new solution algorithm are outlined.

2004-01-01T00:00:00Z Pudimat, Rainer Schukat-Talamazzini, Ernst-Günter Backofen, Rolf http://dl.gi.de/handle/20.500.12116/28675 2019-10-11T11:32:41Z 2004-01-01T00:00:00Z

Feature based representation and detection of transcription factor binding sites Pudimat, Rainer; Schukat-Talamazzini, Ernst-Günter; Backofen, Rolf Giegerich, Robert; Stoye, Jens The prediction of transcription factor binding sites is an important problem, since it reveals information about the transcriptional regulation of genes. A commonly used representation of these sites are position specific weight matrices which show weak predictive power. We introduce a feature-based modelling approach, which is able to deal with various kind of biological properties of binding sites and models them via Bayesian belief networks. The presented results imply higher model accuracy in contrast to the PSSM approach.

2004-01-01T00:00:00Z