On learning gene regulatory networks under the Boo

OnLearningGeneRegulatoryNetworksUndertheBooleanNetworkModelHarriLahdesmakiInstituteofSignalProcessing,DigitalMediaInstitute,TampereUniversityofTechnology,P.O.Box553,FIN-33101Tampere,FinlandTel:[phone]Fax:[phone]([e-mail])IlyaShmulevichUniversityofTexasM.D.AndersonCancerCenter,1515HolcombeBlvd.,Box85,Houston,TX77030,USA([e-mail])OlliYli-HarjaInstituteofSignalProcessing,DigitalMediaInstitute,TampereUniversityofTechnology,P.O.Box553,FIN-33101Tampere,Finland([e-mail])Abstract.Booleannetworksareapopularmodelclassforcapturingtheinter-actionsofgenesandglobaldynamicalbehaviorofgeneticregulatorynetworks.Recently,asignicantamountofattentionhasbeenfocusedontheinferenceoridenticationofthemodelstructurefromgeneexpressiondata.WeconsidertheConsistencyaswellasBest-FitExtensionproblemsinthecontextofinferringthenetworksfromdata.Thelatterapproachisespeciallyusefulinsituationswhengeneexpressionmeasurementsarenoisyandmayleadtoinconsistentobservations.WeproposesimpleecientalgorithmsthatcanbeusedtoanswertheConsistencyProblemandndoneorallconsistentBooleannetworksrelativetothegivenexam-ples.ThesamemethodisextendedtolearninggeneregulatorynetworksundertheBest-FitExtensionparadigm.WealsointroduceasimpleandfastwayofndingallBooleannetworkshavinglimitederrorsizeintheBest-FitExtensionProblemsetting.Weapplytheinferencemethodstoarealgeneexpressiondatasetandpresenttheresultsforaselectedsetofgenes.Keywords:generegulatorynetworks,networkinference,ConsistencyProblem,Best-FitExtensionParadigmCorrespondingauthorc2002KluwerAcademicPublishers.PrintedintheNetherlands.BNLearnRev.tex;5/11/2002;17:36;p.12Lahdesmaki,H.,Shmulevich,I.,andYli-Harja,O.1.INTRODUCTIONAcentralfocusofgenomicresearchconcernsunderstandingthemannerinwhichcellsexecuteandcontroltheenormousnumberofoperationsrequiredfornormalfunctionandthewaysinwhichcellularsystemsfailindisease.Inbiologicalsystems,decisionsarereachedbymethodsthatareexceedinglyparallelandextraordinarilyintegrated.Animportantgoalistounderstandthenatureofcellularfunctionandthemannerinwhichgenesandandtheirproductscollectivelyformabiologicalsystem.Incontrasttothereductionisticapproachesinbiology,itisbecomingincreasinglyapparentthatitisnecessarytostudythebe-haviorofgenesinaholisticratherthaninanindividualmanner.Suchapproachesinevitablyrequirecomputationalandformalmethodstoprocessmassiveamountsofdata,tounderstandgeneralprinciplesgov-erningthesystemunderstudy,andtomakeusefulpredictionsaboutsystembehaviorinthepresenceofknownconditions.Asignicantroleisplayedbythedevelopmentandanalysisofmathematicalandcomputationalmethodsinordertoconstructformalmodelsofgeneticinteractions.Thisresearchdirectionprovidesinsightandaconceptualframeworkforanintegrativeviewofgeneticfunctionandregulationandpavesthewaytowardunderstandingthecomplexrelationshipbetweenthegenomeandthecell.Anumberofdierentapproachestogeneregulatorynetworkmod-elinghavebeenintroduced,includinglinearmodels(D'Haeseleeretal.,1999),Bayesiannetworks(MurphyandMian,1999;Friedmanetal.,2000;Harteminketal.,2001),neuralnetworks(Weaveretal.,1999;Vohradsky,2001),dierentialequations(Chenetal.,1999;Mestletal.,1995),andmodelsincludingstochasticcomponentsonthemolec-ularlevel(McAdamsandArkin,1997)(see(Smolenetal.,2000;Hastyetal.,2001;deJong,2002)forreviewsofgeneralmodels).AmodelclassthathasreceivedaconsiderableamountofattentionistheBooleannet-work(BN)modeloriginallyintroducedbyKauman(Kauman,1969;GlassandKauman,1973).Goodreviewscanbefoundin(Huang,1999;Kauman,1993;SomogyiandSniegoski,1996).Inthismodel,thestateofageneisrepresentedbyaBooleanvariable(ONorOFF)andinteractionsbetweenthegenesarerepresentedbyBooleanfunctions,whichdeterminethestateofageneonthebasisofthestatesofsomeothergenes.Recentworksuggeststhatevenwhengeneexpressiondataareanalyzedentirelyinthebinarydomain(onlytwoquanti-zationlevels),meaningfulbiologicalinformationcanbesuccessfullyextracted(ShmulevichandZhang,2002c;Tabusetal.,2002).OneoftheappealingpropertiesofBNsisthattheyareinherentlysimple,empha-sizinggenericnetworkbehaviorratherthanquantitativebiochemicalBNLearnRev.tex;5/11/2002;17:36;p.2OnLearningGeneRegulatoryNetworks3details,butareabletocapturemuchofthecomplexdynamicsofgeneregulatorynetworks.MostoftherecentworkonBooleannetworkshasfocusedonidenti-fyingthestructureoftheunderlyinggeneregulatorynetworkfromgeneexpressiondata(Liangetal.,1998;Akutsuetal.,1998;Akutsuetal.,1999;Idekeretal.,2000;Karpetal.,1999;Makietal.,2001;Nodaetal.,1998;Shmulevichetal.,2002b).Arelatedissueistondanetworkthatisconsistentwiththegivenobservationsordeterminewhethersuchanetworkexistsatall.ThisisknownastheConsistencyProblem(seeSection3.1).TheConsistencyProblemhasbeenaddressedandalgorithmssolvingtheproblemhavebeenintroducedin(Akutsuetal.,1998;Akutsuetal.,1999).Ontheotherhand,onemayarguethatthesimpleConsistencyProblemcannotbeusedtoinferanetworkfromrealdata.Thatis,duetothecomplexmeasurementprocess,rangingfromhybridizationconditionstoimageprocessingtechniques,expressionpatternsexhibituncertainty.Forexample,