We develop a new, self-contained proof that the expected number of generations required for gene allele fixation or extinction in a population of size n is O(n) under general assumptions. The proof relies on a discrete Markov chain analysis. We further dev
Fisher-Wrightandcoalescenceproblems5theO(n)coalescenttheorem,basedonthemeanandweakvariationconditionsplusanadditionalassumptionthatletsusde nethetime-reversalofanevolutionaryprocess.Forinstance,thebinomialandhypergeometricprocesses,aswellthegeneralizedbi-nomialandhypergeometricprocessesofM¨ohle[20],areprovedtohaveO(n)expectednumberofgenerationsbeforeaMRCAisreached.Unlikeearlierproofs,ourproofisbasedontheforwardabsorptiontimesoftheFisher-Wrightproblem,ratherthanonananalysisofthedeathprocess.
2.Preliminariesandde nitions
Werestrictattentiontohaploidindividuals,whocarryasinglesetofgeneticmaterialandreceivetheirgenesfromasingleparent.However,ourresultscanapplytodiploidgenesaswell,aslongasthegenesarenotsex-orreproduction-linked.Weassumethereisnomutationandthattheevolutionaryprocessistime-homogeneous.
Thepopulationsareassumedtoconsistofdiscrete,non-overlappinggenerations,eachofsizen.Eachindividualcarriesoneoftwoalleles,Aora.IfiindividualsofagenerationhavealleleA,thenn ihavealleleaandthegenerationisin“statei.”ThepopulationismodeledbyaMarkovchain(Q,M),whereQ={0,1,2,...,n}isthesetofstatesandM=(mi,j)isaastochastictransitionmatrix.Thetransitionprobabilitymi,jistheprobabilitythatstateiisfollowedimmediatelybystatej.WeoftendroptheQfromthenotationandrefertoMasaMarkovchain.
Wehavem0,0=1andmn,n=1sincethestates0andnareabsorbingstateswherealltheindividualscarryingthesameallele.TheMarkovchaincanbeviewedasstoppingonceitentersoneofthesetwostates.Themeanstoppingtimeortheexpectedabsorptiontimeistheexpectednumberofgenerationsuntilanabsorbingstateisreached.Themeanstoppingtimeisafunctionoftheinitialstate.
TheFisher-Wrightproblemconcernsboundingthemeanstoppingtime.Forthetra-ditionalFisher-Wrightproblem,thetransitionprobabilitiesarede nedbymi,j=pi,jwherethepi,j’sarede nedin(1).Sometimes,theprobabilitiesqi,jfromequation(2)areusedinstead.Togeneralizetoawiderrangeoftransitionprobabilities,wede neameanconditionandtwoconditionsonthevarianceoftheprobabilities.
De nition1.AMarkovchainsatis esthemeanconditionif,foralln≥3andforall
热门文档