evolutioncncn.com

cncn.com  时间:2021-04-11  阅读:()
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

LOCVPS:美国XEN架构VPS七折,全场八折,日本/新加坡XEN架构月付29.6元起

LOCVPS发来了针对XEN架构VPS的促销方案,其中美国洛杉矶机房7折,其余日本/新加坡/中国香港等机房全部8折,优惠后日本/新加坡机房XEN VPS月付仅29.6元起。这是成立较久的一家国人VPS服务商,目前提供美国洛杉矶(MC/C3)、和中国香港(邦联、沙田电信、大埔)、日本(东京、大阪)、新加坡、德国和荷兰等机房VPS主机,基于XEN或者KVM虚拟架构,均选择国内访问线路不错的机房,适合建...

Virmach:1核/512M1核M1核512M/夏季美国vps促销,年付$7.2,9月更换AMD平台

virmach怎么样?virmach家这几年非常火,从商家的黑五闪购开始,以超低的价格吸引了大批的国人客户,而且商家的机器还是非常稳定的,站长手里的4.75刀年付已经用了两年了,非常稳定,不过商家到国内的线路一般,目前商家新上了夏季优惠促销,价格低到发指,年付7.2美元起,商家反馈将在9月开始更换AMD+NVMe平台,这个消息从年初就有了,不过一直没有更换,目前这个时间也不确定是否准确。点击进入:...

PQ.hosting:香港HE/乌克兰/俄罗斯/荷兰/摩尔多瓦/德国/斯洛伐克/捷克vps,2核/2GB内存/30GB NVMe空间,€3/月

PQ.hosting怎么样?PQ.hosting是一家俄罗斯商家,正规公司,主要提供KVM VPS和独立服务器,VPS数据中心有香港HE、俄罗斯莫斯科DataPro、乌克兰VOLIA、拉脱维亚、荷兰Serverius、摩尔多瓦Alexhost、德国等。部分配置有变化,同时开通Paypal付款。香港、乌克兰、德国、斯洛伐克、捷克等为NVMe硬盘。香港为HE线路,三网绕美(不太建议香港)。免费支持wi...

cncn.com为你推荐
capitalcapital啥意思哈利波特罗恩升级当爸哈利波特的爸爸妈妈身份www.haole012.com012qq.com真的假的www.se222se.com原来的www站到底222eee怎么了莫非不是不能222eee在收视com了,/?求解dadi.tv智能网络电视smartTV是什么牌子www.xvideos.com请问www.****.com.hk 和www.****.com.cn一样吗?官人放题SBNS-088 中年男の夢を叶えるセックス やりたい放題! 4(中文字幕)种子下载地址有么?好人一生平安猴山条约猴山条约是怎么回事啊?有知道的吗?m.yushuwu.com至尊影视网www.xuexiyu.com 怎么只收录首页啊长房娇谁知道以下几种都是什么花?花期多长?
虚拟主机提供商 vps服务器租用 深圳域名空间 已备案域名出售 42u机柜尺寸 http500内部服务器错误 免费mysql idc资讯 183是联通还是移动 静态空间 nerds 空间登录首页 web服务器是什么 cxz 新加坡空间 江苏徐州移动 重庆联通服务器托管 globalsign alexa搜 hosts文件修改 更多