Logo des Repositoriums

Auflistung nach Autor:in "Posch, Stefan"

1 - 10 von 24
  • 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.
  • 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
    A Comparative Study of Robust Feature Detectors for 2D Electrophoresis Gel Image Registration
    (German Conference on Bioinformatics, 2008) Möller, Birgit; Greß, Oliver; Posch, Stefan
    In this study we consider the performance of different feature detectors used as the basis for the registration of images from two-dimensional gel electrophoresis. These are three spot detectors also used to identify proteins, and two domain inde- pendent keypoint detectors. We conduct a case study with images from a publically available data set which are synthetically distorted using thin plate splines. The per- formance is assessed by the repeatability score, the probability of an image structure to be detected in original and distorted images with reasonable localization accuracy.
  • 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.
  • Konferenzbeitrag
    Discovering temporal patterns of differential gene expression in microarray time series
    (German conference on bioinformatics 2009, 2009) Stegle, Oliver; Denby, Katherine J.; McHattie, Stuart; Mead, Andrew; Wild, David L.; Ghahramani, Zoubin; Borgwardt, Karsten M.
    A wealth of time series of microarray measurements have become available over recent years. Several two-sample tests for detecting differential gene expression in these time series have been defined, but they can only answer the question whether a gene is differentially expressed across the whole time series, not in which intervals it is differentially expressed. In this article, we propose a Gaussian process based approach for studying these dynamics of differential gene expression. In experiments on Arabidopsis thaliana gene expression levels, our novel technique helps us to uncover that the family of WRKY transcription factors appears to be involved in the early response to infection by a fungal pathogen.
  • Konferenzbeitrag
    EFMEvolver: Computing elementary flux modes in genome-scale metabolic networks
    (German conference on bioinformatics 2009, 2009) Kaleta, Christoph; Figueiredo, Luís Filipe de; Behre, Jörn; Schuster, Stefan
    Elementary flux mode analysis (EFM analysis) is an important method in the study of biochemical pathways. However, the computation of EFMs is limited to small and medium size metabolic networks due to a combinatorial explosion in their number in larger networks. Additionally, the existing tools to compute EFMs require to enumerate all EFMs before selecting those of interest. The method presented here extends EFM analysis to genome-scale models. Instead of computing the entire set of EFMs an optimization problem is used to determine a single EFM. Coupled with a genetic algorithm (GA) this allows to explore the solution space and determine specific EFMs of interest. Applied to a network in which the set of EFMs is known our method was able to find all EFMs in two cases and in another case almost the entire set before aborted. Furthermore, we determined the parts of three metabolic networks that can be used to produce particular amino acids and found that these parts correspond to significant portions of the entire networks. Availability: Source code and an executable are available upon request.