On learning gene regulatory networks under the Boo

MachineLearning,52,147–167,2003c
2003KluwerAcademicPublishers.ManufacturedinTheNetherlands.OnLearningGeneRegulatoryNetworksUndertheBooleanNetworkModelHARRIL¨AHDESM¨AKIharri.lahdesmaki@tut.fiInstituteofSignalProcessing,DigitalMediaInstitute,TampereUniversityofTechnology,P.O.Box553,FIN-33101Tampere,[e-mail]ory,UniversityofTexasM.D.AndersonCancerCenter,1515HolcombeBlvd.,Box85,Houston,TX77030,[e-mail].fiInstituteofSignalProcessing,DigitalMediaInstitute,TampereUniversityofTechnology,P.O.Box553,FIN-33101Tampere,FinlandEditors:PaolaSebastiani,IsaacS.KohaneandMarcoF.RamoniAbstract.Booleannetworksareapopularmodelclassforcapturingtheinteractionsofgenesandglobaldy-namicalbehaviorofgeneticregulatorynetworks.Recently,asignificantamountofattentionhasbeenfocusedontheinferenceoridentificationofthemodelstructurefromgeneexpressiondata.WeconsidertheConsistencyaswellasBest-FitExtensionproblemsinthecontextofinferringthenetworksfromdata.Thelatterapproachisespeciallyusefulinsituationswhengeneexpressionmeasurementsarenoisyandmayleadtoinconsistentobser-vations.WeproposesimpleefficientalgorithmsthatcanbeusedtoanswertheConsistencyProblemandfindoneorallconsistentBooleannetworksrelativetothegivenexamples.ThesamemethodisextendedtolearninggeneregulatorynetworksundertheBest-FitExtensionparadigm.WealsointroduceasimpleandfastwayoffindingallBooleannetworkshavinglimitederrorsizeintheBest-FitExtensionProblemsetting.Weapplytheinferencemethodstoarealgeneexpressiondatasetandpresenttheresultsforaselectedsetofgenes.Keywords:generegulatorynetworks,networkinference,ConsistencyProblem,Best-FitExtensionparadigm1.IntroductionAcentralfocusofgenomicresearchconcernsunderstandingthemannerinwhichcellsex-ecuteandcontroltheenormousnumberofoperationsrequiredfornormalfunctionandthewaysinwhichcellularsystemsfailindisease.Inbiologicalsystems,decisionsarereachedbymethodsthatareexceedinglyparallelandextraordinarilyintegrated.Animportantgoalistounderstandthenatureofcellularfunctionandthemannerinwhichgenesandtheirproductscollectivelyformabiologicalsystem.Incontrasttothereductionisticapproachesinbiology,itisbecomingincreasinglyapparentthatitisnecessarytostudythebehaviorofgenesinaholisticratherthaninanindividualmanner.Suchapproachesinevitablyre-quirecomputationalandformalmethodstoprocessmassiveamountsofdata,tounderstandgeneralprinciplesgoverningthesystemunderstudy,andtomakeusefulpredictionsabout148H.L¨AHDESM¨AKI,I.SHMULEVICH,ANDO.YLI-HARJAsystembehaviorinthepresenceofknownconditions.Asignificantroleisplayedbythedevelopmentandanalysisofmathematicalandcomputationalmethodsinordertoconstructformalmodelsofgeneticinteractions.Thisresearchdirectionprovidesinsightandacon-ceptualframeworkforanintegrativeviewofgeneticfunctionandregulationandpavesthewaytowardunderstandingthecomplexrelationshipbetweenthegenomeandthecell.Anumberofdifferentapproachestogeneregulatorynetworkmodelinghavebeenin-troduced,includinglinearmodels(D’Haeseleeretal.,1999)Bayesiannetworks(Murphy&Main,1999;Friedmanetal.,2000;Harteminketal.,2001),neuralnetworks(Weaver,Workman,&Stormo,1999;Vohradsky,2001),differentialequations(Chen,He,&Church,1999;Mestl,Plahte,&Omholt,1995),andmodelsincludingstochasticcomponentsonthemolecularlevel(McAdams&Arkin,1997)(seeSmolen,Baxter,&Byrne,2000;Hastyetal.,2001;deJong,2002)forreviewsofgeneralmodels).AmodelclassthathasreceivedaconsiderableamountofattentionistheBooleannetwork(BN)modeloriginallyintroducedbyKauffman(Kauffman,1969;Glass&Kauffman,1973).GoodreviewscanbefoundinHuang(1999),Kauffman(1993),andSomogyiandSniegoski(1996).Inthismodel,thestateofageneisrepresentedbyaBooleanvariable(ONorOFF)andinteractionsbetweenthegenesarerepresentedbyBooleanfunctions,whichdeterminethestateofageneonthebasisofthestatesofsomeothergenes.Recentworksuggeststhatevenwhengeneexpressiondataareanalyzedentirelyinthebinarydomain(onlytwoquantizationlevels),meaningfulbiologicalinformationcanbesuccessfullyextracted(Shmulevich&Zhang,2002c;Tabus,Rissanen,&Astola,2002).OneoftheappealingpropertiesofBNsisthattheyareinherentlysimple,emphasizinggenericnetworkbehaviorratherthanquantitativebiochemicaldetails,butareabletocapturemuchofthecomplexdynamicsofgeneregulatorynetworks.MostoftherecentworkonBooleannetworkshasfocusedonidentifyingthestructureoftheunderlyinggeneregulatorynetworkfromgeneexpressiondata(Liang,Fuhrman,&Somogyi,1998;Akutsuetal.,1998;Akutsu,Miyano,&Kuhara,1999;Ideker,Thorsson,&Karp,2000;Karp,Stoughton,&Yeung,1999;Makietal.,2001;Nodaetal.,1998;Shmulevichetal.,2002b).Arelatedissueistofindanetworkthatisconsistentwiththegivenobservationsordeterminewhethersuchanetworkexistsatall.ThisisknownastheConsistencyProblem(seeSection3.1).TheConsistencyProblemhasbeenaddressedandalgorithmssolvingtheproblemhavebeenintroducedinAkutsuetal.(1998)andAkutsu,Miyano,andKuhara(1999).Ontheotherhand,onemayarguethatthesimpleConsistencyProblemcannotbeusedtoinferanetworkfromrealdata.Thatis,duetothecomplexmeasurementprocess,rangingfromhybridizationconditionstoimageprocessingtechnique