COMPUTATIONAL METHODS FOR UNDERSTANDING BACTERIAL AND ARCHAEAL CENOMES SERIES ON ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY Series Editors: ISSN: 1751-6404 Ying XU (University of Georgia, USA) Limsoon WONG (National University of Singapore, Singapore) Associate Editors: Ruth Nussinov (NCI, USA) See-Kiong Ng (Inst for Infocomm Res, Singapore) Rolf Apweiler (EBI, UK) Kenta Nakai (Univ of Tokyo, Japan) Ed Wingender (BioBase, Germany) Mark Ragan (Univ of Queensland, Australia) Vol. 1: Proceedings of the 3rd Asia-Pacific Bioinformatics Conference Eds: Yi-Ping Phoebe Chen and Limsoon Wong Vol. 2: Information Processing and Living Systems Eds: Vladimir B. Bajic and Tan Tin Wee Vol. 3: Proceedings of the 4th Asia-Pacific Bioinformatics Conference Eds: Tao Jiang, Ueng-Cheng Yang, Yi-Ping Phoebe Chen and Limsoon Wong Vol. 4: Computational Systems Bioinformatics 2006 Eds: Peter Markstein and Ying Xu ISSN: 1762-7791 Vol. 5: Proceedings of the 5th Asia-Pacific Bioinformatics Conference Eds: David Sankoff, Lusheng Wang and Francis Chin Vol. 6: Proceedings of the 6th Asia-Pacific Bioinformatics Conference Eds: Alvis Brazma, Satoru Miyano and Tatsuya Akutsu Vol. 7: Computational Methods for Understanding Bacterial and Archaeal Genomes Eds: Ying Xu and J. Peter Gogarten Wanda - Computational Methods for.pmd 2 9/19/2008, 6:49 PM Series on Advances in Bioinformatics and Computational Biology - Volume 7 COMPUTATIONAL METHODS FOR UNDERSTANDING BACTERIAL AND ARCHAEAL GENOMES Edi ToRs xu YiNG UNlVERSiTY Of GEORGIA, USA 1. PETERG OGARTEN UNiVERSiTY Of CONNECTiCUT, USA Imperial College Press Published by Imperial College Press 57 Shelton Street Covent Garden London WC2H 9HE Distributed by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. COMPUTATIONAL METHODS FOR UNDERSTANDING BACTERIAL AND ARCHAEAL GENOMES Series on Advances in Bioinformatics and Computational Biology — Vol. 7 Copyright © 2008 by Imperial College Press All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. ISBN-13 978-1-86094-982-1 ISBN-10 1-86094-982-7 Typeset by Stallion Press Email: [email protected] Printed in Singapore. Wanda - Computational Methods for.pmd 1 9/19/2008, 6:49 PM June 26, 2008 9:18 9.75 x 6.5 B-631 fm PREFACE Sequencing technology has advanced to such a level that large sequencing centers such as the Joint Genome Institute (JGI) of the US Department of Energy can sequence a prokaryotic genome within a day. As of this writing, ∼800 prokaryotic genomeshavebeensequencedandatleast1,000areinthepipelinebeingsequenced. Knowinga few largesequencingeffortscurrentlyunder planning,we couldpossibly seeover10,000completeprokaryoticgenomeswithinthenextfewyears.Inaddition, the sequencing efforts of metagenomes have produced over one billion base-pairsof sequencefragmentssince2000,andtheeffortsareexpectedtoscaleuprapidly,soon toproducesubstantiallymoregenomicsequencedatathanwhatwehaveseeninthe pasttwentyyears.Whilethesegenomicsequencedatahaveprovidedunprecedented opportunities for biologiststo study andto understandthese organisms,it has also raised some highly challenging problems regarding how to “mine” the genomes, extract the information encoded in the genomes, in a much more effective manner thanwhattheexistingtoolscanoffer,simplytokeepupwiththepaceofworld-wide genome sequencing efforts. Compared to eukaryotic genomes which are more complex in general, prokaryotic genomes pose a set of unique challenging problems. First, prokaryotic genomes are much more dynamic in terms of their gene compositions than the typical eukaryotic genomes since horizontal gene transfers take place substantially more often in prokaryotes. Second, prokaryotes evolve at much faster rates than eukaryotesingeneral,hencemakingtheirgenomesdivergefaster.Third,prokaryotes have been found in broader environments than eukaryotes, suggesting their more flexible adaptability to the environments. Fourth, prokaryotes often co-exist with otherprokaryotesasamutuallydependentcommunity,partsofwhosemetabolisms are inter-species, making studies of their biochemistry and their genomes rather unique. Comparative genomics has been the most effective approach to mining the genomes and deciphering the information encoded in genomes. Numerous computational techniques have been developed based on comparative strategies, to predict genes and the functions of their protein products, to elucidate operonic structures, to detect previously unknown structures such as uber-operons, and to predictregulatoryelementsandinteractionsofbiochemicalpathways.Fundamental to these computational techniques is our understanding about the evolution of genes, molecular interactions, biological processes and genomes. It is the v June 26, 2008 9:18 9.75 x 6.5 B-631 fm vi Preface theoretical framework for studying these evolutionary processes that have guided our computational studies of the prokaryotic genomes and their structures. For this reason, we have designed this book in such a way that it tightly integrates computational studies with theoretical discussions of prokaryotic genomes. We believethatitisessentialtohaveagoodunderstandingaboutboththeevolutionary theories for prokaryotes and the possibilities and limitations of computational genome analysis techniques, in order to carry out in-depth computational studies that may generate new insights about these genomes and the information they encode. In this book, we included a collection of cohesively written chapters on prokaryoticgenomes,theirorganizationandevolution,theinformationtheyencode, computationalapproachestoderivingsuchinformation,andtounderstandingtheir organizationandevolution.Whenappropriate,weattempttoprovideacomparative view of the bacterial and archaeal genomes and of how information is differently encoded in these two domains of life. This book is intended to be used as an introductory text book for a graduate-level microbial genomics and bioinformatics courseaswellasa referencebookfor researchersworkinginthe areaofprokaryotic genome studies While the chapters are organized in a logical order, each chapter in the book is a self-contained review of a specific subject. Hence a reader does not necessarily have to read through the chapters in their sequential order. Since this is a rapidly evolving field that encompasses an exceptionally wide range of research topics, it is difficult for any individual to write a comprehensive textbook on the entire field. Most of the chapters are written by members of our two labs at the University of Georgia and the University of Connecticut, respectively. The remaining chapters, which,wefeel,willhelptofillgapsincoveringthe field,arewrittenbyexpertswho are actively doing researchat the forefront of the selected topical areas. Chapter1(General characteristics of prokaryotic genomes)explainsthenotion of a genome as a collection of replicons in a cell, and provides an overview of different types of replicons and their distinguishing characteristics.This is followed by a review of the diversity of prokaryotic chromosomes with respect to their size, gene content, G+C content, codon usage, oligonucleotide composition, amino acid usage, repeat content, and intragenomic compositional heterogeneity emphasizing contrasts between eukaryotes and prokaryotes. Chapter 2 (Genes in prokaryotic genomes and their computational prediction) begins with a historical account of the development of gene prediction methods. These methods exploit either intrinsic information, that is, nucleotide ordering patternsintrinsictoaDNAsequence,orextrinsicinformationgainedfromsequence conservation in evolution. The basic idea and models underlying the prediction programs utilizing either intrinsic information or extrinsic information or both are described, followed by a critical comparative assessment of their performance on experimentally validated datasets. The strengths and weaknesses of the current programs and the future challenges are discussed, with suggestions for addressing the remaining core issues in this field. June 26, 2008 9:18 9.75 x 6.5 B-631 fm Preface vii Chapter 3 (Evolution of the genetic code: computational methods and inferences) focuses on the evolution of genetic codes. Ever since its discovery, the genetic code has been one of the most difficult puzzles for evolutionary biology to unravel.AstheevolutionofearlylifeonEarthisinextricablylinkedtotheevolution of the genetic code, understanding its history has been the focus of numerous investigations over the last several years. We present several of the computational methodsthathavebeenappliedtothisproblem,includingabriefdiscussionoftheir results and significance. Chapter4(Dynamics of prokaryotic genome evolution)addressesthedynamics of genome evolution. The ever-increasing amount of genome sequences available in public databases allows a better comprehension of how evolutionary forces act on prokaryotic species. Several methods exist to categorize genes based on their frequency of occurrence among genomes, and are used to predict the genes’ roles and modes of evolution. This chapter describes practical approaches used in the comparison of multiple genomes, and discusses the current status of the field of prokaryotic genome evolution. In Chapter 5 (Mobile genetic elements and their prediction), we review mobile geneticelements,withafocusonthosethatcanbecomputationallypredictedwithin genomesequences.Wediscussthefeaturesoftheseelementsrangingfromthesmall neutralInsertionSequence(IS)elements,tothelargegenomicislandsandprophage regions that can encode antibiotic resistance and virulence-related functions. The chapterfocusesontheinsilico predictionoftheseelements,includingthediscussion of severalexisting tools and databases.In addition, we point out the strengths and weaknesses of the existing methods and suggest future avenues of research in this area. Chapter 6 (Horizontal gene transfer: its detection and role in microbial evolution) provides a brief history of the discovery of gene transfer and how it impacted attempts to develop a natural taxonomy for prokaryotes. We review species concepts as applied to bacteria and archaea, look at examples of multilevel selection acting on genes, organisms and communities, and examine biological processes and artifacts that can create conflicts between gene and genome phylogenies.Wedescribephylogeneticandsurrogateapproachesthataimtoidentify transferredgenesanddiscusstheadvantagesandproblemsassociatedwithdifferent methods, and provide an outlook on future developments that will allow to trace the history of genes and pathways through the network of organismalhistory. In Chapter 7 (Genome reduction during prokaryotic evolution), we review the phenomenon of genome reduction, which has taken place independently many timesinseveralprokaryoticlineages.Thischapterdescribesmethodstoreconstruct ancestral genome contents and to infer genome expansion and contraction. The mutationalandselectivehypothesestoexplainthesechangeswillbediscuss.Finally, we describe the gene content of the smallest genomes and the fuzzy boundary between cells and organelles. Chapter 8 (Comparative mechanisms on transcription and regulatory signals in archaea and bacteria) describes our current knowledge about regulation of June 26, 2008 9:18 9.75 x 6.5 B-631 fm viii Preface transcription in archaea and bacteria. This overview emphasizes the main cis- regulatorysignals,trans-regulatoryfactors (TFs) and alternative RNA polymerase types constituting the machinery needed for proper regulationof genes in response to changing environmental conditions at the level of transcription initiation. In archaeathebasalmachineryfortranscriptionisrelatedtoRNAPIIfromeukaryotes while the use of TFs for modulating gene transcription is similar to those used by bacteria. We describe the promoter at different levels, including the activity of the basalmachineryfortranscriptionandtheuseofspecifictranscriptionfactorssensing and responding to particular effectors signals. We also summarize regulation at other levels beyond transcription initiation. There is an inherent limitation in this comparative approach given the limited amount of knowledge of the regulation mechanisms in archaea. Furthermore, these comparisons also bring eukaryotic transcription to the scene when searching for an evolutionary understanding of the diverse puzzle of similarities and differences in gene organization, conservation of proteins and their mechanisms involved in bacteria, archaea and eukaryotes. Chapter 9 (Computational techniques for orthologous gene prediction in prokaryotes) discusses the definitions of homologs, orthologs, paralogs and their subtypes, and reviews the existing gene family databases and the approaches to homology assignment as well as family-superfamily classification systems. The chapter focuses on the automated methods of orthologous gene prediction. It describes the reciprocal best blast hit method, reciprocal smallest distance method, tree reconciliation algorithm, and the phylogenetic clustering algorithm BranchClust. In Chapter 10 (Computational elucidation of operons and uber-operons), we describe the basics about operons as the basic units of transcription regulation as well as their ties to biological pathways and networks. In addition, we discuss a relativelynewandlesswell-studiedlayerofgenomicstructure,calleduber-operons. The chapter presents a number of basic ideas as well as computational methods for operon and uber-operon prediction, plus relevant prediction servers publicly available on the Internet. We also showcase one study on the evolution of operons, suggesting possible rules for operon evolution. Chapter 11 (Prediction of regulons through comparative genome analyses) introduces first the typical structure of a regulon in prokaryotes, and the special regulon prediction problem as well as the genome-wide de novo regulon prediction problem. It then links these problems to the prediction problem of cis-regulatory binding sites. The chapter details a widely used phylogenetic foot-printing motif finding algorithm as well as a genome-wide scanning procedure for solving the special regulonprediction problem. For the more challenging genome-wide de novo prediction of regulons, the chapter introduces a recently developed phylogenetic foot-printing based algorithm.Examples of practicalapplications are also givenfor each described computational procedure. Chapter 12 (Prediction of biological pathways through data mining and information fusion) presents a few approaches to biological pathway construction June 26, 2008 9:18 9.75 x 6.5 B-631 fm Preface ix usingmultiplesourcesofinformation,includingtranscriptomicdata,genomicdata, proteomicdataaswellasprotein-proteinandprotein-DNAinteractiondata.Several computational algorithms for these predictions are reviewed in this chapter. A comprehensivedescriptiononhowtoestimate parametersinmetabolicpathwaysis also included in this chapter. Chapter 13 (Microbial pathway models) emphasizes the importance of mathematical modeling approaches to understanding microbial systems. It reviews traditionalapproachesofenzymekineticsandleadsthereadertothestateoftheart in metabolic modeling. Particular focus is placed on Biochemical Systems Theory, which in several hundred publications has proven an invaluable tool for designing, analyzing,manipulating,andoptimizingbiologicalsystems,eveninsituationswhere information on the target network is uncertain or partially missing. Chapter 14 (Metagenomics) reviews a new scientific endeavor, metagenomics, which is emerging with the convergence of sequencing and computational technologies focused on communities of microbes. The techniques and strategy of metagenomics enable the exploration of the genomes and the natural world of microbeswithouttheirpriorisolationandcultivation.Whilebuildingonpioneering researchoverroughlythepasttwodecadesandtheirenhancementbytheconvergent technologies, this exceptionally interdisciplinary endeavor, which also brings in biogeochemistry and ecological, evolutionary and environmental biology, as well as the wide range of research in microbiology and genomics, is just being defined. To invite the reader to participate in this endeavor, the chapter provides a brief overview of the current state of knowledge and the opportunities that create the excitement and bring together scientists from such diverse disciplines. Research observations in metagenomics, for example, have already demonstrated the vast diversity of microbial proteins and suggest extensive implications for applied life sciences (from environmental science to medicine), as well as for our fundamental understanding of biology. Ying Xu and J. Peter Gogarten