JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 Intelligent Bioinformatics The application of artificial intelligence techniques to bioinformatics problems Edward Keedwell and Ajit Narayanan School of Engineering, Computer Science and Mathematics University of Exeter, UK iii JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 ii JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 Intelligent Bioinformatics i JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 ii JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 Intelligent Bioinformatics The application of artificial intelligence techniques to bioinformatics problems Edward Keedwell and Ajit Narayanan School of Engineering, Computer Science and Mathematics University of Exeter, UK iii JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 Copyright(cid:1)C 2005 JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester, WestSussexPO198SQ,England Telephone (+44)1243779777 Email(forordersandcustomerserviceenquiries):[email protected] VisitourHomePageonwww.wileyeurope.comorwww.wiley.com AllRightsReserved.Nopartofthispublicationmaybereproduced,storedinaretrieval systemortransmittedinanyformorbyanymeans,electronic,mechanical,photocopying, recording,scanningorotherwise,exceptunderthetermsoftheCopyright,Designsand PatentsAct1988orunderthetermsofalicenceissuedbytheCopyrightLicensingAgency Ltd,90TottenhamCourtRoad,LondonW1T4LP,UK,withoutthepermissioninwritingof thePublisher.RequeststothePublishershouldbeaddressedtothePermissionsDepartment, JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester,WestSussexPO198SQ, England,[email protected],orfaxedto(+44)1243770620. Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarks. Allbrandnamesandproductnamesusedinthisbookaretradenames,servicemarks, trademarksorregisteredtrademarksoftheirrespectiveowners.ThePublisherisnot associatedwithanyproductorvendormentionedinthisbook. Thispublicationisdesignedtoprovideaccurateandauthoritativeinformationinregardto thesubjectmattercovered.ItissoldontheunderstandingthatthePublisherisnotengaged inrenderingprofessionalservices.Ifprofessionaladviceorotherexpertassistanceis required,theservicesofacompetentprofessionalshouldbesought. OtherWileyEditorialOffices JohnWiley&SonsInc.,111RiverStreet,Hoboken,NJ07030,USA Jossey-Bass,989MarketStreet,SanFrancisco,CA94103-1741,USA Wiley-VCHVerlagGmbH,Boschstr.12,D-69469Weinheim,Germany JohnWiley&SonsAustraliaLtd,33ParkRoad,Milton,Queensland4064,Australia JohnWiley&Sons(Asia)PteLtd,2ClementiLoop#02-01,JinXingDistripark, Singapore129809 JohnWiley&SonsCanadaLtd,22WorcesterRoad,Etobicoke,Ontario,CanadaM9W1L1 Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappears inprintmaynotbeavailableinelectronicbooks. LibraryofCongressCataloguing-in-PublicationData BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN0470021756 Typesetin10.5/13.5ptSabonbyTechBooks,NewDelhi,India PrintedandboundinGreatBritainbyTJInternationalLtd.,Padstow,Corwall Thisbookisprintedonacid-freepaperresponsiblymanufacturedfromsustainableforestry inwhichatleasttwotreesareplantedforeachoneusedforpaperproduction. iv JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 Contents Preface ix Acknowledgement xi PART 1 INTRODUCTION 1 1 Introduction to the Basics of Molecular Biology 3 1.1 Basiccellarchitecture 3 1.2 Thestructure,contentandscaleofdeoxyribonucleicacid(DNA) 4 1.3 Historyofthehumangenome 9 1.4 Genesandproteins 10 1.5 Currentknowledgeandthe‘centraldogma’ 21 1.6 Whyproteinsareimportant 23 1.7 Geneandcellregulation 24 1.8 Whencellregulationgoeswrong 26 1.9 So,whatisbioinformatics? 27 1.10 Summaryofchapter 28 1.11 Furtherreading 29 2 Introduction to Problems and Challenges in Bioinformatics 31 2.1 Introduction 31 2.2 Genome 31 2.3 Transcriptome 40 2.4 Proteome 50 2.5 Interferencetechnology,virusesandtheimmunesystem 57 2.6 Summaryofchapter 63 2.7 Furtherreading 64 v JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 vi CONTENTS 3 Introduction to Artificial Intelligence and Computer Science 65 3.1 Introductiontosearch 65 3.2 Searchalgorithms 66 3.3 Heuristicsearchmethods 72 3.4 Optimalsearchstrategies 76 3.5 Problemswithsearchtechniques 83 3.6 Complexityofsearch 84 3.7 Useofgraphsinbioinformatics 86 3.8 Grammars,languagesandautomata 90 3.9 Classesofproblems 96 3.10 Summaryofchapter 98 3.11 Furtherreading 99 PART 2 CURRENT TECHNIQUES 101 4 Probabilistic Approaches 103 4.1 Introductiontoprobability 103 4.2 Bayes’Theorem 105 4.3 Bayesiannetworks 111 4.4 Markovnetworks 116 4.5 Summaryofchapter 125 4.6 References 126 5 Nearest Neighbour and Clustering Approaches 127 5.1 Introduction 127 5.2 Nearestneighbourmethod 130 5.3 Nearestneighbourapproachforsecondarystructureprotein foldingprediction 132 5.4 Clustering 135 5.5 Advancedclusteringtechniques 138 5.6 Applicationguidelines 144 5.7 Summaryofchapter 145 5.8 References 146 6 Identification (Decision) Trees 147 6.1 Method 147 6.2 Gaincriterion 152 6.3 Overfittingandpruning 157 6.4 Applicationguidelines 160 6.5 Bioinformaticsapplications 163 6.6 Background 169 JWBK023-FM JWBK023-Keedwell April5,2005 23:30 CharCount=0 CONTENTS vii 6.7 Summaryofchapter 170 6.8 References 170 7 Neural Networks 173 7.1 Method 173 7.2 Applicationguidelines 185 7.3 Bioinformaticsapplications 187 7.4 Background 192 7.5 Summaryofchapter 193 7.6 References 193 8 Genetic Algorithms 195 8.1 Single-objectivegeneticalgorithms–method 195 8.2 Single-objectivegeneticalgorithms–example 202 8.3 Multi-objectivegeneticalgorithms–method 205 8.4 Applicationguidelines 207 8.5 Geneticalgorithms–bioinformaticsapplications 210 8.6 Summaryofchapter 217 8.7 Referencesandfurtherreading 217 PART 3 FUTURE TECHNIQUES 219 9 Genetic Programming 221 9.1 Method 221 9.2 Applicationguidelines 230 9.3 Bioinformaticsapplications 232 9.4 Background 236 9.5 Summaryofchapter 236 9.6 References 237 10 Cellular Automata 239 10.1 Method 239 10.2 Applicationguidelines 245 10.3 Bioinformaticsapplications 247 10.4 Background 251 10.5 Summaryofchapter 252 10.6 Referencesandfurtherreading 252 11 Hybrid Methods 255 11.1 Method 255 11.2 Neural-geneticalgorithmforanalysinggeneexpressiondata 256 11.3 Geneticalgorithmandknearestneighbourhybridfor biochemistrysolvation 262