Efficient Transition Probability Computation for Continuous-Time Branching Processes via Compressed Sensing.

Area of Science:

• Computational Biology
• Mathematical Biology
• Statistical Modeling

Background:

• Branching processes, a type of continuous-time Markov chain (CTMC), are widely used but pose inference challenges.
• Computing transition probabilities in partially observed CTMCs with large or infinite state spaces is computationally difficult.
• Classical methods like matrix exponentiation and sampling are often infeasible or too slow for large populations.

Purpose of the Study:

• To develop a computationally efficient method for calculating transition probabilities in branching processes.
• To address the limitations of existing methods (matrix exponentiation, generating functions) for large state spaces.
• To accelerate statistical inference in complex, partially observed CTMC models.

Main Methods:

• Proposed a compressed sensing framework to accelerate the generating function method for branching processes.
• Leveraged the assumption of sparsity in the probability mass of transitions.
• Reduced computational cost by a logarithmic factor compared to standard generating function techniques.

Main Results:

• Demonstrated accurate and efficient computation of transition probabilities using the compressed sensing approach.
• Successfully applied the method to models of blood cell formation.
• Validated the approach on models of self-replicating transposable elements in bacterial genomes.

Conclusions:

• The compressed sensing framework significantly enhances the efficiency of the generating function method for branching processes.
• This approach offers a practical solution for statistical inference in large-scale, partially observed CTMC models.
• The method has demonstrated efficacy in biological applications, including population dynamics and genomic evolution.