Phylogenetic Comparative Assembly, Peter Husemann, Jens Stoye
Background: Recent high throughput sequencing technologies are capable of generating a huge amount of data for bacterial genome sequencing projects. Although current sequence assemblers successfully...
Phylogenetic comparative assembly (2010)
Abstract Background Recent high throughput sequencing technologies are capable of generating a huge amount of data for bacterial genome sequencing projects. Although current sequence assemblers...
r2cat: synteny plots and comparative assembly (2010)
Summary: Recent parallel pyrosequencing methods and the increasing number of finished genomes encourage the sequencing and investigation of closely related strains. Although the sequencing itself...
Gerlach, Wolfgang, Jünemann, Sebastian, Tille, Felix, Goesmann, Alexander, Stoye, Jens
Abstract Background Metagenomics is a new field of research on natural microbial communities. High-throughput sequencing techniques like 454 or Solexa-Illumina promise new possibilities as they are...
the Identification of Conserved (2009)
Jomuna Veronica Choudhuri, M. Sc. Jomuna, Veronica Choudhuri, Ag Praktische Informatik, Technische Fakultät, Universität Bielefeld, ...
I would like to express my gratitude to my two supervisors, Prof. Dr. Robert Giegerich and Dr. Thomas Schmitt-John, for their careful guidance in these years, for their keen sense of timing and,...
Technische Fakultät, Abteilung Informationstechnik, Jomuna V. Choudhuri, Chris Schleiermacher, Impressum Herausgeber, Robert Giegerich, ...
GenAlyzer:
Constantin Bannert, Martin Vingron, Jens Stoye, Hannes Luz, Sebastian Böcker
These lecture notes are the result of a collaborative effort of many people. They result from a series of lectures given by Martin Vingron (MPI/FU Berlin) and Jens Stoye (Bielefeld University) and a...
ChromA: signal-based retention time alignment for chromatography-mass spectrometry data (2009)
Summary: We describe ChromA, a web-based alignment tool for chromatography–mass spectrometry data from the metabolomics and proteomics domains. Users can supply their data in open and standardized...
A report on the 2009 SIG on short read sequencing and algorithms (Short-SIG) (2009)
Brudno, Michael, Medvedev, Paul, Stoye, Jens, De La Vega, Francisco M.
Finding Nested Common Intervals Efficiently (2009)
Blin, Guillaume, Faye, David, Stoye, Jens
In this paper, we study the problem of efficiently finding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering...
Finding Nested Common Intervals Efficiently (2009)
Blin, Guillaume, Faye, David, Stoye, Jens
In this paper, we study the problem of efficiently finding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering...
Finding Nested Common Intervals Efficiently (2009)
Blin, Guillaume, Faye, David, Stoye, Jens
In this paper, we study the problem of efficiently finding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering...
Finding Nested Common Intervals Efficiently (2009)
Blin, Guillaume, Faye, David, Stoye, Jens
In this paper, we study the problem of efficiently finding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering...
Im Fach Naturwissenschaftliche Informatik, Wolfgang Gerlach, Betreuer Dipl. -inform, Klaus-bernd Schürmann, Dr. Veli Mäkinen, Prof Dr, ...
Character sets of strings (2008)
Gilles Didier, Thomas Schmidt, Jens Stoye, Dekel Tsur
Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S ′ of S is the subset C ⊆ Σ of the symbols occurring in S ′. The study of the...
An incomplex algorithm for fast suffix array construction (2008)
Softw Pract Exper, Klaus-bernd Schürmann, Jens Stoye
The suffix array of a string is a permutation of all starting positions of the string’s suffixes that are lexicographically sorted. We present a practical algorithm for suffix array construction...
THE MONEY CHANGING PROBLEM REVISITED: COMPUTING THE FROBENIUS NUMBER IN TIME O(k a1) (2008)
Technische Fakultät, Abteilung Informationstechnik, Sebastian Böcker, Zsuzsanna Lipták, Impressum Herausgeber, Robert Giegerich, ...
Abstract. The Money Changing Problem is as follows: Let a1 < a2 < · · · < ak be fixed positive integers with gcd(a1,..., ak) = 1. Given some integer n, are there non-negative integers...
Suffix Tree Construction and Storage with Limited Main Memory (2008)
Technische Fakultät, Abteilung Informationstechnik, Klaus-bernd Schürmann, Jens Stoye, Impressum Herausgeber, Robert Giegerich, ...
Abstract. Suffix trees have been established as one of the most versatile index structures for unstructured string data like genomic sequences and other strings. In this work, our goal is the...
BIOINFORMATICS APPLICATIONS NOTE doi:10.1093/bioinformatics/btl007 Sequence analysis (2008)
Sequence Analysis, Michael Sammeth, Thasso Griebel, Felix Tille, Jens Stoye
Motivation: The first version of the graphical multiple sequence alignment environment QAlign was published in 2003. Heavy response from the molecular-biological user community clearly demonstrated...
Suboptimal Local Alignments across Multiple Scoring Schemes (preview (2008)
Morris Michael, Christoph Dieterich, Jens Stoye
Abstract. Sequence alignment algorithms have a long standing tradition in bioinformatics. In this paper, we formulate an extension to existing local alignment algorithms: local alignments across...
Computation of Median Gene Clusters (2008)
Sebastian Böcker, Katharina Jahn, Julia Mixtacki, Jens Stoye
Abstract. Whole genome comparison based on gene order has become a popular approach in comparative genomics. An important task in this field is the detection of gene clusters, i.e. sets of genes that...
2-Stage Fault Tolerant Interval Group Testing (2008)
Technische Fakultät, Abteilung Informationstechnik, Ferdinando Cicalese, José Augusto, Amgarten Quitzau, Impressum Herausgeber, ...
Abstract. We study the following fault tolerant variant of the interval group testing model: Given three positive integers n, p,e, determine the minimum number of questions needed to identify a...
Character sets of strings (2008)
Gilles Didier, Thomas Schmidt, Jens Stoye, Dekel Tsur
Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S ′ of S is the subset C ⊆ Σ of the symbols occurring in S ′. The study of the...
A space efficient representation for sparse de Bruijn subgraphs (2008)
Quitzau, José Augusto Amgarten, Stoye, Jens
De Bruijn graphs are structures that appear naturally in the study of strings. Therefore the rise of de Bruijn graph based sequence analysis approaches is not a surprise. The problem with de Bruijn...
Online abelian pattern matching (2008)
Ejaz, Tahir, Rahmann, Sven, Stoye, Jens
An abelian pattern describes the set of strings that comprise of the same combination of characters. Given an abelian pattern P and a text T [Epsilon] [Sigma]^n, the task is to find all occurrences...
MeltDB: a software platform for the analysis and integration of metabolomics experiment data (2008)
Neuweger, Heiko, Albaum, Stefan P., Dondrup, Michael, Persicke, Marcus, Watt, Tony, Niehaus, Karsten, ...
Motivation: The recent advances in metabolomics have created the potential to measure the levels of hundreds of metabolites which are the end products of cellular regulatory processes. The automation...
Phylogenetic classification of short environmental DNA fragments (2008)
Krause, Lutz, Diaz, Naryttza N., Goesmann, Alexander, Kelley, Scott, Nattkemper, Tim W., Rohwer, Forest, ...
Metagenomics is providing striking insights into the ecology of microbial communities. The recently developed massively parallel 454 pyrosequencing technique gives the opportunity to rapidly obtain...
Oehm, Sebastian, Gilbert, David, Tauch, Andreas, Stoye, Jens, Goesmann, Alexander
In order to understand the phenotype of any living system, it is essential to not only investigate its genes, but also the specific metabolic pathway variant of the organism of interest, ideally in...
Finding maximal pairs with bounded gap Gerth Stlting Brodal (2007)
Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
Abstract. A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them...
Statistics for Fragment Comparison - A Biologically Motivated Approach to Sequence Alignment (2007)
Sören W. Perrey, Andreas W.M. Dress, Jens Stoye
4> i=1;::;N ; =1;::;k (s i () 2 A [ f\Gammag; k; N 2 N) be a family of N multiply aligned sequences s 1 ; ::; s N of length k, whose entries come from the union A [ f\Gammag of some finite...
Sequence Database Search Alignments Using Jumping (2007)
Rainer Spang, Marc Rehmsmeier, Jens Stoye
We describe a new algorithm for amino acid sequence classification and the detection of remote homologues. The algorithm is based on the dynamic programming principle and evaluates the fit of a...
Sux Tree Construction for Large Strings Klaus-Bernd Schurmann (2007)
Freie Universitat Berlin, Jens Stoye
Our aim is the development of algorithms for the ecient construction of sux trees of very large strings. We present an algorithm that improves upon results presented by Hunt, Atkinson and Irving...
Algorithms for Finding Gene Clusters Steen Heber 1 (2007)
Abstract. Comparing gene orders in completely sequenced genomes is a standard approach to locate clusters of functionally associated genes. Often, gene orders are modeled as permutations. Given k...
Constantin Bannert, Marc Rehmsmeier, Rainer Spang, Jens Stoye
We present an algorithm for amino acid sequence classification and the detection of remote homologues. The rationale is to exploit vertical and horizontal information of a multiple alignment in a...
Daniel A Pollard, Jens Stoye, Susan E Celniker, Michael B Eisen, Open Access
© 2004 Pollard et al; licensee BioMed Central Ltd. This is an Open Access article: verbatim copying and redistribution of this article are permitted in all media for any purpose, provided this...
Mellmann, Alexander, Weniger, Thomas, Berssenbrügge, Christoph, Rothgänger, Jörg, Sammeth, Michael, Stoye, Jens, ...
Abstract Background For typing of Staphylococcus aureus , DNA sequencing of the repeat region of the protein A ( spa ) gene is a well established discriminatory method for outbreak investigations....
GISMO--gene identification using a support vector machine for ORF classification (2007)
Krause, Lutz, McHardy, Alice C., Nattkemper, Tim W., Pühler, Alfred, Stoye, Jens, Meyer, Folker
We present the novel prokaryotic gene finder GISMO, which combines searches for protein family domains with composition-based classification based on a support vector machine. GISMO is highly...
On common intervals with errors (2006)
Chauve, Cedric, Diekmann, Yoan, Heber, Steffen, Mixtacki, Julia, Rahmann, Sven, Stoye, Jens
The information that groups of genes co-occur in several genomes provides a basis for further comparative genomic analysis. The task of finding such constellations, mostly referred to as gene...
On Common Intervals with Errors (2006)
Technische Fakultät, Abteilung Informationstechnik, Cedric Chauve, Yoan Diekmann, Steffen Heber, Julia Mixtacki, ...
The information that groups of genes co-occur in several genomes provides a basis for further comparative genomic analysis. The task of finding such constellations, mostly referred to as gene...
On Common Intervals with Errors (2006)
Technische Fakultät, Abteilung Informationstechnik, Cedric Chauve, Yoan Diekmann, Steffen Heber, Julia Mixtacki, ...
The information that groups of genes co-occur in several genomes provides a basis for further comparative genomic analysis. The task of finding such constellations, mostly referred to as gene...
machine for ORF classification (2006)
Lutz Krause, Alice C. Mchardy, Tim W. Nattkemper, Alfred Pühler, Jens Stoye, Folker Meyer
GISMO—gene identification using a support vector
machine for ORF classification (2006)
Lutz Krause, Alice C. Mchardy, Tim W. Nattkemper, Alfred Pühler, Jens Stoye, Folker Meyer
GISMO—gene identification using a support vector
A unifying view of genome rearrangements (2006)
Anne Bergeron, Julia Mixtacki, Jens Stoye, Technische Fakultät, Universität Bielefeld
Abstract. Genome rearrangements have been modeled by a variety of operations such as inversions, translocations, fissions, fusions, transpositions and block interchanges. The double cut and join...
Panta rhei (QAlign2): an open graphical environment for sequence analysis (2006)
Sammeth, Michael, Griebel, Thasso, Tille, Felix, Stoye, Jens
Motivation: The first version of the graphical multiple sequence alignment environment QAlign was published in 2003. Heavy response from the molecular-biological user community clearly demonstrated...
GISMO--gene identification using a support vector machine for ORF classification (2006)
Krause, Lutz, McHardy, Alice C., Nattkemper, Tim W., Pühler, Alfred, Stoye, Jens, Meyer, Folker
We present the novel prokaryotic gene finder GISMO, which combines searches for protein family domains with composition-based classification based on a support vector machine. GISMO is highly...
Finding novel genes in bacterial communities isolated from the environment (2006)
Krause, Lutz, Diaz, Naryttza N., Bartels, Daniela, Edwards, Robert A., Pühler, Alfred, Rohwer, Forest, ...
Motivation: Novel sequencing techniques can give access to organisms that are difficult to cultivate using conventional methods. When applied to environmental samples, the data generated has some...
Panta rhei (QAlign2): an open graphical environment for sequence analysis (2006)
Sammeth, Michael, Griebel, Thasso, Tille, Felix, Stoye, Jens
Motivation: The first version of the graphical multiple sequence alignment environment QAlign has been published in 2003. Heavy response from the molecular-biological user community clearly...
Panta rhei (QAlign2): an open graphical environment for sequence analysis (2006)
Sammeth, Michael, Griebel, Thasso, Tille, Felix, Stoye, Jens
Motivation: The first version of the graphical multiple sequence alignment environment QAlign has been published in 2003. Heavy response from the molecular-biological user community clearly...
Panta rhei (QAlign2): an open graphical environment for sequence analysis (2006)
Sammeth, Michael, Griebel, Thasso, Tille, Felix, Stoye, Jens
Motivation: The first version of the graphical multiple sequence alignment environment QAlign has been published in 2003. Heavy response from the molecular-biological user community clearly...
GISMO--gene identification using a support vector machine for ORF classification (2006)
Krause, Lutz, McHardy, Alice C., Nattkemper, Tim W., Pühler, Alfred, Stoye, Jens, Meyer, Folker
We present the novel prokaryotic gene finder GISMO, which combines searches for protein family domains with composition-based classification based on a support vector machine. GISMO is highly...
A unifying view of genome rearrangements (2006)
Anne Bergeron, Julia Mixtacki, Jens Stoye
Abstract. Genome rearrangements have been modeled by a variety of operations such as inversions, translocations, fissions, fusions, transpositions and block interchanges. The double cut and join...
Large scale hierarchical clustering of protein sequences (2005)
Krause, Antje, Stoye, Jens, Vingron, Martin
Abstract Background Searching a biological sequence database with a query sequence looking for homologues has become a routine operation in computational biology. In spite of the high degree of...
Large Scale Hierarchical Clustering of Protein Sequences (2005)
Krause,Antje, Stoye,Jens, Vingron,Martin
Background Searching a biological sequence database with a query sequence looking for homologues has become a routine operation in computational biology. In spite of the high degree of sophistication...
Counting suffix arrays and strings (2005)
Schürmann, Klaus-Bernd, Stoye, Jens
Suffix arrays are used in various application and research areas like data compression or computational biology. In this work, our goal is to characterize the combinatorial properties of suffix...
Alignment of tandem repeats with excision, duplication, substitution and indels (EDSI) (2005)
Traditional sequence comparison by alignment applies a mutation model comprising two events, substitutions and indels (insertions or deletions) of single positions (SI). However, modern genetic...
Large Scale Hierarchical Clustering of Protein Sequences (2005)
Krause, Antje, Stoye, Jens, Vingron, Martin
Background Searching a biological sequence database with a query sequence looking for homologues has become a routine operation in computational biology. In spite of the high degree of sophistication...
Efficient q-Gram Filters for Finding All ɛ-Matches Over a Given Length (2005)
Kim R. Rasmussen, Jens Stoye, Eugene W. Myers
Abstract. Fast and exact comparison of large genomic sequences remains a challenging task in biosequence analysis. We consider the problem of finding all ɛ-matches between two sequences, i.e. all...
Antje Krause, Jens Stoye, Martin Vingron
Background: Searching a biological sequence database with a query sequence looking for homologues has become a routine operation in computational biology. In spite of the high degree of...
Counting Suffix Arrays and Strings (2005)
Technische Fakultät, Abteilung Informationstechnik, Klaus-bernd Schürmann, Jens Stoye, Impressum Herausgeber, Robert Giegerich, ...
Suffix arrays are used in various application and research areas like data compression or computational biology. In this work, our goal is to characterize the combinatorial properties of suffix...
On sorting by translocations (2005)
Anne Bergeron, Julia Mixtacki, Jens Stoye
Abstract. The study of genome rearrangements is an important tool in comparative genomics. This paper revisits the problem of sorting a multichromosomal genome by translocations, i.e. exchanges of...
Zsuzsanna Lipták, Dr. Sebastian Böcker, Dr. Sebastian Böcker, Prof Dr, Jens Stoye, For Nando
This thesis treats two problem areas in bioinformatics which can both be beneficially formalized as string problems. The first (and larger) part deals with weighted string problems as they arise from...
Bartels, Daniela, Kespohl, Sebastian, Albaum, Stefan, Drüke, Tanja, Goesmann, Alexander, Herold, Julia, ...
Summary: We provide the graphical tool BACCardI for the construction of virtual clone maps from standard assembler output files or BLAST based sequence comparisons. This new tool has been applied to...
Benchmarking tools for the alignment of functional noncoding DNA (2004)
Pollard, Daniel A, Bergman, Casey M, Stoye, Jens, Celniker, Susan E, Eisen, Michael B
Abstract Background Numerous tools have been developed to align genomic sequences. However, their relative performance in specific applications remains poorly characterized. Alignments of...
Algorithmic complexity of protein identification: Combinatorics of weighted strings (2004)
Mark Cieliebak, Thomas Eriebach, Zsuzsanna Liptak, Jens Stoye, Emo Welzl
We investigate a problem from computational biology: Given a constant size alphabet M with a weight function / : M--> +, find an efficient data structure and query algorithm solving the following...
Benchmarking tools for the alignment of functional noncoding DNA (2004)
Daniel A. Pollard, Jens Stoye, E. Celniker, Michael B. Eisen, Cb Eh
* corresponding author. Background Numerous tools have been developed to align genomic sequences. However, their relative performance in specific applications remains poorly characterized. Alignments...
Technische Fakultät, Abteilung Informationstechnik, Ferdinando Cicalese, Peter Damaschke, Ugo Vaccaro, Impressum Herausgeber, ...
We consider the following constrained version of the classical Group Testing Problem: Given a finite set of items identified with the set of natural numbers 2, . . . , n} and an unknown distinguished...
Mark Cieliebak, Thomas Erlebach, Zsuzsanna Lipták, Jens Stoye, Emo Welzl
We investigate a problem which arises in computational biology: Given a constant– size alphabet A with a weight function µ: A → N, find an efficient data structure and query algorithm solving...
Reversal distance without hurdles and fortresses (2004)
Anne Bergeron, Julia Mixtacki, Jens Stoye
Abstract. This paper presents an elementary proof of the Hannenhalli-Pevzner theorem on the reversal distance of two signed permutations. It uses a single PQ-tree to encode the various features of a...
Quadratic time algorithms for finding common intervals in two and more sequences (2004)
Abstract. A popular approach in comparative genomics is to locate groups or clusters of orthologous genes in multiple genomes and to postulate functional association between the genes contained in...
BIOINFORMATICS ORIGINAL PAPER (2004)
Genome Analysis, Daniela Bartels, Sebastian Kespohl, Stefan Albaum, Tanja Drüke, Er Goesmann, ...
BACCardI—a tool for the validation of genomic assemblies, assisting genome finishing and intergenome comparison
Bartels, Daniela, Kespohl, Sebastian, Albaum, Stefan, Drüke, Tanja, Goesmann, Alexander, Herold, Julia, ...
Motivation: Genomic assemblies generated from sequence information need to be validated by independent methods such as physical maps. The time-consuming task of building physical maps can be...
Bartels, Daniela, Kespohl, Sebastian, Albaum, Stefan, Drüke, Tanja, Goesmann, Alexander, Herold, Julia, ...
Motivation: Genomic assemblies generated from sequence information need to be validated by independent methods such as physical maps. The time-consuming task of building physical maps can be...
Suffix tree construction and storage with limited main memory (2003)
Schürmann, Klaus-Bernd, Stoye, Jens
Suffix trees have been established as one of the most versatile index structures for unstructured string data like genomic sequences and other strings. In this work, our goal is the development of...
On the Similarity of Sets of Permutations and its Applications to Genome Comparison (2003)
Abteilung Informationstechnik, Impressum Herausgeber, Robert Giegerich, Ralf Hofestädt, Peter Ladkin, Helge Ritter, ...
The comparison of genomes with the same gene content relies on our ability to compare permutations, either by measuring how much they di#er, or by measuring how much they are alike. With the notable...
Michael Sammeth, Burkhard Morgenstern, Jens Stoye
Vol. 19 Suppl. 2 2003, pages ii189–ii195
Divide-and-conquer multiple alignment with segment-based constraints (2003)
Sammeth, Michael, Morgenstern, Burkhard, Stoye, Jens
A large number of methods for multiple sequence alignment are currenty available. Recent benchmarking tests demonstrated that strengths and drawbacks of these methods differ substantially. Global...
On the similarity of sets of permutations and its applications to genome comparison (2003)
The comparison of genomes with the same gene content relies on our ability to compare permutations, either by measuring how much they differ, or by measuring how much they are alike. With the notable...
A novel approach to remote homology detection: jumping alignments. (2002)
Spang,Rainer, Rehmsmeier,Marc, Stoye,Jens
We describe a new algorithm for protein classification and the detection of remote homologs. The rationale is to exploit both vertical and horizontal information of a multiple alignment in a...
A novel approach to remote homology detection: jumping alignments. (2002)
Spang, Rainer, Rehmsmeier, Marc, Stoye, Jens
We describe a new algorithm for protein classification and the detection of remote homologs. The rationale is to exploit both vertical and horizontal information of a multiple alignment in a...
A novel approach to remote homology detection: jumping alignments (2002)
Rainer Spang, Marc Rehmsmeier, Jens Stoye
We describe a new algorithm for protein classi � cation and the detection of remote homologs. The rationale is to exploit both vertical and horizontal information of a multiple alignment in a...
EIMaR: A Protein Docking System using Flexibility Information (2002)
Universitt Bielefeld, Technische Fakultt, Abteilung Informationstechnik, Frank Zöllner, Steffen Neumann, Kerstin Koch, ...
We give an overview of the ELMAR Docking System. Using a distributed modular and optionally parallel architecture results can be obtained within a few minutes. ELMAR incorporates protein flexibility...
Finding all common intervals of k permutations (2001)
1 Introduction Let \Pi = (ss1; : : : ; ssk) be a family of k permutations of N = f1; 2; : : : ; ng. A k-tuple of intervals of these permutations consisting of the same set of elements is called a...
Finding all common intervals of k permutations (2001)
Abstract. Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a...
REPuter: the manifold applications of repeat analysis on a genomic scale (2001)
Kurtz, Stefan, Choudhuri, Jomuna V., Ohlebusch, Enno, Schleiermacher, Chris, Stoye, Jens, Giegerich, Robert
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
Sequence database search using jumping alignments (2000)
Rainer Spang, Marc Rehmsmeier, Jens Stoye
We describe a new algorithm for amino acid sequence classi cation and the detection of remote homologues. The rationale is to exploit both vertical and horizontal information of a multiple alignment...
Computation and visualization of degenerate repeats in complete genomes (2000)
Stefan Kurtz, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, Robert Giegerich
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
Sequence database search using jumping alignments (2000)
Rainer Spang, Marc Rehmsmeier, Jens Stoye
We describe a new algorithm for amino acid sequence classi cation and the detection of remote homologues. The algorithm is based on the dynamic programming principle and evaluates the t of a...
Computation and Visualization of Degenerate Repeats in Complete Genomes (2000)
Stefan Kurtz, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, Robert Giegerich
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
Computation and Visualization of Degenerate Repeats in Complete Genomes (2000)
Stefan Kurtz, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, Robert Giegerich
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
An iterative method for faster sum-of-pairs multiple sequence alignment (2000)
Reinert, Knut, Stoye, Jens, Will, Torsten
Motivation: Multiple sequence alignment is an important tool in computational biology. In order to solve the task of computing multiple alignments in affordable time, the most commonly used multiple...
Finding maximal pairs with bounded gap (1999)
Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, Jens Stoye
Finding maximal pairs with bounded gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Finding maximal pairs with bounded gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Consistent Equivalence Relations: a Set-Theoretical Framework for Multiple Sequence Alignment (1999)
Burkhard Morgenstern, Jens Stoye, Andreas Dress, Essex Rm Xs
Recently, Morgenstern et al. have proposed a new mathematical definition of sequence alignment (Morgenstern et al.,1996). In this paper, we discuss this definition in more detail. We demonstrate that...
Finding Maximal Pairs with Bounded Gap (1999)
Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them different. The...
Finding maximal pairs with bounded gap (1999)
Gerth Sto/lting Brodal, Rune B. Lyngso, Christian N. S. Pedersen, Jens Stoye
1 Introduction A pair in a string is the occurrence of the same substring twice. A pair is leftmaximal (right-maximal) if the characters to the immediate left (right) of the two occurrences of the...
Efficient Implementation of Lazy Suffix Trees (1999)
Robert Giegerich, Stefan Kurtz, Jens Stoye
Abstract. We present an efficient implementation of a write-only topdown construction for suffix trees. Our implementation is based on a new, space-efficient representation of suffix trees which...
Sorting Leaf-Lists in a Tree (1998)
Christian N. S. Pedersen, Jens Stoye
Introduction Let T be a rooted tree of size n with leaves labelled with distinct elements from an ordered set. We describe a simple method to obtain the sorted leaf-lists of all nodes one at a time...
Linear Time Algorithms for Finding and Representing all Tandem Repeats in a String (1998)
Dan Gusfield, Dan Gusfield, Jens Stoye, Jens Stoye
A tandem repeat (or square) is a string ffff, where ff is a nonempty string. We present an O(jSj)-time algorithm that operates on the suffix tree T (S) for a string S, finding and marking the...
Linear Time Algorithms for Finding and Representing all the Tandem Repeats in a String (1998)
A tandem repeat (or square) is a string aa; where a is a non-empty string. We present an OðjSjÞ-time algorithm that operates on the suffix tree TðSÞ for a string S; finding and marking the...
Generating Benchmarks for Multiple Sequence Alignments and Phylogenetic Reconstructions (1997)
Phylogenetic Reconstructions, Jens Stoye, Dirk Evers, Folker Meyer, Technische Fakultat
We present a new probabilistic model of evolution of RNA-, DNA-, or protein-like sequences and a tool rose that implements this model. By insertion, deletion and substitution of characters, a family...
Rose: Generating Sequence Families (1997)
Forschungsbericht Der, Abteilung Informationstechnik, Jens Stoye, Dirk Evers, Folker Meyer, Impressum Herausgeber, ...
2 2 Introduction 3 3 Systems and Methods 5 4 Algorithm 6 4.1 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.2 The Root Sequence . . . . . . . . . . . . . . . . . . . . . ....
Divide-and-Conquer Multiple Sequence Alignment (1997)
Technischen Fakultat, Abteilung Informationstechnik, Jens Stoye, Impressum Herausgeber, Robert Giegerich, Alois Knoll, ...
Contents 1 Introduction 1 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3...
Stoye, Jens, Moulton, Vincent, Dress, Andreas W.M.
Motivation: DCA is a new computer program for multiple sequence alignment which utilizes a ‘divide-and-conquer’ type of heuristic approach. Availability: The algorithm is freely available from...
A General Method for Fast Multiple Sequence Alignment (1996)
Forschungsschwerpunkt Mathematisierung, Andreas W. M. Dress, Udo Tönges, Udo Tonges, Sören W. Perrey, Soren W. Perrey, ...
We have developed a fast heuristic algorithm for multiple sequence alignment which provides near-to-optimal results for sufficiently homologous sequences. The algorithm makes use of the standard...
Fast Approximation to the NP-hard Problem of Multiple Sequence Alignment (1996)
The study and comparison of several sequences of characters from a finite alphabet is relevant to various areas of science, in particular molecular biology. It has been shown that multiple sequence...
Improving the Divide-and-Conquer Approach to Sum-of-Pairs Multiple Sequence Alignment (1996)
Forschungsschwerpunkt Mathematisierung, Jens Stoye, Jens Stoye, Andreas W.M. Dress, Andreas W. M. Dress, Sören W. Perrey, ...
We consider the problem of multiple sequence alignment: given k sequences of length at most n and a certain scoring function, find an alignment that minimizes the corresponding "sum of...
REPuter: the manifold applications of repeat analysis on a genomic scale
Kurtz, Stefan, Choudhuri, Jomuna V., Ohlebusch, Enno, Schleiermacher, Chris, Stoye, Jens, Giegerich, Robert
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
Benchmarking tools for the alignment of functional noncoding DNA
Pollard, Daniel A, Bergman, Casey M, Stoye, Jens, Celniker, Susan E, Eisen, Michael B
REPuter: the manifold applications of repeat analysis on a genomic scale
Kurtz, Stefan, Choudhuri, Jomuna V., Ohlebusch, Enno, Schleiermacher, Chris, Stoye, Jens, Giegerich, Robert
The repetitive structure of genomic DNA holds many secrets to be discovered. A systematic study of repetitive DNA on a genomic or inter-genomic scale requires extensive algorithmic support. The...
Benchmarking tools for the alignment of functional noncoding DNA
Pollard, Daniel A, Bergman, Casey M, Stoye, Jens, Celniker, Susan E, Eisen, Michael B
GISMO—gene identification using a support vector machine for ORF classification
Krause, Lutz, McHardy, Alice C., Nattkemper, Tim W., Pühler, Alfred, Stoye, Jens, Meyer, Folker
We present the novel prokaryotic gene finder GISMO, which combines searches for protein family domains with composition-based classification based on a support vector machine. GISMO is highly...
Mellmann, Alexander, Weniger, Thomas, Berssenbrügge, Christoph, Rothgänger, Jörg, Sammeth, Michael, Stoye, Jens, ...
Phylogenetic classification of short environmental DNA fragments
Krause, Lutz, Diaz, Naryttza N., Goesmann, Alexander, Kelley, Scott, Nattkemper, Tim W., Rohwer, Forest, ...
Metagenomics is providing striking insights into the ecology of microbial communities. The recently developed massively parallel 454 pyrosequencing technique gives the opportunity to rapidly obtain...
Oehm, Sebastian, Gilbert, David, Tauch, Andreas, Stoye, Jens, Goesmann, Alexander
In order to understand the phenotype of any living system, it is essential to not only investigate its genes, but also the specific metabolic pathway variant of the organism of interest, ideally in...
This document in subdirectoryRS/99/12/
Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, Jens Stoye, Copyright C, Gerth Stølting Brodal, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
ChromA: signal-based retention time alignment for chromatography–mass spectrometry data
Summary: We describe ChromA, a web-based alignment tool for chromatography–mass spectrometry data from the metabolomics and proteomics domains. Users can supply their data in open and standardized...
r2cat: synteny plots and comparative assembly
Summary: Recent parallel pyrosequencing methods and the increasing number of finished genomes encourage the sequencing and investigation of closely related strains. Although the sequencing itself...