evolutioncncn.com

JustandEncisoAdvancesinDierenceEquations2013,2013:313http://www.
advancesindifferenceequations.
com/content/2013/1/313RESEARCHOpenAccessOrdereddynamicsinbiasedandcooperativeBooleannetworksWinfriedJust1*andGermánAEnciso2*Correspondence:mathjust@gmail.
com1DepartmentofMathematics,OhioUniversity,Athens,45701,USAFulllistofauthorinformationisavailableattheendofthearticleAbstractThispapercontributestothetheoreticalanalysisofthequalitativebehavioroftwotypesofBooleannetworks:biasedandcooperativeones.
ABooleannetworkisbiasedifatleastaspeciedfractionofitsregulatoryfunctionsreturnsoneBooleanvaluemoreoftenthantheotherandiscooperativeiftherearenonegativeinteractionsbetweenthevariables.
Weprovenontrivialupperboundsonthemaximumlengthofperiodicorbitsinsuchnetworksundertheassumptionthatthemaximumnumberofinputsandoutputspernodeisaxedconstantr.
Forthecaseofn-dimensionalnetworkswithr=2inwhichonlyANDandORareallowed,wendanupperboundof10n/4,whichisasymptoticallyoptimalinviewofpreviouslypublishedcounterexamples.
Thetheoreticalresultsaresupplementedbysimulationsofthegenericbehaviorofcooperativenetworkswhichindicatethatforlargeindegrees,trajectoriestendtoconvergerapidlytowardsasteadystateorasmallperiodicorbit.
ThelatterstarklycontrastswiththebehaviorofrandomarbitraryBooleannetworks.
MSC:05A15;06A07;34C12;39A33;94C10;92C42Keywords:Booleannetworks;cooperativedynamicalsystems;biasedregulatoryfunctions;chaoticdynamics;Spernerfamilies1IntroductionMathematicalmodelsofbiologicalproblemshavebecomeincreasinglysophisticatedwiththeadventofnewquantitativetechniques.
Modelsinvolvingdozensofproteinsatthecelllevelaboundintheliterature[,],mostlycreatedusingcontinuousmethods.
Aninter-estingcounterparttocontinuoussystemsareBooleannetworks,characterizedbydiscretetimedynamicsandtheexistenceofonlytwopossiblestates(and)foreachvariableatanygiventime[].
Inthefaceofparameteruncertainty,modelingusingBooleannetworkscanproducequalitativepredictionsattherightlevelofdetailformanyapplications.
Thispapercontinuesalineoftheoreticalresearchexploringthequalitativebehaviorofso-calledcooperativeBooleannetworks.
Thisconceptcorrespondstosystemsthathaveexclusivelypositiveinteractionsamongtheirvariables,andinparticulararemonotone,whichmeansthattheyhaveonlypositivefeedbackloops.
Suchnetworkshavebeenpro-posedasimportanttoolsforgaininginsightintothedynamicsofgeneregulatoryandotherbiologicalnetworks[].
Inthecaseofsystemswithatmosttwoinputsforeachvariable,acooperativeBooleannetworkcanonlyhaveconstant,AND,ORandCOPYregulatoryfunctions.
Thecontinuouscounterpartofthisdenitionhasbeenstudiedextensively[],andundermildconditionsthegenerictrajectoryofacontinuouscooperativesystemisguaranteedtoconvergetowardsthesetofequilibria.
2013JustandEnciso;licenseeSpringer.
ThisisanOpenAccessarticledistributedunderthetermsoftheCreativeCommonsAttributionLicense(http://creativecommons.
org/licenses/by/2.
0),whichpermitsunrestricteduse,distribution,andreproductioninanymedium,providedtheoriginalworkisproperlycited.
JustandEncisoAdvancesinDierenceEquations2013,2013:313Page2of19http://www.
advancesindifferenceequations.
com/content/2013/1/313MuchoftheliteratureonthedynamicsofBooleannetworkshasfocusedonthestudyofso-calledrandomBooleannetworksorRBNs,whereann-dimensionalBooleannetworkisrandomlydrawnfromtheclassofallsuchnetworkswithamaximumofrinputspernode.
Forr>,thetrajectoryofarandomlychoseninitialstatetendstoreachaperiodicorbitwhosesizescalesexponentiallyinn.
Suchlongorbitsareconsideredahallmarkofchaoticdynamics.
Anotherhallmarkofchaoticdynamicsissensitivitytoinitialconditions.
Thiscanbeconceptualizedinavarietyofways,forexample,intermsofp-instability,asdenedattheendofSection.
Athirdhallmarkofchaosarerelativelyfewornoeventuallyfrozennodes,thatis,nodeswhosestatewillchangeonlynitelyoftenduringthetrajectory.
Thesehallmarksusually,butnotalways,gotogether.
Itisamatterofjudgementwhichhallmarksaredeemednecessaryforconsideringthedynamicstrulychaotic;see[]forexamplesandfurtherdiscussiononthispoint.
Intermsofthesehallmarks,thedynamicsofRBNstendstobecome,onaverage,morechaoticasrisincreasedoriftheaveragebiasoftheregulatoryfunctions,denedasthedierencebetween.
andtheproportionofinputvectorsonwhichittakestheBooleanvalue,decreases.
Forsurveysoftheseandrelatedresults,see[–].
InSectionwebrieyexploretheanalogueforcooperativeBooleannetworks.
Thatis,forr∈{,,,}wesimulatethetrajectoriesofrandomlychoseninitialstatesinBooleannetworksthatarerandomlychosenfromtheclassofallcooperativeBooleannetworkswithatmostrinputspernode.
Wendthatforr>trajectoriestendtoreachasteadystateoraverysmallperiodicorbitafterafewsteps,andthispatternappearstobestrongerforlargerrandn.
Wealsogiveanargumentinsupportofaconjecturethatifthereisnorestrictiononthenumberofinputs,forsucientlylargen,thevastmajorityofthetrajec-torieswillreacheitherofthesteady-statevectors(,.
.
.
,)or(,.
.
.
,).
Thus,onaverage,randomcooperativeBooleannetworkstendtohavemuchshorterperiodicorbitsthancorrespondingRBNs,andincontrasttothelatter,theirdynamicsappearstobecomelesschaotic,atleastintermsoflengthsofperiodicorbitsthatarereachedfromrandomini-tialconditionsandtheproportionofeventuallyfrozennodes,asthenumberrofallowedinputspernodeincreases.
Theseobservationsaboutaveragebehaviornaturallyleadtothequestionwhetherthereexistprovableandnontrivialupperboundsonthelengthofperiodicorbits,oratleastonthemedianlengthofperiodicorbits,thatwillbereachedfromrandomlydrawninitialconditions.
Sincethestatespaceofann-dimensionalBooleannetworkhassizen,aboundmightbeconsiderednontrivialifitdoesnotexceedcnforsomeconstantcn/,theconstructionsJustandEncisoAdvancesinDierenceEquations2013,2013:313Page3of19http://www.
advancesindifferenceequations.
com/content/2013/1/313usedintheproofofthistheoremgivesystemsinwhichthevastmajorityofvariablestakejustoneinput,thatis,theirregulatoryfunctionisCOPY.
NotethatwhileCOPYisanunbiasedfunction,bothANDandORarebiased.
Forexample,binaryANDreturnsforonlyonequarterofitsinputs.
Inotherwords,forevery√insystemsofthisformthatarep-unstableforpsucientlycloseto.
ByTheorem.
of[],thelatterboundisasymp-toticallyoptimal.
NotethatincontrasttoTheorem,noupperboundonthenumberofoutputspernodeisrequiredinTheorem.
PreliminaryversionsoftheproofsgiveninSections-werepostedinthepreprint[].
Onepurposeofthispaperistomakestreamlinedandmoreeasilyreadableversionsoftheseargumentsavailableinpeer-reviewedjournalform.
ThematerialinSectionisentirelynew.
2DenitionsAnn-dimensionalBooleannetwork(g,)consistsofastatespace={,}n,togetherwithatimeevolutionmapg:→.
Eachindividualcomponentgk:→{,}iscalledthekthregulatoryfunction,andatrajectoryofthesystemisafunctions:N→suchthats(t+)=g(s(t))foreveryt∈N.
Sincethestatespaceisnite,eachtrajectorymusteventuallybecomeperiodic.
Thesetofstatesintheperiodicpartofthetrajectorywillbecalledaperiodicorbit.
Periodicorbitsthatarereachedfromagiveninitialconditionareoftencalledattractorsorlimitcyclesofthetrajectoryintheliterature.
Thebasinofattractionofagivenperiodicorbitisthesetofallinitialconditionsfromwhichtheorbitisreached.
Denethepartialorder≤onbyx≤yifxi≤yiforeveryi.
Aregulatoryfunctiongkiscooperativeifx≤yimpliesgk(x)≤gk(y).
ABooleannetworkiscooperativeifeachofitsregulatoryfunctionsiscooperative,i.
e.
,ifx≤yimpliesg(x)≤g(y).
AnequivalentdenitioncanbeobtainedbyrequiringthateachregulatoryfunctioncanbewrittenasacompositionofBooleanfunctionsthatuseonlytheoperatorsANDandORwithoneormoreinputs.
Sincethenegationoperatorisnotneeded,cooperativeBooleannetworksareexactlytheoneswithoutnegativeinteractions.
Wedenea(b,r)-Booleannetworkasasysteminwhicheachregulatoryfunctiongkactu-allydependsonatmostrinputs,andeachvariablehasatmostboutputs(i.
e.
,itaectstheJustandEncisoAdvancesinDierenceEquations2013,2013:313Page4of19http://www.
advancesindifferenceequations.
com/content/2013/1/313dynamicsofatmostbothervariables).
Ifr=,wecallthesystemquadratic;a(,)-systemiscalledbi-quadratic.
Aregulatoryfunctionthatdependsononlyonevariableiscalledmonic;anon-monicquadraticregulatoryfunctioniscalledstrictlyquadratic.
ABooleannetworkwithonlyquadraticregulatoryfunctionswillbecalledastrictlyquadraticnet-work.
Noticethatinastrictlyquadratic,bi-quadraticnetworkeveryvariablemusthaveexactlytwoinputsandtwooutputs.
Ann-dimensionalBooleannetworkissaidtobec-chaotic,forc,andletb,rbepositiveintegers.
Thenthereexistsapositiveconstantc(α,b,r)c(α,b,r)andsucientlylargen,thereisnoc-chaotic,n-dimensional,α-biased(b,r)-Booleansystem.
Inparticular,foreveryc>c(α,,r)andsucientlylargen,everyc-chaotic,n-dimensionalcooperative(,r)-BooleansystemusesCOPYformorethan(–α)nofitsregulatoryfunctions.
ProofWewillproveonlytherstpartofthetheorem;thesecondpartthenfollowsfromtheobservationthattheonlynonconstantcooperativeunbiasedBooleanfunctionthattakesatmosttwoinputsistheCOPYfunction.
JustandEncisoAdvancesinDierenceEquations2013,2013:313Page5of19http://www.
advancesindifferenceequations.
com/content/2013/1/313Fixα,b,rasintheassumptions,andlet(,g)beann-dimensional(b,r)-Booleansystem.
Assumethatatleastαnoftheregulatoryfunctionsgkarebiased.
LetS=(s:∈[L])beasequenceof(notnecessarilypairwisedistinct)elementsof={,}n.
IftheelementsofShappentobepairwisedistinct,thenwewillspeakofSbeingasubsetof.
Leti∈[n]andconsidertheratioζi(S)=|{∈[L]:si=}|L.
Moregenerally,letv∈[n]andσ:[v]→{,}.
Forv-elementsubsetsI={i,.
.
.
,iv}of[n]withisuchthatforall(,g)asabove,allbiasedgk,allperiodicorbitsSof(,g)andallsubsetsSwith|S|≥(–τ)|S|,itholdsthatζI(S)=forI={k}∪dom(gk).
ProofLetε>besuchthatforeachofthenitelymanybiasedBooleanfunctionswithdomain{,}r,wehave|–.
|≥ε.
Letτ>besmallenoughthat(–τ)ε–τ=ε–τ(ε–)>.
Choosegkasintheassumptionandassumewlogthat≥.
+ε;theproofinthecasewhen≤.
–εissymmetric.
LetJbethedomainofgk,andletI={k}∪J.
ConsiderasubsetSofaperiodicorbitSwith|S|≥(–τ)|S|.
Aswementionedinthediscussionthatfollows(),ifζJ(S)=,thenalsoζI(S)=andthereisnothingtoprove.
SoassumethatζJ(S)=.
ThenallpossibleinputvectorsforgkappearinexactlyequalproportioninS,anditfollowsthat|{s∈S:gk(s)=}|≥|S|≥(–τ)|S|.
Thefollowinginequalitiesshowthatinthiscaseζk(S)>.
,whichimpliesζI(S)=.
|S|ζkS≥|S|ζk(S)–τ={s∈S:sk=}–τ|S|=s∈S:gk(s)=–τ|S|≥s∈S:gk(s)=–τ|S|≥(–τ)|S|–τ|S|≥(–τ)|S|(.
+ε)–τ|S|=|S|.
+(–τ)ε–τ>|S|,andtheinequalityζ{k}>.
follows.
ThisinparticularimpliesζI(S)=.
JustandEncisoAdvancesinDierenceEquations2013,2013:313Page6of19http://www.
advancesindifferenceequations.
com/content/2013/1/313Letβ,τ>,letS{,}n,andletDbeafamilyofpairwisedisjointsubsetsI[n]ofsize≤|I|≤r+eachwith|D|≥βn.
WesaythatSisβ-τ-balancedforDifthereexistI∈DandSSwith|S|≥(–τ)|S|suchthatζI(S)=,andthatSisβ-τ-balancedifitisβ-τ-balancedforeverysuchD.
LemmaThereexistsaconstantβ>suchthatforτasinLemma,noperiodicorbitof(,g)canbeβ-τ-balanced.
ProofForeachk∈[n],letIk={k}∪dom(gk).
Since(,g)isa(b,r)-Booleansystem,foreachsuchIkthereexistatmostr+b(r–)otherIwithIk∩I=.
Arecursiveconstructionallowsustondαn/(r+b(r–)+)pairwisedisjointsetsIkcorrespondingtobiasedfunctionsgk.
Thatis,forβ:=αr+b(r–)+,thereexistsafamilyDofpairwisedisjointsubsetsI[n]ofsize≤|I|≤r+each,with|D|≥βn,suchthateachsetinDisoftheformIkforsomebiasedgk.
ByLemma,thisfamilywitnessesthatnoperiodicorbitof(,g)canbeβ-τ-balanced.
NowTheorembecomesaconsequenceofthefollowingresult.
LemmaLet>β,τ>.
ThenthereexistsaconstantcE(N)≥PN>εcnεcnthatwecanassumePN≤εcn≥.
.
()NowassumethatthereisanysubsetS+{,}nofsizecnthatisnotβ-τ-balancedforD,andsupposethatSexistsforwhichN(S)≤εcnandS(S)=S+.
ConsiderI={i,.
.
.
,iv}∈D.
IfζI(S)λβandnsucientlylarge,estimates()and()implyP(ηc≥ε)≤(r+)βnλβncn,butgivesnoestimatesofthemagnitudeofthedierence.
Somelowerboundsforthedier-enceswereextractedfromtheproofofthetheoreminAppendixCofpreprint[];theyappeartosubstantiallyunderestimatetheactualdierence.
Forexample,theproofofThe-oremshowsonlythatc(,,)≤.
.
Ontheotherhand,Corollaryofthepreprint[]givesanupperboundofc(α,,)≤(–α)/,whichismorestringentifαissucientlycloseto.
Inparticular,sinceforc>c(,,)nostrictlyquadratic,bi-quadraticBooleannetworkcanbec-chaotic,thisresultimpliestogetherwithTheorem(iii)thatthelatterestimateisoptimalinthiscaseandc(,,)=/≈.
.
Wewillprovethisresulthereonlyforthespecialcaseofcooperativesystems,whichmakestheargumentmoretransparent.
Theproofforthegeneralcasegivenin[]usesessentiallythesameideas.
TheoremConsiderastrictlyquadratic,bi-quadratic,cooperativeBooleansystem(,f)ofdimensionnwithaperiodicorbitofsizecn.
Thenc≤/.
ProofLet(,f)beasintheassumption,with(f,.
.
.
,fn).
CallasubsetI[n]closedifeachfifori∈ItakesinputsonlyfromI,andcallIminimalclosedifnopropersubsetofIisclosed.
Giventheconstraintsontheindegreeandoutdegreeofeachnode,itfollowsthatallin-andoutdegreesareequaltotwo,andthatalloutputsofelementsfromamin-imalclosedsetIarealsoinsideI.
Therefore[n]istheunionofpairwisedisjointminimalclosedsetsI,for∈[L],with≤|I|≤nforall.
Letuscallavectorg=(g,.
.
.
,gk)ofBooleanfunctionson[k]aBooleank-blockifthecorrespondingBooleansystem({,}k,g)isstrictlyquadraticandbi-quadraticand[k]isminimalclosedinthissystem.
LetusdeneR(k)fork≥asthemaximalsizeoftherangeofanyBooleank-block.
Let(k)=(R(k))/k,andlet=max{(k):≤k}.
Returningto(,f),wecanseethatL=|I|=nandforanyCintherangeofg,inparticular,foranyCthatisaperiodicorbitofthesystem,wemusthave|C|≤L=R|I|≤L=|I|=n.
Nowthetheoremisaconsequenceofthefollowinglemma.
Lemma(k)≤/forallintegersk≥.
ProofFork=wehave()=√.
ConsideraBooleank-blockg=(g,.
.
.
,gk).
ItisnothardtoseethatafterasuitablerenumberingoftheinputJustandEncisoAdvancesinDierenceEquations2013,2013:313Page9of19http://www.
advancesindifferenceequations.
com/content/2013/1/313variables,wecanassumewlogthatgitakesinputssi,si+foralli∈[k–]andgktakesinputss,sk.
Foreaseofnotation,letusidentifyk+with.
Wecallj∈[k]ano-nodeifgj=sj∨sj+andana-nodeifgj=sj∧sj+.
Theproofofthelemmanowsplitsintotwocases.
Case:Thesetsofo-nodesanda-nodesarebothnonemptyInthiscasewecangroupthevariablesin[k]intooneormoreconsecutiveintervalsIm={j:im.
–α+ln(.
c)ln.
.
Thennoα-biasedquadraticBooleansystemcansimultaneouslybec-chaoticandp--unstable.
ProofLetcbeasintheassumptionandassume(,g)isac-chaoticstrictlyquadraticcooperativeBooleansystemofdimensionn.
Apair(j,j)withj,j∈[n]willbecalleddom-inatingiftherearei,i∈[n]suchthat{si,si}isthesetofinputvariablesforbothgjandgj,andatleastoneofthefunctionsgj,gjisbiased.
LetIbethesetofallsiwithoutdegreethatactasaninputofadominatingpair.
LemmaThesetIhascardinalityatmostnln(.
c)ln.
.
ProofLetJbetheunionofalldominatingpairsforwhichatleastoneinputvariableisinI.
Notethatif(j,j),(k,k)aredominatingpairsofvariableswhoseinputvariablescontainvariableswithoutdegree,then{j,j}∩{k,k}=.
Thus|J|≥|I|.
JustandEncisoAdvancesinDierenceEquations2013,2013:313Page11of19http://www.
advancesindifferenceequations.
com/content/2013/1/313Let(j,j)∈J,andleti,ibethecorrespondingindicesoftheinputs.
Assumewlogthatgjisbiasedandtakesthevalueoninputvectorsx,y,z∈{,}{i,i}.
Thengjtakesthesamevalueonatleasttwoofthevectorsx,y,z,anditfollowsthattherangeofgj*gjhassizeatmost.
Sinceweassumedthatthereexistsaperiodicorbitoflengthatleastcn,wemusthave|J|/n–|J|≥cn,andthelemmafollowsbytakinglogarithms.
NowletIdenotethesetofvariablessiwithoutdegreezero,Idenotethesetofvariablessiwithoutdegreethatactasaninputtoabiasedregulatoryfunction,andIthesetofvariablessioutsideofIwithoutdegreethatactasaninputtotwobiasedregulatoryfunctions.
Considerarandominitialstates()andthestates()obtainedbyippingthevalueofthevariablesi().
Clearly,ifsi∈I,thens()=s(),sincethevariablesiisnotusedatalltocalculatethenextstate.
Ifsi∈I,thenthereisexactlyonesjforwhichsiactsasaninput.
Sincegjisassumedbiased,itmusttakeanotherinputi,andthereexistsavaluek∈{,}suchthatthevalueofgjdoesnotdependontheinputsiaslongassi=k.
Thelatterhappenswithprobability.
;thuswithprobability≥.
,wewillhaves()=s().
Nowconsiderthecasewhensi∈I.
Thentherearej=jsuchthatsiactsasaninputtobothgjandgj,andgj,gjarebothbiased.
Sincei/∈IbydenitionofI,theotherinputvariablessi,siofgj,gjaredistinctanddierentfromsi.
Sincegj,gjarebothbiased,thereexistk,k∈{,}suchthatneitherthevalueofgjnorthevalueofgjdependsontheinputsiaslongassi=kandsi=k.
Thelatterhappenswithprobability.
;thuswithprobability≥.
,wewillhaves()=s().
Letusrstassumeforsimplicitythat(,g)isstrictlyquadraticandbi-quadratic.
Sincethesumofallindegreesisequaltothesumofalloutdegrees,thesetsIandIareemptyinthiscase.
Thesetofvariablesthatactasaninputtoatleastoneunbiasedregulatoryfunctionhassizelessthan(–α)n,thuswemusthave|I|>αn–n–|I|.
Then,byLemma,|I|≥αn–n–nln(.
c)ln.
.
()Sincewithprobability.
asingle-bitipofanodeinIhasnoeectafteronetimestep,inequality()impliesthatPrs()=s()≥.
|I|n≥α–.
–ln(.
c)ln.
,andthetheoremfollowsforthisspecialcase.
Nowletusturntothegeneralcasewhen(,g)isonlyassumedquadratic.
Foreachk,letIkdenotethesetofvariableswithoutdegreek.
ThenI=I,butIasdenedabovemaybeapropersubsetofI;similarlyforI.
Sincethesumofalloutdegreesmustequalthesumofallindegreesandthesystemwasassumedtobequadratic,wemusthavenk=kIk=I+I+nk=Ik+nk=(k–)Ik≤n=I+I+I+nk=Ik.
()JustandEncisoAdvancesinDierenceEquations2013,2013:313Page12of19http://www.
advancesindifferenceequations.
com/content/2013/1/313Wecandeducefrom()thatnk=Ik≤nk=(k–)Ik≤I+I,whichinturnimpliesI+I+I≥n.
()Aswementionedabove,I=I.
Moreover,sincefewerthan(–α)ofallregulatoryfunctionsareunbiased,wehaveI\I+I\(I∪I)arereachedfromasignicantfractionofinitialconditionsforr∈{,,},butforr=thisfractionisalreadymuchsmaller,andforr=itbecomesnegligible.
Overall,wefoundthatmosttrajectoriesforallrthatweinvestigatedconvergetowardsasteadystate.
Forr∈{,},almostallofthesearedierentfromtheconstantvectors(,.
.
.
,)and(,.
.
.
,),andforr=mosttrajectoriesconvergetowardsthesetwovectors.
Thelargestbasinsofattractiononaveragecompriseabouthalfofthestatespace;forinstance,ifr=theaveragesteadystateoftypeattracts%ofthetrajectories.
Sincetherearetwosuchsteadystates,theycombinetoattractanaverageof%ofalltrajectories.
Closeinspectionofasubsetofoursimulationsconrmedthatthemostcomplexbehav-ioroccursforr=,withmanytrajectoriesreachingperiodicorbitsofthefourthtype,thatis,oflength>,thatappeartohaveverysmallbasinsofattraction.
Ontheotherhand,somenetworksforr=appeartohaveasinglesteadystatethatattractsalmostallinitialconditions.
JustandEncisoAdvancesinDierenceEquations2013,2013:313Page15of19http://www.
advancesindifferenceequations.
com/content/2013/1/313Figure3(a)Tablerepresentingthevaluesofp(r,x)forseveralvaluesofr∈Nandx∈{0,1}k.
(b)Fordierentvaluesofr,x,theprobabilitythatg(x)=0ifacooperativefunctiongofrinputsisrandomlysampled.
Theabovesimulationsindicatethatforsucientlylarger,randomcooperativenet-workstendtohavehighlyordereddynamics,andthattheamountofchaos,atleastintermsofthelengthsofobservedperiodicorbitsandthepercentageofeventuallyfrozennodes,isverylow.
ThelatterisexactlytheoppositeofwhatisknownforRBNswithouttheassumptionofcooperativity,anditcallsforatheoreticalexplanation.
Forxedr,considerthefamilyA(r)ofallantichainsin{,}rwiththeuniformdis-tribution.
Furthermore,forx∈{,}r,letp(r,x)denotetheprobabilitythatx≤aforsomea∈A,whenAisrandomlychosenfromA(r).
Bysymmetry,p(r,x)dependsonlyonrand|x|,sowecanextendittoafunctiondenedonpairsofpositiveintegers,withp(r,k)=p(r,x)for|x|=k.
SeeFigureforcalculationsofthevalueofp(r,k)fordierentvaluesofr,k,displayedbothintableforminpanel(a)andinnormalizedforminpanel(b).
Whilethereexistsavastliteratureonantichains(see[]foranencyclopedicreview),thefunctionp(r,k)appearsnottohavebeenexplicitlyinvestigated.
Theliteratureindi-catesthatthevastmajorityofantichainstendtomostlycontainelementsofsizeveryclosetor;inparticular,theproofsofasymptoticformulasforthenumberofantichainson{,}rthatwerederivedin[]and[]pointinthisdirection.
Thusitappearsthatifk(r)growsalittleslowerthanr,weshouldhavelimr→∞p(r,k(r))=,andifk(r)growsalittlefasterthanr,weshouldhavelimr→∞p(r,k(r))=.
Letuscallafunctionκ:Z+→Z+fastifp(r,r+κ(r))=o(r–)andp(r,r–κ(r))=–o(r–).
ConjectureThereexistsafastfunctionκsuchthatκ(r)=o(√r).
Thisconjectureappearstobehighlyplausible[],butmaynotimmediatelyfollowfromknownresults.
Toseewhyitseemsplausible,considertherelatedfunctionp(r,k)thatisdenedlikep(r,k),butforantichainsAthatarerandomlydrawnfromthefamilyofallantichainson{,}rthatconsistofelementswithidenticalnorms.
Thenfork>rtheprobabilityp(r,k)isboundedfromabovebytheprobabilitythatarandomlychosenantichainintherestrictedclassconsistsofelementswithnormforsome≥k.
Notethatfork>rwehavek≤rr/r–kk+.
Thisinturnimpliesthatifk>r+c√rforsomec>,thenrp(r,k)≤rr=k(r)(rr/)≤r(r–k+)(rr/)r–c√rr+c√r(rr/)≤–c√r+c(rr/)+logr,()JustandEncisoAdvancesinDierenceEquations2013,2013:313Page16of19http://www.
advancesindifferenceequations.
com/content/2013/1/313andtheanalogueofConjectureforp(r,k)withk>rfollowssincerr/growsmuchfasterthan√r.
Forkk,thenforagivenxwith|x|=k,theprobabilitythatAcontainsanawithx≤aisequalto––(k).
Itmaybepossibletoextractaproofoftheconjecturebycarefullyanalyzingtheargu-mentsin[,],butthisisnoteasyandwouldgobeyondthescopeofthispaper.
OurnextresultshowsthatConjecturehasastrikingconsequenceforthedynamicsofrandomcooperativenetworkswithoutrestrictionsonthenumberofinputsrpervariable.
Theexplicitcalculationsandsimulationsthatwewereabletoperformforsmallvaluesofr(seeFiguresand)addsomecredibilitytothisconsequenceoftheconjecture.
LemmaAssumethatConjectureholds.
Thentheprobabilitythatthetrajectoryofarandomlychoseninitialconditioninarandomlychosenn-dimensionalcooperativeBooleannetworkreacheseitherthesteadystatevector(,.
.
.
,)orthesteadystatevector(,.
.
.
,)afteroneupdatingstepapproachesasn→∞.
ProofForxedn,choosingarandomcooperativenetworkcanbeconceptualizedasthesameprocedureaswehavebeenfollowinginoursimulations,butwithr=n.
Thusforeachk∈[n]werandomlyandindependentlychooseanantichainAk∈A(n),andthenwedenetheregulatoryfunctiongk=gAk,asin().
Nowxaprobability,weshouldseeonaveragemoreinputvectorswithnormsignif-icantlylargerthanrthaninputvectorswithnormsignicantlysmallerthanrandviceversa.
Thusifp(r,k)decayssucientlyfasttoas|k–r|increases,|s()|–rshouldbeex-pectedtohavealargerabsolutevalueandthesamesignas|s()|–r,andtheeectshouldamplifyduringsubsequentiterations,untilasteadystateoraperiodicorbitwithallnormsclosetoornisreached.
Thisseemstobeexactlywhatweobserveinoursimulationsforr∈{,}.
7ConclusionsVerylongperiodicorbitsareahallmarkofchaoticdynamicsinBooleannetworks.
Ithaslongbeenknownthatsuchfeaturesasfewinputspernodeandprevalenceofsignicantlybiasedregulatoryfunctionsreduce,onaverage,thepropensitytowardschaoticbehaviorJustandEncisoAdvancesinDierenceEquations2013,2013:313Page17of19http://www.
advancesindifferenceequations.
com/content/2013/1/313insuchnetworks,inparticular,theprevalenceofverylongperiodicorbits.
However,non-trivialupperboundsonthelengthsofperiodicorbitshadpreviouslybeenprovedonlyforsomeveryrestrictedclassesofBooleannetworks.
Themainresultofthispaper,Theorem,showstheexistenceofsuchboundsifboththenumberofinputsandthenumberofoutputspernodeareboundedbyaconstantandaxedminimalfractionofallregulatoryfunctionsisassumedtobebiased.
SincethereareonlynitelymanydierentBooleanfunctionsonagivensetofinputs,theassumptionsofthistheoremimplyalowerboundontheamountofbiasweseeineachregulatoryfunction.
However,theanalogueofthetheoremfailsifitisonlyassumedthataxedfractionofregulatoryfunctionsshowsaspeciedminimalamountofbias,evenwhenthenumberofinputs(butnotoutputs)ofeachregulatoryfunctionisbounded.
ThisfollowsfromapreviouslypublishedresultthatisreproducedasTheorem(ii)here.
Ifboththenumberofinputsandthatofoutputsareboundedbyandallregulatoryfunctionsarebiased,thenn/isanupperboundonthelengthofperiodicorbitsinn-dimensionalnetworks.
Thisresultisprovedinfullgeneralityinthepreprint[];hereweillustratedthemainideasoftheproofbyderivingthespecialcaseforcooperativenetworks(Theorem).
Bypreviouslypublishedresults,theupperboundisoptimal.
Itcanbefurtherimprovedforsystemsthatshowp--instabilityforsucientlylargepisimpliedbyallmeaningfulformaldenitions.
Cooperativityistheabsenceofnegativeinteractions,inparticular,negativefeedbackloops.
Previousempiricalstudieshadalreadyshownthatreducingtheamountofnegativefeedbacktendstoreduce,onaverage,thepropensitytowardschaoticdynamicsinBooleannetworks[].
SimulationstudiesreportedinSectionaboveindicatethatcooperativeBooleannetworksthatarerandomlydrawnfromtheclassofallsuchnetworkswithatmostrinputspernodetendtohavetrajectoriesthatquicklyconvergetoasteadystateorasmallperiodicorbit.
Theeectbecomesmorepronouncedasrincreases.
Forr∈{,},almostallsampledtrajectoriesconvergedtosteadystates,andforr=,mostofthesewereconstantBooleanvectors.
ThusthedynamicsofrandomcooperativeBooleannetworksappearstobecomelesschaotic,atleastintermsoflongperiodicorbitsandthepropor-tionofeventuallyfrozennodes,asthenumberofinputspernodeincreases;exactlytheoppositeofwhathasbeenobservedforRBNswithoutanassumptionofcooperativity.
Westatedaconjectureaboutthedistributionofsizesofsetsinrandomlychosenantichainsthatappearstoconformwith,butnotimmediatelyfollowfrom,knownresultsaboutthesecombinatorialobjects.
TheconjectureimpliesthatifacooperativeBooleannetworkandaninitialconditionarerandomlychosen(withoutanyrestrictionsonthenumberofinputspernode),theprobabilitythatasteadystateisreachedafteronlyonestepapproachesasthedimensionofthenetworkincreaseswithoutbound.
Theseresultsopenupseveralnewavenuesoffurtherresearch.
SinceTheoremas-sumesaxedboundonthenumberofoutputs,itdoesnotdirectlyapplytothestudyofRBNsfromtheclassforwhichanupperboundronthenumberofinputsistheonlyJustandEncisoAdvancesinDierenceEquations2013,2013:313Page18of19http://www.
advancesindifferenceequations.
com/content/2013/1/313restriction.
Withprobabilityapproachingasn→∞,thefractionofbiasedregulatoryfunctionswillbeveryclosetothefractionofbiasedBooleanfunctionsamongallthosewithrinputs,sothevastmajorityofsuchnetworkswillbeα-biasedforsuitableα.
How-ever,thenumberofoutputspernodewillroughlyfollowaPoissondistributionwithpa-rameterλ=r,withonlyveryfewnodeshavinga(moderately)largenumberofoutputs.
TheknowncounterexamplesdonotprecludeageneralizationofTheoremtothisweakerassumptiononthedistributionofoutputs,anditbecomesanaturalquestionwhetheronecanproveordisprovesuchaversionofthetheorem.
Similarly,itmightbeofinteresttondgeneralizationsofTheoremsandthatdealwiththecaser=tocorrespondingnetworkswithr>.
InSectionwedenedafunctionp(r,k)thatexpressesthesizedistributionsofsetsinantichainsakaSpernerfamilies.
Aswearguedattheendofthatsection,acharacteriza-tionoftheasymptoticbehaviorofthefunctionp(r,k)shouldallowonetoderiveanalyticboundsontheprobabilityoftrajectoriesinrandomcooperativeBooleannetworkswithuptorinputspernodeeventuallyreachingasteadystate,andupperboundsontheex-pectedlengthsofthetransients.
Inouropinion,thefunctionp(r,k)deservesmoresys-tematicstudybycombinatorists.
Acharacterizationoftheasymptoticbehaviorofthisfunctionwouldallowprecisequanticationofthewell-knownobservationthatforlargertheoverwhelmingmajorityofSpernerfamilieson{,}rcontainspredominantlyvectorswithclosetor/coordinatesequalto.
OfparticularinterestfromourpointofviewwouldbeaproofofConjecture,whichhypothesizesspecicboundsonasymptoticbehaviorofthisfunction.
CompetinginterestsTheauthorsdeclarethattheyhavenocompetinginterests.
Authors'contributionsTheresultsofSections3-5aremainlyduetoWJ;Section6ismainlyduetoGE.
Bothauthorsequallycontributedtotheeditingoftheentirematerial,read,andapprovedthenalmanuscript.
Authordetails1DepartmentofMathematics,OhioUniversity,Athens,45701,USA.
2DepartmentofMathematics,UniversityofCalifornia,Irvine,92697,USA.
AcknowledgementsWewouldliketothanktherefereesforinsightfulandvaluablesuggestionsonhowtoimprovethemanuscript.
Received:2June2013Accepted:14October2013Published:08Nov2013References1.
Chuang,HY,Hofree,M,Idekker,T:Adecadeofsystemsbiology.
Annu.
Rev.
CellDev.
Biol.
26,721-744(2010)2.
Tindall,MJ,Porter,SL,Maini,PK,Gaglia,G,Armitage,JP:OverviewofmathematicalapproachesusedtomodelbacterialchemotaxisI:thesinglecell.
Bull.
Math.
Biol.
70,1525-1569(2008)3.
Albert,R,Othmer,HG:ThetopologyoftheregulatoryinteractionspredictstheexpressionpatternofthesegmentpolaritygenesinDrosophilamelanogaster.
J.
Theor.
Biol.
223,1-18(2003)4.
Sontag,ED:Monotoneandnear-monotonebiochemicalnetworks.
Syst.
Synth.
Biol.
1,59-87(2007)5.
Smith,HL:MonotoneDynamicalSystems.
MathSurveysandMonographs.
Am.
Math.
Soc.
,Providence(1995)6.
Just,W,Malicki,M:CooperativeBooleansystemswithgenericallylongattractorsII.
Adv.
Dier.
Equ.
2013,ArticleID268(2013)7.
Aldana,M,Coppersmith,S,Kadano,LP:Booleandynamicswithrandomcouplings.
In:Kaplan,E,Marsden,JE,Sreenivasan,KR(eds.
)PerspectivesandProblemsinNonlinearScience,pp.
23-90.
Springer,Berlin(2003)8.
Drossel,B:RandomBooleannetworks.
In:Schuster,HG(ed.
)ReviewsofNonlinearDynamicsandComplexity,vol.
1,pp.
69-110.
Wiley,NewYork(2008)9.
Kauman,SA:OriginsofOrder:Self-OrganizationandSelectioninEvolution.
OxfordUniversityPress,Oxford(1993),10.
Kaufman,V,Drossel,B:OnthepropertiesofcyclesofsimpleBooleannetworks.
Eur.
Phys.
J.
B43,115-124(2005)11.
Paul,U,Kaufman,V,Drossel,B:PropertiesofattractorsofcanalyzingrandomBooleannetworks.
Phys.
Rev.
Lett.
73,026118(2006)12.
Ho,J-L:GlobalconvergencefortheXORBooleannetworks.
Taiwan.
J.
Math.
13(4),1271-1282(2009)JustandEncisoAdvancesinDierenceEquations2013,2013:313Page19of19http://www.
advancesindifferenceequations.
com/content/2013/1/31313.
Ho,J-L:AglobalconvergencetheoreminBooleanalgebra.
Taiwan.
J.
Math.
14(3B),1135-1144(2010)14.
Jarrah,AS,Laubenbacher,R,Veliz-Cuba,A:ThedynamicsofconjunctiveanddisjunctiveBooleannetworkmodels.
Bull.
Math.
Biol.
72,1425-1447(2010)15.
Arcena,J,Demongeot,J,Goles,E:Onlimitcyclesofmonotonefunctionswithsymmetricconnectiongraph.
Theor.
Comput.
Sci.
322,237-244(2004)16.
Enciso,GA,Just,W:AnaloguesoftheSmaleandHirschtheoremsforcooperativeBooleanandotherdiscretesystems.
J.
Dier.
Equ.
Appl.
18,223-238(2012)17.
Just,W,Enciso,GA:ExtremelyChaoticBooleanNetworks.
Preprint(2008).
arXiv:0811.
011518.
Just,W,Enciso,G:ExponentiallylongorbitsinBooleannetworkswithexclusivelypositiveinteractions.
NonlinearDyn.
Syst.
Theory11,275-284(2011)19.
Just,W,Malicki,M:CooperativeBooleansystemswithgenericallylongattractorsI.
J.
Dier.
Equ.
Appl.
19,772-795(2013)20.
Hoeding,W:Probabilityinequalitiesforsumsofboundedrandomvariables.
J.
Am.
Stat.
Assoc.
58(301),13-30(1963)21.
Austin,RB,Guy,RK:Binarysequenceswithoutisolatedones.
FibonacciQ.
16,84-86(1978)22.
McGarvey,G:SequenceA109377.
TheOn-LineEncyclopediaofIntegerSequences,Sloane,NJA(ed.
)(2008).
Publishedelectronicallyathttp://oeis.
org/A10937723.
Schrder,BS:OrderedSets:AnIntroduction.
Birkhuser,Boston(2003)24.
Engel,K:SpernerTheory.
EncyclopediaofMathematicsandItsApplications,vol.
65.
CambridgeUniversityPress,Cambridge(1997)25.
Kleitman,D,Markowsky,G:OnDedekind'sproblem:thenumberofisotoneBooleanfunctionsII.
Trans.
Am.
Math.
Soc.
213,373-390(1975)26.
Korshunov,AD:ThenumberofmonotoneBooleanfunctions.
Probl.
Kibern.
38,5-108(1981)(inRussian)27.
Engel,K:Privatecommunication.
October29,201228.
Sontag,ED,Veliz-Cuba,A,Laubenbacher,R,Jarrah,AS:TheeectofnegativefeedbackloopsonthedynamicsofBooleannetworks.
Biophys.
J.
95(2),518-526(2008)10.
1186/1687-1847-2013-313Citethisarticleas:JustandEnciso:OrdereddynamicsinbiasedandcooperativeBooleannetworks.
AdvancesinDierenceEquations2013,2013:313