Lieu Chat Luong BIOINFORMATICS SECOND EDITION METHODS OF BIOCHEMICAL ANALYSIS Volume 43 BIOINFORMATICS A Practical Guide to the Analysis of Genes and Proteins SECOND EDITION Andreas D. Baxevanis Genome Technology Branch National Human Genome Research Institute National Institutes of Health Bethesda, Maryland USA B. Francis Ouellette Centre for Molecular Medicine and Therapeutics Children’s and Women’s Health Centre of British Columbia University of British Columbia Vancouver, British Columbia Canada A JOHN WILEY & SONS, INC., PUBLICATION New York • Chichester • Weinheim • Brisbane • Singapore • Toronto Designations used by companies to distinguish their products are often claimed as trademarks. In all instances where John Wiley & Sons, Inc., is aware of a claim, the product names appear in initial capital or ALL CAPITAL LETTERS.
Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration. Copyright 䉷 2001 by John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic or mechanical, including uploading, downloading, printing, decompiling, recording or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the Publisher.
Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 605 Third Avenue, New York, NY 10158-0012, (212) 850-6011, fax (212) 850-6008, E-Mail: PERMREQ@WILEY. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold with the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional person should be sought.
This title is also available in print as ISBN 0-471-38390-2 (cloth) and ISBN 0-471-38391-0 (paper). For more information about Wiley products, visit our website at www. ADB dedicates this book to his Goddaughter, Anne Terzian, for her constant kindness, good humor, and love—and for always making me smile. BFFO dedicates this book to his daughter, Maya.
Her sheer joy and delight in the simplest of things lights up my world everyday. xvii 1 BIOINFORMATICS AND THE INTERNET 1 Andreas D. Baxevanis Internet Basics. 2 Connecting to the Internet.
7 File Transfer Protocol. 10 The World Wide Web. 13 Internet Resources for Topics Presented in Chapter 1. 17 2 THE NCBI DATA MODEL 19 James M.
Wheelan, and Jonathan A. 19 PUBs: Publications or Perish. 24 SEQ-Ids: What’s in a Name?. 31 BIOSEQ-SETs: Collections of Sequences.
34 SEQ-ANNOT: Annotating the Sequence. 35 SEQ-DESCR: Describing the Sequence. 40 Using the Model. 43 3 THE GENBANK SEQUENCE DATABASE 45 Ilene Karsch-Mizrachi and B.
Francis Ouellette Introduction. 45 Primary and Secondary Databases. Content: Computers vs. 49 vii viii CONTENTS The GenBank Flatfile: A Dissection.
58 Internet Resources for Topics Presented in Chapter 3 .1 Example of GenBank Flatfile Format .2 Example of EMBL Flatfile Format .3 Example of a Record in CON Division. 63 4 SUBMITTING DNA SEQUENCES TO THE DATABASES 65 Jonathan A. Francis Ouellette Introduction. 65 Why, Where, and What to Submit?.
67 Population, Phylogenetic, and Mutation Studies. 69 Protein-Only Submissions. 69 How to Submit on the World Wide Web. 70 How to Submit with Sequin.
77 Consequences of the Data Model. 77 EST/STS/GSS/HTG/SNP and Genome Centers. 79 Contact Points for Submission of Sequence Data to DDBJ/EMBL/GenBank. 80 Internet Resources for Topics Presented in Chapter 4.
81 5 STRUCTURE DATABASES 83 Christopher W. Hogue Introduction to Structures. 83 PDB: Protein Data Bank at the Research Collaboratory for Structural Bioinformatics (RCSB). 87 MMDB: Molecular Modeling Database at NCBI.
91 Stucture File Formats. 94 Visualizing Structural Information. 95 Database Structure Viewers. 100 Advanced Structure Modeling.
103 Structure Similarity Searching. 103 Internet Resources for Topics Presented in Chapter 5. 107 6 GENOMIC MAPPING AND MAPPING DATABASES 111 Peter S. White and Tara C.
Matise Interplay of Mapping and Sequencing. 112 Genomic Map Elements. 113 CONTENTS ix Types of Maps. 115 Complexities and Pitfalls of Mapping.
122 Mapping Projects and Associated Resources. 127 Practical Uses of Mapping Resources. 142 Internet Resources for Topics Presented in Chapter 6. 149 7 INFORMATION RETRIEVAL FROM BIOLOGICAL DATABASES 155 Andreas D.
Baxevanis Integrated Information Retrieval: The Entrez System. 172 Sequence Databases Beyond NCBI. 181 Internet Resources for Topics Presented in Chapter 7. 185 8 SEQUENCE ALIGNMENT AND DATABASE SEARCHING 187 Gregory D.
187 The Evolutionary Basis of Sequence Alignment. 188 The Modular Nature of Proteins. 190 Optimal Alignment Methods. 193 Substitution Scores and Gap Penalties.
195 Statistical Significance of Alignments. 198 Database Similarity Searching. 202 Database Searching Artifacts. 204 Position-Specific Scoring Matrices.
210 Internet Resources for Topics Presented in Chapter 8. 212 9 CREATION AND ANALYSIS OF PROTEIN MULTIPLE SEQUENCE ALIGNMENTS 215 Geoffrey J. 215 What is a Multiple Alignment, and Why Do It?. 216 Structural Alignment or Evolutionary Alignment?.
216 How to Multiply Align Sequences. 217 x CONTENTS Tools to Assist the Analysis of Multiple Alignments. 222 Collections of Multiple Alignments. 227 Internet Resources for Topics Presented in Chapter 9.
230 10 PREDICTIVE METHODS USING DNA SEQUENCES 233 Andreas D. 241 How Well Do the Methods Work?. 246 Strategies and Considerations. 248 Internet Resources for Topics Presented in Chapter 10.
251 11 PREDICTIVE METHODS USING PROTEIN SEQUENCES 253 Sharmila Banerjee-Basu and Andreas D. Baxevanis Protein Identity Based on Composition. 254 Physical Properties Based on Sequence. 257 Motifs and Patterns.
259 Secondary Structure and Folding Classes. 263 Specialized Structures or Features. 274 Internet Resources for Topics Presented in Chapter 11. 279 12 EXPRESSED SEQUENCE TAGS (ESTs) 283 Tyra G.
Wolfsberg and David Landsman What is an EST?. 288 TIGR Gene Indices. 293 ESTs and Gene Discovery. 294 The Human Gene Map.
294 Gene Prediction in Genomic DNA. 295 ESTs and Sequence Polymorphisms. 296 Assessing Levels of Gene Expression Using ESTs. 296 Internet Resources for Topics Presented in Chapter 12.
299 CONTENTS xi 13 SEQUENCE ASSEMBLY AND FINISHING METHODS 303 Rodger Staden, David P. Judge, and James K. Bonfield The Use of Base Cell Accuracy Estimates or Confidence Values. 305 The Requirements for Assembly Software.
307 Preparing Readings for Assembly. 308 Introduction to Gap4. 311 The Contig Selector. 311 The Contig Comparator.
312 The Template Display. 313 The Consistency Display. 316 The Contig Editor. 316 The Contig Joining Editor.
319 Experiment Suggestion and Automation. 321 Internet Resources for Topics Presented in Chapter 13. 322 14 PHYLOGENETIC ANALYSIS 323 Fiona S. Brinkman and Detlef D.
Leipe Fundamental Elements of Phylogenetic Models. 325 Tree Interpretation—The Importance of Identifying Paralogs and Orthologs. 327 Phylogenetic Data Analysis: The Four Steps. 327 Alignment: Building the Data Model.
329 Alignment: Extraction of a Phylogenetic Data Set. 333 Determining the Substitution Model. 335 Tree-Building Methods. 340 Distance, Parsimony, and Maximum Likelihood: What’s the Difference?.
348 Internet-Accessible Phylogenetic Analysis Software. 354 Some Simple Practical Considerations. 356 Internet Resources for Topics Presented in Chapter 14. 357 15 COMPARATIVE GENOME ANALYSIS 359 Michael Y.
Galperin and Eugene V. Koonin Progress in Genome Sequencing. 360 Genome Analysis and Annotation. 366 Application of Comparative Genomics—Reconstruction of Metabolic Pathways.
382 Avoiding Common Problems in Genome Annotation. 385 xii CONTENTS Conclusions. 387 Internet Resources for Topics Presented in Chapter 15. 387 Problems for Additional Study.
390 16 LARGE-SCALE GENOME ANALYSIS 393 Paul S. 393 Technologies for Large-Scale Gene Expression. 394 Computational Tools for Expression Analysis. 407 Prospects for the Future.
409 Internet Resources for Topics Presented in Chapter 16. 410 17 USING PERL TO FACILITATE BIOLOGICAL ANALYSIS 413 Lincoln D. Stein Getting Started. 414 How Scripts Work.
416 Strings, Numbers, and Variables. 419 Basic Input and Output. 427 What is Truth?. 430 Combining Loops with Input.
432 Standard Input and Output. 433 Finding the Length of a Sequence File. 441 Arrays and Lists. 444 Split and Join.
445 A Real-World Example. 446 Where to Go From Here. 449 Internet Resources for Topics Presented in Chapter 17. 457 FOREWORD I am writing these words on a watershed day in molecular biology.
This morning, a paper was officially published in the journal Nature reporting an initial sequence and analysis of the human genome. One of the fruits of the Human Genome Project, the paper describes the broad landscape of the nearly 3 billion bases of the euchromatic portion of the human chromosomes. In the most narrow sense, the paper was the product of a remarkable international collaboration involving six countries, twenty genome centers, and more than a thou- sand scientists (myself included) to produce the information and to make it available to the world freely and without restriction. In a broader sense, though, the paper is the product of a century-long scientific program to understand genetic information.
The program began with the rediscovery of Mendel’s laws at the beginning of the 20th century, showing that information was somehow transmitted from generation to generation in discrete form. During the first quarter-century, biologists found that the cellular basis of the information was the chromosomes. During the second quarter-century, they discovered that the molecular basis of the information was DNA. During the third quarter-century, they unraveled the mechanisms by which cells read this information and developed the recombinant DNA tools by which scientists can do the same.
During the last quarter-century, biologists have been trying voraciously to gather genetic information-first from genes, then entire genomes. The result is that biology in the 21st century is being transformed from a purely laboratory-based science to an information science as well. The information includes comprehensive global views of DNA sequence, RNA expression, protein interactions or molecular conformations. Increasingly, biological studies begin with the study of huge databases to help formulate specific hypotheses or design large-scale experi- ments.
In turn, laboratory work ends with the accumulation of massive collections of data that must be sifted. These changes represent a dramatic shift in the biological sciences. One of the crucial steps in this transformation will be training a new generation of biologists who are both computational scientists and laboratory scientists. This major challenge requires both vision and hard work: vision to set an appropriate agenda for the computational biologist of the future and hard work to develop a curriculum and textbook.
James Watson changed the world with his co-discovery of the double-helical structure of DNA in 1953. But, he also helped train a new generation to inhabit that new world in the 1960s and beyond through his textbook, The Molecular Biology of the Gene. Discovery and teaching go hand-in-hand in changing the world. xiii xiv FOREWORD In this book, Andy Baxevanis and Francis Ouellette have taken on the tremen- dously important challenge of training the 21st century computational biologist.
To- ward this end, they have undertaken the difficult task of organizing the knowledge in this field in a logical progression and presenting it in a digestible form. And, they have done an excellent job. This fine text will make a major impact on biological research and, in turn, on progress in biomedicine. We are all in their debt.
Lander February 15, 2001 Cambridge, Massachusetts PREFACE With the advent of the new millenium, the scientific community marked a significant milestone in the study of biology—the completion of the ‘‘working draft’’ of the human genome.