Bioinformatics: From Nucleic Acids and Proteins to Cell Metabolism 4b VCH Gesellschaft fur Biotechnologische Forschung mbH Distribution: VCH, I? 0. Box 10 11 61, D-69451 Weinheim (Federal Republic of Germany) Switzerland: VCH, F! 0. Box, CH-4020 Basel (Switzerland) United Kingdom and Ireland: VCH, 8 Wellington Court, Cambridge CB1 1HZ (United Kingdom) USAand Canada: VCH, 220 East 23rd Street, New York, NY 10010-4606 (USA) Japan: VCH, Eikow Building, 10-9 Hongo I-chome, Bunkyo-ku, Tokyo 113 (Japan) ISBN 3-527-30072-4 ISSN 0930-4320 GBF Monographs Volume 18 Bioin for mat ics : From Nucleic Acids and Proteins to Cell Metabolism Edited by Dietmar Schomburg Uta Lessel Contributions to the Conference on “Bioinformatics” October 9 to 11,1995 Braunschweig, Germany Prof. Dr. Dietmar Schomburg Dr. Uta Lessel GBF Gesellschaft fur Biotechnologische Forschung mbH Molekulare und lnstrumentelle Strukturforschung Mascheroder Weg 1 D-38124 Braunschweig Federal Republic of Germany This book was carefully produced. Nevertheless, authors, editors and publisher do not warrant the information containedt herein to be free of efms. Readers are advised to keep in mind that statements, data, illustrations, procedural details or other items may inadvertently be inaccurate. Standard Edition published jointly by VCH Verlagsgesellschaft mbH, Weinheim (Federal Republic of Germany) VCH Publishers, Inc., New York, NY (USA) Copy Editor: Dr. J.-H. Walsdorff, Gesellschaft fur BiotechnologischeF orschung, Braunschweig Responsible for the contents: The contributors Cover illustration: Schroers Werbeagentur, Braunschweig Library of Congress Card No. applied for. A catalogue for this book is available from the British Library. Deutsche Bibliothek Cataloguing-in-PublicationD ata: Bioinformatics : from nucleic acids and proteins to cell metabolism ; contributions to the Conference on "Bioinformatics", October 9 to 11, 1995, Braunschweig, Germany / ed. by Dietmar Schomburg ; Uta Lessel. - Weinheim ; Basel ; Cambridge ; New York, NY ;Tokyo : VCH, 1995 (GBF monographs ; Vol. 18) ISBN 3-527-30072-4 NE: Schomburg, Dietmar [Hrsg.]; Conference on Bioinformatics <1995, Braunschweig>; Gesellschaft fur Biotechnologische Forschung <Braunschweig>: GBF-Monographien 0 GBF (Gesellschaft fur BiotechnologischeF orschung mbH), D-38124 Braunschweig (Federal Republic of Germany), 1995 Printed on acid-free and chlorine-free paper. All rights reserved (including those of translation into other languages). No part of this book may be repro- duced in any form - by photoprinting, microfilm, or any other means - nor transmitted or translated into a machine language without written permissionf rom the publishers. Registered names, trademarks, etc. used in this book, even when not specifically marked as such, are not to be considered unprotected by law. Printing: betz-druck GmbH, D-64291 Darmstadt Bookbinding: J. Schaffer, D-67269 Grijnstadt Printed in the Federal Republic of Germany Preface The term bioinformatics has two quite distinct meanings. It may describe information handling in living organisms, and it is widely used for the application of computer science to biological problems. It is this second area which is covered in this book. The series of articles presented here represents a selection of the papers given at an invigorating conference on BioinformaticdComputer Application in the Biosciences, held in October 1995 in Braunschweig at the German National Laboratory for Biotechnology. The development and use of computer applications in the biological sciences, though initiated rather late compared to the situation in physics and chemistry, has reached a high standard nowadays and has become an indispensable part of any research in this area. A strong impetus has come from modem gene sequencing projects and also from the rapid development in the field of structural biochemistry, i.e. the determination of protein and DNA/RNA 3D-structures as well as rational protein engineering and design. This is reflected in the subjects covered in the articles in this book. They describe the present state in this field, in particular the following facts become obvious: - The use and development of biological data bases has become an essential foundation for research in protein science and molecular biology. - Whereas the coding regions of DNA have been the main target of research in the past, nowadays the non-coding regions and RNA are receiving closer attention. - The sequence comparison and correct alignment of protein sequences is a prerequisite for any protein engineering. Although routinely used in almost all biochemistry laboratories, alignment of sequences with low homology still requires further intensive research so that significantly better results can be produced than those currently available. - The description and simulation of the interactions between different biological molecules will be one of the fascinating areas of future research. - In addition to understanding the biological processes on a molecular level, we have to simulate the metabolism in the living cell in order to achieve real metabolic design for the optimal biotechnological production of compounds. Whereas the first development of these methods stems from the sixties and seventies, it is only recently that biologists, chemists and computer scientists have channelled their expertize into large scale collaborative projects aimed at the advancement in this exciting area. Government programs started, for example in Germany and the UK, have provided extra money for joint projects involving computer scientists and biologists. Together with the rapid progress in modem biology and biotechnology, we can expect to see wide-ranging new developments in bioinformatics in the years to come. Dietmar Schomburg Uta Lessel October 1995 Contents List of Authors IX I. Biological Data Bases 1 An Integrated Services Approach to Biological Sequence Databases 3 K. Heumann, C. Harris, A. Kaps, S. Liebl, A. Maierl, F. Pfeirer, H.W. Mewes 11. DNA and RNA 17 The Gene Sequence Analysis System DIANA [Das Gensequenzanalysesystem DIANA] 19 A. Hatzigeorgiou, T. Harrer, N. Mache, M. Reczko Statistical Analysis of DNA Sequences 29 H. Herzel, W. Ebeling, I. Grosse, A.O. Schmitt A Consensus Match Scoring System that is Correlated with Biological Functionality 47 K. Quandt, K. Frech, G. Herrmann, T. Werner Algorithmic Representation of Large RNA Folding Landscapes 59 W. Griiner, R. Giegerich, D. Strothmann 111. Protein Sequences and Structures 73 Statistical Significance of Local Alignments with Gaps 75 M. Vingron, M.S. Waterman Classification of Local Protein Structural Motifs by Kohonen Networks 85 J. Schuchhardt, G. Schneider, J. Reichelt, D. Schomburg, P. Wrede Vlll Contents Data set heterogeneities and their effects on the derivation of contact potential 93 J. Selbig 3D-Segmentation and Vectorvalued Scoring Functions for Symbolic Docking of Proteins [3 D-Segmentierungstechniken und vektorwertige Bewertungsfunktionen fir symbolisches Protein-Protein-Docking] 105 F. Ackennann, G. Herrmann, S. Posch, G. Sagerer An Algorithm for the Protein Docking Problem 125 H.-P. Lenhof IV. From Molecules to Cell Metabolism 141 Force Field Minimization: Domain Decomposition, Positive Definite Functions, and Wavelets 143 E. Schmitt Similarity Analysis of Biologically Active Molecules with Self-Organizing Maps trained by Topological Autocorrelation Vectors [Ahnlichkeitsanalyse biologisch aktiver Molekule mit durch Autokorrelations- vektoren trainierten selbstorganisierenden Karten] 153 H. Bauknecht, A. 211, H. Bayer, P. Levi, M. Wagener, J. Sadowski, J. Gasteiger Algebraic Methods for the Analysis of Redundancy and Identifiability in Metabolic '3C-Labelling Systems 169 W. Wiechert Simulation and Animation of Intracellular Diffusion 185 H.- G. Lipinski List of Authors Ackermann, F. 105 Sagerer, G. 105 Bauknecht, H. 153 Schmitt, A.O. 29 Bayer, H. 153 Schmitt, E. 143 Ebeling, W. 29 Schneider, G. 85 Frech, K. 47 Schomburg, D. 85 Gasteiger, J. 153 Schuchhardt, J. 85 Giegerich, R. 59 Selbig, J. 93 Grosse, I. 29 Strothmann, D. 59 Griiner, W. 59 Vingron, M. 75 Harrer, T. 19 Wagener, M. 153 Harris, C. 3 Waterman, M.S. 75 Hatzigeorgiou, A. 19 Werner, T. 47 Herrmann, Grit 105 Wiechert, W. 169 Henmann, Gunter 47 Wrede, P. 85 Herzel, H. 29 211, A. 153 Heumann, K. 3 Kaps, A. 3 Lenhof, H.-P. 125 Levi, P. 153 Liebl, S. 3 Lipinski, H.-G. 185 Mache, N. 19 Maierl, A. 3 Mewes, H.W. 3 Pfeiffer, F. 3 Posch, S. 105 Quandt, K. 47 Reczko, M. 19 Reichelt, J. 85 Sadowski, J. 153 I. Biological Data Bases Bioinformatics: From Nudeic Acids and Proteins b Cell Metabolism Edited by Dietmar Schomburg, Uta Lessel Q GEF (Gesellschait for BiotechnologischeF orschung mbH), 1995 An Integrated Services Approach to Biological Sequence Databases Heumunn" K., Harris C., Kaps A., Liebl S., Maierl A., Pfeifler F., Mewes H. W. MIPS at the Max-Planck-Institut fir Biochemie, Am Klopferspitz, 82 152 Martinsried, Germany e-mail: [email protected] [email protected] Phone: 1-49 89 8578 245 1 FAX: 4 98 9 8578 2655 Abstract Database users in molecular biology are faced with steadily increasing amounts of raw data, multiple database providers and services. Here we describe the integration of a set of previously isolated database services and demonstrate their accessibility through a uniform user interface. A multi-layered software architecture is applied to make different degrees of service integration transparent to the user. We focus on the design of specialized gateways that integrate services differing in temporal behavior and stateless or state dependent operation. Gateways may reside on heterogeneous platforms. A link layer is introduced to integrate individual query functions in order to interrelate simple, complex and state dependent services through a common, unique interface. It is possible to generate new complex services by a combination of multiple functions. We describe the application of the World Wide Web (WWW) as the implementation framework of the interface layer. To assure interoperability of services, integrity of data resources must be supervised. Consistency control is issued by a dedicated synchronization layer. Introduction IJsers of molecular biology databases that wish to benefit from multiple services provided by different resources are confronted with various user interfaces that must be mastered prior to exploring a particular service. Because these isolated services were developed independently, rarely was an interrelation with other services considered at the time of development. The user must establish this relationship in order to evaluate the results from different resources or analytical tools. Recently, the need for database interoperability and the need to develop effective mechanisms for inter-database communication have obtained increasing attention [GE095]. Moreover, information provided by independent sites is notoriously inconsistent, i.e. information