Logo des Repositoriums

Auflistung nach Autor:in "Schreiber, Falk"

1 - 10 von 28
  • Konferenzbeitrag
    2D projections of RNA folding landscapes
    (German conference on bioinformatics 2009, 2009) Lorenz, Rony; Flamm, Christoph; Hofacker, Ivo L.
    The analysis of RNA folding landscapes yields insights into the kinetic folding behavior not available from classical structure prediction methods. This is especially important for multi-stable RNAs whose function is related to structural changes, as in the case of riboswitches. However, exact methods such as barrier tree analysis scale exponentially with sequence length. Here we present an algorithm that computes a projection of the energy landscape into two dimensions, namely the distances to two reference structures. This yields an abstraction of the high-dimensional energy landscape that can be conveniently visualized, and can serve as the basis for estimating energy barriers and refolding pathways. With an asymptotic time complexity of O(n7) the algorithm is computationally demanding. However, by exploiting the sparsity of the dynamic programming matrices and parallelization for multi-core processors, our implementation is practical for sequences of up to 400 nt, which includes most RNAs of biological interest.
  • Konferenzbeitrag
    Aligning protein structures using distance matrices and combinatorial optimization
    (German conference on bioinformatics 2009, 2009) Wohlers, Inken; Petzold, Lars; Domingues, Francisco S.; Klau, Gunnar W.
    Structural alignments of proteins are used to identify structural similarities. These similarities can indicate homology or a common or similar function. Several, mostly heuristic methods are available to compute structural alignments. In this paper, we present a novel algorithm that uses methods from combinatorial optimization to compute provably optimal structural alignments of sparse protein distance matrices. Our algorithm extends an elegant integer linear programming approach proposed by Caprara et al. for the alignment of protein contact maps. We consider two different types of distance matrices with distances either between Cα atoms or between the two closest atoms of each residue. Via a comprehensive parameter optimization on HOMSTRAD alignments, we determine a scoring function for aligned pairs of distances. We introduce a negative score for non-structural, purely sequence-based parts of the alignment as a means to adjust the locality of the resulting structural alignments. Our approach is implemented in a freely available software tool named PAUL (Protein structural Alignment Using Lagrangian relaxation). On the challenging SISY data set of 130 reference alignments we compare PAUL to six state-of-the-art structural alignment algorithms, DALI, MATRAS, FATCAT, SHEBA, CA, and CE. Here, PAUL reaches the highest average and median alignment accuracies of all methods and is the most accurate method for more than 30% of the alignments. PAUL is thus a competitive tool for pairwise high-quality structural alignment.
  • Textdokument
    Analyse und Aufzeigen von Zusammenhängen
    (INFORMATIK 2017, 2017) Schreiber, Falk
  • Zeitschriftenartikel
    Analyse und Visualisierung biologischer Netzwerke
    (Informatik-Spektrum: Vol. 32, No. 4, 2009) Schreiber, Falk
    Moderne Analysemethoden ermöglichen es, die elementaren Bausteine biologischer Systeme im großen Umfang zu bestimmen. Sie sind damit Grundlage für einen ganzheitlichen Ansatz der Untersuchung biologischer Systeme im Sinne der Systembiologie, um aufbauend auf den einzelnen Elementen und ihren Interaktionen das Gesamtsystem zu verstehen. Netzwerke spielen dabei eine entscheidende Rolle, da sie ein geeignetes Medium zur Integration der unterschiedlichen Daten darstellen. Durch die Entwicklung neuer Analyse- und Visualisierungsmethoden für biologische Netzwerke kann die Informatik wesentlich zum besseren Verständnis der komplexen Prozesse in Lebewesen beitragen. Dieser Artikel gibt einen Überblick über das Thema und zeigt beispielhaft Anwendungen.
  • Konferenzbeitrag
    Automated bond order assignment as an optimization problem
    (German conference on bioinformatics 2009, 2009) Dehof, Anna Katharina; Rurainski, Alexander; Lenhof, Hans -Peter; Hildebrandt, Andreas
    Numerous applications in Computational Biology process molecular structures and hence require not only reliable atomic cordinates, but also correct bond order information. Regrettably, this information is not always provided in molecular databases like the Cambridge Structural Database or the Protein Data Bank. Very different strategies have been applied to derive bond order information, most of them relying on the correctness of the atom coordinates. We extended a different ansatz proposed by Wang et al. that assigns heuristic molecular penalty scores solely based on connectivity information and tries to heuristically approximate its optimum. In this work, we present two efficient and exact solvers for the problem replacing the heuristic approximation scheme of the original approach: an ILP formulation and an A* approach. Both are integrated into the upcoming version of the Biochemical Algorithms Library BALL and have been successfully validated on the MMFF94 validation suite.
  • Konferenzbeitrag
    Comparative generalized logic modeling reveals differential gene interactions during cell cycle exit in Drosophila Wing Development
    (German conference on bioinformatics 2009, 2009) Song, Mingzhou (Jeo); Hong, Chung -Chien; Zhang, Yang; Buttitta, Laura; Edgar, Bruce A.
    A comparative interaction detection paradigm is proposed to study the complex gene regulatory networks that control cell proliferation during development. Instead of attempting to reconstruct the entire cell cycle regulatory network from temporal transcript data, differential interactions – represented by generalized logic – are detected directly from time course transcript data under two distinct conditions. This comparative approach is scaleand shift-invariant and is capable of detecting nonlinear differential interactions. Simulation studies on E. coli circuits demonstrated that the proposed comparative method has substantially increased statistical power over the intuitive reconstruct-then-compare approach. This method was therefore applied to a microarray experiment, profiling gene expression in the fruit fly wing as cells exit the cell cycle, and under a condition which delays this exit, over-expression of the cell cycle regulator E2F. One statistically significant differential interaction was identified between two gene clusters that is strongly influenced by E2F activity, and suggests the involvement of the Hippo signaling pathway in response to E2F, a finding that may provide additional insights on cell cycle control mechanisms. Furthermore, the comparative modeling can be applied to both static and dynamic gene expression data, and is extendible to deal with more than two conditions, useful in many biological studies.
  • Konferenzbeitrag
    Comparative identification of differential interactions from trajectories of dynamic biological networks
    (German conference on bioinformatics 2009, 2009) Ouyang, Zhengyu; Song, Mingzhou (Joe)
    It is often challenging to reconstruct accurately a complete dynamic biological network due to the scarcity of data collected in cost-effective experiments. This paper addresses the possibility of comparatively identifying qualitative interaction shifts between two dynamical networks from comparative time course data. An innovative approach is developed to achieve differential interaction detection by statistically comparing the trajectories, instead of numerically comparing the reconstructed interactions. The core of this approach is a statistical heterogeneity test that compares two multiple linear regression equations for the derivatives in nonlinear ordinary differential equations, statistically instead of numerically. In detecting any shift of an interaction, the uncertainty in estimated regression coefficients is taken into account by this test, while it is ignored by the reconstruction-based numerical comparison. The heterogeneity test is accomplished by assessing the gain in goodnessof-fit from using a single common interaction to using a pair of differential interactions. Compared with previous numerical comparison methods, the proposed statistical comparison always achieves higher statistical power. As sample size decreases or noise increases in a certain range, the improvement becomes substantial. The advantage is illustrated by a simulation study on the statistical power as functions of the noise level, the sample size, and the interaction complexity. This method is also capable of detecting interaction shifts in the oscillated and excitable domains of a dynamical system model describing cdc2-cyclin interactions during cell division cycle. Generally, the described approach is applicable to comparing dynamical systems of additive nonlinear ordinary differential equations.
  • Konferenzbeitrag
    Comparison of centralities for biological networks
    (German Conference on Bioinformatics 2004, GCB 2004, 2004) Koschützki, Dirk; Schreiber, Falk
    The analysis of biological networks involves the evaluation of the vertices within the connection structure of the network. To support this analysis we discuss five centrality measures and demonstrate their applicability on two example networks, a protein-protein-interaction network and a transcriptional regulation network. We show that all five centrality measures result in different valuations of the vertices and that for the analysis of biological networks all five measures are of interest.
  • Konferenzbeitrag
    Converting DNA to music: COMPOSALIGN
    (German conference on bioinformatics 2009, 2009) Ingalls, Todd; Martius, Georg; Hellmuth, Marc; Marz, Manja; Prohaska, Sonja J.
    Alignments are part of the most important data type in the field of comparative genomics. They can be abstracted to a character matrix derived from aligned sequences. A variety of biological questions forces the researcher to inspect these alignments. Our tool, called COMPOSALIGN, was developed to sonify large scale genomic data. The resulting musical composition is based on COMMON MUSIC and allows the mapping of genes to motifs and species to instruments. It enables the researcher to listen to the musical representation of the genome-wide alignment and contrasts a bioinformatician's sight-oriented work at the computer.
  • Konferenzbeitrag
    CUDA-based multi-core implementation of MDS-based bioinformatics algorithms
    (German conference on bioinformatics 2009, 2009) Fester, Thilo; Schreiber, Falk; Strickert, Marc
    Solving problems in bioinformatics often needs extensive computational power. Current trends in processor architecture, especially massive multi-core processors for graphic cards, combine a large number of cores into a single chip to improve the overall performance. The Compute Unified Device Architecture (CUDA) provides programming interfaces to make full use of the computing power of graphics processing units. We present a way to use CUDA for substantial performance improvement of methods based on multi-dimensional scaling (MDS). The suitability of the CUDA architecture as a high-performance computing platform is studied by adapting a MDS algorithm on specific hardware properties. We show how typical bioinformatics problems related to dimension reduction and network layout benefit from the multi-core implementation of the MDS algorithm. CUDA-based methods are introduced and compared to standard solutions, demonstrating 50-fold acceleration and above.